299 - Train Swapping

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Gazi Shaheen Hossain
New poster
Posts: 7
Joined: Fri Sep 03, 2004 6:47 pm

299 (c++)WA

Post by Gazi Shaheen Hossain » Mon Sep 13, 2004 12:54 pm

Why it gives me WA?
some one help me.plz.
[cpp]
#include<stdio.h>
void main()
{
unsigned long N,i;
unsigned long j,x,y,L,carrage[50],temp,swap;
scanf("%lu",&N);
for(i=1;i<=N;i++)
{
scanf("%lu",&L);
for(j=0;j<L;j++)
scanf("%lu",&carrage[j]);
swap=0;
for(x=0;x<L-1;x++)
for(y=0;y<L-x-1;y++)
{
if(carrage[y]>carrage[y+1])
{
temp=carrage[y];
carrage[y]=carrage[y+1];
carrage[y+1]=temp;
swap++;
}
}
printf("Optimal train swapping takes %lu swaps.\n",swap);
}
}[/cpp]

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Mon Sep 13, 2004 2:53 pm

Try this input:

3
3
1 3 2
4
4 3 2 1
2
2 1
3
3
1 3 2
4
4 3 2 1
2
2 1


Your program gives following output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

But it should be

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Hope this will help.
Junayeed

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Thu Sep 16, 2004 6:24 am

Junayeed wrote:Try this input:
but it should be

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Hope this will help.
umm no, the first line states that there is only 3 test cases so it should only output 3 test cases.

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Fri Sep 17, 2004 10:55 am

My AC program gives me that output for the above input.
Junayeed

User avatar
Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby » Fri Sep 17, 2004 8:01 pm

To Gazi Shaheen Hossain :
I can't determine whether is your method correct. But my AC code just move 1,2,3 ... N train to their right places one by one.

vadiu
New poster
Posts: 10
Joined: Mon Jul 19, 2004 6:35 pm

299 WA

Post by vadiu » Mon Sep 27, 2004 11:12 pm

I can't understand why this doesn't give me AC. Is there someone who can help me solving this problem? Thanks...

[c]
#include "stdio.h"
#include "string.h"

int main()
{
int N, L, matrix[51], i, a, b, count;

scanf("%d", &N);

for(i=0; i<N; i++)
{

count=0;
b=0;
scanf("%d", &L);

for(a=0; a<L; a++)
scanf("%d", &matrix[a]);

while(1)
{

for(a=1; matrix[a]>matrix[a-1] && a!=L-1; a++);


if(matrix[a]<matrix[a-1])
{
b=matrix[a-1];
matrix[a-1]=matrix[a];
matrix[a]=b;
count++;
continue;
}

if(a==L-1)
break;
}

printf("Optimal train swapping takes %d swaps.\n", count);
}
return 0;
}
[/c]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Sep 28, 2004 1:32 pm

try this input:

[c]
1
1
[/c]

your code hangs for this input.
For that matter, there could be 0 trains, your code also hangs for that input.

vadiu
New poster
Posts: 10
Joined: Mon Jul 19, 2004 6:35 pm

Post by vadiu » Tue Sep 28, 2004 7:16 pm

I changed my code, now it can handle all the inputs (I think). But now it gives me WA. I may be doing something wrong. Any help would be greatly appreciated. Thanks

[c]
#include "stdio.h"
#include "string.h"

int main()
{
int N, L, matrix[51], i, a, b, count;

scanf("%d", &N);

for(i=0; i<N; i++)
{

count=0;
b=0;
scanf("%d", &L);

if(L==0)
{
printf("Optimal train swapping takes 0 swaps.\n");
continue;
}

if(L==1)
{
printf("Optimal train swapping takes 0 swaps.\n");
continue;
}

for(a=0; a<L; a++)
scanf("%d", &matrix[a]);

while(1)
{

for(a=1; matrix[a]>matrix[a-1] && a!=L-1; a++);


if(matrix[a]<matrix[a-1])
{
b=matrix[a-1];
matrix[a-1]=matrix[a];
matrix[a]=b;
count++;
continue;
}

if(a==L-1)
break;
}

printf("Optimal train swapping takes %d swaps.\n", count);
}
return 0;
}
[/c]

hiloshi
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan

Post by hiloshi » Thu Sep 30, 2004 7:07 pm

hi vadiu.

Problem says, "0 <= L <= 50".
So the input maybe a zero.
This is that shamim has also said.
I hope you can understand my poor English.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Plz Help me in prob-299.I've got wa

Post by asif_rahman0 » Sun Jan 16, 2005 6:52 pm

Here is my code.Plz tell me what's the wrong!
#include<stdio.h>

void main()
{
int a[51],n1,n2,i,j,k,count;
scanf("%d",&n1);
while(n1)
{
scanf("%d",&n2);
for(i=0;i<n2;i++)
scanf("%d",&a);
count=0;
for(j=0;j<i;j++)
for(k=j+1;k<i;k++)
if(a[j]>a[k])
{
int temp=a[j];
a[j]=a[k];
a[k]=temp;
count++;
}
printf("Optimal train swapping takes %d swaps\n",count);
n1--;
}
}
:( [/code]

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jan 16, 2005 8:04 pm

Uhm... you have made a little mistake. Read carefully the problem statement, you shouldn't do the swap.

Best regards :)

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Plz tell what's the wrong in my code?

Post by asif_rahman0 » Tue Jan 18, 2005 6:37 pm

Thx for ur reply.Yes I've read the problem carefully and find that it could be done with bubble sort.Yes I know that just count the maximum and the minimum numbers also correct.But I wanted to know what's the problem using bubble sort?Plz tell me where I've done the mistake in my code.

:-?
Asif

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Wed Jan 19, 2005 4:47 am

Well, only for this time...

You must change this part of your code

Code: Select all

if(a[j]>a[k]) 
{ 
int temp=a[j]; 
a[j]=a[k]; 
a[k]=temp; 
count++; 
} 
by this

Code: Select all

if(a[j]>a[k]) 
{ 
  count++; 
} 
For another opportunity, you must find the error by yourself

Regards :D

sunmoon
New poster
Posts: 4
Joined: Tue Jun 29, 2004 12:50 pm
Contact:

299 proof of optimality

Post by sunmoon » Thu Mar 10, 2005 5:22 am

Hi!

I got AC for 299 by using a simple bubble sort approach. Can somebody give the proof of optiimality for this approach?
All

ravi,IITM.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Mar 14, 2005 1:45 pm

There is a theorem: If a sorting algorithm is only allowed to swap two adjacent elements, then the number of swaps necessary to sort the array is equal to the number of inversions in this array.

An inversion is a pair of out-of-order elements: if i < j and a > a[j], then pair (i, j) is an inversion.

There is a proof in Knuth's volume III.

Post Reply

Return to “Volume 2 (200-299)”