10149 - Yahtzee

[forcebrute]

i have been stuck with this problem past 4 days . I know DP will be used.
i will get max in c+1 categories using all possible combinations of c categories .
But how do i incorporate bonus point analysis. somebody please help me out with the algo of the problem.
i am stuck now.......

[Leonid]

I'm stuck with this problem.
First I choose all possible ways to assign categories 1 to 6 that is C(6 out of 13). Then I solve two parts with DP (first part is 1-6 categories), (second part is (7-13) categories). I believe my approach is correct. I ran test cases posted in this thread and the total score was the same (category assignment was different). Additionally I compared 100 test cases with output produced by http://uvatoolkit.com/problemssolve.php . The result was still the same. I'm wondering where could I have made a mistake? I think the mistake can be in category assignment, esp. in full house interpretation. So I ran both interpretation of full house either 11111 is a full house of not but none of them got accepted. I will post the part of my code with interpretations of scoring of each category. I'd really appreciate if someone will take time and consider if this part of the code handles the scoring well.

Code: Select all

int score(vector<int>& comb, int type) {
	int sum = 0;
	if (type < 6) {
		for (int i = 0; i < 5; i++) {
			if (comb[i] == type + 1)
				sum += comb[i];
		}
		return sum;
	}
	switch (type) {
		case 6:
			for (int i = 0; i < 5; i++)
				sum += comb[i];
			break;
		case 7:
			for (int i = 0; i < 3; i++)
				if (comb[i] == comb[i + 2]) {
					sum = score(comb, 6);
				}
			break;
		case 8:
			for (int i = 0; i < 2; i++)
				if (comb[i] == comb[i + 3]) {
					sum = score(comb, 6);
				}
			break;
		case 9:
			if (comb[0] == comb[4]) {
				sum = 50;
			}
			break;
		case 10:
			bool value[6];
			memset(value, 0, sizeof(value));
			for (int i = 0; i < 5; i++) {
				value[comb[i] - 1] = 1;
			}
			for (int i = 0; i < 3; i++) {
				if (value[i] && value[i + 1] && value[i + 2] && value[i + 3])
					sum = 25;
			}
			break;
		case 11:
			memset(value, 0, sizeof(value));
			for (int i = 0; i < 5; i++) {
				value[comb[i] - 1] = 1;
			}
			for (int i = 0; i < 2; i++) {
				if (value[i] && value[i + 1] && value[i + 2] && value[i + 3] && value[i + 4])
					sum = 35;
			}
			break;
		case 12:
			if ((comb[0] == comb[1] && comb[2] == comb[4]) || (comb[0] == comb[2] && comb[3] == comb[4])) {
				sum = 40;
			}
			break;
	}
	return sum;
}

[tryit1]

your case 12 is pretty weird.

i solved it using recur bitmasks. For each unused number, try to fit in category k. But the memo is based on dp[bitmask][score] because same bitmask can be caused at different levels and scores will differ.

[jaken]

I've been getting WA for the past couple days playing with this, and I honestly am baffled as to the case(s) I'm missing. I've generated thousands of sample input games (~10k so far), ran them through the UVA Toolkit, and in every case my optimal score matched the toolkit's output. Typically I'll have about 150 games (per 1000) where my assignments are different from the toolkit's, but the total score is equivalent. (these should still pass, yes?) I've authored some hand-made input designed to catch edge cases and the results match too. (is the UVA toolkit authoritative?)

I'm about to start again using a dynamic programming approach, but wanted to share my current approach in case anyone sees a defect. Currently I'm using a mix of the Hungarian matching algorithm and backtrack search.

First I use the Hungarian matching to generate the optimal assignments (this matching doesnt consider the upper-bonus rule when maximizing the score). If this result does indeed yield the upper bonus, then I consider this matching to be optimal in any case, and I use it as my solution.

If the above matching does not yield the upper bonus I use Hungarian again to score the max in just the upper categories to see if the bonus is possible. If it is NOT then I consider the above matching to be my solution. If it IS then I use a backtrack search to generate all possible upper-category assignments such that we get the upper bonus. (typically < 2000 cases). For each of these I use Hungarian again to maximize the lower categories with the remaining rolls, and take as my solution that with the max score of all considered so far.

So like I said, I ran thousands of test games through the toolkit and havent had a miss yet. If anyone has any insight, please share!

Thanks

[Neil]

I’m surprised no one’s asked about the number of test cases in the input file, so I’ll be the first. The problem statement just says “there may be any number of games in the input data”, which is really unfair because it doesn’t give any sense of how fast a solution needs to be. Any number could be a few, it could be dozens...it could be hundreds! My solution can run over 200 test cases in about 2.5s on my laptop, yet it gets TLE. So for those that got accepted, about how many cases can your solutions run within the time limit? I’m just wondering if my solution just needs a few small optimizations or if I need a whole new algorithm with better complexity...

[Hikari9]

I've been getting WA for the past couple days playing with this, and I honestly am baffled as to the case(s) I'm missing. I've generated thousands of sample input games (~10k so far), ran them through the UVA Toolkit, and in every case my optimal score matched the toolkit's output. Typically I'll have about 150 games (per 1000) where my assignments are different from the toolkit's, but the total score is equivalent. (these should still pass, yes?) I've authored some hand-made input designed to catch edge cases and the results match too. (is the UVA toolkit authoritative?)

I'm about to start again using a dynamic programming approach, but wanted to share my current approach in case anyone sees a defect. Currently I'm using a mix of the Hungarian matching algorithm and backtrack search.

First I use the Hungarian matching to generate the optimal assignments (this matching doesnt consider the upper-bonus rule when maximizing the score). If this result does indeed yield the upper bonus, then I consider this matching to be optimal in any case, and I use it as my solution.

If the above matching does not yield the upper bonus I use Hungarian again to score the max in just the upper categories to see if the bonus is possible. If it is NOT then I consider the above matching to be my solution. If it IS then I use a backtrack search to generate all possible upper-category assignments such that we get the upper bonus. (typically < 2000 cases). For each of these I use Hungarian again to maximize the lower categories with the remaining rolls, and take as my solution that with the max score of all considered so far.

So like I said, I ran thousands of test games through the toolkit and havent had a miss yet. If anyone has any insight, please share!

Thanks

I got AC using the Hungarian algorithm.

What I did was choose any 6 out of the 13 for the first 6 categories (because of the bonus). Then for all cases (there are 1716 == 13 choose 6), I did the Hungarian for maximal matching on the first 6, then apply the bonus if >= 63. Then do another Hungarian for the last 7.

I think what's wrong about your solution is that you're assuming this implication: "if the max has no bonus, then it's the max overall", which is wrong because a bonus roll can exist <35 points away from the "max without bonus".

For example, try this test case:

Code: Select all

1 2 3 4 5
2 2 3 4 5
3 3 1 1 1
5 5 5 5 5
6 6 6 6 6
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

If you keep the max without bonus you'll get 212, which is wrong, because there's an answer with 217:

Code: Select all

1 4 3 4 25 30 15 0 0 0 25 35 40 35 217

I hope that helps.