| ENG RUS | Timus Online Judge |
Discussion of Problem 1743. Domino Sortingjk_qq Hint. // Problem 1743. Domino Sorting 17 Oct 2017 13:42 Find domino with the least number of all 2*n numbers (second number have to be the biggest possible among all dominos with least first number). Let's denote minimal number as MIN and maximum as MAX. Put it in the first position with left half to be the minimal number. Then find all dominos with number more than MAX. Easy to see we already know it's orientation because of first domino (think a moment here). Put all dominos like that (use std::set<pair> or similar ds). Repeat process. Mine impl uses one set for finding first domino and one for finding all dominos with number more than current MAX. (O(N log N)) Felix_Mate To admins // Problem 1743. Domino Sorting 14 Jul 2017 14:10 1)Look at my solution 7450309 (Runtime error (non-zero exit code) on test 23)) and 7450312(AC). Why i got Runtime error (non-zero exit code) on test 23? In first solution i have nmax=123456 and in second 223456. What is range of n? 2)Look on problem 1974. In forum i wrote test when my AC solution get wrong answer(I can write more tests where my old AC solution falls) plp Who could told me the name of this problem's arithmetic? // Problem 1743. Domino Sorting 20 Mar 2012 19:21 Zayakin Andrey[PermSU] Algo [5] // Problem 1743. Domino Sorting 24 Jan 2010 00:35 What is your comlexiety of your algo? my O(n^2) solve this. Lezhankin Petr [Ufa] Re: Algo [4] // Problem 1743. Domino Sorting 25 Jan 2010 20:13 Do u claim that u've got AC with solution in O(n^2)? (n is up to 100000) Zayakin Andrey[PermSU] Re: Algo [3] // Problem 1743. Domino Sorting 26 Jan 2010 16:14 Build all 2*n pairs of numbers, sort this(firstly by first numbers by non-decreasing order, if first number is equal - sorted by second numbers by non-increasing order). And using greedy build sequence with length equal N start with a[0], if we don`t find solution, start with a[1] and so on, if we have solution we stop algo. Sory for my english. ilucian1 Re: Algo [1] // Problem 1743. Domino Sorting 2 Feb 2010 15:33 his algorithm is very good but I think its complexity actually is n*log(n) (sorting) + n (finding the solution) svr Re: Algo // Problem 1743. Domino Sorting 3 Feb 2010 11:04 I suggest math righ algo; Let a:[1..n]->{0,1} - rotate or not. (i,j)- red if must a[i]!=a[j] (i,j)- blue if must a[i]=a[j] Blue connections- equality relation and we form m classes If inside some class there is a red edge- "NO" BFS in superGraph of classes If find not even cicle "NO"- edge along level of graph Rotate classes on even levels. 12 tests Ok test13 TL Edited by author 03.02.2010 16:59 Edited by author 03.02.2010 16:59 Vladislav Re: Algo // Problem 1743. Domino Sorting 21 Sep 2011 20:39 The complexity can be O( n*log(n) ). Sort the 2n pairs as described(increasing by first, decreasing by second) and start from a[0]. The greedy alg. is as follows: go throught a1,a2... , when we find something which we can include and haven't included, include it. It is correct, because for a0 we can only put it in the begining or (inversed) at the end. But if we put it in the end, we can invert the whole sequence and get a solution with it at the begining and so on. So a0 will always give a solution (if possible) and we need one pass. Sandro (USU) Problem 1743. "Domino Sorting" has been rejudged (+) // Problem 1743. Domino Sorting 24 Dec 2010 01:07 New tests by Eugene Kurpilyansky were added. 11 authors lost AC. LSBG tests // Problem 1743. Domino Sorting 24 Jan 2010 02:06 Finally I got accepted. I include several tests to help you debug: input output: 8 YES 1 70 1 70 4 65 4 65 64 66 61 64 61 64 65 64 66 62 66 64 80 50 66 62 80 60 80 60 65 64 80 50 input: output: 3 YES 1 3 1 3 2 1 1 2 2 3 3 2
|