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

Postby .. » Wed Jan 12, 2005 3:54 pm

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:
  • 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

Postby qndel » Wed Jan 12, 2005 6:33 pm

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

Postby .. » Wed Jan 12, 2005 7:18 pm

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

Postby Abednego » Wed Jan 12, 2005 8:24 pm

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.
User avatar
Abednego
A great helper
 
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Re: 10804 Gopher Strategy

Postby misof » Thu Jan 13, 2005 12:09 am

.. 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.
misof
A great helper
 
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: 10804 Gopher Strategy

Postby .. » Thu Jan 13, 2005 6:09 am

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

Postby Abednego » Thu Jan 13, 2005 6:39 am

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.
User avatar
Abednego
A great helper
 
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Postby .. » Thu Jan 13, 2005 7:14 am

//sigh
I find I made 2 typo in my code :oops:
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

Postby Krzysztof Duleba » Mon Feb 07, 2005 6:07 pm

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

Postby Abednego » Mon Feb 07, 2005 7:30 pm

Oops. That should be 4.
Let's hope Yury doesn't notice that I'm solving problems again.
User avatar
Abednego
A great helper
 
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Postby Destination Goa » Tue Feb 15, 2005 9:04 pm

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

Postby lordbogy » Mon Mar 14, 2005 10:29 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
lordbogy
New poster
 
Posts: 1
Joined: Sat Mar 05, 2005 6:22 pm

Postby Abednego » Mon Mar 14, 2005 11:55 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.
User avatar
Abednego
A great helper
 
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Postby Farid Ahmadov » Mon May 09, 2005 12:25 am

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

Postby Abednego » Mon May 09, 2005 9:23 am

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.
User avatar
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 1 guest