title: Uva Judge 10149, Yahtzee
body: <p><strong>UPDATE</strong>: I have found the problem that my DP solution didn't handle bonus correctly. I added one more dimension to the state array to represent the sum of the first 6 categories. However, the solution got timed out. It's not badly timeout since each test case can be solved less than 1 sec on my machine.</p>
  
  <p>The problem description is here: <a href="http://uva.onlinejudge.org/external/101/10149.html" rel="nofollow">http://uva.onlinejudge.org/external/101/10149.html</a></p>
  
  <p>I searched online and found that it should be solved by DP and bitmask. I implemented the code and passed all test cases I tested, but the Uva Judge returns wrong answer.</p>
  
  <p>My idea is to have state[i][j] to be matching round i to category bitmasked by j. Please point out my mistakes or link some code that can solve this problem correctly. Here is my code:</p>
  
  <pre><code>public class P10149 {
  
      public static void main(String[] args) throws IOException {
          Scanner in = new Scanner(new FileInputStream("input.txt"));
          // Scanner in = new Scanner(System.in);
          while (in.hasNextLine()) {
              int[][] round = new int[13][5];
              for (int i = 0; i &lt; 13; i++) {
                  for (int j = 0; j &lt; 5; j++) {
                      round[i][j] = in.nextInt();
                  }
              }
              in.nextLine();
              int[][] point = new int[13][13];
              for (int i = 0; i &lt; 13; i++) {
                  for (int j = 0; j &lt; 13; j++) {
                      point[i][j] = getPoint(round[i], j);
                  }
              }
  
              int[][] state = new int[14][1 &lt;&lt; 13];
              for (int i = 1; i &lt;= 13; i++) {
                  Arrays.fill(state[i], -1);
              }
              int[][] bonusSum = new int[14][1 &lt;&lt; 13];
              int[][] choice = new int[14][1 &lt;&lt; 13];
              for (int i = 1; i &lt;= 13; i++) {
                  for (int j = 0; j &lt; (1 &lt;&lt; 13); j++) {
                      int usedSlot = 0;
                      for (int b = 0; b &lt; 13; b++) {
                          if (((1 &lt;&lt; b) &amp; j) != 0) {
                              usedSlot++;
                          }
                      }
                      if (usedSlot != i) {
                          continue;
                      }
                      for (int b = 0; b &lt; 13; b++) {
                          if (((1 &lt;&lt; b) &amp; j) != 0) {
                              int j2 = (~(1 &lt;&lt; b) &amp; j);
                              int bonus;
                              if (b &lt; 6) {
                                  bonus = bonusSum[i - 1][j2] + point[i - 1][b];
                              } else {
                                  bonus = bonusSum[i - 1][j2];
                              }
                              int newPoint;
                              if (bonus &gt;= 63 &amp;&amp; bonusSum[i - 1][j2] &lt; 63) {
                                  newPoint = 35 + state[i - 1][j2] + point[i - 1][b];
                              } else {
                                  newPoint = state[i - 1][j2] + point[i - 1][b];
                              }
                              if (newPoint &gt; state[i][j]) {
                                  choice[i][j] = b;
                                  state[i][j] = newPoint;
                                  bonusSum[i][j] = bonus;
                              }
                          }
                      }
                  }
              }
  
              int index = (1 &lt;&lt; 13) - 1;
              int maxPoint = state[13][index];
              boolean bonus = (bonusSum[13][index] &gt;= 63);
              int[] mapping = new int[13];
              for (int i = 13; i &gt;= 1; i--) {
                  mapping[choice[i][index]] = i;
                  index = (~(1 &lt;&lt; choice[i][index]) &amp; index);
              }
  
              for (int i = 0; i &lt; 13; i++) {
                  System.out.print(point[mapping[i] - 1][i] + " ");
              }
              if (bonus) {
                  System.out.print("35 ");
              } else {
                  System.out.print("0 ");
              }
              System.out.println(maxPoint);
          }
      }
  
      static int getPoint(int[] round, int category) {
          if (category &lt; 6) {
              int sum = 0;
              for (int i = 0; i &lt; round.length; i++) {
                  if (round[i] == category + 1) {
                      sum += category + 1;
                  }
              }
              return sum;
          }
          int sum = 0;
          int[] count = new int[7];
          for (int i = 0; i &lt; round.length; i++) {
              sum += round[i];
              count[round[i]]++;
          }
          if (category == 6) {
              return sum;
          } else if (category == 7) {
              for (int i = 1; i &lt;= 6; i++) {
                  if (count[i] &gt;= 3) {
                      return sum;
                  }
              }
          } else if (category == 8) {
              for (int i = 1; i &lt;= 6; i++) {
                  if (count[i] &gt;= 4) {
                      return sum;
                  }
              }
          } else if (category == 9) {
              for (int i = 1; i &lt;= 6; i++) {
                  if (count[i] &gt;= 5) {
                      return 50;
                  }
              }
          } else if (category == 10) {
              for (int i = 1; i &lt;= 3; i++) {
                  if (isStraight(count, i, 4)) {
                      return 25;
                  }
              }
          } else if (category == 11) {
              for (int i = 1; i &lt;= 2; i++) {
                  if (isStraight(count, i, 5)) {
                      return 35;
                  }
              }
          } else if (category == 12) {
              for (int i = 1; i &lt;= 6; i++) {
                  for (int j = 1; j &lt;= 6; j++) {
                      if (i != j &amp;&amp; count[i] == 3 &amp;&amp; count[j] == 2) {
                          return 40;
                      }
                  }
              }
          }
          return 0;
      }
  
      static boolean isStraight(int[] count, int start, int num) {
          for (int i = start; i &lt; start + num; i++) {
              if (count[i] == 0) {
                  return false;
              }
          }
          return true;
      }
  }
  </code></pre>