10570 - Meeting with Aliens

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

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]

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]

Thanks, Adrian. I've corrected my mistake. I get TLE, but that's probably because my loop doesn't end for whatever reason.

[Pier]

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


Thanks!

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

[Per]

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]

You're right, of course, Per. =)

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

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

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

[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?

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

[..]

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

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

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