## 10327 - Flip Sort

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

Moderator: Board moderators

mystical_liu
New poster
Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

### 10327 - Flip Sort

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
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
Your algorithm is wrong, check your inner loop.
And there is no need to use big numbers.

mystical_liu
New poster
Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

### i fix my code... but ....

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
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

### Re: i fix my code... but ....

mystical_liu wrote: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
New poster
Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm
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
New poster
Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

### OH!!!!I got it!!

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

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 10327

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
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm
You only have to count all inversions (such i<j that t>t[j])

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thanks. I got accepted. Thank you very much.

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

### 10327 help

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

### 10327 help

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

begin
while not eof do
begin
for i:=1 to n do
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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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.