Match Editorial

Match summary

After two matches, competitors have finally remembered what solving Div1 Hard during the match looks like. This match proved to be of average difficulty. The success rate for almost all problems was pretty good.

The match was won by a great high schooler yuhch123 - in a moment he submitted all three problems. The second and third places were taken by Michael_Levin and liympanda. The Top-3 in Div-II was formed by pavel13, litwin and lshmouse.

The Problems

Value	250
Submission Rate	457 / 469 (97.44%)
Success Rate	397 / 457 (86.87%)
High Score	TopRushers for 249.09 points (1 mins 43 secs)
Average Score	224.32 (for 397 correct submissions)

First of all, we need to determine, whether the sequence represents an integer arithmetic or geometric progression. In an integer arithmetic progression the difference between neighbouring elements is constant. In an integer geometric progression the quotient of neighbouring elements is constant. So we need to check these properties. Then we need to calculate parameter q of the sequence (we don't need parameter p), and to return the next element of the sequence.

If the sequence represents an integer arithmetic progression then:

• q is equal to the absolute difference between any two neighbouring elements (i.e., A[i] - A[i - 1]).
• The next element is calculated as (the last element of the sequence) + q.

If the sequence represents an integer geometric progression, we do following:

• q is now equal to the quotient of any two neighbouring elements (i.e., A[i] / A[i - 1]).
• The next element is calculated as (the last element of the sequence) * q.

For a clear implementation see ron.iiita's code.

Value	600
Submission Rate	182 / 469 (38.81%)
Success Rate	59 / 182 (32.42%)
High Score	Steps09 for 482.88 points (14 mins 45 secs)
Average Score	315.65 (for 59 correct submissions)

Value	300
Submission Rate	343 / 442 (77.60%)
Success Rate	226 / 343 (65.89%)
High Score	overwise for 286.08 points (6 mins 19 secs)
Average Score	201.05 (for 226 correct submissions)

The crucial part is to notice that in each optimal solution we can always have one joker box, even if we don't use it at all. That joker box doesn't need to contain marbles of different colors - it may also contain only marbles of the same color or even contain no marbles at all. Now, let's try every box as a joker box and try to optimally solve the problem in each situation. If we know how to do that, the solution is the minimum of optimal solutions for all these situations. Let's see what would we do with each box (except joker box) in dependence with box state:

• Box is empty

We will eliminate those boxes from consideration as they don't have any importance. Instead of moving marbles to such box, we can move them to joker box.

• Box contains marbles of different colors

As each box must either be empty or contain only marbles of the same color, we will surely need to eliminate some marbles from that box. So, one move will surely be performed. As we can take any number of marbles from one box in one move, why not move all marbles from that box into joker box. So, move them all.

• Box contains only marbles of the same color

As we cleared all boxes with state 1 or 2, we got only boxes which contain only marbles of the same color. The only trouble we can have now is the restriction that all marbles of the same color (except those in the joker box) must be in the same box. So, if marbles of the same color (except those in the joker box) are distributed in multiple different boxes, we need to group them into one box. So, clear all those boxes, except one.

Just perform that algorithm with each possible box as a joker box, and take the minimum of the results. For the clear implementation of this approach see ardiankp's code. One more optimization can be achieved - we don't need to try each box as a joker box. But that's for an easy homework.

Value	1000
Submission Rate	16 / 469 (3.41%)
Success Rate	8 / 16 (50.00%)
High Score	mohamad_jrs for 701.43 points (20 mins 27 secs)
Average Score	536.88 (for 8 correct submissions)

We know that, on the end, all marbles of the same color will be in the same box and each box will either be empty or contain only marbles of the same color. So, if we know the end-box for some color (the box in which all marbles of that color will be in the end), we simply move all marbles of that color to it, except those which are already in it. So, in every end-box positioning for all colors, we need to count only the marbles which are not already in boxes they should be in the end. That number will be the number of moves necessary to solve the problem with specified end-box positioning in minimal number of moves.

Now the problem is: How to position end-boxes for all colors so that we need minimal number of moves necessary to solve the problem? Equivalent question is: How to position end-boxes for all colors so that the number of marbles which are already in their end-boxes is maximal? Let's try to answer on the first question.

First of all, let's create a bipartite graph where on the one side are vertices representing all colors, and on the other side are boxes. We will connect i-th color to j-th box with an edge whose weight is equal to:

(total number of marles of color i) - boxes[j][i]

which is actually the number of marbles of color i we will need to move. Now we want to match every color with some box and we want to have a minimal sum of weights of included edges. That's exactly min-cost max flow problem. And it's obviously not appropriate for Div2 Hard. But, with given constraints, it can be done using dynamic programming technique.

We will define a function opt(upto, used), where upto tells that only boxes with indexes [0..upto] are considered, and ones in the binary representation of used tells us to which colors we still need to assign the end-boxes. That function returns the minimal number of moves necessary to complete the task starting from a given state. Once we have calculated some function, we store it's result in dp[upto][used]. Now we need to define the opt function's body. The following pseudo code does that:

opt(upto, used): returns integer
    if upto = -1
        if used = 0 // end-boxes must be assigned to all colors
            return 0;
        else
            return infinite;

    if already calculated
        return dp[upto][used];

    // don't assign upto's box to any color
    dp[upto][used] = opt(upto - 1, used);

    // try to assign upto's box to some color
    for i := 0 to number_of_colors - 1 do
        if i-th bit in used is 1
            used1 = (used, with flipped bit on i-th position);
            t = boxes[upto][i] + opt(upto - 1, used1);

            if (dp[upto][used] > t)
                dp[upto][used] := t;
    end of for

    return dp[upto][used];

The solution to the problem will be opt(n, first m bits set to 1), where n represents the number of boxes, and m - the number of colors. For the implementation of similar algorithm see z7oka's solution.

Value	500
Submission Rate	223 / 442 (50.45%)
Success Rate	171 / 223 (76.68%)
High Score	Gluk for 484.92 points (5 mins 2 secs)
Average Score	350.50 (for 171 correct submissions)

There are several approaches to this problem. Most of them use dynamic programming, but some optimized brute-force solutions may also pass system test. Here will be explained an O(n^2) algorithm and it can be relatively easily modified to have O(n * lg(n)) complexity, where n is the number of intervals.

First of all, let's sort intervals by their finish points. Then we'll define two functions, partial(x) and total(x). The total(x) returns the number of valid subsets of the set formed by first x + 1 intervals. The partial(x) returns the number of valid subsets, which contains x-th interval, of the set formed by the first x + 1 intervals. The solution would be total(n), where n is the number of intervals. Now, let's see how to calculate each of those two functions.

• partial(x):

Find the interval with the greatest index less then x which doesn't intersect with x-th interval. If such interval doesn't exist, result is 1. If it exists, let its index be y. Then the result is total(y).
• total(x):

We want to find all intervals, with indexes between 0 and x, which can be the rightmost intervals in some valid subset (now we don't consider the valid subsets of the whole set of intervals but only of the first x + 1 intervals). When we find them, the solution would be the sum of all partials()-s for each of them. Now, let's see what those intervals found look like - for one with index y we can't find interval with index z such that z > y and z <= x, and y-th interval doesn't intersect z-th interval. If such interval exists, we can add it to the subset as it wouldn't make subset invalid.

Here is the implementation of that algorithm in C++:

    // it's assumed that intervals are sorted by finish
    int n = intervals.size();

    // solve
    partial[0] = total[0] = 1;
    for (int i = 1; i < n; ++i) {

        // calculate partial[i]
        partial[i] = 1;
        for (int j = i - 1; j >= 0; --j) {
            if (finish[j] < start[i]) {
                partial[i] = total[j];
                break;
            }
        }

        // calculate total[i]
        total[i] = 0;
        int lmax = 0; // the rightmost start of some processed interval
        for (int j = i; j >= 0 && finish[j] >= lmax; --j) {
            total[i] += partial[j];
            lmax >= start[j];
        }
    }

    return total[n - 1];

For another approach see AdrianKuegel's soluton.

Value	950
Submission Rate	59 / 442 (13.35%)
Success Rate	41 / 59 (69.49%)
High Score	Michael_Levin for 795.81 points (13 mins 2 secs)
Average Score	511.45 (for 41 correct submissions)

Let L be the least common multiple of A.size and B.size. Now, let's calculate first L elements by simple iteration. If N is less or equal to L, then we'll calculate the result only by iteration. But if it's not, additional calculations need to be performed. Each element will be calculated as A[x] ^ y (^ denotes to exponentation). Now, consider (x + L)-th element - it can be calculated as A[x] ^ (y + L / B.size) as corresponding element in B will be incremented exactly L / B.size times. So, each element of the first L elements will be the first element of some geometric progression of the form:

A[x] ^ y, A[x] ^ (y + C), A[x] ^ (y + 2*C), ... , A[x] ^ (y + R*C)

where C is equal to L / B.size and R + 1 represents the number of elements in that sequence (for i-th element R is equal to (N - i) / L). We need to find the sum of all those elements. To calculate that sum, a simple divide and conquer algorithm exists. So, for each of first L elements calculate the sum of all elements of "its" geometric progression. Then the result is the sum of all those sums.

For example of that approach, see yuhch123's solution.