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 precomputationfree 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 ProblemsDivToZeroUsed as: Division Two  Level One:
Here we try every possible twodigit 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 twodigit 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: Used as: Division One  Level One:
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) { ArrayListYahtzeeBestScore Used as: Division Two  Level Three:
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:
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:
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. 
