JOIN
 Match Editorial
SRM 246
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 div1-hard 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 Problems

CalcTest
Used as: Division Two - Level One:
 Value 250 Submission Rate 243 / 268 (90.67%) Success Rate 209 / 243 (86.01%) High Score a2nnu for 249.92 points (0 mins 30 secs) Average Score 210.70 (for 209 correct submissions)

The most elegant solution for this problem uses regular-expressions. Here is a sample Java submission:

```for (int i = 0; i < numbers.length; i++)
numbers[i] = numbers[i].replaceAll(" ","").replaceAll("[^0-9]",".");
return numbers;
```

Conglutination
Used as: Division Two - Level Two:
 Value 400 Submission Rate 223 / 268 (83.21%) Success Rate 88 / 223 (39.46%) High Score korntest for 390.85 points (4 mins 22 secs) Average Score 297.17 (for 88 correct submissions)

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 `strToInt` should return negative results for strings that represent integers greater than `expectation`.

CalcButton
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 162 / 268 (60.45%) Success Rate 16 / 162 (9.88%) High Score DarkSolver for 859.35 points (11 mins 54 secs) Average Score 650.36 (for 16 correct submissions)
Used as: Division One - Level Two:
 Value 500 Submission Rate 226 / 231 (97.84%) Success Rate 107 / 226 (47.35%) High Score misof for 484.94 points (5 mins 2 secs) Average Score 391.96 (for 107 correct submissions)

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 three-digit 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.

PiCalculator
Used as: Division One - Level One:
 Value 250 Submission Rate 229 / 231 (99.13%) Success Rate 191 / 229 (83.41%) High Score Eryx for 248.37 points (2 mins 18 secs) Average Score 206.90 (for 191 correct submissions)

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:
 Value 1000 Submission Rate 199 / 231 (86.15%) Success Rate 72 / 199 (36.18%) High Score Krzysan for 978.74 points (4 mins 12 secs) Average Score 739.29 (for 72 correct submissions)

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(A1/B1 - sqrt(N)) < abs(A2/B2 - sqrt(N)))
...
```

The standard double type does not provide the required precision.

So, let's solve the following problem. There are two fractions A1/B1 and A2/B2. Which of them is closer to sqrt(N)? Let A2/B2 be greater than A1/B1. If A2/B2 less than sqrt(N) or A1/B1 greater than sqrt(N) when the closest fraction is obvious (A2/B2 in the first case, A1/B1 in the second). So we can assume that

```A1/B1 < sqrt(N) < A2/B2.
```

In this case the fraction A1/B1 is closer to sqrt(N) if and only if

```sqrt(N) - A1/B1 < A2/B2 - sqrt(N)
```

And after a number of manipulations:

```4*N*(B1*B2)2 < (A1*B2+A2*B1)2
```

All described calculation can be done within 64bit integers.

Some coders was searching for the closest fraction minimizing `abs((A/B)2 - N)` function. In the problem limitations this solution is also possible.

By Andrew_Lazarev
TopCoder Member