Page 1 of 2
10570 - Meeting with Aliens
Posted: Tue Oct 14, 2003 9:06 pm
by Larry
Can someone post the result of:
Code: Select all
4
1 2 3 4
4
4 3 2 1
4
2 3 1 4
6
3 1 2 5 6 4
9
1 2 3 4 8 7 6 5 9
100
84 83 82 81 80 79 78 77 76 100 98 99 97 96 95 94 93 92 91 90 89 88 87 86 85 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
100
8 9 7 6 5 4 3 2 1 84 83 82 81 80 79 78 77 76 100 98 99 97 96 95 94 93 92 91 90 89 88 87 86 85 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14
13 12 11 10
5
5 4 3 2 1
5
2 3 1 5 4
3
1 3 2
10
10 1 2 3 4 5 6 7 8 9
I get:
Thanks.
Basically, my algorithm is finding permutation groups, is there a simpler way just that my implementation is wrong? Thanks.
Posted: Tue Oct 14, 2003 9:12 pm
by Adrian Kuegel
My output is:
0
0
1
2
2
23
24
0
1
0
0
By the way, do you terminate the program if a zero occurs? The input is terminated by a case with n = 0.
Posted: Tue Oct 14, 2003 10:22 pm
by Larry
Thanks, Adrian. I've corrected my mistake. I get TLE, but that's probably because my loop doesn't end for whatever reason.
Time Limit Exceeded
Posted: Wed Oct 15, 2003 9:56 pm
by Pier
I have a n^3 algorithm and I get TLE. How should I approach this problem to get a better algorithm?
Thanks!
Posted: Wed Oct 15, 2003 10:47 pm
by Larry
you probably tried to sort it like I did.
Instead, let's say we have:
1 3 2 5 4,
and without cycling and stuff, so we're trying to convert it to
1 2 3 4 5
you'll notice the optimal answer is 2 - changing 3 and 2, and 5 and 4. So they're disjoint, as in, they don't depend on each other.
Let's look at a more complicated example:
3 1 2 5 7 6 4
edit:
converting the above to 1 2 3 4 5 6 7. The optimal answer is actually 2, but I just wanted to demonstrate an example. Sorry for any confusion.
You can break it down to getting:
3 1 2 -> 1 2 3
and
5 7 4 -> 4 5 7
in which the total cost is 4, since the 6 is in the right spot.
Basically, it boils down to finding these "cycles", and just sum up the cost. You can do this in linear time given an array, since you can argue that each element won't be moved more than once, if you do it correctly. N iterations of shifting/reversing, and that's an O(n^2) algorithm.
I don't know if I made it clear enough, but if not, do ask.
Posted: Wed Oct 15, 2003 11:16 pm
by Per
Larry wrote:Basically, it boils down to finding these "cycles", and just sum up the cost. You can do this in linear time given an array, since you can argue that each element won't be moved more than once, if you do it correctly. N iterations of shifting/reversing, and that's an O(n^2) algorithm.
Nitpick: that's not strictly true (e.g. if we want to go from 2 3 1 to 1 2 3, some element has to be moved twice).
(you still get the same time complexity though, O(N) to check how many swaps are needed to reach a specific final position, and 2N possible final positions.)
Posted: Wed Oct 15, 2003 11:41 pm
by Larry
You're right, of course, Per. =)
Posted: Thu Oct 16, 2003 6:33 am
by Subeen
How the input :
6
3 1 2 5 6 4
produces output:
2
please explain it to me. ( i think the output should be 3 )
Posted: Thu Oct 16, 2003 7:26 am
by mbakht
Hi Subeen,
For the input
6
3 1 2 5 6 4
We can think of the sequence
3 2 1 6 5 4 (which is mirror image of 4 5 6 1 2 3=> 1 2 3 4 5 6)
Just two swaps ( 2<->1 , 5<->6) are needed.
Hope it helps.
Posted: Thu Oct 16, 2003 7:27 am
by Per
First swap 1 and 2. Then swap 5 and 6. The result is 3 2 1 6 5 4, so the aliens are sitting in order.
Posted: Thu Oct 16, 2003 8:15 am
by Subeen
thanks to mehedi bhai and Per.
Larry,
for input: 3 1 2 5 7 6 4
if we swap 2<->1, then 5<->6 and then 6<->7
we get, 3 2 1 7 6 5 4, which can be arranged as: 1 2 3 4 5 6 7.
so it takes only 3 swaps, not 4, am I right?
Posted: Thu Oct 16, 2003 1:54 pm
by Larry
Ya, that's a better solution.
But I was simply trying to illustrate how you would calculate the number of swaps from:
3 1 2 5 7 6 4
to
1 2 3 4 5 6 7
Sorry if I confused you.
10570 Do I understand it correctly?
Posted: Sun Dec 21, 2003 6:07 pm
by ..
In the sample input.
4
2 3 1 4
Does it mean that, now the 4 aliens sit around the table such that
alien 2 is next to alien 3 and alien 4
alien 3 is next to alien 2 and alien 1
alien 1 is next to alien 3 and alien 4
alien 4 is next to alien 1 and alien 2
And I need to do the minimum number of operations to exchange 2 aliens
(even they are not adjacent) so that
alien 2 is next to alien 3 and alien 1
alien 3 is next to alien 2 and alien 4
alien 1 is next to alien 4 and alien 2
alien 4 is next to alien 1 and alien 3??
Am I correct?? My program get WA for using 0.02s, much shorter than every accepted program. I think I have wrong understanding. Otherwise this problem should be solved in O(n)........
Posted: Mon Dec 22, 2003 1:21 am
by Larry
You have to make it so that it'll be 1 2 3 4, or 4 3 2 1 in that order, wrapping around..
So in your case, you could've swapped 1 and 4, in one move, and then have:
2 3 4 1, which is in order.
Posted: Tue May 08, 2007 9:23 am
by Kallol
i tol TLE . I think i am getting the right answer , but i need better algorithm , can anyone help me?
here is my code:
Code: Select all
#include<stdio.h>
int a[600];
int a1[600];
int a2[600];
int min(int a,int b)
{
if(a<b)
{
return a;
}
return b;
}
void rotate(int n)
{
int temp=a[n-1];
int i;
for(i=n-2;i>=0;i--)
{
a[i+1]=a[i];
a1[i+1]=a[i];
a2[i+1]=a[i];
}
a[0]=temp;
a1[0]=temp;
a2[0]=temp;
return;
}
int asc(int n)
{
int count=0;
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a1[i]>a1[j])
{
int temp=a1[i];
a1[i]=a1[j];
a1[j]=temp;
count++;
}
}
}
return count;
}
int dsc(int n)
{
int count=0;
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a2[i]<a2[j])
{
int temp=a2[i];
a2[i]=a2[j];
a2[j]=temp;
count++;
}
}
}
return count;
}
int main(void)
{
int n,i,m,M;
while(1)
{
scanf("%d",&n);
if(n==0)
{
break;
}
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
a1[i]=a[i];
a2[i]=a[i];
}
M=min(asc(n),dsc(n));
for(i=0;i<n;i++)
{
rotate(n);
m=min(asc(n),dsc(n));
if(m<M)
{
M=m;
}
}
printf("%d\n",M);
}
return 0;
}