ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1609. Tram Tile

But how to solve this problem??
Posted by caoqinxiang 6 Apr 2008 07:49
Re: But how to solve this problem??
Posted by DK [Samara SAU 1: X2008] 27 Apr 2008 01:58
Use the "SHAMANIZM" to overcome time-limit ;)
Re: But how to solve this problem??
Posted by svr 18 Jun 2008 13:53
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??
Posted by Denis Koshman 26 Aug 2008 07:04
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??
Posted by Shen Yang 10 May 2018 13:46
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