10149 - Yahtzee
Moderator: Board moderators
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.
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
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
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
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
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?
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?
i am use the DP but not as fast as the search.......
10149 - Yahtzee
i keep getting the wrong answer,
can someone post some (tricy) test cases
is 11111 a full house?
can someone post some (tricy) test cases
is 11111 a full house?
-
- New poster
- Posts: 12
- Joined: Tue Sep 12, 2006 6:54 pm
-
- 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
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!!
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!!