UVA:10149 - Yahtzee
Background- This is tough one. Took long time to find out correct solution for this Yahtzee game. I am not posting the complete solution for now. It has rank 27 with timing 0.012 but I am writing down the algorithm and optimization I have used -
Data Structures -
1. 5 dices - string(5)
2. Analogus code - string(5)
Analogous_code(dices, code)
suppose dices are 23545: code 22111
12345: code 11111
66666: code 55555
replace each face with its count and sort it.
3. Scores Short[15].
4. Category vector<short>
5. Game multimap<string, Category>
Algorithm:
1. Read the 13 rounds and construct Game, Category will contain score of each round in all 13 categories (use analogous code to decide quickly).
2. At this point we are having 13*13 matrix.
3. Pick categories 1-6 (faces) transpose it.
4. Run the munker's algorithm to find out assignment for max profit.
5. If it has bonus -
a. update score and run for the rest of category
b. clear scores and run munker's algorithm for 13*13 transposed matrix assignment for max profit.
Have fun coding this problem, There needs some more conditions in 5'a but dont worry Judges input's are not tough you will get clear.
-Ajeet
Background- This is tough one. Took long time to find out correct solution for this Yahtzee game. I am not posting the complete solution for now. It has rank 27 with timing 0.012 but I am writing down the algorithm and optimization I have used -
Data Structures -
1. 5 dices - string(5)
2. Analogus code - string(5)
Analogous_code(dices, code)
suppose dices are 23545: code 22111
12345: code 11111
66666: code 55555
replace each face with its count and sort it.
3. Scores Short[15].
4. Category vector<short>
5. Game multimap<string, Category>
Algorithm:
1. Read the 13 rounds and construct Game, Category will contain score of each round in all 13 categories (use analogous code to decide quickly).
2. At this point we are having 13*13 matrix.
3. Pick categories 1-6 (faces) transpose it.
4. Run the munker's algorithm to find out assignment for max profit.
5. If it has bonus -
a. update score and run for the rest of category
b. clear scores and run munker's algorithm for 13*13 transposed matrix assignment for max profit.
Have fun coding this problem, There needs some more conditions in 5'a but dont worry Judges input's are not tough you will get clear.
-Ajeet
No comments:
Post a Comment