## 10327 - Flip Sort

Moderator: Board moderators

### 10327 help

junjieliang said that i can simply count the inversion....
but if the three swapping senetnces are omitted, i still got WA

Thus how can I "only count the inversions" ?
route
New poster

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

Try this:
Code: Select all
`inversion := 0;for i := 1 to n-1 do  for j := i+1 to n do    if (m[i] > m[j]) then inc(inversion);`

This should work. Btw there might be compile error (fix them yourself), since I typed this straight into the textbox...

Good luck!
junjieliang
Experienced poster

Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

### 10327 WA?????

Here is my code. I got WA in this problem.Where is my problem plz ?
[c]
----------- CUT AFTER AC ---------------
[/c]
Last edited by Jewel of DIU on Sat Mar 20, 2004 3:55 pm, edited 1 time in total.
Hate WA
Visit phpBB!
Jewel of DIU
New poster

Posts: 32
Joined: Thu Jul 31, 2003 6:21 am

change your bubble function into like this

[cpp]int bubble(int n)
{
int i,j,count=0;
long temp;
if( n==0 !! n==1) return 0;
for(i=0;i<n-1;i++)
{
for(j=i;j<n;j++)
{
if(data[i]>data[j])
{
count++;

}
}
}
return count;
}
[/cpp]

everything else seems fine.

you only need to count the exchange operations,
not to swap it.

I'm pretty sure that's the only problem here..

good luck
deddy one
Experienced poster

Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

### 10327

First I thought this could be a complicated problem, but soon I wrote a 20 line code and got accepted at first submission.
Many ideas passed through my mind and I would like to share them with you.

Let's say we have an algorithim that flips adjacent numbers, but it's not optimal. What makes it non-optimal is the non-required flips it makes.

By the way, what is a non-required flip? It's any flip that's done towice (two numbers being fliped once and unflipped later).

An optimal algorithim does all the required flips but any of the non-required ones. So:
O = T - N
O: Optimal number of flips
T: Total number of flips an algorithim does
N: Non-required flips it does

So we can count the flips (T), discover which were non-required (N) and calculate the O.

But we can go further, because the non-required flips can be recognized without doing them. A non required flip is the one that will need to be undone. So it's a flip that puts a bigger number after a smaller one:
50 100
100 50 -> this flip will need to be undone

It's clear that the number N will always be a even number.

Note now that the number of required flips can also be identified. Look at the number 7 in the sequence below. With how many other numbers do you think it needs to flip?
The answer is simple, just count how many numbers greater than 7 exist at it's LEFT and now many numbers smaller than 7 exist at it's RIGHT. All of those need to be flipped with the number 7.

5 1 7 2 6 3 8 4 9

Now, forget about the 7 (or erase it) and do the same process with each one of the other numbers, and you have counted ALL of the REQUIRED flips you need to do

For an easy algorithim, start with the number X at left, count the required flips (how many numbers smaller than it exist on it's right) and forget about such number X.
Repeat this process untill you have "forgotten" all of them.
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180
Algoritmo
New poster

Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm

If I clearly understand you, this is finding the 'inversion number' (this algoritm works).
Piotrek Mazur
New poster

Posts: 17
Joined: Thu Jul 15, 2004 10:55 am
Location: Poland, Rzeszow University of Technology

[quote][/quote]
Last edited by efr_shovo on Thu Sep 30, 2004 8:09 am, edited 1 time in total.
efr_shovo
New poster

Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

I can't Under stand Why 10327 Gives Wrong Ans.

here is my code.

#include<stdio.h>
#define MAX 1000

int n;
long item[MAX],temp,i,j,flip;

void main()
{

while(1==scanf("%d",&n))
{
if(n<=0||n>1000)
break;
for(i=0;i<n;i++)
scanf("%ld",&item[i]);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(item[j]<item[i])
{
flip++;
temp=item[i];
item[i]=item[j];
item[j]=temp;
}
printf("Minimum exchange operations : %ld\n",flip);
flip=0;
}
}
efr_shovo
New poster

Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

Hi !! efr_shovo your algo is not right you are counting the swaps of the selection algo, in this problem you have to count the swpas of the ......... well if I say I give the answer not so in that way try to think in one algo that make very swaps

Hope it helps
Keep posting !!

Ghust_omega
Experienced poster

Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Thanks I have Now Accepted
efr_shovo
New poster

Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 10327 why WA????

plz help me
why WA?
#include<stdio.h>
#include<iostream.h>
int main()
{
long long n,data[10000],j,k,i,temp,swap;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>data[i];
swap=0;
for(k=1;k<=n-1;k++)
{
for(j=1;j<=n-k;j++)
{
if(data[j]>=data[j+1])
{
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
swap++;
}
else continue;
}
}
printf("Minimum exchange operations : %lld",swap);
printf("\n");
}
return 0;
}
New poster

Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm

your program doesnt output the minimum exchange
input
Code: Select all
`44 3 2 1`

output
Code: Select all
`Minimum exchange operations : 2`

Minimum exchange operations : 4

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

### 10327-CE

i dont understand why CE with this simple sortin code.anyone pls help.
#include<stdio.h>
#include<conio.h>
int main()
{

int i,j,count,temp,c;
unsigned long a[1000];

while(scanf("%d",&c)!=EOF){
count=0;

for(i=0;i<c;i++) scanf("%lu",&a[i]);

for(i=0;i<c;i++){
for(j=i+1;j<c;j++){
if(a[i]>a[j]){
temp=a[j];
a[j]=a[i];
a[i]=temp;
count++;}
}
}

printf("Minimum exchange operations : %d\n",count);
}

return 0;
}
aaa
59557RC
New poster

Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm

I'm guessing you're getting the following compile error:

conio.h: No such file or directory

conio.h is not part of the C standard. It is a Borland extension, and works only with Borland compilers (and perhaps some other commercial compilers)

dumb dan
Learning poster

Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Yes Conio.h is reason for compile error..u can`t use it in the acm..
And u need not to declare array unsigned long i use int and got acc.

J&Jewel
New poster

Posts: 50
Joined: Thu Jul 31, 2003 10:43 am