OJ Board

Try this:

I used the following DP-approach: The problem basically comes down to splitting a set of objects into three sets (the three trucks) in such a way that the maximum of the weights of the numbers a set is minimal. This can be solved using a three dimensional dp, where dp [j][k] denotes if it is possibl...

I also use Ford-Fulkerson (with dijkstra / priority_queue to find the maximal augmenting path), but I did apply max-flow for all intervals (so not only for the intervals containing more than m monkeys). But even after implementing this optimalization, it still runs for 6.322 secs. Can you send me yo...

My AC program gives the following:

I used cos(a+b)=cos(a)*cos(b)-sin(a)*sin(b) to write cos(NA) in terms of cos((N-1)A), cos(A), sin((N-1)A) and sin(A). Then I expanded the sin((N-1)A) using sin(a+b)=sin(a)*cos(b)+cos(A)+sin(b) into terms of sin((N-2)A), sin(A), cos((N-2)A) and cos(A). Then there appears a term sin^2(A)*X which can b...

Almost same challenge case:

5 2
1 0 1
2 2 4
2 2 4
1 0 2
2 0 4
0

I don't want to give everything away, but you need to calculate the average distance to a line in O(1) time. Try to think of a way yourself.

I already used that interval-contraction idea (and no, it isn't silly, it's necessary)

Ok, so I should rephrase my question. Anybody got CORRECT ideas to solve this faster? (instead of just ideas that get accepted).

Ah, I should've noticed that it was a prime. It would've been a lot easier I used the 'looping over all primes'-thing I described above.

If I understand you correctly, it wont find an answer for this case:

5 2
1 0 1
1 2 3
1 2 3
1 0 2
2 0 3
0

I got this problem accepted using a max-flow approach. But that algorithm barely runs in time (6,5 seconds) and for that I had to use a pretty efficient max-flow algorithm. So I wonder if someone used another approach. Maybe some kind of dp or greedy, or backtracking with pruning, etc. I tried to th...

During the contest, I missed that nice observation at which Erik hinted above, but I got accepted by implementing the choose function nicely. You can do this as follows: * Calculate all primes. * Make a function f(n,p) that calculates how many times a prime p will appear in n! * To get choose(n,x_1,...

Am I the only one here who used DP (complexity O(n^3)) ? I find the problem very similar to the 'round-trip trough canada'-problem, for those who know what I mean. Basically the idea is as follows. A solution is a set of two paths from one side to the other that have no small rocks in common. We're ...

Thanks for the hint misof. And what a surprising result! (the limit for n to infinity is nonzero) Really a fun puzzle. By the way, does anybody has a proof that there is no better strategy? For those still struggling with the problem: work out the case for n=4 by hand. Let the second box the first p...