10327 - Flip Sort

[mystical_liu]

i send my programe tothe judge !!but it got WA and I don't know why!!
is there anyone can help me to find the bug ???
[cpp]
#include<stdio.h>
int in[5000],input,time=0,ins;
main()
{
while(scanf(" %d",&input)==1)
{
time=0;
for(int i=0;i<input;i++)
scanf(" %d",&in);
for(int i=0;i<input;i++)
{
for(int j=i+1;j<input;j++)
{
if(in>in[j])
{
ins=in;
in=in[j];
in[j]=ins;
time++;
}
}
}
printf("Minimum exchange operations : %d\n",time);
}
}[/cpp]

[Shih-Chia Cheng]

Your algorithm is wrong, check your inner loop.
And there is no need to use big numbers.

[mystical_liu]

i fix my code but it still WA!!
can you say more clear???

i find the smallest number and change
Is there any thing i didn't consider???

[cpp]
#include<stdio.h>
int in[5000],input,time=0,ins,min=0;
main()
{
int i,j;
while(scanf(" %d",&input)==1)
{
time=0;
for(i=0;i<input;i++)
scanf(" %d",&in);
for(i=0;i<input;i++)
{
min=i;
for(j=i+1;j<input;j++)
if(in>in[j])
min=j;
if(in>in[min])
{
ins=in;
in=in[min];
in[min]=ins;
time++;
}
}
printf("Minimum exchange operations : %d\n",time);
}
}[/cpp]

[Joe Smith]

i fix my code but it still WA!!
can you say more clear???

i find the smallest number and change
Is there any thing i didn't consider???

[cpp]
#include<stdio.h>
int in[5000],input,time=0,ins,min=0;
main()
{
int i,j;
while(scanf(" %d",&input)==1)
{
time=0;
for(i=0;i<input;i++)
scanf(" %d",&in);
for(i=0;i<input;i++)
{
min=i;
for(j=i+1;j<input;j++)
if(in>in[j]) <-------- in[min]>in[j] i think is what you want
min=j;
if(in>in[min])
{
ins=in;
in=in[min];
in[min]=ins;
time++;
}
}
printf("Minimum exchange operations : %d\n",time);
}
}[/cpp]

[sweko]

read the problem description carefully:

In this approach only one operation ( Flip ) is available and that is you can exchange two adjacent terms.

Tip: try your first version, minus the swaping of the list elements.

--
SWeko has spoken

[mystical_liu]

OH!!!
I got it !!!!!
thinks a lot!!~!~
I know where am I wrong!!
thinks your remide!!!

[yahoo]

hI why i am getting tle for this problem? is there any efficient algorithm for this problem. Will anybody kindly see my code and tell me where i am doing too much.Here is my code:
#include <stdio.h>

main()
{
int a[1001],r,n,i,j,temp,cnt,count;
while(1)
{
r=scanf("%d",&n);
if(r==EOF) break;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
a[i]=0;
cnt=0;
for(i=0;i<n;i++)
{
count=0;
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
cnt++;
temp=a[j];
a[j]=a[i];
a[i]=temp;
i++;
if(i>=n-1) {i=-1;break;}
}
else if(a[i]<a[j])
{
count++;
if (count==n-1) {i=n;break;}
i++;
if(i>=n-1) {i=-1;break;}

}
}
}
printf("Minimum exchange operations : %d\n",cnt);
}
return 0;
}

[gawry]

You only have to count all inversions (such i<j that t>t[j])

[yahoo]

Would you please kindly explain what do you mean by i<j such that t[i]>t[j]. I can't understand. Thanks in advance.

[Dominik Michniewski]

It's easy - let's take a sequence
seq = [1, 3, 2]
for i=2 and j=3 (like in Pascal) seq > seq[j] , but i < j. it's inversion ...

You should only find and count all this situations - after it print counted number and it's all

nice work

[yahoo]

Thanks. I got accepted. Thank you very much.

[route]

can i use number of swapping in bubble sort to calculate the min. operation ?
If yes, why there is still WA?

[junjieliang]

Counting bubblesort swaps should be correct, are you sure there is no bug in your program?
Actually to make it faster, you don't have to swap at all. Simply count the number of inversions...

[route]

[pascal]
Program flip;
var i, j, cnt, n, temp:longint;
m:array[1..1000] of longint;

begin
while not eof do
begin
readln(n);
for i:=1 to n do
read(m);
cnt:=0;
for i:=1 to n-1 do
for j:=n downto i+1 do
If m[j] < m[j-1] then
begin
temp:=m[j-1]; (*this sentence is omitted*)
m[j-1]:=m[j]; (*this sentence is omitted*)
m[j]:=temp; (*this sentence is omitted*)
inc(cnt);
end;
writeln('Minimum exchange operations : ', cnt);
end;
end.
[/pascal]



This is my program ...
and I try to omit some sentences after you've told swapping is not necessary...
I think there is no bug....
but i still got WA
can you tell me what the problem is ?
Thanks
[/pascal]

[junjieliang]

I got your program AC with a minor change. Add a "readln;" after reading in array m.

Reason: The input is something like 3<eoln>1<space>2<space>3<space><eoln><eof>
Without the readln your program will process the last case twice, hence WA.