| ENG RUS | Timus Online Judge |
Обсуждение задачи 1485. Лживый футболMaryin Dima very easy [6] // Задача 1485. Лживый футбол 11 окт 2006 20:55 It was very easy. Backtracking(перебор с возвратом) svr Re: very easy [5] // Задача 1485. Лживый футбол 15 окт 2006 13:03 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. svr Re: very easy [4] // Задача 1485. Лживый футбол 16 окт 2006 22:59 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. Orenburg SU 7 Re: very easy [3] // Задача 1485. Лживый футбол 16 окт 2006 23:23 In worst case in complexy is O(n^2) Denis Koshman Re: very easy [2] // Задача 1485. Лживый футбол 22 авг 2008 14:25 Yes, it's O(N^2). And resembles another problem of this type: 1382 Stefan Re: very easy [1] // Задача 1485. Лживый футбол 26 май 2009 15:04 does transitive closure algorithm work here? bsu.mmf.team Re: very easy // Задача 1485. Лживый футбол 9 июн 2016 23:53 Just a standard 2-SAT problem. yzxshuaige123 Can anyone give me some test ? Please , help me !! // Задача 1485. Лживый футбол 4 дек 2012 12:13 Burunduk1 Why "Impossible" in the second case? [1] // Задача 1485. Лживый футбол 7 янв 2007 22:32 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 Denis Koshman Re: Why "Impossible" in the second case? // Задача 1485. Лживый футбол 22 авг 2008 14:18 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 Nebojsa Help please [3] // Задача 1485. Лживый футбол 4 май 2008 20:30 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 Nebojsa Re: Help please [2] // Задача 1485. Лживый футбол 5 май 2008 04:25 Any body???? Denis Koshman Re: Help please [1] // Задача 1485. Лживый футбол 22 авг 2008 14:15 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 Denis Koshman Re: Help please // Задача 1485. Лживый футбол 22 авг 2008 14:16 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. AndreySUrSU I have WA 30. [3] // Задача 1485. Лживый футбол 10 окт 2006 15:01 What test? Nechaev Ilya (Rybinsk SAAT) Re: I have WA 30. [2] // Задача 1485. Лживый футбол 10 окт 2006 18:28 Nice. And I have WA 28 =) AndreySUrSU Re: I have WA 30. [1] // Задача 1485. Лживый футбол 10 окт 2006 23:52 When i have WA on 30 test, in my solution there was much errors... Many incorrect solutions got WA on 2? - 3? tests. :) Aleksandar Tomic Re: I have WA 30.-same here // Задача 1485. Лживый футбол 27 май 2008 03:21 i also have WA30:( any help? what was the problem? AlexF [USTU Frogs] AC) // Задача 1485. Лживый футбол 15 ноя 2007 11:15 Very good problem)) Thanks to author!)) Ostap Korkuna (LNU) WA10? // Задача 1485. Лживый футбол 8 окт 2006 16:28 What is the trick about that test?
|