10149 - Yahtzee

[BiK]

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]

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]

any hints to solve this problem?
thanks.
-titid-

[Whinii F.]

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

[junbin]

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]

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

[bluebird]

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]

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]

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

is 11111 a full house?

[sds1100]

i don't know

[sds1100]

i don't know

[StanleY Yelnats]

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]

it's a full house!

[StanleY Yelnats]

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]

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