Match Editorial

Match summary

Being the last SRM before TCO, the match attracted 1361 competitors. However, the problems in both division were not easy. The success rate for two DPs in both divisions was surprisingly low, making the challenge phase very eventful.

Only two competitors solved all three problems successfully. Petr won the match by a huge gap, despite resubmitting the hard, OpenGL got the second and became the sixth target from China. Congratulations to OpenGL! They're followed by fpavetic, with 7 successful challenges on the medium.

Nobody got all 3 problems correct in Division 2. martins256 won with 7 successful challenges on the hard, despite his own solution failed. A newcomer ljcarter15 closely followed and got the second place. He had a small bug on his medium, which made him the only person who failed the medium among the top 100 competitors in Division 2. nocut98, with 5 successful challenges, rounded the top-3.

The Problems

Value	250
Submission Rate	692 / 771 (89.75%)
Success Rate	586 / 692 (84.68%)
High Score	ChronotriggerBG for 246.69 points (3 mins 18 secs)
Average Score	192.52 (for 586 correct submissions)

Since maxCount is small, counting numbers one by one will be sufficient. A method used by many coders uses a variable dir to represent the current counting direction. Change the direction when finger 1 or 5 is just used. See pszemsza_'s solution. It's not hard to see that the fingers he used is periodic. A period could be stored in an array fingers, so the i-th finger he used would be fingers[i % 8], where i % 8 means i modulo 8. This is another way to simulate the counting process. See nocut98's solution for a clear implementation. The most common mistake in these simulation-based solutions is to count the next number first, then update the counter. These solutions fail the test case "1,1".

It is also possible to calculate the answer directly by some maths. See rudiso's solution for example. But it is relatively easy to make mistakes, as in many failed solutions.

Value	500
Submission Rate	324 / 771 (42.02%)
Success Rate	122 / 324 (37.65%)
High Score	rudiso for 469.44 points (7 mins 20 secs)
Average Score	329.08 (for 122 correct submissions)

Value	250
Submission Rate	548 / 588 (93.20%)
Success Rate	435 / 548 (79.38%)
High Score	lovro for 249.01 points (1 mins 48 secs)
Average Score	206.99 (for 435 correct submissions)

This problem may look terrible, but actually it's not that hard. let d[i] be the remainder of the concatenation of i copies of number, divided by k, Then we're to find the smallest i such that d[i]=0. From number theory, for i >= 2, we have b[i]=(b[i-1] * 10^m + number) mod k, where m is the number of digits in number. This avoids BigInteger operations and keeps b[i] smaller than k.

But k could be up to 10⁵, so the recurrence above may still overflow if coders use 32-bit integers. This provides a good chance for the challenge phase. In fact, we've added an example test case to warn people that multiplication might overflow, but the test case "10⁹,3" is so special that even if the multiplication overflowed, the result didn't change. A sensible coder might be aware of this if he checks the examples by hand, though.

The main algorithm loops the answer starting from 1, until a solution is found. But what is the maximal possible answer? How can we discover the situation when no solution could be found? The situation is very much like expanding a fraction to an infinite decimal: stop when a cycle is found. Cycle detection could be done with a set of numbers that have been already encountered, but since the cycle length cannot exceed k, a quicker solution is to simply loop the answer from 1 to k. See lovro's solution for a clear implementation.

A few coderes had trouble calculating the number of digits in number, some other coders did this after updating number to number mod k, but the number of digits in number mod k is usually different from that in number.

Value	1000
Submission Rate	127 / 771 (16.47%)
Success Rate	1 / 127 (0.79%)
High Score	ljcarter15 for 712.03 points (19 mins 50 secs)
Average Score	712.03 (for 1 correct submission)

The extremely low success rate is a surprise. The low constraint on the number of patterns strongly suggests that the problem could be solved by dynamic programming, as many Div 2 hard problems. Let d[i][S] be the number of strings of length i that matches all pattersn in the set S but none of other patterns. Then for each character c, we can use d[i-1][S] to update d[i][S & v], where & stands for bitwise-add operator, and v is the set of patterns that character c matches at position i. For more information on bitwise operations and this kind of dynamic programming, see this tutorial.

