10327 - Flip Sort

[route]

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]

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

Your code works as it is, I got AC in around 0:00:300. Just add a readln;
Good luck!

[Jewel of DIU]

Here is my code. I got WA in this problem.Where is my problem plz ?
[c]
----------- CUT AFTER AC ---------------
[/c]

[deddy one]

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

[Algoritmo]

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.

[Piotrek Mazur]

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

[efr_shovo]

[quote][/quote]

[efr_shovo]

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

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

[Ghust_omega]

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]

Thanks I have Now Accepted

[Fuad Hassan_IIUC(DC)]

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

[emotional blind]

your program doesnt output the minimum exchange
think about it
input

Code: Select all

4
4 3 2 1


output

Code: Select all

Minimum exchange operations : 2



but your program gives
Minimum exchange operations : 4

[59557RC]

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

[dumb dan]

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]

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.