|
|
Show all threads Hide all threads Show all messages Hide all messages | very easy | Maryin Dima | 1485. Football and Lie | 9 Jun 2016 23:53 | 7 | It was very easy. Backtracking(перебор с возвратом) I think that it is hard problem and has exp(n) complexity. If remove psevdopractic decoration it is to solve a system boolean equation of 100 unknows Xi with type of Xi^Xj=0; (NotXi)^Xj=0;(NotXi)^(NotXj)=0. Amount of equation is near 10000. Thus we have easy problem for weak tests and very hard problem for detailed test. This situation was brightly shoun for identical Ships problems.Programmers should create code working on all possible tests in prescribed range of variables. Now I am also having Ac(0.031) by using backtracking. I have applied this method to boolean problem not to Graf. But I fear that we all will lost our submits if problem will be rejudged. In worst case in complexy is O(n^2) Yes, it's O(N^2). And resembles another problem of this type: 1382 does transitive closure algorithm work here? Just a standard 2-SAT problem. | Can anyone give me some test ? Please , help me !! | yzxshuaige123 | 1485. Football and Lie | 4 Dec 2012 12:13 | 1 | | Why "Impossible" in the second case? | Burunduk1 | 1485. Football and Lie | 22 Aug 2008 14:18 | 2 | Why this answer is not correct? 0 3 1 0 0 0 0 3 1 1 1 0 0 1 1 3 1 1 0 0 3 1 1 0 0 Teams 4 and 5 played 0-0. Outcome for ANY pair of teams must be 0-3, 3-0 or 1-1 Edited by author 22.08.2008 14:21 | Help please | Nebojsa | 1485. Football and Lie | 22 Aug 2008 14:16 | 4 | Can somebody explain me this test input -1 1 0 1 -1 -1 0 1 -1 output 0 0 1 3 0 3 1 0 0 If some captain tells the truth, then for each cell of his row: A[i,j]==-1 || A[i,j] == (bool)B[i][j] If some captain lies, then for each cell of his row: A[i,j]==-1 || A[i][j] != (bool)B[i][j] Matrix B must be such that every pair B[i][j], B[j][i] is one of three forms: 1,1 0,3 3,0 (bool)x = 0 if x=0, and 1 otherwise So, for that test: 1st and 3rd captains lie. The 2nd tells the truth. This is not necessarily the only possible distribution of truths and lies. | I have WA 30. | AndreySUrSU | 1485. Football and Lie | 27 May 2008 03:21 | 4 | Nice. And I have WA 28 =) When i have WA on 30 test, in my solution there was much errors... Many incorrect solutions got WA on 2? - 3? tests. :) i also have WA30:( any help? what was the problem? | AC) | AlexF [USTU Frogs] | 1485. Football and Lie | 15 Nov 2007 11:15 | 1 | AC) AlexF [USTU Frogs] 15 Nov 2007 11:15 Very good problem)) Thanks to author!)) | WA10? | Ostap Korkuna (LNU) | 1485. Football and Lie | 8 Oct 2006 16:28 | 1 | WA10? Ostap Korkuna (LNU) 8 Oct 2006 16:28 What is the trick about that test? |
|
|
|