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

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

Re: 10327 - Flip Sort

Post by pok » Mon Nov 10, 2008 11:54 pm

thanks a lot..

i got it..

take care...bye ....

rubelreza
New poster
Posts: 2
Joined: Fri Jun 26, 2009 12:08 am

Re: 10327 - Flip Sort

Post by rubelreza » Fri Jul 24, 2009 3:40 pm

WHY I M GETTING WA???
CAN ANYONE TELL ME PLEASE..



#include<stdio.h>

int main(){

char s[1000];
int i,j,M=0,n,a,b;

while(scanf("%d\n",&n)==1){
M=0;
for(i=0;i<n;i++){
scanf("%d",&s);}


for(b=0;b<n-1;b++){
for(j=0;j<n-1;j++){

if(s[j]>s[j+1])
{
a=s[j];
s[j]=s[j+1];
s[j+1]=a;
M++;
}}}
printf("Minimum exchange operations : %d\n",M);

}

return 0;
}

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 » Sat Jul 25, 2009 12:00 am

Your approach seems wrong to me.
Just do bubble sort and don't exchange the values just count how many ways. :)

And read the whole thread before posting. There are many discussion about it. :-?
>>Use code tags while posting your code. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

tanjima09
New poster
Posts: 3
Joined: Mon Aug 10, 2009 7:04 pm

Re: 10327 - Flip Sort

Post by tanjima09 » Wed Aug 12, 2009 10:12 am

#include <iostream>
#include <algorithm>
#include <algo.h>
using namespace std;

int main ()
{
int a[1002],n,i,count=0;

while(cin >> n)
{
if(n<=0)
break;
count=0;
for (i=0; i<n; i++)
cin >>a;


while (!is_sorted(a,a+n))
{
for (i=0; i<n; i++)
{
if (a>a[i+1])
{
swap(a, a[i+1]);
count++;
}
}
}
cout<<"Minimum exchange operations : "<<count<<endl;
}
return 0;
}

tanjima09
New poster
Posts: 3
Joined: Mon Aug 10, 2009 7:04 pm

Re: 10327 - Flip Sort

Post by tanjima09 » Wed Aug 12, 2009 10:27 am

Code: Select all

#include <iostream>
#include <algorithm>
#include <algo.h>
using namespace std;

int main ()
{
	int a[1002],n,i,count=0;
		
	while(cin >> n)
	{
	if(n<=0)	
		break;
		
	count=0;
		for (i=0; i<n; i++)
			cin >>a[i];
		
		
	while (!is_sorted(a,a+n))
			{
			for (i=0; i<n; i++)	 
				{
				if (a[i]>a[i+1])	
					{
					swap(a[i], a[i+1]);
					count++;
					}
				
				}
			
			}
			cout<<"Minimum exchange operations : "<<count<<endl;

	
	}	 	 	  
	return 0;
}

i am getting a WA, i don't know what is the problem.. please help me with this....

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10327 - Flip Sort

Post by sazzadcsedu » Thu Aug 13, 2009 12:11 am

Your code is not correct.
Things to note:
for (i=0; i<n; i++)
cin >>a;

for (i=0; i<n; i++)
{
if (a>a[i+1]) .....//problem here

look here you r comparing a[n-1]>a[n] when i=n-1(final pass).but what is the index of last element in a[]??is it n or n-1???
so write i<n-1 rather than n.


you have used #include <algo.h> i dont know what is this :-?
you have also used several built in function like is_sorted,swap.
i think u shouldn't use built in function for such a simple problem if you want to learn programing.
you should code this bubble sort manually.

here is ACC version of your code.try to understand the code.and write yourself. :D

Code: Select all

 removed.
Last edited by sazzadcsedu on Thu Aug 13, 2009 8:43 pm, edited 1 time in total.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

tanjima09
New poster
Posts: 3
Joined: Mon Aug 10, 2009 7:04 pm

Re: 10327 - Flip Sort

Post by tanjima09 » Thu Aug 13, 2009 7:22 pm

thanks for ur reply.nw i understand where the problem was actually... yes i got an AC.. anywaz. i can do that by bubble sort. but i use those functions just because i want to. another thing is that <algo.h> is a very old name from STL HP implementation.thnx for helping :)

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

10327 why WA please heeeeeelp me????

Post by @mjad » Sat Jul 31, 2010 8:47 am

Code: Select all

#include<iostream>


using namespace std;

