But how to solve this problem??

Re: But how to solve this problem??

Use the "SHAMANIZM" to overcome time-limit ;)

Re: But how to solve this problem??

Posted by

svr 18 Jun 2008 13:53

Another advice:

I guess that rested domino must form graph with next specific:

It must be reduced to empty by sequental removing of

vertex with degree=1 and adjacent with one.

("должен общипываться").What kind of these graphs?

*Edited by author 18.06.2008 14:10*

Re: But how to solve this problem??

Dominos are usually solved by finding perfect bipartie matching between odd and even cells (for their x+y). Now the problem is to fix minimal number of matched edges, so that maximum matching over remaining graph is unique. If there is alternating cycle, then matching is not unique.

*Edited by author 26.08.2008 07:12*

Re: But how to solve this problem??

Posted by

svr 12 Feb 2009 12:10

What algo could we design based on it?

1. Find all cycles.

2. For each edge form set of all circles containig it.

3. Find minimal covering of set of all circles.

Shortly, we should use minimal covering problem?

*Edited by author 12.02.2009 12:11*

Re: But how to solve this problem??

sure there is not more than min(n,m)/2+3 ones, but how we can prove or say its wrong there is no more optimal solution