Match Editorial

Match summary

Egor, with fast time on all three problems, won the match thanks to a last minute challenge that left AdrianKuegel, with 7 successful challenges and a resubmit on the 500, behind. They were followed by kia, konqueror and yuhch123 who also had all three problems solved and each had at least one successful challenge. Contestants faced a simple but tricky (and challengeable) 250, a moderate 500 that trapped many coders, and a 1000 that wasn't a big problem for red and top yellow with even some blue coders solving it.

Division 2 was won by WilliamLP with 300 points on challenges followed by deena and AlexBoyko.

The Problems

Value	250
Submission Rate	452 / 565 (80.00%)
Success Rate	356 / 452 (78.76%)
High Score	srele for 246.78 points (3 mins 15 secs)
Average Score	187.39 (for 356 correct submissions)

For every word in the input check if it's the same as at least the one that appeared before it in the input. If there is no such word, add 1 to the solution. The only thing that's left is to make a function that checks if the two words are the same. We can easily generate all the representations of one word. Two words are equal if and only if there exists at least one representation of the first word that is equal to the second word.

Also, we can normalize each word so the two words are equal if and only if their normalizations are equal. Normalization of a word is its unique representation, which can be defined as the lexicographically lowest of all its representations. So, normalization of a word "ball" is lexicographically lowest of { "ball", "allb", "llba", "lbal" }, which is "allb".

For implementation using normalization refer to kjan's solution.

Value	500
Submission Rate	260 / 565 (46.02%)
Success Rate	22 / 260 (8.46%)
High Score	tangyouze for 431.30 points (11 mins 43 secs)
Average Score	300.65 (for 22 correct submissions)

Value	250
Submission Rate	454 / 476 (95.38%)
Success Rate	217 / 454 (47.80%)
High Score	kia for 245.88 points (3 mins 41 secs)
Average Score	192.76 (for 217 correct submissions)

This one was a gold mine for people who found tricky cases like optimal solution navigating to pages over 500,000. Also, many people's solution thought it can go to page 0 even if the button '0' is broken. You had to be very careful in reading the statement as in the actual programming to solve it.

The Optimal entered page will never be larger than 1,000,000, so simple brute force will run in time. Many people wrongly understood the problem statement thinking you can't enter pages larger than 500,000. For every possible entered page (page for which the digit buttons are not broken) we navigate first to that page and then enter the '+' or '-' buttons. The number of presses required is the number of digits of the entered page (let's say page 100 has 0 digits) + the absolute difference between the entered and desired page (number of '+' or '-' button presses).

For a nice clean implementation see sluga's solution.

Value	1000
Submission Rate	12 / 565 (2.12%)
Success Rate	0 / 12 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Classic example of dynamic programming unfortunately proved to be too hard for division 2 coders.

Let's first solve the problem of finding out how many n-digit numbers have the required property. Start building the number from left to right. The only things that we must know in a certain moment is how many digits we must add, how many last digits are the same, and whether we reach the required maximum subsequence before. Let that number be f( n, last_same, did_reach ). It is fairly easy to get the recurrence relation from this formula, as we know that exactly one number will increase the last_same by 1, and the other 9 numbers will downgrade it back to 1.

To get how many numbers with exactly n digits are there we call 9*f( n-1, 1, false ). For every number i from k to n we sum up number of solutions with exactly i digits and return the sum. Java code follows:

public class SameDigits {
    final static long MOD = 44444444;
    long[][][] memo;
    int K;

    long f( int n, int last_same, int did_reach ){
        if( memo[n][last_same][did_reach] != -1 ) return memo[n][last_same][did_reach];

        if( n == 0 ){
            if( did_reach == 1 || last_same == K ) {
                return memo[n][last_same][did_reach] = 1;
            } else {
                return memo[n][last_same][did_reach] = 0;
            }
        }
        if( k == K ) return memo[n][last_same][did_reach] = ( 9*f( n-1, 1, 1 ) )%MOD;

        return memo[n][last_same][did_reach] = 
            ( f( n-1, last_same+1, did_reach ) + 9*f( n-1, 1, did_reach ) )%MOD;
    }

    public int howMany( int n, int k ) {
        K = k;
        memo = new long[ n+1 ][ k+1 ][2];

        for( int i = 0; i < memo.length; ++i ) 
            for( int j = 0; j < memo[i].length; ++j ) Arrays.fill( memo[i][j], -1 );

        long sol = 0;
        for( int i = k; i <= n; ++i ){
            sol = (sol + 9*f( i-1, 1, 0 )) % MOD;
        }
        
        return (int)sol;
    }
}

Value	500
Submission Rate	184 / 476 (38.66%)
Success Rate	81 / 184 (44.02%)
High Score	Egor for 461.31 points (8 mins 22 secs)
Average Score	303.39 (for 81 correct submissions)

First, let's divide all elements from weight with greatest common divisor of weight. Now, gcd of weight is 1. I will proove that subset of weight that can measure every element from weight is equivalent to subset of weight for which gcd is 1. If gcd of a subset is 1, with generalization of Bézout's identity we can easily see that we can measure all positive integers and therefore we can measure every element from the set. If gcd of a subset is k which is greater than 1, we can only measure integers divisible by k. GCD of weight is 1, so there exists at least one element not divisible by k and therefore not measurable.

Now we see that the problem is equivalent to finding minimum subset of weight so that gcd of that subset equals gcd of weight (or 1 after we divide all the elements with gcd of a set).

Factorize all the elements, so that for every element you have an array of different prime factors of that element (we ignore multiple prime factors). The maximal number of different prime factors for number less than or equal to 10,000,000 is 8. For every element first assume that it's in the final answer. Then notice that for each of these different prime factors there must be at least one element in the final answer that doesn't contain the prime factor. Do a dynamic programming for every element trying to nullify all of his prime factors. C++ code of the solve function follows:
(PF[i] is vector containing prime factors of i-th weight)

int solve( int k, int n, int mask ){
    if( n >= w.size() ) {
        if( mask == ( ( 1 << PF[k].size() ) - 1 ) ) return 0;
        else return INF;
    }

    if( memo[k][n][mask] != -1 ) return memo[k][n][mask];

    int new_mask = mask;
    
    for( int i = 0; i < PF[k].size(); ++i ){
        if( w[n] % PF[k][i] != 0 ) new_mask |= (1<<i);
    }

    return memo[k][n][mask] = 
        min( solve( k, n+1, mask ), solve( k, n+1, new_mask )+1 );
}

Value	1000
Submission Rate	138 / 476 (28.99%)
Success Rate	51 / 138 (36.96%)
High Score	kedaizd for 886.11 points (10 mins 27 secs)
Average Score	648.15 (for 51 correct submissions)

We have to maximize the number of eaten sharks. We will first consider a little easier variation of this problem, in which every shark can eat at most one other shark. Let's describe our problem through a bipartite graph. Every shark will be represented with two nodes, Ai and Bi. If shark x can eat shark y, let's draw a arc from Ax to By. Now all we need is to do a maximum cardinality matching, and report number_of_sharks - maximum_matching_cardinality as the answer.

Similary, if every shark can eat at most 2 other sharks, we will represent every shark as 3 nodes, namely A1i, A2i and Bi. And if shark x can eat shark y then draw an arc to both A1x->By and A2x->By. Again, just do the maximum cardinality matching and report the answer.

There was a tricky part of ensuring that two sharks don't eat each other. This is only possible when these sharks have exactly the same properties. We will call such sharks equivalent. Such cases can be handled by not letting a shark eat another equivalent shark which has a lower index than him.

For implementation, refer to DStepanenko's solution.