Search found 39 matches

by krijger
Sun Jun 10, 2007 1:06 pm
Forum: Volume 112 (11200-11299)
Topic: 11220 - Decoding the message.
Replies: 54
Views: 20017

Try this:

Code: Select all

2

note the space after the last word of the next line
second line 
by krijger
Tue Mar 06, 2007 3:10 pm
Forum: Volume 111 (11100-11199)
Topic: 11187 - Water Crisis
Replies: 12
Views: 5095

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...
by krijger
Tue Feb 20, 2007 5:21 pm
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900

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...
by krijger
Tue Feb 20, 2007 4:19 pm
Forum: Volume 111 (11100-11199)
Topic: 11168 - Airport
Replies: 19
Views: 8866

My AC program gives the following:

Code: Select all

Case #1: 78903.722
Case #2: 77266.451
Case #3: 78024.986
Case #4: 77425.874
Case #5: 77151.380
Case #6: 77910.437
by krijger
Tue Feb 20, 2007 11:03 am
Forum: Volume 111 (11100-11199)
Topic: 11170 - Cos(NA)
Replies: 22
Views: 13067

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...
by krijger
Tue Feb 20, 2007 1:26 am
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900

Almost same challenge case:
5 2
1 0 1
2 2 4
2 2 4
1 0 2
2 0 4
0
by krijger
Mon Feb 19, 2007 9:04 pm
Forum: Volume 111 (11100-11199)
Topic: 11168 - Airport
Replies: 19
Views: 8866

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.
by krijger
Mon Feb 19, 2007 12:45 am
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900

I already used that interval-contraction idea (and no, it isn't silly, it's necessary) :)
by krijger
Sun Feb 18, 2007 8:06 pm
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900

Ok, so I should rephrase my question. Anybody got CORRECT ideas to solve this faster? (instead of just ideas that get accepted). :)
by krijger
Sun Feb 18, 2007 8:04 pm
Forum: Volume 111 (11100-11199)
Topic: 11174 - Stand in a Line
Replies: 9
Views: 3570

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.
by krijger
Sun Feb 18, 2007 7:09 pm
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900

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
by krijger
Sun Feb 18, 2007 6:47 pm
Forum: Volume 111 (11100-11199)
Topic: 11167 - Monkeys in the Emei Mountain
Replies: 30
Views: 14900

11167 - Monkeys in the Emei Mountain

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...
by krijger
Sun Feb 18, 2007 6:41 pm
Forum: Volume 111 (11100-11199)
Topic: 11174 - Stand in a Line
Replies: 9
Views: 3570

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,...
by krijger
Wed Jan 24, 2007 5:42 pm
Forum: Volume 111 (11100-11199)
Topic: 11157 - Dynamic Frog
Replies: 22
Views: 13735

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 ...
by krijger
Sun Oct 15, 2006 4:16 pm
Forum: Volume 111 (11100-11199)
Topic: 11118 - Prisoners, Boxes and Pieces of Paper
Replies: 7
Views: 3178

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...

Go to advanced search