Page 2 of 2
Posted: Mon Aug 21, 2006 4:03 pm
by shanto86
well i got AC this morning. the idea given above is nothing but garbage.
actually i though that i only needed the maximum size, but later i noticed that i also need total as well...
if it was only maximum then that would come to play!
Posted: Fri Aug 25, 2006 12:44 pm
by sluga
Could someone write here the 6 intersection sets in the last example in the sample input? I only find 2 of them, no matter what I do ( I even searched for sets using O( 2^n ) algorithm ).
Those I find are:
0 3 4 7
1 2 5 6
( edit )
I realize my mistake now... I thought the first number was the number of maximal sets.
Posted: Wed Nov 08, 2006 9:15 pm
by rammestain
please give me hint for solving this problem
Posted: Sun Nov 12, 2006 3:18 pm
by satej
mf wrote:I guess the test cases in the input aren't too tough.
I've used backtracking with some pruning to generate every independent set, and it got just ~0.6 seconds.
The maximum answer can be 2^30. So a backtracking solution should not work for such limits.
Posted: Sun Nov 12, 2006 4:20 pm
by mf
sqtej wrote:The maximum answer can be 2^30.
So, can you please show a test case where the answer would be 2^30?
(Don't forget, that "the graph representing the city's network of roads [should] be connected.")