Page 1 of 2
10149 Yahtzee
Posted: Mon Oct 20, 2003 2:39 pm
by 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.
10149 - Yatzee
Posted: Wed Jan 21, 2004 12:53 am
by 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
10149 Yatzee
Posted: Mon Mar 08, 2004 5:04 pm
by titid_gede
any hints to solve this problem?
thanks.
-titid-
Posted: Mon Mar 08, 2004 7:51 pm
by 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..
Posted: Tue Mar 09, 2004 2:17 am
by 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?
Can you tell me some detail on how to search that fast?
Posted: Thu May 27, 2004 8:19 pm
by Alec
i am use the DP but not as fast as the search.......
Posted: Thu Nov 03, 2005 3:30 am
by 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?
Posted: Mon Jan 30, 2006 6:54 am
by 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?
10149 - Yahtzee
Posted: Sun Feb 19, 2006 11:35 pm
by abilendur
i keep getting the wrong answer,
can someone post some (tricy) test cases
is 11111 a full house?
i don't know
Posted: Tue Mar 14, 2006 4:19 pm
by sds1100
i don't know
i don't know
Posted: Tue Mar 14, 2006 4:19 pm
by sds1100
i don't know
Posted: Wed Oct 18, 2006 9:01 pm
by 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?!!!
Posted: Wed Oct 18, 2006 9:12 pm
by StanleY Yelnats
it's a full house!
Posted: Wed Oct 18, 2006 9:14 pm
by 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
10149 - Yahtzee HOWTO SOLVE
Posted: Wed Nov 21, 2007 11:34 am
by 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!!