Show all threads Hide all threads Show all messages Hide all messages  But how to solve this problem??  caoqinxiang  1609. Tram Tile  10 May 2018 13:46  6  Use the "SHAMANIZM" to overcome timelimit ;) 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 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 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 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  Could you tell me how to solve this problem?  yuyan  1609. Tram Tile  21 Jan 2009 12:54  1  First,I think it might use "Bit DP" to solve this problem.But I failed Second,I think it might have a method to make a solution for given N,M .But I can't find this method. Last,I want to calculate all the case because N and M is very small.But I can't decide whether it is the best solution for each case. I have no idea for this problem.Could you please tell me how to solve this problem?Thank you. By the way,I'm sorry for my poor English.I wish you could know what I say.  Give some Hint,please  olao  1609. Tram Tile  29 Apr 2008 21:22  1   How to prove that...  DK [Samara SAU 1: X2008]  1609. Tram Tile  27 Apr 2008 02:01  3  If there is at least one empty cell, every cell could be covered more than one way, and there is a way to cover all the cells, there is another way to cover all the cells? Your reasoning is wrong. I give you example. Could you find more than one way for cover this cells? 110000 011000 001100 000000 000000 000000 this case works, only by making "oneway" steps i can fill the board, 11GGEE 211FFD 2311CD 4388CB 46699B 5577AA note that "EVERY cell could be covered more than one way" in your case this wrong for cell (2,1) Edited by author 27.04.2008 02:03 

