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 Top3 in DivII was formed by pavel13, litwin and lshmouse. The ProblemsGuessingNextElementUsed as: Division Two  Level One:
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:
If the sequence represents an integer geometric progression, we do following:
For a clear implementation see ron.iiita's code. MarblesRegroupingEasyUsed as: Division Two  Level Two: Used as: Division One  Level One:
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:
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.
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.
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. MarblesRegroupingHardUsed as: Division Two  Level Three:
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 endbox 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 endbox 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 endbox positioning in minimal number of moves. Now the problem is: How to position endboxes for all colors so that we need minimal number of moves necessary to solve the problem? Equivalent question is: How to position endboxes for all colors so that the number of marbles which are already in their endboxes 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 ith color to jth 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 mincost 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 endboxes. 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 // endboxes 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 ith bit in used is 1 used1 = (used, with flipped bit on ith 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. IntervalSubsetsUsed as: Division One  Level Two:
There are several approaches to this problem. Most of them use dynamic programming, but some optimized bruteforce 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 xth 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.
Find the interval with the greatest index less then x which doesn't intersect with xth interval. If such interval doesn't exist, result is 1. If it exists, let its index be y. Then the result is total(y). 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 yth interval doesn't intersect zth 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. StrangeArrayUsed as: Division One  Level Three:
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 ith 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. 
