## 10570 - Meeting with Aliens

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10570 - Meeting with Aliens

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:

Code: Select all

``````0
0
1
2
2
16
17
0
1
0
0
``````
Thanks.

Basically, my algorithm is finding permutation groups, is there a simpler way just that my implementation is wrong? Thanks.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Thanks, Adrian. I've corrected my mistake. I get TLE, but that's probably because my loop doesn't end for whatever reason.

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

### Time Limit Exceeded

I have a n^3 algorithm and I get TLE. How should I approach this problem to get a better algorithm?

Thanks!
There are 10 kind of people on this world: those who understand binary and those who don't!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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.
Last edited by Larry on Thu Oct 16, 2003 1:56 pm, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
You're right, of course, Per. =)

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:
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 )

mbakht
New poster
Posts: 16
Joined: Fri Feb 28, 2003 7:54 pm
Location: Bangladesh
Contact:
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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:
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?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 10570 Do I understand it correctly?

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)........
Last edited by .. on Mon Dec 22, 2003 7:49 pm, edited 1 time in total.
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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;
}

``````
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh