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

Gungchil
New poster
Posts: 2
Joined: Mon Aug 21, 2006 3:10 pm

10327

Post by Gungchil » Mon Aug 21, 2006 3:58 pm

Plz help me to find the mistake
Here is my code
#include<stdio.h>
int main()
{
long int n,i,j,temp,a[100000],k,count=0,p;
while(scanf("%ld",&n)==1)
{
for(i=0;i<n;i++)
scanf("%ld",&a);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a>a[j])
{
temp=a;
a=a[j];
a[j]=temp;
count++;
}
}
printf("Minimum exchange operations : %ld\n",count);
count=0;
}
return 0;
}

Rushow
New poster
Posts: 14
Joined: Sat Oct 14, 2006 4:09 pm
Location: Dhaka,Bangladesh

10327

Post by Rushow » Thu Nov 02, 2006 5:46 pm

This is my source code. Anyone can tell what's the problem in it?



/* p10327 */
/* Flip Sort */

#include<stdio.h>
void main()
{
long s[1002],n,i,j,x,m;
while(scanf("%ld",&n)!=EOF)
{
m=0;
for(i=0;i<n;i++)
scanf("%d",&s);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(s>s[j])
{
x=s;
s=s[j];
s[j]=x;
m++;
}
}

}

printf("Minimum exchange operations : %ld\n",m);
}
}

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Thu Nov 16, 2006 12:34 pm

Rushow, you forgot the terms & conditions of the problem
only one operation ( Flip ) is available and that is you can exchange two adjacent terms
but your algorithm didn't perform like this.
think about second sample input-
2 3 1
in your algo, first interchange occurs between 2 and 1, but 2 and 1 is not adjacent. always swap between two adjacent (consecutive positioned) number (when needed).
so your algo is not flip (bubble) sort, actually replacement sort.

recently, our teacher taught us bubble sort, but you mistook. so bad.
let observe step by step, how flip sort will work
(currently comparing numbers will be shown in red)-
3 2 1 //the initial position of the array n=3 elements
3 2 1 //swap. after swapping: 2 3 1
2 3 1 //swap
2 1 3 //after n-1 comparison the largest element will in last position. so no eed to compare with it latter. again start from the beginning)
2 1 3 //swap
1 2 3 //after n-2 comparison the 2nd largest element will in 2nd last position. so no need to compare with it latter. there has only one element. so sorting was completed)
we swapped for 3 times. so ans=3.

to clear more, u can also get help from: http://www.comp.nus.edu.sg/~stevenha/pr ... rting.html

// N.B. while writing code, use BBcode tags. visit BBcode Guide
[ Common thing of every man is that, everyone thinks that he is uncommon ]

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sun Jul 22, 2007 12:35 pm

thank you jainal.
you are really a genish!!!
Last edited by newton on Mon Jul 23, 2007 11:01 am, edited 1 time in total.

User avatar
jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

Post by jainal cse du » Sun Jul 22, 2007 2:40 pm

Hi Newton,you have to count only minimum exchange operations.
So,replace it .

Code: Select all

for(i = 0;i < num-1; i++) 
{ 
         for(j = i+1;j < num;j++) 
         { 
               if(array[i] > array[j]) 
              { 
                    cnt++; 
                    tmp = array[i]; 
                    array[i] = array[j]; 
                    array[j] = tmp; 
              } 
         } 
} 

By following

Code: Select all

cnt = 0;
for(i = 0;i < num; i++) 
{ 
         for(j = i+1;j < num;j++) 
         { 
              if(array[i] > array[j]) 
                     cnt++;  
         } 
} 


andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Mon Aug 20, 2007 11:37 am

HOW can this code give WA?
I got already 7 (or like that) WAs on this easy prob.

Code: Select all

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  a: array [1..1000] of integer;
  i,j,k,l,n: integer;
  fl: boolean;

begin
  while not eof do
  begin
    readln (n);
    if eof then break;
    for i:=1 to n do
      read (a[i]);
    k := 0;
    fl := true;
    while fl do
    begin
      fl := false;
      for j:=1 to n-1 do
        if a[j]>a[j+1] then
        begin
          inc(k);
          fl := true;
          l := a[j];
          a[j] := a[j+1];
          a[j+1] := l;
          fl := true
        end
    end;
    writeln ('Minimum exchange operations : ',k)
  end;
end.

Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Aug 20, 2007 11:54 am

Maybe your program actually gets a runtime error.
Judge doesn't detect runtime errors for Pascal programs, and incorrectly gives WA verdict instead.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

10327....

Post by Obaida » Wed Jan 30, 2008 9:04 am

I don't know why judge give me worng answer.... plezz help me.... This is too..... much crazy.

Code: Select all

removed
Last edited by Obaida on Tue Feb 24, 2009 2:49 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Tue Feb 12, 2008 8:10 pm

Cheque it

Code: Select all

Input:
5
5 1 3 5 1
output:
Minimum exchange operations : 5
Thanks
Keep posting
sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Thanks....

Post by Obaida » Tue Feb 19, 2008 11:25 am

8) Thank You..... Got Ac.... 8)
try_try_try_try_&&&_try@try.com
This may be the address of success.

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

10327 - Flip Sort --> more inputs

Post by carliros » Thu Aug 28, 2008 6:16 pm

Input
5
6 2 1 5 4
8
3 5 8 2 1 9 7 0
2
0 0
12
0 1 2 5 4 1 2 0 5 0 7 9
30
21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21

output
Minimum exchange operations : 6
Minimum exchange operations : 16
Minimum exchange operations : 0
Minimum exchange operations : 19
Minimum exchange operations : 168
Minimum exchange operations : 67

debugger
New poster
Posts: 8
Joined: Tue Jul 29, 2008 6:24 pm

Re: 10327 - Flip Sort --> more inputs

Post by debugger » Sun Sep 14, 2008 1:17 pm

carliros wrote: Input
Minimum exchange operations : 6
Minimum exchange operations : 16
Minimum exchange operations : 0
Minimum exchange operations : 19
Minimum exchange operations : 168
Minimum exchange operations : 67
Do your code is accepted?? I am quite confused! :roll: Though i do not get ac, but your output have increased my confusion. :roll: :oops:

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

Re: 10327 - Flip Sort

Post by carliros » Sun Sep 21, 2008 3:12 pm

yes, my code was AC.

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 10327 - Flip Sort

Post by pok » Mon Nov 10, 2008 12:09 am

this is my code. i got WA..
but what is wrong in this code?

#include<stdio.h>

int main()
{
long int n,a[1001];

while(scanf("%ld",&n)==1)
{
long int i,j,x=0,temp;

for(i=0;i<n;i++)
scanf("%ld",&a);

for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a>a[j])
{
temp=a;
a=a[j];
a[j]=temp;
x++;
}

printf("Minimum exchange operations : %ld\n",x);
}

return 0;

}

pls help me..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10327 - Flip Sort

Post by Obaida » Mon Nov 10, 2008 10:41 am

You didn't need to do exchange but count how many exchange are available.

Ok, check this input,

Code: Select all

Input:
5
5 1 3 5 1
output:
Minimum exchange operations : 5
Hope you find your mistake. :wink:
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 103 (10300-10399)”