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

Post by mystical_liu » Sun Jul 21, 2002 1:22 pm

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:

Post by Shih-Chia Cheng » Sun Jul 21, 2002 5:16 pm

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

Post by mystical_liu » Mon Jul 22, 2002 4:06 pm

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

Post by Joe Smith » Mon Jul 22, 2002 5:57 pm

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

Post by sweko » Wed Jul 24, 2002 12:27 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!!

Post by mystical_liu » Wed Jul 24, 2002 2:39 pm

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

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

10327

Post by yahoo » Sun Aug 04, 2002 8:37 pm

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

Post by gawry » Mon Aug 05, 2002 6:28 pm

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

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

Post by yahoo » Tue Aug 06, 2002 7:39 pm

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: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Aug 08, 2002 7:55 am

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

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

Post by yahoo » Fri Aug 09, 2002 4:07 pm

Thanks. I got accepted. Thank you very much.

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

10327 help

Post by route » Tue Dec 24, 2002 8:15 pm

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

Post by junjieliang » Wed Dec 25, 2002 5:24 am

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

Post by route » Wed Dec 25, 2002 6:21 am

[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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Dec 25, 2002 8:35 am

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.

Post Reply

Return to “Volume 103 (10300-10399)”