Code: Select all

```
2
note the space after the last word of the next line
second line
```

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

Try this:

Code: Select all

```
2
note the space after the last word of the next line
second line
```

- Tue Mar 06, 2007 3:10 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11187 - Water Crisis
- Replies:
**12** - Views:
**5265**

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

- Tue Feb 20, 2007 5:21 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11167 - Monkeys in the Emei Mountain
- Replies:
**30** - Views:
**15495**

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

- Tue Feb 20, 2007 4:19 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11168 - Airport
- Replies:
**19** - Views:
**9018**

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

- Tue Feb 20, 2007 11:03 am
- Forum: Volume 111 (11100-11199)
- Topic: 11170 - Cos(NA)
- Replies:
**22** - Views:
**13381**

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

- Tue Feb 20, 2007 1:26 am
- Forum: Volume 111 (11100-11199)
- Topic: 11167 - Monkeys in the Emei Mountain
- Replies:
**30** - Views:
**15495**

- Mon Feb 19, 2007 9:04 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11168 - Airport
- Replies:
**19** - Views:
**9018**

- Mon Feb 19, 2007 12:45 am
- Forum: Volume 111 (11100-11199)
- Topic: 11167 - Monkeys in the Emei Mountain
- Replies:
**30** - Views:
**15495**

- Sun Feb 18, 2007 8:06 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11167 - Monkeys in the Emei Mountain
- Replies:
**30** - Views:
**15495**

- Sun Feb 18, 2007 8:04 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11174 - Stand in a Line
- Replies:
**9** - Views:
**3664**

- Sun Feb 18, 2007 7:09 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11167 - Monkeys in the Emei Mountain
- Replies:
**30** - Views:
**15495**

- Sun Feb 18, 2007 6:47 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11167 - Monkeys in the Emei Mountain
- Replies:
**30** - Views:
**15495**

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

- Sun Feb 18, 2007 6:41 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11174 - Stand in a Line
- Replies:
**9** - Views:
**3664**

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

- Wed Jan 24, 2007 5:42 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11157 - Dynamic Frog
- Replies:
**22** - Views:
**14074**

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

- Sun Oct 15, 2006 4:16 pm
- Forum: Volume 111 (11100-11199)
- Topic: 11118 - Prisoners, Boxes and Pieces of Paper
- Replies:
**7** - Views:
**3242**

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