| ENG RUS | Timus Online Judge |
Обсуждение задачи 1609. Трамвайная плиткаDeepesson Good test cases [3] // Задача 1609. Трамвайная плитка 7 фев 2021 19:15 Some good test cases: 2 8 3 01100011 00011000 1 2 0 00 Edited by author 07.02.2021 19:15 Deepesson Re: Good test cases [2] // Задача 1609. Трамвайная плитка 8 фев 2021 16:35 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 Deepesson Re: Good test cases [1] // Задача 1609. Трамвайная плитка 8 фев 2021 17:39 10 10 5 0000000000 1000000000 1100000000 0111100000 0010110000 0000000000 0000000000 0000000000 0000000000 0000000000 Deepesson Re: Good test cases // Задача 1609. Трамвайная плитка 8 фев 2021 17:48 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. caoqinxiang But how to solve this problem?? [5] // Задача 1609. Трамвайная плитка 6 апр 2008 07:49 DK [Samara SAU 1: X2008] Re: But how to solve this problem?? [4] // Задача 1609. Трамвайная плитка 27 апр 2008 01:58 Use the "SHAMANIZM" to overcome time-limit ;) svr Re: But how to solve this problem?? [3] // Задача 1609. Трамвайная плитка 18 июн 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 Denis Koshman Re: But how to solve this problem?? [2] // Задача 1609. Трамвайная плитка 26 авг 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 svr Re: But how to solve this problem?? [1] // Задача 1609. Трамвайная плитка 12 фев 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 Shen Yang Re: But how to solve this problem?? // Задача 1609. Трамвайная плитка 10 май 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 yuyan Could you tell me how to solve this problem? // Задача 1609. Трамвайная плитка 21 янв 2009 12:54 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. olao Give some Hint,please // Задача 1609. Трамвайная плитка 29 апр 2008 21:22 Tx.. DK [Samara SAU 1: X2008] How to prove that... [2] // Задача 1609. Трамвайная плитка 31 мар 2008 02:28 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? BellnoX [Tyumen SU] Re: How to prove that... [1] // Задача 1609. Трамвайная плитка 31 мар 2008 22:18 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 DK [Samara SAU 1: X2008] Re: How to prove that... // Задача 1609. Трамвайная плитка 27 апр 2008 02:01 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
|