11167  Monkeys in the Emei Mountain
Moderator: Board moderators
11167  Monkeys in the Emei Mountain
I got this problem accepted using a maxflow approach. But that algorithm barely runs in time (6,5 seconds) and for that I had to use a pretty efficient maxflow 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.
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.
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

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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.
Ok, how about first running a greedy algorithm, and then using maxflow to improve its solution.krijger wrote:Ok, so I should rephrase my question. Anybody got CORRECT ideas to solve this faster? (instead of just ideas that get accepted).
That would be correct and run pretty fast on current judge's data, since apparently greedy already produces good enough solutions on it.
+1little joey wrote:If the input is really so weak that it can't withstand a greedy approach, it should be fixed IMO.
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 ?
Thanks in advance.
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
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")
Thnaks in advance.
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
How about the following fix to mf's greedy algorithm:
instead of choosing m.b as small as possible, first choose m.bm.v as small as possible, and if there are several possible choices, choose m.v as large as possible.
The intuition for the first criterion is that m.bm.v is a more accurate measure than m.b of how "urgent" m is. The intuition for the second criterion is that larger m.v gives more possibilities for m to get in the way of other monkeys.
I haven't been able to find a test case for which this fails, and I think (haven't thought through the details) that I can prove that it is optimal, but it gets WA, whereas changing the selection criterion to the one used by mf gets me AC (so my implementation appears to be correct). So, why does this fail?
instead of choosing m.b as small as possible, first choose m.bm.v as small as possible, and if there are several possible choices, choose m.v as large as possible.
The intuition for the first criterion is that m.bm.v is a more accurate measure than m.b of how "urgent" m is. The intuition for the second criterion is that larger m.v gives more possibilities for m to get in the way of other monkeys.
I haven't been able to find a test case for which this fails, and I think (haven't thought through the details) that I can prove that it is optimal, but it gets WA, whereas changing the selection criterion to the one used by mf gets me AC (so my implementation appears to be correct). So, why does this fail?