Search found 8 matches

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

11357 - Ensuring Truth

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

11302 - Hexadecimal Digits of an Integral

I think it's very funny, but the formula is rather complicated. Any hints?
by RoBa
Thu Aug 16, 2007 10:26 am
Forum: Volume 111 (11100-11199)
Topic: 11183 - Teen Girl Squad
Replies: 28
Views: 13003

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 ...
by RoBa
Sun Aug 05, 2007 7:46 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4408

Got it. Thanks very much! :)
by RoBa
Sun Aug 05, 2007 7:10 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4408

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...
by RoBa
Sun Aug 05, 2007 6:53 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4408

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 ...
by RoBa
Sat Aug 04, 2007 5:55 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4408

I think there needs something like Generating Function, but I don't know how. :(
by RoBa
Sun Dec 31, 2006 1:21 pm
Forum: Volume 111 (11100-11199)
Topic: 11149 - Power of Matrix
Replies: 42
Views: 19824

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.

Go to advanced search