JOIN
 Match Editorial
SRM 262
Friday, September 9, 2005

Match summary

Friday's early SRM featured something not seen in quite a while, precomputation. marian and Petr, who finished second and third respectively, both submitted precomputed solutions to the Div 1 hard. Despite this sturdy opposition, kalinov's precomputation-free solution earned him the first place crown. In Division 2, dynamitehacker and pashka took first and second place with scores over 1350. pashka, who made 2 successful challenges, fell short of first by 6.9 points.

# The Problems

DivToZero
Used as: Division Two - Level One:
 Value 250 Submission Rate 279 / 301 (92.69%) Success Rate 251 / 279 (89.96%) High Score meisterT for 247.60 points (2 mins 48 secs) Average Score 208.62 (for 251 correct submissions)

Here we try every possible two-digit ending, and take the first one that works. The solution featured here loops through the possibilities for each digit separately. The constraints guarantee that some two-digit suffix will work. Java code follows:

```
public String lastTwo(int num, int factor) {
String val = (num+"").substring(0,(num+"").length()-2);
for (char t = '0'; ; t++) {
for (char on = '0'; on <= '9'; on++) {
String curr = val+t+""+on;
int f = Integer.parseInt(curr);
if (f % factor == 0) return t+""+on;
}
}
}
```

SortBooks
Used as: Division Two - Level Two:
 Value 500 Submission Rate 220 / 301 (73.09%) Success Rate 136 / 220 (61.82%) High Score isv for 474.92 points (6 mins 35 secs) Average Score 338.32 (for 136 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 235 / 242 (97.11%) Success Rate 210 / 235 (89.36%) High Score lovro for 247.55 points (2 mins 50 secs) Average Score 204.48 (for 210 correct submissions)

Here we must determine if something is detectably a title. This can be done in an auxiliary function check. To utilize the library effectively, I surround the string with spaces, and then search for possible substrings. To count the number of words, I use a tokenizer and split by spaces. Once check is written, we simply loop through the input and compare each pair. Java code follows:

```boolean check(String s) {
String t = " "+s.toUpperCase()+" ";
return s.split(" +").length > 3 || t.indexOf(" THE ") > -1 ||
t.indexOf(" AND ") > -1 || t.indexOf(" OF ") > -1;
}
public int[] checkManually(String[] field1, String[] field2) {
ArrayList al = new ArrayList();
for (int i = 0; i< field1.length; i++) {
if (check(field1[i]) == check(field2[i])) {
}
}
int[] ret = new int[al.size()];
for (int i = 0; i < ret.length; i++) {
ret[i] = al.get(i);
}
return ret;
}
```

YahtzeeBestScore
Used as: Division Two - Level Three:
 Value 1100 Submission Rate 54 / 301 (17.94%) Success Rate 9 / 54 (16.67%) High Score dynamitehacker for 716.53 points (23 mins 37 secs) Average Score 589.19 (for 9 correct submissions)

The solution to this problem consists of two very distinct parts. The core algorithm runs through each permutation of the hands. Once a permutation is chosen, you have a mapping between rolls and score types. Then you check if each roll matches the corresponding score type, and if it does, add that to the total score. The largest return is kept. In the following code, rec recursively generates permutations. The pair of score functions handle the Yahtzee specific information. Java code follows:

```int score(String[] hands, int[] order) {
int ret = 0;
for (int i = 0; i < order.length; i++) ret += score(hands[order[i]],i);
return ret;
}
//Given the hand and hand type, determines the score
int score(String hand, int pos) {
int cnts[] = new int[6], p = 1, M = 0, s = 0;
for (int i = 0; i < hand.length(); i++) cnts[ hand.charAt(i) - '1' ]++;
for (int i = 0; i < cnts.length; i++) if (cnts[i] > 0) {
p *= cnts[i];
s += cnts[i]*(i+1);
if (cnts[i] > M) M = cnts[i];
}
if (M == 5 && pos == 0) return 50;
if (M == 5 && pos == 1) return 25;
if (p == 6 && pos == 1) return 25;
if (M >= 4 && pos == 2) return s;
if (M >= 3 && pos == 3) return s;
if (p == 1 && (cnts[0] == 0 || cnts[5] == 0) && pos == 4) return 40;
if (p == 1 && (cnts[0] == 0 || cnts[5] == 0) && pos == 5) return 30;
if (p == 1 && (cnts[1] == 0 || cnts[4] == 0) && pos == 5) return 30;
if (p == 2 && (cnts[0]+cnts[1])*(cnts[4]+cnts[5])*(cnts[0]+cnts[5]) == 0
&& pos == 5) return 30;
if (pos == 6) return s;
return 0;
}
int rec(String[] hands, int pos, boolean[] mark, int[] order) {
if (pos == hands.length) return score(hands,order);
int ret = 0;
for (int i = 0; i < mark.length; i++) {
if (mark[i]) continue;
mark[i] = true;
order[pos] = i;
ret = Math.max(rec(hands,pos+1,mark,order),ret);
mark[i] = false;
}
return ret;
}
public int bestLowerScore(String[] hands) {
return rec(hands,0,new boolean[hands.length],new int[hands.length]);
}

```

BestYahtzeeScore
Used as: Division One - Level Two:
 Value 500 Submission Rate 160 / 242 (66.12%) Success Rate 57 / 160 (35.62%) High Score monsoon for 416.43 points (13 mins 17 secs) Average Score 294.06 (for 57 correct submissions)

To solve this Yahtzee problem, we compute every possible way of keeping/rolling the dice. For each way, we compute the score, and take the best value. The scoring method is similar to the div 2 hard, and will not be discussed. The core choosing code can be implemented recursively by storing how many rolls have been used, how many dice have been used, and what the current hand is. Every possible subset of the 5 dice can be removed and replaced with new dice. The code here runs through each subset, and then recursively determines what to do next. Java code follows containing everything but the Yahtzee score computation function:

```//Compute score of hand
int score(String hand);
int solve(String rolls, String hand, int pos, int num) {
int best = score(hand);
if (num == 3) return best;
//Test each subset
for (int i = 1; i < 1 << 5; i++) {
char[] h = hand.toCharArray();
int p = pos;
for (int j = 0; j < 5; j++) {
if ( ((1 << j) & i) == 0) continue;
h[j] = rolls.charAt(p++);
}
best = Math.max(best, solve(rolls,new String(h),p,num+1));
}
return best;
}
public int bestScore(String rolls) {
return solve(rolls,rolls.substring(0,5),5,1);
}
```

MagicBoxes
Used as: Division One - Level Three:
 Value 1000 Submission Rate 63 / 242 (26.03%) Success Rate 11 / 63 (17.46%) High Score kalinov for 682.52 points (21 mins 36 secs) Average Score 527.53 (for 11 correct submissions)

To solve this problem, we first compute how many boxes can be placed if only area considerations are taken into account. Starting with this upper limit, we try each number of boxes separately. When a quantity works, we return. When trying to place k actual boxes, we would like to try every possible position and recurse, but this type of implementation is too naive to run in time. Fortunately, a relatively simple optimization works. For each box, starting with the largest, we try all possible placements with the following restriction: one vertical side and one horizontal side must lay against the container or another box. This does not hamper our ability to place the maximum number of boxes, and allows our algorithm to easily finish in time.

By brett1479
TopCoder Member