## 10804 - Gopher Strategy

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 10804 - Gopher Strategy

What does this statement mean?

Code: Select all

Every answer will obey the formula
fabs(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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole
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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

### Re: 10804 Gopher Strategy

.. wrote:What does this statement mean?

Code: Select all

Every answer will obey the formula
fabs(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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
//sigh
I find I made 2 typo in my code
It seems that I made a lagre piece of the WA/TLE submissions.......
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Why in the example N = 5 if there are only 4 cases?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Oops. That should be 4.
If only I had as much free time as I did in college...

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
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!

lordbogy
New poster
Posts: 1
Joined: Sat Mar 05, 2005 6:22 pm
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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Yes, it can, but it's not that complicated. You can use an easier algorithm than min cost max flow.
If only I had as much free time as I did in college...

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...