|
|
For me from statement was clear, that there are always solutions, either one or multiple. But in test 5 there is no solution. You have to print IMPOSSIBLE in this case. Does anybody have an idea ? Edited by author 04.04.2010 08:24 6 6 1 2 1 2 3 2 3 1 3 4 5 1 5 6 2 6 4 3 1.00 0.00 2.00 1.00 0.00 2.00 Thanks. Was my bug as well (forgot that there can be more than one connected component). TRY THIS ONE 6 7 1 2 3 2 3 4 3 4 3 1 3 4 4 5 33 5 6 3 4 6 -2 IMPOSSIBLE Edited by author 27.04.2021 21:36 Edited by author 27.04.2021 21:37 Every connected component have to contain cycle of odd length (prove it). Find such a cycle and solve. Proof that a system of linear equation has a unique solution if the corresponding cycle is of an odd length. system of LE x1 + x2 = y1 x2 + x3 = y2 ... x_{n-1} + x_n = y_{n - 1} x1 + x_n = y_n Is written in matrix form (i'll skip the last column) 1 1 0 ... 0 0 1 1 0 ... 0 0 0 1 1 0 ... 0 . . . 0 ... 0 1 1 1 0 ... 0 1 It's determinant can be computed as follows det( 1 1 .. 0 0 1 1 .. 0 . 0 0 .0 1 1 0 ... 0 1 ) +-(!!!) det ( 1 0 .. 0 1 1 0 .. 0 . . 1 0 0 ... 0 1 1 ) I took entries (1, 1) and (n, 1) to form these two. The sign (+-) depends on dimention and is equal to (-1)^(n + 1). The two determinans are equal as the first one is equal to 1 1 0 1 which can be seen if you keep choosing entry (n, n) to form determinant and the second one is equal to 1 0 1 1 keep choosing (1, 1) So, the determinant of initial matrix is equal to 2 if the number of variables odd which means the system has a unique solution. The system can't have one in the case of zero determinant which is when the number of variables is even. Edited by author 01.09.2018 17:02 6 7 1 2 3 2 3 3 3 4 4 1 4 4 4 5 5 2 6 3 6 5 3 I think it's clear for the system of linear equations, that if M<N, than it's impossible. If M=N then it may be possible (and I know how to check). How about case M>N? We need to select N pairs that get an unambiguous solution? You have to keep only the lineary independet ones, I think. What I did is I kept only the first 5 ones, which contain certain number (so the matrix in the end was at most 5000 rows long, containing at least 5 rows, containing a digit at each position) and it passed system test (otherwise the solution was right, but too slow) Just find at least one odd loop in each connected component Just find at least one odd loop in each connected component hmm i make this but i get TLE( test 12)... (with a BFS) any ideea why? What I did is I kept only the first 5 ones, which contain certain number Strange. It will not work for this test (A_i can be arbitrary). 43 43 2 3 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 2 8 0 2 9 0 2 10 0 2 11 0 2 12 0 2 13 0 3 14 0 3 15 0 3 16 0 3 17 0 3 18 0 3 19 0 4 20 0 4 21 0 4 22 0 4 23 0 4 24 0 4 25 0 5 26 0 5 27 0 5 28 0 5 29 0 5 30 0 5 31 0 6 32 0 6 33 0 6 34 0 6 35 0 6 36 0 6 37 0 7 38 0 7 39 0 7 40 0 7 41 0 7 42 0 7 43 0 Edited by author 20.01.2018 04:30I am getting WA 25. Can anybody give me some test case? What is wrong with test 4? 5 6 5 4 9 4 2 6 5 1 6 1 2 3 5 3 8 3 2 5 IMPOSSIBLE 0.00 3.00 2.00 3.00 6.00 Isn't this the correct answer? :? Nevermind, it is actually undeterminable. Edited by author 16.11.2014 22:56 Edited by author 16.11.2014 23:08 Give plz some tests Edited by author 21.10.2007 22:20 Edited by author 21.10.2007 22:20 8 8 3 4 2 4 5 4 5 3 6 1 2 1 2 3 1 5 6 1 6 7 1 7 8 1 2.00 -1.00 2.00 0.00 4.00 -3.00 4.00 -3.00 I get a Wrong answer on test case 6 on this problem. Would it be possible (and legal, of course) for me to see the test case and/or a similar case that demonstrates why my solution is incorrect so I can test it locally? I need a hint ( or test case ) aswell. I was looking for an TLE error but instead I got WA. This test helped me to resolve WA6: 4 4 1 2 2 2 3 2 3 4 2 4 2 2 Answer is: 1.00 1.00 1.00 1.00 4 4 1 2 0 2 3 0 3 4 0 4 1 0 Impossible What is test case 8 ? Try this test: 4 4 1 2 2 1 3 2 3 4 2 1 4 2 Answer: 1.00 1.00 1.00 1.00 Edited by author 10.04.2010 16:20 Edited by author 10.04.2010 16:20 Thanks for the help, Boris, but I'm still getting WA8, eventhough it gives me correct result for this test case. I solved it with gauss - 0.453 How faster? Give me some tests, please:) In the 7th test students lie or make mistake. For example 4 4 1 2 0 2 3 0 3 4 0 4 1 1 Expected answer is IMPOSSIBLE. try this test: 3 3 1 2 0 2 3 0 3 1 0 (generated by hedrok (ONPU)) 5 6 1 2 0 2 3 0 3 4 0 4 5 0 5 1 0 1 3 1 Test isn't correct? Or I must output IMPOSSIBLE?) Edited by author 13.10.2007 15:32 My AC program, output IMPOSSIBLE. It's not hard to check unique solution for being a solution... input 4 3 1 2 2 1 3 4 1 4 6 output 1.00 1.00 3.00 5.00 What is wrong with this output? ??? M<N - It's IMPOSSIBLE! This output is not unique, that's the problem :) |
|
|