32 / 32
Mar 2011

Take the input:

10
3 2 1 7 4 5 6 9 10 8

This can be divided into several "cycles" i.e. smallest groups of numbers that can be rearranged among themselves to produce the correct permutation. The cycles are:

3 1 - length 2
2 - length 1
7 4 5 6 - length 4
9 10 8 - length 3

Obviously, cycles of length 1 are already solved and cycles of length 2 can be solved just by swapping the two numbers. But what would you do for the cycle of length 3 or 4? Or how about 6, like the example given by whiz? If all the numbers form a single cycle, then by the problem's constraints you might have to deal with a cycle as long as 5000.

Try solving by hand cycles of small lengths, and then you might think of a solution that works for any length.

Hello,

I tried a bit of a crazy idea on this problem, it seemed to work on every "small" test case that I built. The concept was to first identify cycles. Once you have them the way of ordering each cycle is as follows:
- Take the bigest and smallest value that haven't been swaped yet.
- Swap them.
- Reapet until the bigest and smallest values are the same.
After this, one day has passed, and the array is not necesarely ordered yet, so we reapet everything including the cycle identification until all cycles are of length 1.

Here is my output for problem's example:

input:
7
2 1 3 5 6 7 4

output:
3 2-1 7-4 6-5
1 6-4

It's not the same as the sample output but it is such as valid.

Here is my output for whiz's example:

input:
6
6 1 2 3 4 5

output:
3 6-1 5-2 4-3
2 6-2 5-3

But, I am getting a nice WA. Dos anyone know what could be wrong?

Thanks in advace.

TripleM is right. If the output is WA, you give the wrong answer. I won't tell the solution here, but just a hint: The number of days needed is bounded by a surprisingly low constant, not depending on cycle length, whereas the naive implementation, I also tried first, scales with O(log len). Any algorithm that is worse than O(1) days is correctly rejected as WA.

Examining the example with the 6-cycle that is solved in 2 instead of 3 days (given in this forum) pushed me to the right track. buldae_bien_'s algorithm happens to hit the optimal implementation under certain circumstances, for example in whiz's example, but does not do so in other cases, where a heuristic assumption included in it fails.

PS: I won't give any further hints to this problem. I go back squeezing more digits of SQRT(2).

Hello,

Thanks twice11, you were very right. I have found the constant that is an upper bound for this problem, regardless of the cycle length. What I don't seem to find is an algorithm that can fit to this constant for every test case. My latest non-implemented idea was to just swap with backtracking every posible swap combination until we only have length 2 cycles, but this would sure give TLE. I'm a bit frustraded with this problem. :S

I think with your 'lucky' previous idea you should be able to get to a correct algorithm.
Hint: you can relabel a cycle of length n to 'n 1 2 .. (n-1)'. The relabelling is easy enough, so all you need to do is work out how to solve that particular instance..

I am getting [color=red]runtime error (other)[/color] in this one.
Any idea of what does 'other' mean?

Y.

In most cases this means "memory limit exceeded".

Hello,

TripleM thanks for the hint, but I don't think that my first lucky guess can produce a correct algorithm. For example take this test case:

8
5 4 6 3 7 1 8 2

Even cuting the calculations with the constant upper bound, my original algorithm of swaping the biggest and smallest value would lead this test case to either run forever or write an incorrect answer.

How you can see this test case is one single 8-length cycle, I don't know if I understood correctly your hint, but this test case doesn't seem like it can be relabelled to n 1 2 ... (n-1).

The only set of optimal swaps that I found for this test case are as follows:

2
4 2-5 1-4 3-6 7-8
3 1-2 4-6 5-8

And I can't find any relation or pattern of choice that could induce to a correct algorithm.

Thanks anyway. stuck_out_tongue

8
5 4 6 3 7 1 8 2

This is just the cycle 1->5->7->8->2->4->3->6.

On the other hand,
8
h a b c d e f g

That is just the cycle a->h->g->f->e->d->c->b.

So if you know how to solve the second one, you immediately know how to solve the first one (just replace each letter by its matching number).

Thank you very, very much TripleM, now got AC. The solution is quite interesting. I still cant belive it works for every case.

8 days later

