## 299 - Train Swapping

Moderator: Board moderators

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

### 299 (c++)WA

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,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
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

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
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
My AC program gives me that output for the above input.
Junayeed

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University
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.

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

### 299 WA

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, 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]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.

New poster
Posts: 10
Joined: Mon Jul 19, 2004 6:35 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, 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

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

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

void main()
{
int a,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
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?

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
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 sunmoon
New poster
Posts: 4
Joined: Tue Jun 29, 2004 12:50 pm
Contact:

### 299 proof of optimality

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:
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.