888 - Donkey

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

Moderator: Board moderators

Post Reply
User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

888 - Donkey

Post by Christian Schuster » Mon Dec 12, 2005 12:18 am

Hello folks. This problem seemd quite simple to me: Some backtracking+memoization (or DP) should be sufficient. However, I got a bunch of WAs within times comparable to the AC solutions. My solution uses the tuple of distances to the capital as memoization key. As I don't think my calculations are prone to floating point errors, there must be something else.

Are there any tricky cases? The only "special" case I could imagine is M=0, for which the result is 1.000 if player 1 starts, or 0.000 otherwise.

Except the creators of the input file, only two people got it AC yet, which makes me doubt the correctness of the input file. Please resolve my doubts! ;)

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

Re: 888 - Donkey

Post by little joey » Mon Dec 12, 2005 2:25 pm

Christian Schuster wrote: Except the creators of the input file, only two people got it AC yet, which makes me doubt the correctness of the input file. Please resolve my doubts! ;)
The other two people are not the worlds worst problemsolvers, and not many people have tried this problem yet, which makes me doubt the correctness of your program.
If you want, you can PM me your code and I'll run it against the judges input to resolve both our doubts.

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

Post by little joey » Mon Dec 12, 2005 5:41 pm

To all other people having problems getting accepted: be sure to use the proper rounding. 0.0625 (1/16) and 0.9375 (15/16) should be rounded up to 0.063 and 0.938 respectively!

lpereira
New poster
Posts: 5
Joined: Wed Nov 16, 2005 7:35 pm
Location: Campinas - SP - Brazil
Contact:

Post by lpereira » Sat Jun 03, 2006 5:57 am

Please provide me some testcases.
I've tested all I can imagine and all I get is WA...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 888 - Donkey

Post by brianfry713 » Tue Apr 03, 2012 8:43 pm

Input:

Code: Select all

7
3 2 1 2 1
6 3 1 2 3 2
6 3 4 1 3 2
42 1 15 1
22 2 10 12 2
13 3 8 2 9 2
8 4 7 4 1 6 3
AC output:

Code: Select all

Game 1:the probability that player 1 wins = 0.667
Game 2:the probability that player 1 wins = 0.093
Game 3:the probability that player 1 wins = 0.366
Game 4:the probability that player 1 wins = 1.000
Game 5:the probability that player 1 wins = 0.224
Game 6:the probability that player 1 wins = 0.212
Game 7:the probability that player 1 wins = 0.222
Check input and AC output for thousands of problems on uDebug!

metaphysis
Experienced poster
Posts: 138
Joined: Wed May 18, 2011 3:04 pm

Re: 888 - Donkey

Post by metaphysis » Tue Mar 05, 2019 7:20 am

This problem should employ special judge.

Post Reply

Return to “Volume 8 (800-899)”