Page 1 of 3

11167 - Monkeys in the Emei Mountain

Posted: Sun Feb 18, 2007 6:47 pm
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 think of these kind of techniques, but I don't see how they can be used.

Posted: Sun Feb 18, 2007 7:01 pm
I've used a greedy algorithm:

Code: Select all

``````for t = 0 to 50000
for k = 1 to M
choose a monkey m, such that m.a<=t<m.b and m.v>0 and m.b is the smallest possible
if such a monkey exists,
assign m to time interval [t, t+1]
decrease m.v by 1
``````

Posted: Sun Feb 18, 2007 7:09 pm
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

Posted: Sun Feb 18, 2007 7:18 pm
Yep.

But it was accepted. Weak tests, I suppose.

Posted: Sun Feb 18, 2007 8:06 pm
Ok, so I should rephrase my question. Anybody got CORRECT ideas to solve this faster? (instead of just ideas that get accepted).

Posted: Mon Feb 19, 2007 12:12 am
I haven't solved it, so maybe it's a silly idea, but can't you use 'interval contraction', that is: instead of having 50000 exit flows each with capacity m, use the fact that there are only 100 monkeys which define max. 200 intervals. I'll try it tomorrow and report. If the input is really so weak that it can't withstand a greedy approach, it should be fixed IMO.

Posted: Mon Feb 19, 2007 12:45 am
I already used that interval-contraction idea (and no, it isn't silly, it's necessary)

Posted: Mon Feb 19, 2007 3:42 am
krijger wrote:Ok, so I should rephrase my question. Anybody got CORRECT ideas to solve this faster? (instead of just ideas that get accepted).
Ok, how about first running a greedy algorithm, and then using maxflow to improve its solution.
That would be correct and run pretty fast on current judge's data, since apparently greedy already produces good enough solutions on it.
little joey wrote:If the input is really so weak that it can't withstand a greedy approach, it should be fixed IMO.
+1

Posted: Mon Feb 19, 2007 2:51 pm
Getting dozens of WA..

I made a simple test generator and correcter, and tested my program.
Seems that no problem when it says "Yes".
So I think its ouputing "No" when it should be "Yes"..

Here are two test case that my programs says "No". Is it right ?

Code: Select all

``````24 2
10 58 79
10 5 32
3 12 31
6 30 47
10 9 48
8 23 38
2 40 54
9 28 39
8 48 58
2 44 63
4 18 33
9 3 29
5 28 62
1 41 69
2 36 42
4 23 54
3 41 47
4 47 82
8 23 46
6 62 96
3 20 37
10 20 47
9 38 60
8 8 38
24 2
8 43 68
9 27 41
10 11 36
9 15 53
1 61 63
9 58 74
9 15 31
7 50 85
1 36 60
7 56 84
6 34 41
6 20 54
9 5 21
3 63 88
6 45 70
3 41 57
7 27 62
8 52 74
2 48 68
10 52 73
3 15 31
8 28 37
8 15 29
7 49 61
0
``````

Posted: Mon Feb 19, 2007 3:56 pm
It is right.

Posted: Mon Feb 19, 2007 4:32 pm

Hmm, so I'm stucked now. I'll retry this problem latter.

Posted: Mon Feb 19, 2007 6:08 pm
Still not giving up. Could someone verify my i/o test ?

Its little too large to paste, so I uploaded.
Input:
http://lilii.hp.infoseek.co.jp/in
Output:
http://lilii.hp.infoseek.co.jp/out
Output:(only the "Yes", "No")

Code: Select all

``````Case 1: Yes
Case 2: Yes
Case 3: No
Case 4: Yes
Case 5: No
Case 6: No
Case 7: No
Case 8: No
Case 9: No
Case 10: Yes
``````

Posted: Mon Feb 19, 2007 6:20 pm
"Yes"/"No"'s are the same with mine.

Posted: Mon Feb 19, 2007 6:40 pm