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

[qndel]

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

[..]

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?

[Abednego]

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.

[misof]

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.

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.

[..]

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.

[Abednego]

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.

[..]

//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.

[Krzysztof Duleba]

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

[Abednego]

Oops. That should be 4.

[Destination Goa]

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.

[lordbogy]

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]

Yes, it can, but it's not that complicated. You can use an easier algorithm than min cost max flow.

[Farid Ahmadov]

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!

[Abednego]

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.