int main()
{
	//freopen("flip sort.txt","r",stdin);
	//freopen("flip sort output.txt","a+",stdout);

	unsigned long int i,c,j,num;
	char val[10],t;

    while(1)
	{
		 
			cin>>num;
			for(i=0;i<num;i++)
			{
				cin>>t;
				val[i]=t-48;
		
			}
			
	
			c=0;
			for(i=1;i<num;i++)
			{
				for(j=0;j<num-i;j++)
				{
					if(val[j]>val[j+1])
					{
						t=val[j];
						val[j]=val[j+1];
						val[j+1]=t;
						c++;
					}
				}
			}
	
			cout<<"Minimum exchange operation : "<<c<<endl;
		 
	}
	return 0;
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10327 why WA please heeeeeelp me????

Post by sazzadcsedu » Sat Jul 31, 2010 4:14 pm

Keep in mind the following things :-

Do not open a new thread when it is already existing.There is a search box ,so search here for your problem.

Next thing your program is full of error.

1.you are using char val[10], but problem statement says there are at most 1000 number.So certainly you will get Runtime error.

2.If you be able to overcome Runtime error by increasing array size, you will certainly get Time limit exceed,because your program never terminate.

3.If you be able to overcome these two thing then you will certainly get Wrong answer.I don't know why you used char array to take integer number.if num is 10 what value your char type contain?Use integer array.

best of luck.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Re: 10327 why WA please heeeeeelp me????

Post by @mjad » Mon Aug 02, 2010 2:27 pm

thanks for your reply

now change my algorithm
but i have still same problem
why? help me

Code: Select all

//#include<iostream>
#include<stdio.h>

//using namespace std;


int main()
{
	//freopen("trainswapping.txt","r",stdin);

	int ks,l,i,j,m,n,t;
	long count=0;
	int num[1005];
	       count=0;
		scanf("%d",&l);
		for(j=0;j<l;j++)
		{
			scanf("%d",&num[j]);
		}
		for(m=0;m<l;m++)
		{
			for(n=0;n<l-m-1;n++)
			{
				if(num[n]>num[n+1])
				{
					t=num[n];
					num[n]=num[n+1];
					num[n+1]=t;
					count++;
				}
			}
		}
		printf("Minimum exchange operations : %ld\n",count);
 
	
	return 0;
}

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10327 why WA please heeeeeelp me????

Post by sazzadcsedu » Mon Aug 02, 2010 5:19 pm

Your program still not terminating.
Use this

while(scanf("%d",&l)==1)
{

//write everything inside


}


And why you are saying your program receive Wrong answer, Wrong answer,time limit exceed ,Run time error these are not the same.And don't forget to initialize count before every case.

best of luck.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Re: 10327 why WA please heeeeeelp me????

Post by @mjad » Mon Aug 02, 2010 5:29 pm

i am really sorry for my mistake :)
thanks for your reply
now i go AC

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10327 why WA please heeeeeelp me????

Post by Shafaet_du » Mon May 09, 2011 8:53 pm

Both merge sort and bubble sort can be used to solve this problem.

asufcis
New poster
Posts: 1
Joined: Wed Dec 21, 2011 3:37 am

Re: 10327 - Flip Sort

Post by asufcis » Sat Dec 24, 2011 6:25 pm

I'm gettin WA don'y know why ?

Code: Select all

#include <iostream>
#include <iomanip>

using namespace std;
int main ()
{
	//freopen("input.in", "r", stdin);

int n,x[1003];
while(cin>>n)
{
for(int i=0;i<n;i++)
{cin>>x[i];}

int count=0;
///////////ARRANGING ARRAY (SORTING) --->HERE ASCENDING FOR EXAMPLE//////////////
for(int i=0;i<n;i++)
	for(int j=i+1;j<n;j++)
{
	if (x[i]>x[j]) /////Swapping
	{swap(x[i],x[j]);
	count++;
	}
}
//////////////////////END OF SORTING///////////////////////////////////////

	cout<<"Minimum exchange operations : "<<count<<endl;
	
}



	return 0;
}

RoniphpBB
New poster
Posts: 10
Joined: Sat Feb 09, 2013 11:22 am

Re: 10327 - Flip Sort

Post by RoniphpBB » Sat Jun 15, 2013 11:10 pm

WA and TLE after modify I can't understand what is my problem plz anyone help me
here is my code

Code: Select all

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string.h>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int main()
{
    int i,T,n[1000],temp,swap=0;
    //vector<int>v;

    while(1)
    {
        cin>>T;
        if(T==0) break;

        for(i=0;i<T;i++)
        {
        cin>>n[i];
      //  v.push_back(n);
        }
        for(i=0;i<T-1;i++)
        {
            for(int j=i+1;j<T;j++)
            {
                if(n[i]>n[j])
                {
                    temp=n[i];
                    n[i]=n[j];
                    n[j]=temp;
                    swap++;
                }
            }
        }
        cout<<"Minimum exchange operations : "<<swap<<endl;
    swap=0;
    }
        //cout<<endl;
//        v.clear();

    return 0;

}


Post Reply

Return to “Volume 103 (10300-10399)”