It's a great problem. I enjoyed solving it! DP on subsets + match in bigraph - was not hard to implement at all. Just nice step-by-step implementation! And what a great time! Only 0.031 !

It's really great!)

Edited by author 30.06.2007 21:15

What is your complexity?
Does your solution use (2^n) * (2^n) memory?

Edited by author 10.07.2007 13:39

The complexity of my solution is approximately O((2^N)*(2^N)*N*N).
More exactly it is O(Mk*N*N), where Mk = C(N,N-1)+C(N,N-2)*2^2+C(N,N-3)*2^3+...+C(N,2)*2^(N-2)+C(N,1)*2^(N-1)
where C(N,M) - is the number of combinations :)

I use as much as O((2^N)*(2^N)) memory.

Good luck!

Thank you for answer.

I have tried to find algo with O( 2^n ) memory, but it seems, that there does not exist such "non factorial" algorithm :(

So I have implemented O( (2^n)*(2^n)*n*n ) algorithm that uses O((2^n)*(2^n)) memory (asymptotic is correct).
This algorithm does not use bipartite matching algo at all.
AC in (0.015 :: 1 287 KB).

UPD:
Also I realized O((3^n)*n) algo with O((3^n)*n) memory which  has taken AC in (0.031 :: 8 439 KB), but I was aware of low level optimization

Edited by author 17.07.2007 15:58

It's easy to implement O(2^N) memory algo - just DP on subset of pupils that know those news, each bit 1 can spawn at most one more bit 1 if there is an edge, the set of transitions can be calculated at O(2^N * N^2) overall time (state with 2^P ones leads to at most 2^(N-P) ones and these transitions can be calculated by BFS - number_of_src_bit1 X number_of_dst_bit1)

P.S: AC in 0.015 sec / 305Kb, 1st effort :)

Edited by author 12.08.2008 02:14

There is 3^n * n^3 algo. For every mask check its sub masks (total 3^n checks). Every check - finding bipartite matching in graph. But a do it easy: for every 2^n masks generate all masks what we can achieve with recursive function.