|
|
Problem statement says "His friends write numbers from 1 to N on cards", but it doesn't mention that these numbers should be distinct. Yet, it seems like the problem only accepts solutions in which the numbers are distinct (i.e. the numbers on the N cards are a permutation of [1..N]). A dozen of new tests has been added. Time limit has been decreased to 500 ms. All submissions have been rejudged - 58 authors have lost their AC. Can anybody provide me with 37 test? I have runtime error in Python. 4 2 4 3 2 4 4 2 1 1 2 3 4 // 2 1 2 2 4 3 2 1 2 1 1 4 4 4 2 3 1 // 1 1 2 2 2 2 2 2 1 1 1 // 1 1 3 1 2 1 2 3 2 3 1 3 // 1 1 1 Edited by author 24.01.2009 20:24 Hint: Try to build bipartite graph with 2*N edges. Then iteratively find vertice with only one connected edge. This edge will be "true" anyhow, so its pair from the guy's statement is "false". Also "false" are all edges, connected to both vertices of current one, and then you can mark their pairs as "true" ans so on... What residue graph after this procedure. Can it have vertices with deg>2? Logically it must be union of separeted edges(matched vertices) and disjoint circles. But My Ac prog says that in 9 test residue graph has vertice with deg>2. Edited by author 20.06.2009 09:17 I'm not sure how do you build that "residue graph", but the answer is most likely to be "no")) I would not mind helping you, but don't want to post ideas in forum. Edited by author 19.06.2009 13:37 What if there is no such edge? 5 5 4 5 5 1 5 4 1 5 4 4 3 4 1 5 5 2 5 4 4 5 1 3 4 3 3 5 5 1 5 5 I hope they can help~ o(∩_∩)o... Both of these tests are incorrect. My AC program fails on them. input: 6 1 2 4 2 3 5 3 1 6 1 5 4 5 6 5 6 4 6 output: 1 1 1 2 2 2 hope can help you. GOOD LUCK!!! I think tests for this problem are weak. For example, there is no tests like 1000 2 2 2 1 1 1 4 4 4 3 3 3 ... 1000 1000 1000 999 999 99 My program works slowly on this test (nearly 0.5sec) but it's fly like a wind on submission my 2-sat get Wa 11..I dont know why....Can someone give me hints?Thanks! accepted.. It's my stupid fault...And the following test helped me: 3 2 3 3 3 1 1 1 3 2 my answer is : 1 1 1 Hope it may help. Can I just search,or there're some other better ways? Potentialy very interesting but with too weak tests problem I got Ac very unexpected on halphway of solution. MY prog can't process test 4 1 2 1 2 1 2 3 4 3 4 3 4 with answer 1 1 1 1 This specific case most interesting case when there are K~100-250 unintersecting circles in given graph. We should build forest consist of such circles and process each tree from the root. Circles are bound throught whome each statement belong. All this situation is unreflected because weak tests. Edited by author 12.02.2007 22:08 Edited by author 12.02.2007 22:09 Edited by author 12.02.2007 22:09 Edited by author 12.02.2007 22:11 There is an easier greedy solution. Edited by author 21.08.2008 16:04 |
|
|