JOIN
 Match Editorial
SRM 387
Wednesday, January 9, 2008

## 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

GuessingNextElement
Used as: Division Two - Level One:
 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.

MarblesRegroupingEasy
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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.

MarblesRegroupingHard
Used as: Division Two - Level Three:
 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;

return dp[upto][used];

dp[upto][used] = opt(upto - 1, used);

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.

IntervalSubsets
Used as: Division One - Level Two:
 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];
}
}

```

For another approach see AdrianKuegel's soluton.

StrangeArray
Used as: Division One - Level Three:
 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.

By Relja
TopCoder Member