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

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

10327 help

Post by route » Thu Dec 26, 2002 12:31 pm

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

Post by junjieliang » Fri Dec 27, 2002 10:31 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...

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

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

10327 WA?????

Post by Jewel of DIU » Mon Nov 03, 2003 4:34 pm

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

Post by deddy one » Tue Nov 11, 2003 8:43 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>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

Post by Algoritmo » Tue May 04, 2004 5:01 pm

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

Post by Piotrek Mazur » Tue Aug 10, 2004 11:43 pm

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

10327 Why Gives Wrong Ans?Please Help

Post by efr_shovo » Thu Sep 30, 2004 7:22 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

Re: 10327 Why Gives Wrong Ans?Please Help

Post by efr_shovo » Thu Sep 30, 2004 8:07 am

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

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Oct 01, 2004 6:06 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 :P so in that way try to think in one algo that make very swaps

Hope it helps
Keep posting !! :D

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

Post by efr_shovo » Sat Oct 02, 2004 9:37 am

Thanks I have Now Accepted

Fuad Hassan_IIUC(DC)
New poster
Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm
Location: Bangladesh

10327 why WA????

Post by Fuad Hassan_IIUC(DC) » Fri Feb 04, 2005 3:52 pm

plz help me :o
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;
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;
}
fuad

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

Post by emotional blind » Sat Feb 05, 2005 3:48 pm

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
:D

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

10327-CE

Post by 59557RC » Mon May 09, 2005 2:48 pm

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

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

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Mon May 09, 2005 3:17 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)

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Wed May 11, 2005 12:36 pm

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.
I hate Wrong Answer!

Post Reply

Return to “Volume 103 (10300-10399)”