605 - The Rotating Disk

[Miguel Angel]

How to solve it?. I can think about Greedy, but some cases my heuristhics don't work. Or search, but won't be too large store partial permutations?

[Alexander Denisjuk]

How to solve it?. ?

Well, just analyse the problem to see when it is soluable, when it is not. If yes, my algorithm is to place all the numbers to their places, one by one.

A propos, does anybody know if there is any problem, which can be solved by using some heuristics?

[Subfallen]

I have two doubts regarding 605.

(1) Is there supposed to be a limit for n? It is not given in the problem!

(2) Does anyone know a deterministic approach for converting a set of numbers to natural order? I have not been able to think of a way, and am about to attempt a heuristic search

[Shit]

Excuse me, but there is small problem in this problem
Please tell me why
the code

#include <stdio.h>

void main()

#include <stdio.h>
void main()
{
int a;
scanf("%d",&a);
while (a)
{
printf("%d",a);
scanf("%d",&a);
}
}

gives me

Time Limit Exceeded 0:10.064

, but not a wrong answer ??

[emotional blind]

the loop

while(a){
...
}

continues untill a==0
but the input does not contain any zero
so your loop doesnt end
and you get TLE

[little joey]

Yes, the problem is slightly under-specified.

(1) I use 4 <= n <= 256.

(2) It doesn't state that the solution has to be optimal. My algo performs < 4*n*n steps worst case, but significantly less on average. I don't know what the output limit is, but I suppose it's not too difficult to write a program that reaches it.

[Yu Fan]

in this problem,how can we detemine whether the track can be solved?
thanks in advance

[christephan]

in this problem,how can we detemine whether the track can be solved?
thanks in advance

You can write another programme to find out when the track can be solved.

[stencel]

I'm still fighting the prob and cannot get accepted. Could someone please share with me some clarifications of the tasks? The description is rather vague.

1. What is "the natural order"? Is the reverse "3 2 1" natural?
2. How do you understand "You must not display moves around the whole
track."? Ain't we allowed to do anything when N == 4 or we are allowed
but we are supposed not to print it?
3. Could someone please show me your correct output for the test case below?
4. Do you know about other nasty traps in this problem description?

Code: Select all

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

EDIT: I finally got AC Here are the answer (from email from Cedric Lin; thanks!):

1. "natural order" is just increasing order, I believe. So "3 2 1" is not natural.
2. I think what is meant by "moves around the whole track" are moves that would wraparound the output line. (So you can't have "1 2* 3 4 5 6 7 8 *9 10" to indicate that you are rotating the disk with 9, 10, 1 and 2.)

Code: Select all

1

1 2

2 1

1 2 3

1 3 2
It is not possible to rearrange these disks in natural order.

2 1 3
It is not possible to rearrange these disks in natural order.

2 3 1

3 1 2

3 2 1
It is not possible to rearrange these disks in natural order.

1 2 3 4

1 2 4 3
It is not possible to rearrange these disks in natural order.

1 3 2 4
It is not possible to rearrange these disks in natural order.

1 3 4 2
It is not possible to rearrange these disks in natural order.

1 4 3 2
*2 3 4 1*

1 4 2 3
It is not possible to rearrange these disks in natural order.

5 4 3 2 1
*2 3 4 5* 1

6 5 4 3 2 1
5 4 *6 1 2 3*
*1 6 4 5* 2 3
1 *2 5 4 6* 3
1 2 *3 6 4 5*
*6 3 2 1* 4 5
6 3 *5 4 1 2*
6 *1 4 5 3* 2
6 1 *2 3 5 4*
*3 2 1 6* 5 4
3 *5 6 1 2* 4
*1 6 5 3* 2 4
1 *2 3 5 6* 4
*5 3 2 1* 6 4
5 3 *4 6 1 2*
5 *1 6 4 3* 2
5 1 *2 3 4 6*
*3 2 1 5* 4 6
3 *4 5 1 2* 6
*1 5 4 3* 2 6
1 *2 3 4 5* 6

7 6 5 4 3 2 1
It is not possible to rearrange these disks in natural order.

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

BTW: I checked that there are no inputs with N < 4.