10094 - Place the Guards

[jamu]

Nick, your answer is wrong for 14:

4 6 8 10 12 14 2 13 1 3 5 7 9 11

I am convinced that there is some general pattern for the case
n = 6K+2 or 6K+3 , seeing the very low runtimes.
I can't see it yet.

All the answers that are not of the form 6k+2 or 6k+3 can be very simple with property of rotational symmetry (Nick's output for 6 and 12), all the answers in the sample output of the problem in the problemset archive have rotational symmetry, even the output for 8, which is of the form 6k+2.

Try to generate all the different answers for 8, 14 and 20 that are rotational symmetric (this is relatively small subset of all the answers for 8, 14 and 20), look for simple answers (similar to these which are not of the form 6k+2 or 6k+3) and then you should find out some really simple pattern. Answers for 9, 15, 21, ... can be easily made from 8, 14, 20, ...

[Jan]

I think u dont need to backtrack. Just read the algorithm carefully.

1. If given n is in the form 6*k+2 or 6*k+3 then goto step 3.
2. Print 2, 4, 6 ... upto n then print 1, 3, 5 ... upto n, goto step 7.
3. Find the value of k.
4. Then u can print form 2*k+2 ... upto n, then print 2, 4 ... upto 2*k.
5. Check if 1, 3, ... is valid, if not then start from 3, 5, ..., if not start from 5, 7... and so on.
6. Print the valid odd numbers.
7. End.

Then you can avoid TLE.

Hope it helps.

[yiuyuho]

Can you explain step 5 more elaborately? I am guessing 1,3,... means 1,3,5,7,...n and 3,5,... means 3,5,7,9,...,n,1,3 ??

[Jan]

Can you explain step 5 more elaborately? I am guessing 1,3,... means 1,3,5,7,...n and 3,5,... means 3,5,7,9,...,n,1,3 ??

Yes, you are correct. Just try to draw smaller boards to find the pattern. Remember that you have printed the even numbers, and you have to print the odd numbers in a cyclic order.

If you can't find then PM me. May be describing step 5 would be too much spoiler.

[tiendaotd]

I used this "naive solution" and it worked : I supposed that the answer will be two part : one includes all even number and one includes all odd number , all number from 1 to n.

Then I "greedily" place the queen start from x, then x+2, x+4 , ...till the end of the board and begin again from 2 to x-2 . The same rule for odd number. Then I just check if this configuration is valid , if yes, print answer, if no, try next start number of odd , and then start number of even. This solution works in O((n/2)^3)

My algo looks like this :

Code: Select all

n = 8
Even : 
2468
Odd : 1357 valid ? no
Odd : 3571 valid ? no
Odd : 5713 valid ? no
Odd : 7135 valid ? no
Even : 
4682
Odd : 1357 valid ? no
Odd : 3571 valid ? no
Odd : 5713 valid ? no
Odd : 7135 valid ? yes -> print