11167 - Monkeys in the Emei Mountain

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

11167 - Monkeys in the Emei Mountain

Post by krijger » 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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » 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

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » 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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Feb 18, 2007 7:18 pm

Yep.

But it was accepted. Weak tests, I suppose.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » 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). :)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Mon Feb 19, 2007 12:45 am

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » 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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » 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
Thanks in advance.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Mon Feb 19, 2007 3:56 pm

It is right.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Feb 19, 2007 4:32 pm

Thanks for your reply Hadi.

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » 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
Thnaks in advance.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Mon Feb 19, 2007 6:20 pm

"Yes"/"No"'s are the same with mine.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Feb 19, 2007 6:40 pm

Thank for your replay, Hadi.

I found my bug and got AC.
Note that there should be exactly one space between k and pairs (ai,bi), but no space within each pair.
I forgotted to separate pairs with spaces. It gaved me WA not PE.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Feb 20, 2007 1:21 am

How about the following fix to mf's greedy algorithm:
instead of choosing m.b as small as possible, first choose m.b-m.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.b-m.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?

Post Reply

Return to “Volume 111 (11100-11199)”