Thursday, June 9, 2005 Match summary This problem set was pretty easy. Some coders completed their work in 20 minutes. There was a long list of contestants with a complete set of problems after 40 minutes and at the end of the challenge 86.15% of coders had submitted the hardest task. But only 36.18% of div1hard solutions were correct. Im2Good, who made 12 successful challenges, won this match and became the Highest Match Total champion (a title that hasn't changed since 05.08.01). misof and jdmetz took second and third. In the division 2, korntest was first, followed by p45c4l and titid_gede who took second and third. The ProblemsCalcTestUsed as: Division Two  Level One:
The most elegant solution for this problem uses regularexpressions. Here is a sample Java submission: for (int i = 0; i < numbers.length; i++) numbers[i] = numbers[i].replaceAll(" ","").replaceAll("[^09]","."); return numbers;Conglutination Used as: Division Two  Level Two:
There are at most 19 split points. We can try all of them and choose one with the smallest A value (if any). Here is a sample Java submission: for (int i = 1; i < conglutination.length(); i++) { int A = strToInt(conglutination.substring(0,i)); int B = strToInt(conglutination.substring(i)); if (A >= 0 && B >= 0 && A + B == expectation) return conglutination.substring(0,i) + "+" + conglutination.substring(i); } return "";
The only trick is that Used as: Division Two  Level Three: Used as: Division One  Level Two:
There are only 1000 different buttons and we can test all of them. If we know the digits on the button how many clicks are required for typing the sequence? The secret is easy: if the next three digits in the sequence equals to the corresponding button's digits, we should click threedigit button. The result will be optimal. Here is a sample Java submission: //merge sequence into char array s ... String ans = ""; int bestRes = s.length + 1; for (char ch1='0';ch1<='9';ch1++) for (char ch2='0';ch2<='9';ch2++) for (char ch3='0';ch3<='9';ch3++) { int curRes = 0; int index = 0; while (index < s.length) { if (index + 2 < s.length && s[index] == ch1 && s[index + 1] == ch2 && s[index + 2] == ch3) { index += 3; } else { index += 1; } curRes += 1; } if (curRes < bestRes) { bestRes = curRes; ans = "" + ch1 + ch2 + ch3; } } return ans; Some coders (for example Im2Good, John Dethridge...) used dynamic programming to obtain the required amount of clicks. This solution is also correct. PiCalculatorUsed as: Division One  Level One:
For solving this problem we should manually round the value of Π. Note contains several first Π value digits and this amount is enough for solving this problem. Here is a sample Java submission: byte[] pi = "3.141592653589793238462643383279".getBytes(); if (pi[precision + 2] > '4') pi[precision + 1]++; int index = precision; while (pi[index + 1] > '9') { pi[index + 1] = (byte)'0'; pi[index]++; index; } return new String(pi, 0, precision + 2);CalcRoot Used as: Division One  Level Three:
There are at most 1000 possible denominators. We can try all of them. If we know a denominator B, a numerator A of the closest fraction can be easily found using the following formula: A = round(B * sqrt(N)) After that we can compare the obtained fraction with the currently best fraction and update it if needed. Where is the trick? The trick in the phrase "we can compare obtained fraction with the currently best fraction" because we can't do it in a usual way: if (abs(A_{1}/B_{1}  sqrt(N)) < abs(A_{2}/B_{2}  sqrt(N))) ... The standard double type does not provide the required precision. So, let's solve the following problem. There are two fractions A_{1}/B_{1} and A_{2}/B_{2}. Which of them is closer to sqrt(N)? Let A_{2}/B_{2} be greater than A_{1}/B_{1}. If A_{2}/B_{2} less than sqrt(N) or A_{1}/B_{1} greater than sqrt(N) when the closest fraction is obvious (A_{2}/B_{2} in the first case, A_{1}/B_{1} in the second). So we can assume that A_{1}/B_{1} < sqrt(N) < A_{2}/B_{2}. In this case the fraction A_{1}/B_{1} is closer to sqrt(N) if and only if sqrt(N)  A_{1}/B_{1} < A_{2}/B_{2}  sqrt(N) And after a number of manipulations: 4*N*(B_{1}*B_{2})^{2} < (A_{1}*B_{2}+A_{2}*B_{1})^{2} All described calculation can be done within 64bit integers. Some coders was searching for the closest fraction minimizing 
