## 10804 - Gopher Strategy

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

Moderator: Board moderators

### 10804 - Gopher Strategy

What does this statement mean?
Code: Select all
Every answer will obey the formulafabs(ans*1e3 - floor(ans*1e3) - 0.5) > 1e-2

If "ans" means the value rounded to 3 decimals, then the formula can't be obeyed as "ans" is already rounded, ans*1e3 is an integer......

Anyway, is there any tricky input except the some input value = 0?
I think I have handles these cases correctly, but still WA
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Don't worry about that, i don't know for what is it but if you write it in normal way, wou will get AC
NOthing special
qndel
New poster

Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

So strange, I think I am familiar with such max. flow problem. My template code should be ok. The only possible source of error is the modelling.....

If 2 gophers/holes have the same coordinate, we should count them distinct, right?
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

There is no special correction program, so the formula is used to get rid of test cases that may cause rounding errors.

If 2 gophers/holes have the same coordinates, they should be considered distinct.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

### Re: 10804 Gopher Strategy

.. wrote:What does this statement mean?
Code: Select all
Every answer will obey the formulafabs(ans*1e3 - floor(ans*1e3) - 0.5) > 1e-2

If "ans" means the value rounded to 3 decimals, then the formula can't be obeyed as "ans" is already rounded, ans*1e3 is an integer......

Here ans means the exact answer. The formula says the following:
Let ans = a_0.a_1a_2a_3a_4... (a_0 is an int, a_i are digits for i>0).
Take ans, multiply by 1000, let this be x.
Take floor(x), subtract it from x.
You are left with the fractional part of x. In our case it is the number 0.a_4a_5a_6...

We are guaranteed that this number differs from 0.5 by a substantial margin, i.e. when three digits after the decimal point are output there should be no rounding errors due to precision.

.. wrote:Anyway, is there any tricky input except the some input value = 0?
I think I have handles these cases correctly, but still WA

Care to explain your algorithm instead? I've got AC, but I'm unaware of any too special cases.
misof
A great helper

Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

### Re: 10804 Gopher Strategy

misof wrote:Care to explain your algorithm instead? I've got AC, but I'm unaware of any too special cases.

Tha algorithm is the normal thing: Max. flow + bisection.
Sort the all pair distance(so as time as hopher runs in unit per second) between gopher and hole.
Then use bisection to find the min. time T, such that,
if we build a bipartite graph G between gopher g and hole h, dis(g,h) <= T iff (g,h) \in G. Then G has a bipartite matching of at least m-k.
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

The only difference in the judge's solution is that it does binary search (or bisection) directly on the distance instead of the array of possible distances. I know somebody who solved it with your algorithm and got the same answer as I did.

I'm reluctant to say that your code has a bug because you have solved twice as many problems as me. If you want, send your code to me (abednego at gmail), and I will run it on the official data. If you have a bug, I will not give you any hints, but if there is something wrong with the problem, it will help me find out.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

//sigh
I find I made 2 typo in my code
It seems that I made a lagre piece of the WA/TLE submissions.......
Thanks for all of your reply.
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Why in the example N = 5 if there are only 4 cases?

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

Oops. That should be 4.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Actually there is a special case of k=m. I got several WA due to that because I would output minimal distance instead of zero. I think this is not very obvious because Min(<empty set>) is undefined. Would it be some other physical value (not time), zero wouldn't be such logical miniumum for value of <whatever>. Zero is logical here, but it's not mathematical.
To be the best you must become the best!
Destination Goa
Experienced poster

Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

I'm not quite familiar with max flow but I was wondering if this problem can be solved by finding a minimum cost maximum flow on the same graph used as a network and solved with bin search.

Thank you
lordbogy
New poster

Posts: 1
Joined: Sat Mar 05, 2005 6:22 pm

Yes, it can, but it's not that complicated. You can use an easier algorithm than min cost max flow.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

I need some I/O... my program gets WA...
I used this algo:
It finds possible distances and sorts them, doing binary search on sorted array of distances it every time makes new graph G where g[i,j]=1 if distance between gopher i and hole j is less than current selected distance on binary search array. Then it runs max.match(Ford-Falkerson, max.flow) algo on this graph G and finds if current flow>=m-k... at last it finds minimum such distance where flow>=m-k or find that it is not possible...

Maybe this algo is a little bit slow, but it should work I think. I need some tricky I/O than could help me find the bug in my program...

Any help is appreciated!
_____________
NO sigNature
Farid Ahmadov
Experienced poster

Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

My algorithm is almost the same as yours, but I don't understand what you mean by this:
Code: Select all
 at last it finds minimum such distance where flow>=m-k or find that it is not possible...

I think your binary search should do this automatically. Actually, instead of making an array of distances, what I did was a binary search directly on the distance itself, until the error in the distance is smaller than 1e-7.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Next

Return to Volume CVIII

### Who is online

Users browsing this forum: No registered users and 0 guests