Обсуждение @ 1744. Рота Капитана @ Timus Online Judge

Vedernikoff Sergey (HSE: АОП) Algorithm (+) [5] // Задача 1744. Рота Капитана 20 сен 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?

Ripatti [Ufa] Re: Algorithm (+) [4] // Задача 1744. Рота Капитана 28 окт 2010 01:58

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

Vedernikoff Sergey (HSE: АОП) Re: Algorithm (+) [3] // Задача 1744. Рота Капитана 28 окт 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 =)

Ripatti [Ufa] Re: Algorithm (+) [2] // Задача 1744. Рота Капитана 29 окт 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.

Vedernikoff Sergey (HSE: АОП) Re: Algorithm (+) [1] // Задача 1744. Рота Капитана 29 окт 2010 19:09

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

Ripatti [Ufa] Re: Algorithm (+) // Задача 1744. Рота Капитана 30 окт 2010 19:04

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

Обсуждение задачи 1744. Рота Капитана