Algorithm (+)

Solved the problem with pure brute-force in 0.031 sec. BTW, my program works for much larger n's than in the problem statement.

I'm wondering whether there is more rigorous solution?

Re: Algorithm (+)

There rigorous algo exists. It has O(N^2) complexity and about 10 lines of code.

Re: Algorithm (+)

My solution is not much longer - about 20 lines of code. But complexity is O(2^(N/2)*(1/2*N^2)!). But works fast for almost any N =)

Re: Algorithm (+)

It means that you are very cool:D

For Petrozavodsk this problem was planned as solvable by brute force and some precalculation. Just for fun.

Re: Algorithm (+)

Thanks, but, probably, you could give some clue for algorithmic solution of the problem?

Re: Algorithm (+)

Try to arrange soldiers in vertices of regular n-polygon and mind geometrically.