| ENG RUS | Timus Online Judge |
Discussion of Problem 1676. Mortal KombatMichail Yudin WA8 give me some tests [3] // Problem 1676. Mortal Kombat 18 Jan 2009 23:26 Thx a lot for every man and women for tests. Al.Cash Re: WA8 give me some tests [1] // Problem 1676. Mortal Kombat 30 Jan 2009 16:34 Try this: 4 4 1111 1110 1100 1000 The answer: 1110 1101 1011 0111 Jorjia Re: WA8 give me some tests // Problem 1676. Mortal Kombat 18 Nov 2018 21:37 My code gives right answer for this test, but still got WA8. My algo: 1) find any perfect match (I use kuhn algorithm). If there no perfect match print unary matrix and quit. 2) for every i-monster, remove edge (i, match(i)), and try make alternate path for i. save result in d[] array, and restore edge (i, match(i)) . 3) We can select (i,j) edge only if Mij = true AND (i,j) edge in perfect match, or j is free vertex, or d[ match( j ) ] is true. Can give some tests ? Mickkie Re: WA8 give me some tests // Problem 1676. Mortal Kombat 29 Nov 2023 23:38 Test: 6 7 1111000 1110000 1100000 1000100 0000110 0000110 WA8 answer: 0000111 0001111 0011111 0111011 1111001 1111001 AShelyugov What about input/output format? // Problem 1676. Mortal Kombat 16 May 2013 04:59 I'm trying to solve this in java. This probably sounds silly, but I don't get do I need to use StreamTokenizer as was mentioned in the local java guide? Or I just need to read input char by char? Are spaces between numbers necessary? And where if they are? Same question for both input and output. Edited by author 16.05.2013 05:00 Edited by author 16.05.2013 05:01 Georgiy Platonov if there is no solution... [1] // Problem 1676. Mortal Kombat 10 Jan 2009 14:10 If some Earth fighter can defeat no monster, what we must to output? Entire unary matrix or unary column of this fighter and respectively calculated columns for others? olpetOdessaONU [1 2/3] Re: if there is no solution... // Problem 1676. Mortal Kombat 22 Aug 2010 15:22 In the sample test is shown the same case. Right output for it is unary matrix. svr hint [4] // Problem 1676. Mortal Kombat 21 Jan 2009 14:05 Using O(n^2) transitive closure in bipartite Graph was successful. Al.Cash Re: hint [3] // Problem 1676. Mortal Kombat 26 Jan 2009 21:30 Does your solution use Hall's theorem? svr Re: hint [2] // Problem 1676. Mortal Kombat 26 Jan 2009 21:57 May be. If it is Hall's. Now it is mine:edge (ra,rb) can precence in some assigment solution if and only if 1)it's begining ra achievable by alternating path's with respect to some given matching from it's end rb. OR 2) Some free vertex achievable from rb. Edited by author 26.01.2009 22:01 Al.Cash Re: hint [1] // Problem 1676. Mortal Kombat 28 Jan 2009 01:10 Your statement is quite simple to prove and it seems very useful for this problem. But don't you need to build some matching before applying it? Then the algorithm's complexity is O(N^2*M), which is much slower then O(N^2) mentioned before)) svr Re: hint // Problem 1676. Mortal Kombat 28 Jan 2009 09:26 I said about complexity of submethod and not about integral complexity. i.e. about nonstandard part of algo.
|