299 - Train Swapping

[Gazi Shaheen Hossain]

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]

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.

[Betty]

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]

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

[Gigi's Baby]

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]

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]

[shamim]

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]

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]

hi vadiu.

Problem says, "0 <= L <= 50".
So the input maybe a zero.
This is that shamim has also said.

[asif_rahman0]

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]

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

Best regards

[asif_rahman0]

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]

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]

Hi!

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

[mf]

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.