Match Editorial

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

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;

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.

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)

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.

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);

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 A₁/B₁ and A₂/B₂. Which of them is closer to sqrt(N)? Let A₂/B₂ be greater than A₁/B₁. If A₂/B₂ less than sqrt(N) or A₁/B₁ greater than sqrt(N) when the closest fraction is obvious (A₂/B₂ in the first case, A₁/B₁ in the second). So we can assume that

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

In this case the fraction A₁/B₁ 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.