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

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

10327 - <Flip sort >WA ? need test case?

Post by Salman » Sun Jul 10, 2005 8:15 am

Using bubble sort I am getting WA ?

Code: Select all

/*
Name:  Flip Sort 
Number: 10327
Type :  sorting
Process : ON
Author :Salman Zaman
Email : zamansalman@gmail.com
Date : 02/06/05 01:27


*/



#include<stdio.h>




//#include<conio.h>



int main(){

      int input[2000]={0};
      int n,i,temp,j,count; 
   
  // freopen("10327.txt","r",stdin);
   
     while(scanf("%d",&n)!=EOF){
         for(i=1;i<=n;i++){
             scanf("%d",&input[i]);
         }    
         count=0;
         for(i=1;i<=n-1;i++){
            for(j=i;j<=n;j++){
                if(input[i]>input[j]){
                    temp=input[i];
                    input[i]=input[j];
                    input[j]=temp;
                    count++;
                }    
            }       
         }    
         
         printf("Minimum exchange operations : %d\n",count);
     }    
   
   

   //getch();
   return 0;
}

Some one please help.

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

how to calculate minimum operation ?

Post by Salman » Fri Sep 09, 2005 12:36 pm

I donot understand how to calculate the minimum exchange opereation.
Can someone expline?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Sep 19, 2005 9:22 am

for the input

Code: Select all

4 3 2 1
after the first swap operation:between 4 and 1
it becomes:

Code: Select all

1 3 2 4
and after the second swap operation: between 2 and 3 it becomes

Code: Select all

1 2 3 4
that means the input is sorted. only two swap operation needed
now try to find the accurate algorithm for it

wigin
New poster
Posts: 2
Joined: Mon Oct 17, 2005 12:50 pm

10327 flip sort Why WA???

Post by wigin » Thu Oct 27, 2005 5:47 pm

Please help me :o
Why WA?

My Code:

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <math.h>

using namespace std;

int poc=0;
int vel=0;
int *pole;
int vys[100000];
int d=0;
//this function find smallest number and return his position
int nejmensi(int a,int vel){
	int pom=a;
	for(int i=a;i<vel-1;i++){
		if(pole[pom]<=pole[i+1]){
		    //pom=i;
		}else{
		    pom=i+1;
		}			
	}
	return pom;
}
void main() {
	int proh=0;
	int pom=0;
	int p=0;
	while(cin>>vel){
	if(vel<=1000){
	pole=new int[vel];
	for(int a=0;a<vel;a++){
		cin>>p;
		pole[a]=p;
	}
	for(int k=0;k<vel-1;k++){
		pom=nejmensi(k,vel);
		if(pole[k]==pole[pom] ){
		}else{
		proh=pole[k];
		pole[k]=pole[pom];
		pole[pom]=proh;
		poc++;
		}		
	}
	vys[d]=poc;
	poc=0;
	d++;
	delete [] pole;
	}else{
	break;
	}
	}
	for(int j=0;j<d;j++){
		printf("Minimum exchange operations : %ld\n",vys[j]);
		//cout<<endl;
	}
}
Last edited by wigin on Thu Oct 27, 2005 8:56 pm, edited 1 time in total.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Oct 27, 2005 6:25 pm

as far as I can remember the problem was only to find the number of flips required in an "insertion sort"

what algo do u use ??
Where's the "Any" key?

wigin
New poster
Posts: 2
Joined: Mon Oct 17, 2005 12:50 pm

Post by wigin » Thu Oct 27, 2005 8:51 pm

Solaris wrote:as far as I can remember the problem was only to find the number of flips required in an "insertion sort"

what algo do u use ??
My algo work so:
input:

Code: Select all

  4
  4 3 2 1
find smallest number and replace with number which is first position
smaller is 1
replace 4 and 1

Code: Select all

1 3 2 4
next
find smaller number from second position
next number is 2
replace 3 and 2

Code: Select all

1 2 3 4
output:
  Minimum exchange operations : 2
Is my algo wrong?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Oct 27, 2005 9:24 pm

wigin wrote:Is my algo wrong?
Yes, you can only flip two numbers if they are ajacent. So you need 6 flips to sort 4 3 2 1:

Code: Select all

4 3 2 1
3 4 2 1
3 4 1 2
3 1 4 2
1 3 4 2
1 3 2 4
1 2 3 4

those
New poster
Posts: 2
Joined: Tue Oct 11, 2005 3:24 pm

10327----WA!!!!

Post by those » Sun Dec 18, 2005 5:55 am

Code: Select all

var i,j,k,m,n,ans:longint;
    a:array[1..1000] of integer;
begin
  while not eof do
    begin
      readln(n);
      ans:=0;
      for i:=1 to n do read(a[i]);
      for i:=1 to n do
        begin
          m:=i;
          for j:=i+1 to n do 
             if a[j]<a[m] then m:=j;

          if m<>i then
            begin
              ans:=ans+1;
              k:=a[i];
              a[i]:=a[m];
              a[m]:=a[i];
            end;
        end;
      writeln('Minimum exchange operations : ',ans);
    end;
end.


What's wrong with my algo.?
I used a selection algo. but get WA

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

Post by mf » Sun Dec 18, 2005 6:43 am

From the problem statement:
only one operation ( Flip ) is available and that is you can exchange two adjacent terms.
The word adjacent is important: you can swap a only with a[i+1] or a[i-1].

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Wed Feb 22, 2006 12:25 am

I got ac by running bubble sort ! and increasing a
counter if i made a swap
:roll: :roll: :roll: :roll: :roll:
Last edited by 898989 on Fri Sep 15, 2006 11:34 pm, edited 1 time in total.

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Post by SHAHADAT » Sun Jun 25, 2006 10:16 am

I got an AC by doing the bubblesort and count the number of change.

moon
New poster
Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm
Contact:

plz help

Post by moon » Sun Jun 25, 2006 6:33 pm

I also got WA . Is my algo.. wrong????

Plz somebody help me :cry: :cry:

here is my code:

Code: Select all

#include<stdio.h>
#include<math.h>


long long int arr[1001];


int inver_my(int n) 
{ 
	int i,j,c=0; 
	 
	if( n==0 || n==1) 
		return 0; 
	
	for(i=0;i<n-1;i++) 
	{ 
		for(j=i;j<n;j++) 
		{ 
			if(arr[i]>arr[j]) 
			{ 
				c++; 
			
			} 
		} 
	} 
	return c; 
} 



int main()
{
	
	int n;
	
	while(scanf("%d",&n) != EOF)
	{
		int c=0;
		
	
		for(int i =0; i<n ; i++)
		{
			scanf("%lld",&arr[i]);
		}
	
		
		c= inver_my(n);
		
		printf("Minimum exchange operation : %d\n",c);
	}
	
	return 0;
	
}
moon

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Jun 25, 2006 7:32 pm

Yes your algorithm is Wrong
Read Little Joey's post.

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

Post by mf » Sun Jun 25, 2006 8:59 pm

emotional blind wrote:Yes your algorithm is Wrong
Read Little Joey's post.
You're wrong.

moon's algorithm is correct, it counts the number of inversions. The only problem with the code is that it should print "operations" instead of "operation".

moon
New poster
Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm
Contact:

thanx

Post by moon » Mon Jun 26, 2006 9:07 am

Thanks a lot to mf . I am so :oops: for my silly mistake . i got AC
thanks also to emotional blind
moon

Post Reply

Return to “Volume 103 (10300-10399)”