299 - Train Swapping

[Rene]

2 is the right answer?
why?
i think 3 is the right answer. And my code get the answer 3.

[Hisoka]

I know your program will produce 3 for this input. and the right output is 2.
this is that proses:

1 3 4 2 5

proses 1 : 1 3 2 4 5
proses 2 : 1 2 3 4 5

end of proses.

GOOD LUCK.......

[Rene]

oh,i see.
and i have changed a new way to slove this problem and got accepted.
Thanx.

[kenny1har]

I don't understand why my program is wrong
please give any comments....


[pascal]
program p229 (input,output);
type
aset=array[1..50] of integer;
var
a:aset;
n,nn,train,j,k:integer;

function bsort(var a:aset) :integer;
var
j,k,temp,n:integer;
begin
n:=0;
for j:=nn downto 2 do
for k:=1 to nn-1 do
if a[k] > a[k+1] then begin
n:=n+1;
temp:=a[k];
a[k]:=a[k+1];
a[k+1]:=temp;
end;
bsort:=n;
end;

begin
while not eof(input) do begin
readln(n);
if eof(input) then exit;
for j:=1 to n do begin
readln(nn);
if eof(input) then exit;
for k:=1 to nn do begin
read(train);
if eof(input) then exit;
a[k]:=train;
end;
readln;
writeln('Optimal train swapping takes ',bsort(a),' swaps.');
end;
end;
end.
[/pascal]

[cytse]

i think there is no need to check eof after reading each number.

in fact, i got AC with your program after all statements related to eof(input) are removed.

[kenny1har]

thanks for your comments.

[jai166]

Why 299 WA? I can't figure it out!!!
[c]/* 299 */
#include<stdio.h>
#define MAX 95
void main(void)
{
unsigned int maxnum,i,j,pass,maxtimes,times,n[MAX],temp;

scanf("%u",&maxtimes);
for(;maxtimes;maxtimes--){
scanf("%d",&maxnum);
for(i=0;i<maxnum;i++)scanf("%u",&n);
times=0,pass=1;
for(j=maxnum-1;j&&pass;j--)
for(pass=0,i=0;i<j;i++)
if(n>n[i+1]){
times++,pass=1;
temp=n[i+1];n[i+1]=n;n=temp;
}
printf("Optimal train swapping takes %u swaps.\n",times);
}
}[/c]

[shamim]

unsigned int maxnum,i,j,pass,maxtimes,times,n[MAX],temp;

scanf("%d",&maxtimes);

you have declared maxtimes to be of type unsigned int, but your are using '%d'.

[jai166]

I've changed %d to %u, but the result cganged to "Time Limit Exceeded". I use "Bubble Sort" and save how much times it count!
I know bubble sort isn't a powerful sort, but a friend of mine use this way to solve it in the past, and he solved then. But when I transfered his codes yesterday, the result is "Time Limit Exceeded"
Does someone know how to figure the times but use less time? Could you help me?Thank you!!!

[Observer]

BubbleSort is efficient enough for this question.

Of course, if you really want to optimize your code, you may use MergeSort

[Joseph Kurniawan]

Well, I think first you should locate the train with number n. Hopefully by locating the trains, the time will be reduced. Example:
5 trains:
3 4 1 5 2
We expect the train will be 1 2 3 4 5.
1. We want to arrange the train 1 (currently in pos 3) become:
3 4 1 5 2 -> 3 1 4 5 2 -> 1 3 4 5 2
2. Now train no 2 (currently in the last position):
1 3 4 5 2 -> 1 3 4 2 5 -> 1 3 2 4 5 -> 1 2 3 4 5
Well, since the trains are already in order, we don't have to proceed.
Hope it helps !!
[/c]

[jai166]

Well, I just changed "unsigned int" to "int" ,
"scanf("%u",&maxtimes);"
into
"while(scanf("%d",&maxtimes)==1)"

Then, it accepted!

[boyeric]

I thought it should be an easy one, but i don't know why i didn't get through.....
i used the bubble sort and count the steps of sorting, is this algorithm all right for problem 299?? Thanks in advance! here is my code: (in Java)

[java]
import java.util.*;

class Main{
public static void main(String [] args){
String in;
int c, i, size, j, k, t, n;
c = Integer.parseInt(Main.readLine());
StringTokenizer st;
int[] a;
for (i=0 ; i<c ; i++){
if (i!=0)System.out.println();
n=0;
size = Integer.parseInt(Main.readLine());
a = new int [size];
in = Main.readLine();
st = new StringTokenizer(in);
for (j=0 ; j<size; j++){
a[j] = Integer.parseInt(st.nextToken());
}
for (j=0 ; j<size-1 ; j++){
for (k=0 ; k<size-1-j ; k++){
if (a[k]>a[k+1]){
t = a[k];
a[k] = a[k+1];
a[k+1] = t;
n++;
}
}
}
System.out.print("Optical train swapping takes " + n + " swaps.");
}
}

static String readLine(){return token( "\n\r" );}


/* read token from stdIn with standard delims */
static String token( ){return token( " \n\r\t" );}


/* read token from stdIn with custom delims */
/* returns null for end of file or any exceptions */
static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
c = (char) System.in.read();
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
c = (char) System.in.read();
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}

}[/java]

[minskcity]

Your algorithm is good for this problems, I got AC using the same approach. Check your code for reading the input one more time, try to replace the core of your code with something like:[cpp] while(flag){
flag = false;
for(long i = 0; i < n - 1; i++)
if(data > data[i + 1]){
swap(data, data[i + 1]);
ans++;
flag = true;
}
}[/cpp]yes, it's is slower in some cases, but it's accepted It's better to write more robust then faster code before you get AC.
Hope this will help.

[Robert]

Did you allready correct the following mistake:

[java]System.out.print("Optical train swapping takes " + n + " swaps."); [/java]

It's not the "Optical train swapping " that you are looking for - but the
"Optimal"...

Robert