ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1744. The Captain's Squad

Algorithm (+)
Posted by Vedernikoff Sergey (HSE: АОП) 20 Sep 2010 03:51
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 (+)
Posted by Ripatti [Ufa] 28 Oct 2010 01:58
There rigorous algo exists. It has O(N^2) complexity and about 10 lines of code.
Re: Algorithm (+)
Posted by Vedernikoff Sergey (HSE: АОП) 28 Oct 2010 12:04
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 (+)
Posted by Ripatti [Ufa] 29 Oct 2010 14:40
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 (+)
Posted by Vedernikoff Sergey (HSE: АОП) 29 Oct 2010 19:09
Thanks, but, probably, you could give some clue for algorithmic solution of the problem?
Re: Algorithm (+)
Posted by Ripatti [Ufa] 30 Oct 2010 19:04
Try to arrange soldiers in vertices of regular n-polygon and mind geometrically.