## 10149 - Yahtzee

Moderator: Board moderators

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

### 10149 Yahtzee

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

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

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:
I did Simulated Annealing to get AC..
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
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?

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

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

i don't know

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

### i don't know

i don't know

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 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
it's a full house!

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 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

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!!