Here is the implementation of that algorithm in C++. To make it more clear to most people, we did not include any tricks on bitwise operations.

    int d[50][1<<15];
    int n = patterns.size();
    int m = patterns[0].size();
    memset(d, 0, sizeof(d));

     // for every location, try each character
    for(int i = 0; i < m; i++)
        for(char c = 'a'; c <= 'z'; c++) {

          // v is the set of patterns that character c matches at position i
          int v = 0;
          for(int j = 0; j < n; j++)
              if(patterns[j][i] == c || patterns[j][i] == '?')
                  v |= (1 << j);

          // dynamic programming
          if(i == 0)
              d[i][v]++;
          else for(int j = 0; j < (1 << n); j++)
              d[i][j & v] = (d[i][j & v] + d[i - 1][j]) % 1000003;
        }

    // accumulate the answer
    int ans = 0;
    for(int i = 0; i < (1 << n); i++) {
        int bitCount = 0;
        for(int j = 0; j < n; j++)
            if(i & (1 << j)) bitCount++;
        if(bitCount == k)
            ans = (ans + d[m - 1][i]) % 1000003;
    }
    return ans;

The main algorithm has time complexity O(m * c * (n + 2ⁿ)), which is roughly O(m * c * 2ⁿ), Many people came up with an algorithm with a slightly higher time complexity, i.e. O(m * c * n * 2ⁿ), thus failed due to time outs. The trick here is that we only need to compute v once for each character/position combination. This could be done in a separate preprocessing routine, or, like in the sample code above, done together with the dynamic programming. Many coders used another trick to speed up the solution: skip the use of d[i][S]=0, since it cannot update anything. To use the trick, you need a different way to implement the main loop, i.e. loop for S first, then c. Unfortunately, this speed up does not gauarantee to get rid of time outs on some special data in system tests, but on most cases, optimized solution runs a lot faster.

Of 126 failed solutions, 100 has been successfully challenged. Many incorrect solutoins failed a surprisingly test case "?","?",1. The answer should be 0, but many solutions got 52. Many solutions that yielded 52 for this test case loops for all the set of patterns (with k patterns) that are matched, then accumulate the answer for all sets. Unfortunately, calculating the number of strings that matches every pattern in a set but none in another is not particularly easy.

Exercises:

1. Find a test case for which the d[i][S]=0 speed up does not help.
2. Can this problem solved by the principle of inclusion and exclusion?

Value	500
Submission Rate	340 / 588 (57.82%)
Success Rate	42 / 340 (12.35%)
High Score	Vasyl(alphacom) for 438.71 points (10 mins 56 secs)
Average Score	248.68 (for 42 correct submissions)

This is a tough medium, and the low success rate reflected that. Of 298 failed solutions, 212 has been successfully challenged. Most of failed solutions, either by challenge or system test, are due to unfortunate time outs.

Yes, it is a dynamic programming problem, as many coder can guess with a first glance of the problem, but it isn't that easy. Some coders came up with the following algorithm: let d[i][S] be the minimal time for the set S of painters to paint the first i boards. To calculate d[i][S], we need to loop for the last painter that worked, and the starting position. The resulting algorithm has time complexity O(m² * n * 2ⁿ), where n and m are the number of painters and the number of boards, respectively. This complexity is a little bit high and can hardly pass system tests. There are lucky exceptions, though, solutions that runs for >1.7 seconds for many test cases.

Some other coders realized that binary search helps here. If we binary searches the answer, what is left is just check a solution exists. To check this, some coders uses a boolean array d[i][S] to represent whether it is possible to paint the first i boards with a set S of painters. This is correct, but it is almost the same as the slow algorithm mentioned above, except that we have a binary search on top of it! A clever state representation is d[S], how far the set S of painters can paint. Since we've binary searched the answer, each painter should paint as far as he can, which can be done greedily. That is, to calculate d[S], loop for the last painter w that worked, and let him greedily paint as far as he could, as long as the time he spends does not exceed the currenet answer.

This is very close to the intended solution, but here is a question about the implementation details. How to paint as far as a painter can? This could be done adding a loop, but this increases the time complexity! In the worst case, the greedy painting process can take O(m) time, so the whole time complexity would be O(T * 2ⁿ * n * m), where T is the number of iterations of our binary search, which will at most 15. Why 15? Well, the answer should be the work time of a painter, which is always the length of some consecutive boards, divided by some speed. There are only 1+2+...+50=1275 possible lengths, thus 1275*15=19125 possible times, and log₂19125 < 15. This complexity seems too pessimistic, since in most cases, greedy painting processes are very short. I guess this is why many people stopped here. If you discovered that some greedy painting processes are done more than once, you'll happily adds memoization to your code, as in OpenGL's solution, and reduce the time complexity to O(T * (2ⁿ * n + m * m * n)), which is almost same as O(T * 2ⁿ * n).