with "optimal solution" i meant 2, i always find it funny when people always expect the answer to their faces

I didn't 'expect the answer to my face', whatever that means, I was just pointing out that we cannot possibly help you when you say 'I'm right but I'm getting WA'. What did you expect us to say? That you've got an error on line 32?

Yes you are right, i just asked if there is a tricky part on this problem
My method is find cycles and put them on an array
and to the middle of the array swap the begining and the end

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXN 6000
int N,array[2*MAXN],place[2*MAXN],used[2*MAXN],cur=0,list[20][2*MAXN][6],last[2*MAXN];
void change(int x,int y)
{
	if(used[x] || used[y]) return;
	if(x==y) { used[x]=1; return;}
/*	printf("%d with %d\n",x,y);
*/	int xx=array[x],yy=array[y];
	array[x]=yy; place[yy]=x;
	array[y]=xx; place[xx]=y;
	used[x]=used[y]=1;
	list[cur][last[cur]][0]=x;
	list[cur][last[cur]++][1]=y;
}
int main()
{
	int i,j,ctrl;
	scanf(" %d",&N);
	for(i=1;i<=N;i++)
	{
		scanf(" %d",&array[i]);
		place[array[i]]=i;
	}
	int listx[MAXN*2],lastx,x,y;
    while(1)
{
	ctrl=1;
	for(i=1;i<=N;i++) if(array[i]!=i) {ctrl=0; break;}
	if(ctrl) break;

/*	for(i=1;i<=N;i++) printf("%d ",array[i]); printf("\n");
*/
		for(i=1;i<=N;i++)
		{
			if(!used[i] && array[i]!=i)
			{
				lastx=0;
				listx[lastx++]=i;
				while(1)
				{
					x=array[listx[lastx-1]];
					if(x!=i)
					{
						listx[lastx++]=x;
					}
					else break;
				}
				x=0;
				y=lastx-1;
			/*	for(j=lastx-1;j>=0;j--) listx[j+1]=listx[j];
				listx[0]=listx[lastx];
			*/
				while(x<=y)
				{
					change(listx[x],listx[y]);
					x++; y--;
				}
			}
		}
    	for(i=1;i<=N;i++) used[i]=0;

	cur++;
}

printf("%d\n",cur);
for(i=0;i<cur;i++)
{
	printf("%d",last[i]);
	for(j=0;j<last[i];j++)
		printf(" %d-%d",list[i][j][0],list[i][j][1]);
	printf("\n");
}
return 0;
}

i always get WA ...

it works and the last time i tried for randomly generated N=5000 the answer was always 2

No it doesn't..
On the sample input: 2 1 3 5 6 7 4

Your program produces:
3 1-2 4-7 5-6
1 5-7

Which leads to the following
after 1-2: 1 2 3 5 6 7 4
after 4-7: 1 2 3 5 6 4 7
after 5-6: 1 2 3 6 5 4 7
after 5-7: 1 2 3 6 7 4 5

Seems like you didn't understand something. If you change 4-7, you change numbers 4 and 7, not numbers on positions 4 and 7. For example, after 4-7 you suppose that it's
2 1 3 4 6 7 5
but it's really
2 1 3 5 6 4 7

3 years later

Nie cierpię pisać takich postów, ale niestety mało prawdopodobne jest, że otrzymasz tutaj pomoc dotyczącą rzadko używanych języków.
Użytkownicy polskiego SPOJa rzadko używają tych mało popularnych języków, a nawet jeśli, to raczej nie wchodzą na to forum.
Tak więc radziłbym Ci napisać na spoj.pl/forum, gdzie dział "Języki programowania" jest nawet podzielony na poddziały, więc osoby przeglądające dany dział znają się mniej lub więcej na danym języku i jest większe prawdopodobieństwo, że Ci odpowiedzą.

No i może pomoże Ci jeszcze przykładowy kod na ideone.com (ideone działa mniej więcej tak, jak SPOJ):
http://ideone.com/samples#sample_lang_131
Jeśli nie, to na ideone jest też pozycja "Ostatnie kody", w których użytkownicy zgłaszali programy. "Wystarczy" więc znaleźć taki, który nie dostał SIGSEGV.