Discussion @ 1163. Chapaev @ Timus Online Judge

Is greedy method ok or not? Is it nessary to make full search? Nazarov Denis (nsc2001@rambler.ru) 11 Mar 2002 20:43

Re: Is greedy method ok or not? Is it nessary to make full search? svr 27 Jun 2007 13:45

I think that it is DP-problem
We consider 2^16 states from 0 to final=2^16-1
Before we make precalculation finding for each draught
finite possible moves just as adjacent to some
another draught and bisectors between adjacent rays
Anywhere we must use eps≈0.0000001 as precision level.
Having found all possible moves we can easy reduce state k
to states with few value because one move make number of draughts smaller.
Finding all possibilities we must consider adjacent rays to draughts with the same color
as now active draught.

Edited by author 27.06.2007 13:46

Re: Is greedy method ok or not? Is it nessary to make full search? Vedernikoff Sergey 27 Jun 2007 16:42

I think, it is impolite to explain solutions of good problems here in forum. Of course, greedy algo doesn't work here...

Re: Is greedy method ok or not? Is it nessary to make full search? svr 27 Jun 2007 23:36

This is an old problem and beginers need
clear plan before starting to solve.

Re: Is greedy method ok or not? Is it nessary to make full search? Denis Koshman 13 Aug 2008 23:30

I agree with svr. Things required to solve this problem are quite conceptual, so it's ok to tell them in the forum.

Discussion of Problem 1163. Chapaev