Show all threads Hide all threads Show all messages Hide all messages |
wa13 | 👑TIMOFEY👑 | 1580. Dean's Debts | 1 Jul 2023 11:36 | 1 |
wa13 👑TIMOFEY👑 1 Jul 2023 11:36 |
There can be no solution | Igor Parfenov | 1580. Dean's Debts | 1 May 2023 11:53 | 1 |
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. |
WA10 | markopetkovic359 | 1580. Dean's Debts | 8 Aug 2022 09:20 | 4 |
WA10 markopetkovic359 4 Apr 2010 08:23 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 Thanks. Was my bug as well (forgot that there can be more than one connected component). |
if you have wa 7 | Abid29 | 1580. Dean's Debts | 27 Apr 2021 21:36 | 1 |
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 |
Hint. | jk_qq | 1580. Dean's Debts | 1 Sep 2018 17:01 | 2 |
Hint. jk_qq 15 Oct 2017 01:25 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 |
This is a good test | 10100 | 1580. Dean's Debts | 21 Apr 2018 07:52 | 1 |
6 7 1 2 3 2 3 3 3 4 4 1 4 4 4 5 5 2 6 3 6 5 3 |
How about case M>N(+)? | SPIRiT | 1580. Dean's Debts | 20 Jan 2018 04:29 | 5 |
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:30 |
WA 25 | Mahathir Ahmad | 1580. Dean's Debts | 24 Mar 2016 16:38 | 1 |
WA 25 Mahathir Ahmad 24 Mar 2016 16:38 I am getting WA 25. Can anybody give me some test case? |
WA 4 | Catalin Cocis | 1580. Dean's Debts | 16 Nov 2014 22:55 | 4 |
WA 4 Catalin Cocis 3 Apr 2010 01:05 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 Re: WA 4 Nathan Wildenberg 16 Nov 2014 22:55 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 |
WA 6 | Faeton (Kyiv - Mohyla Academy) | 1580. Dean's Debts | 15 Nov 2013 12:16 | 4 |
WA 6 Faeton (Kyiv - Mohyla Academy) 21 Oct 2007 21:36 Re: WA 6 Faeton (Kyiv - Mohyla Academy) 21 Oct 2007 22:20 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 |
Meow) | Cat36 | 1580. Dean's Debts | 7 Jan 2012 12:38 | 2 |
Meow) Cat36 4 Dec 2008 07:59 |
WA 6, can't find the problem | predrag | 1580. Dean's Debts | 8 Jul 2011 17:25 | 3 |
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 |
No subject | Zayakin Andrey[PermSU] | 1580. Dean's Debts | 13 Aug 2010 03:35 | 1 |
No subject Zayakin Andrey[PermSU] 13 Aug 2010 03:35 4 4 1 2 0 2 3 0 3 4 0 4 1 0 Impossible |
WA8 | Dejan | 1580. Dean's Debts | 11 Apr 2010 05:37 | 3 |
WA8 Dejan 10 Apr 2010 02:13 Re: WA8 borisgrubic 10 Apr 2010 16:19 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. |
How faster? | MSDN | 1580. Dean's Debts | 3 Sep 2009 13:35 | 2 |
I solved it with gauss - 0.453 How faster? |
WA16 | VasilySlesarev | 1580. Dean's Debts | 8 May 2009 15:48 | 1 |
WA16 VasilySlesarev 8 May 2009 15:48 Give me some tests, please:) |
wa7 | Fyodor Menshikov | 1580. Dean's Debts | 23 Apr 2009 14:11 | 1 |
wa7 Fyodor Menshikov 23 Apr 2009 14:11 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. |
If you have WA 22 | nikonoff (ONPU) | 1580. Dean's Debts | 27 Dec 2008 15:11 | 1 |
try this test: 3 3 1 2 0 2 3 0 3 1 0 (generated by hedrok (ONPU)) |
This is test is correct?) | pperm | 1580. Dean's Debts | 19 Aug 2008 19:58 | 3 |
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... |
Why is the 2nd input sample's answer "Impossible" | SoSimple | 1580. Dean's Debts | 19 Aug 2008 19:55 | 3 |
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? ??? This output is not unique, that's the problem :) |