| ENG RUS | Timus Online Judge |
Обсуждение задачи 1676. Смертельная битваMichail Yudin WA8 give me some tests [3] // Задача 1676. Смертельная битва 18 янв 2009 23:26 Thx a lot for every man and women for tests. Al.Cash Re: WA8 give me some tests [1] // Задача 1676. Смертельная битва 30 янв 2009 16:34 Try this: 4 4 1111 1110 1100 1000 The answer: 1110 1101 1011 0111 Jorjia Re: WA8 give me some tests // Задача 1676. Смертельная битва 18 ноя 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 // Задача 1676. Смертельная битва 29 ноя 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? // Задача 1676. Смертельная битва 16 май 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] // Задача 1676. Смертельная битва 10 янв 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... // Задача 1676. Смертельная битва 22 авг 2010 15:22 In the sample test is shown the same case. Right output for it is unary matrix. svr hint [4] // Задача 1676. Смертельная битва 21 янв 2009 14:05 Using O(n^2) transitive closure in bipartite Graph was successful. Al.Cash Re: hint [3] // Задача 1676. Смертельная битва 26 янв 2009 21:30 Does your solution use Hall's theorem? svr Re: hint [2] // Задача 1676. Смертельная битва 26 янв 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] // Задача 1676. Смертельная битва 28 янв 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 // Задача 1676. Смертельная битва 28 янв 2009 09:26 I said about complexity of submethod and not about integral complexity. i.e. about nonstandard part of algo.
|