|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Good test cases | Deepesson | 1609. Трамвайная плитка | 8 фев 2021 17:48 | 4 | Some good test cases:
2 8
3
01100011
00011000
1 2
0
00
Edited by author 07.02.2021 19:15 8 10
4
0000011000
0000110000
0000011000
0000110000
0000000000
0000000000
0000000000
0000000000
You should also try switching N and M (10 8)
Edited by author 08.02.2021 16:48 10 10
5
0000000000
1000000000
1100000000
0111100000
0010110000
0000000000
0000000000
0000000000
0000000000
0000000000 AC finally!!! I used a randomized approach, but in the end, I needed to use a special seed. Nice problem, but unfortunately, I wasn't able to find test 74 to share here. | | But how to solve this problem?? | caoqinxiang | 1609. Трамвайная плитка | 10 май 2018 13:46 | 6 | Use the "SHAMANIZM" to overcome time-limit ;) 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. Трамвайная плитка | 21 янв 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. Трамвайная плитка | 29 апр 2008 21:22 | 1 | | | How to prove that... | DK [Samara SAU 1: X2008] | 1609. Трамвайная плитка | 27 апр 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 "one-way" 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 |
|
|
|