Combining all these together, you'll get a solution that runs for at most 60ms on all test cases. Here is the implementation of that algorithm in C++.

    // sum[i]: sum of lengths of first i boards
    int n = painterSpeed.size();
    int m = boardLength.size();
    int sum[51] = {0};
    for(int i = 0; i < m; i++)
        sum[i+1] = sum[i] + boardLength[i];

    // every possible answer
    int total = (m+1)*m/2*n, cur = 0;
    double sortedTime[19125];
    for(int L = 0; L < m; L++)
        for(int R = L; R < m; R++)
            for(int W = 0; W < n; W++)
                sortedTime[cur++] = (double)(sum[R+1]-sum[L])/painterSpeed[W];
    sort(sortedTime, sortedTime + total);

    int d[1<<15], extend[15][51];
    int left = 0, right = total - 1;

    // binary search
    while(left < right) {
        int med = (right - left) / 2 + left;
        double T = sortedTime[med];

        // how far the i-th painter can paint from the j-th board
        for(int i = 0; i < n; i++)
            for(int j = 0; j <= m; j++) {
                int E = j, L = 0;
                while(E < m && L + boardLength[E] < painterSpeed[i] * T + EPS)
                  L += boardLength[E++];
                extend[i][j] = E; 
            }

        // dynamic programming
        for(int mask = 0; mask < (1 << n); mask++) {
            d[mask] = 0;
            for(int w = 0; w < n; w++)
                if((mask & (1 << w)) > 0)
                    d[mask] = max(d[mask], extend[w][d[mask ^ (1 << w)]]);
        }

        // check if the answer is possible
        if(d[(1 << n)-1] == m) right = med; else left = med + 1;
    }
    return sortedTime[left];

Value	1000
Submission Rate	13 / 588 (2.21%)
Success Rate	5 / 13 (38.46%)
High Score	zcgzcgzcg for 459.29 points (43 mins 42 secs)
Average Score	427.77 (for 5 correct submissions)

Though many people realized that the solution is some kind of brute force, only 13 coders managed to submit something. Among these solutions, only 5 was correct. The intended solution was probably sillier than many people have expected: search twice, forward and backward. Nothing special then - no prunings needed, though possible.

First, precalculate everything that can be created with 10 resistors. This could be done with dynamic programming: compute the set of possible results with N resistors, all[N] by combining some result of i resistors and N-i resistors. Don't forget to eliminate duplicates. The number of possible values for N resistors are: 2,4,12,34,108,360,1232,4190,14516,51034.

Here comes the crucial part: backward search. The first way is to do another dynamic programming: let unall[i] be the set of wanted resistance if i resistors have been taken out of the circuit. That is, if you found a circuit with resistance value equal to some element in unall[i], you can obtain the target circuit R=a/b with another i resistors. Initialize unall[0] as a singleton, {a/b}. When calculating unall[i], try every j+k=i, and take out another k resistors (i.e. an element from all[k]) from some element from unall[j]. How many unall[i] should we calculate? Suppose we've taken out 5 resistors, that is, we get a circuit from unall[5]. We cannot check whether it can be obtained with 16 resistors directly, since we haven't prepared all[11]. So we have to continue our backward search. If this circuit must be created as a combination of one from all[5] and one from all[6], the best thing we can do is to take one from all[5] and update unall[10]. That is, we should compute up to unall[10]. For a clear implementation of this method, see Petr's solution. This is the only successful solution that uses this method.

The second way to do backward search is probably easier to understand. Create a method ok(Fraction f, int r) that recursively checks if a resistance f could be obtained by r resistors. During the recursion, look up in all directly when r<=10. 4 out of 5 successful solutions used this method. For a clear implementation of this method, see UdH-WiNGeR's solution.

Exercises:

1. What is the maximum number of iterations in the backward search, for both methods?
2. What is the maximum value of nominator and denominator we might encounter, for both mehods? Is 32-bit integer sufficient to store resistor values?
3. By checking the maximal value of nominator and denominator in all it seems that the maximum value for both nominator and denominator in all[i] is exactly 2ⁱ. Is that true? If the answer is "yes", how to utilize this conclusion to speed up the solution?