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" ?
but if the three swapping senetnces are omitted, i still got WA
Thus how can I "only count the inversions" ?
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
Try this:
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!
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);
Your code works as it is, I got AC in around 0:00:300. Just add a readln;
Good luck!
-
- New poster
- Posts: 32
- Joined: Thu Jul 31, 2003 6:21 am
- Location: Daffodil Univ, Bangladesh
- Contact:
10327 WA?????
Here is my code. I got WA in this problem.Where is my problem plz ?
[c]
----------- CUT AFTER AC ---------------
[/c]
[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!
Visit phpBB!
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
[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
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![:)](./images/smilies/icon_smile.gif)
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.
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
![:)](./images/smilies/icon_smile.gif)
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
-
- New poster
- Posts: 17
- Joined: Thu Jul 15, 2004 10:55 am
- Location: Poland, Rzeszow University of Technology
10327 Why Gives Wrong Ans?Please Help
[quote][/quote]
Last edited by efr_shovo on Thu Sep 30, 2004 8:09 am, edited 1 time in total.
Re: 10327 Why Gives Wrong Ans?Please Help
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;
}
}
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;
}
}
-
- Experienced poster
- Posts: 115
- Joined: Tue Apr 06, 2004 7:04 pm
- Location: Venezuela
-
- New poster
- Posts: 18
- Joined: Fri Jan 07, 2005 9:35 pm
- Location: Bangladesh
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;
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;
}
![:o](./images/smilies/icon_eek.gif)
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
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
your program doesnt output the minimum exchange
think about it
input
output
but your program gives
Minimum exchange operations : 4
![:D](./images/smilies/icon_biggrin.gif)
think about it
input
Code: Select all
4
4 3 2 1
Code: Select all
Minimum exchange operations : 2
Minimum exchange operations : 4
![:D](./images/smilies/icon_biggrin.gif)
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);
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;
}
#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