## 10327 - Flip Sort

Moderator: Board moderators

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

### 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" ?

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

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Contact:

### 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!

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
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>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

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

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

Piotrek Mazur
New poster
Posts: 17
Joined: Thu Jul 15, 2004 10:55 am
Location: Poland, Rzeszow University of Technology
If I clearly understand you, this is finding the 'inversion number' (this algoritm works).

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

[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);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(item[j]<item)
{
flip++;
temp=item;
item=item[j];
item[j]=temp;
}
printf("Minimum exchange operations : %ld\n",flip);
flip=0;
}
}

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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 !! efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am
Thanks I have Now Accepted

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

### 10327 why WA????

plz help me why WA?
#include<stdio.h>
#include<iostream.h>
int main()
{
long long n,data,j,k,i,temp,swap;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>data;
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;
}

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
your program doesnt output the minimum exchange
input

Code: Select all

``````4
4 3 2 1
``````
output

Code: Select all

``````Minimum exchange operations : 2

``````
Minimum exchange operations : 4 59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Contact:

### 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;

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

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

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

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

return 0;
}
aaa

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
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)

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am