## Search found 8 matches

Sun Nov 25, 2007 5:27 pm
Forum: Volume 113 (11300-11399)
Topic: 11357 - Ensuring Truth
Replies: 12
Views: 4425

### 11357 - Ensuring Truth

SAT is NPC, so... how to solve it? Is there something about randomization algorithm?
Mon Oct 01, 2007 6:47 am
Forum: Volume 113 (11300-11399)
Topic: 11302 - Hexadecimal Digits of an Integral
Replies: 10
Views: 2839

### 11302 - Hexadecimal Digits of an Integral

I think it's very funny, but the formula is rather complicated. Any hints?
Thu Aug 16, 2007 10:26 am
Forum: Volume 111 (11100-11199)
Topic: 11183 - Teen Girl Squad
Replies: 28
Views: 13071
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 ...
Sun Aug 05, 2007 7:46 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4483
Got it. Thanks very much!
Sun Aug 05, 2007 7:10 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4483
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 numb...
Sun Aug 05, 2007 6:53 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4483
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 more ...
Sat Aug 04, 2007 5:55 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4483
I think there needs something like Generating Function, but I don't know how.
Sun Dec 31, 2006 1:21 pm
Forum: Volume 111 (11100-11199)
Topic: 11149 - Power of Matrix
Replies: 42
Views: 19995
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.