10149 - Yahtzee

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

Moderator: Board moderators

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

10149 Yahtzee

Post by BiK » Mon Oct 20, 2003 2:39 pm

Hallo,

We've been trying to solve these problem for some time but the solution seems to elude us. We want to avoid all possible mappings of rounds to categories. Do you have any idea how to do this? Please answer. Any help will be appreciated.

edx
New poster
Posts: 1
Joined: Wed Jan 21, 2004 12:47 am

10149 - Yatzee

Post by edx » Wed Jan 21, 2004 12:53 am

Hi,
I've been coding on this problem for two days now and I am totally stuck. I rewrote my program to ensure that there are no typos in there, but it didn't help: I keep getting wrong answer after 0.281 seconds. I tested my program with lots of test data I generated myself, but as usual I certainly have forgotten the "hard" cases.
Can anyone either supply difficult cases or give me a hint where difficulties could occur with the output?
I can post my code here, if necessary, but I didn't want to steal anyone's time reading it ;)

Thanks heaps and best regards,
Felix Arends

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10149 Yatzee

Post by titid_gede » Mon Mar 08, 2004 5:04 pm

any hints to solve this problem?
thanks.
-titid-
Kalo mau kaya, buat apa sekolah?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Mon Mar 08, 2004 7:51 pm

I did Simulated Annealing to get AC.. :lol:
Assigning categories from the first round, we only have 2^13 possibilities, that each category is used/or not.

So a dynamic programming algorithm seems to be feasible..
JongMan @ Yonsei

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Mar 09, 2004 2:17 am

I used brute force with memoization and managed top 25 .. so that should be fast enough..

in general, brute force with memoization can be converted to dp quite easily.. but recursion may be an easier way to represent the problem.

Anyway, the recurrence was, given a certain slot, and a certain number of rolls left, what is the best score I can get?

Alec
New poster
Posts: 8
Joined: Sun Mar 28, 2004 9:00 pm

Can you tell me some detail on how to search that fast?

Post by Alec » Thu May 27, 2004 8:19 pm

i am use the DP but not as fast as the search.......

bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

Post by bluebird » Thu Nov 03, 2005 3:30 am

junbin, I seriously doubt a brute force approach would even bring you within the 10s time limit. I find it hard to believe that memoization would get you top 25.

Perhaps you would care to explain your approach?

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Post by Leonid » Mon Jan 30, 2006 6:54 am

Each round may be scored in a category of the player's choosing.
Does it mean that each round may be scored in at most one category?

abilendur
New poster
Posts: 5
Joined: Wed Feb 15, 2006 7:10 pm
Location: Estonia

10149 - Yahtzee

Post by abilendur » Sun Feb 19, 2006 11:35 pm

i keep getting the wrong answer,
can someone post some (tricy) test cases

is 11111 a full house?

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

i don't know

Post by sds1100 » Tue Mar 14, 2006 4:19 pm

i don't know

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

i don't know

Post by sds1100 » Tue Mar 14, 2006 4:19 pm

i don't know

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by StanleY Yelnats » Wed Oct 18, 2006 9:01 pm

I used hill climbing with random restart

but i had to test the maximum up to 30 times to ensure correct result

p.s what's "randomize()" equivalence in gcc?!!!

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by StanleY Yelnats » Wed Oct 18, 2006 9:12 pm

it's a full house!

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by StanleY Yelnats » Wed Oct 18, 2006 9:14 pm

here's a few io :

Code: Select all

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 1 1 1 1
6 6 6 6 6
6 6 6 1 1
1 1 1 2 2
1 1 1 2 3
1 2 3 4 5
1 2 3 4 6
6 1 2 6 6
1 4 5 5 5
5 5 5 5 6
4 4 4 5 6
3 1 3 6 3
2 2 2 4 6
4 4 4 4 4
2 2 3 6 6
4 3 2 1 5
1 1 3 3 1
5 2 2 5 4
5 1 2 2 6
4 3 1 2 6
5 1 6 5 4
3 3 6 4 1
2 4 2 4 6
2 2 1 1 4
3 3 4 4 4
1 5 4 1 4
2 3 4 1 6
5 1 6 2 4
6 3 1 1 4
5 6 5 3 5
6 5 1 1 6
3 1 5 4 6
2 5 6 4 3
5 2 3 2 4
6 2 6 5 6
4 1 6 6 3
2 4 6 2 4
3 2 3 1 6
6 1 4 5 4
5 2 3 1 3
6 5 2 4 3
2 1 1 1 4
3 6 5 6 1
1 3 1 3 3
6 2 1 1 4
2 5 5 5 4
6 4 2 1 1
4 2 5 4 6
1 4 5 5 4
4 5 6 4 5
6 1 4 5 1
2 6 4 4 4
1 3 2 2 2
6 3 1 3 4
1 1 5 3 5
6 4 2 5 1
4 3 5 2 1
4 1 6 1 4
2 5 5 1 4
6 6 4 6 6
5 4 6 3 1
3 3 4 4 5
3 5 5 5 6
5 2 6 3 6
2 4 4 6 4

Code: Select all

1 2 3 4 5 0 15 0 0 0 25 35 0 0 90
3 6 9 12 15 30 21 20 26 50 25 35 40 35 327
2 4 6 8 10 12 21 18 0 50 25 35 40 0 231
2 4 6 8 15 12 20 25 0 0 25 35 0 0 152
3 2 6 12 10 12 24 21 0 0 0 35 40 0 165
2 6 6 12 15 24 22 0 0 0 25 35 0 35 182

evandrix
New poster
Posts: 8
Joined: Wed Oct 03, 2007 11:07 am

10149 - Yahtzee HOWTO SOLVE

Post by evandrix » Wed Nov 21, 2007 11:34 am

Hi to all,

I code in JAVA and I am stuck at devising an efficient strategy to solve this problem.i can't seem to get anywhere close to the maximum score, even for the test cases specified in the question.

gathering the input from above, there are mentions of simulated annealing, hill climbing with random restart, dp, brute force algorithms to solve this problem, though i'm not sure how this can be implemented in JAVA.

I have managed to sort the rolls and scores for each category for each line in ascending order and eliminate any categories that only have 1/0 nonzero entry (1-only 1 way to assign, so assign it, no choice, 0-no line of dice can be scored for this category).

Also i have set up arrays used, assigned for checking if the line/category has been already used/assigned respectively so as to generate valid cominations for calculation of scores.

I have also prioritised my assigned of scores to categories in descending order ie. yahtzee-50pts, full house-40pts, long straight-35pts, short straight-25pts, then chance, then 6,5,4,3,2,1...

I tried to random through few tens of thousand times out of the 13! possibilities but this only resulted in TLE. not sure how else i can arrive at the best score without any guesswork.

BTW i have read elsewhere in this forum that the PC online judge is broken. Is this true? because i logged into my PC account and it shows that people have ACTUALLY submitted SOLVED solutions.

thanks for any help...esp Darko/Jan for their help...really need help...have been trying for the past 2-3 days!!

Post Reply

Return to “Volume 101 (10100-10199)”