Обсуждение @ 1485. Лживый футбол @ Timus Online Judge

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.

Обсуждение задачи 1485. Лживый футбол