OJ Board

SAT is NPC, so... how to solve it? Is there something about randomization algorithm?

I think it's very funny, but the formula is rather complicated. Any hints?

I wonder the time complexity of the ACed algorithm. I got TLE with an O(V^3) implementation, and finally AC with an ugly O(VE).

And I agree with fh: If we are asked which edges from the original graph belong to the directed MST, it will be much harder. Could someone please show me an implementation ...

Got it. Thanks very much!

Use principle of inclusion-exclusion to answer queries.

er... Is it something like this :

If we call 4 kinds of coins A, B, C and D. Then for each query, we calcuate (the number of ways using A) + (the number of ways using B) + (the number of ways using C) + (the number of ways using D) - (the ...

A little hint: You should be able to answer each query in O(2^W) based on the result of a DP, where W is the number of coins, which is always 4 in this problem.

i.e. After running a DP, you should answer each query in almost constant time.

I still can't understand. Could you please explain in ...

I think there needs something like Generating Function, but I don't know how.

How to make it in 2 seconds?

My ACed program (C++) cost about 5 seconds, but the time limit is 2s during the contest...

mf wrote:

Ivan wrote:Is a solution with a complexity roughly n^3 * log(k) supposed to pass the time limit ?

Mine passed.