Saturday, December 20, 2008 Match summaryThe problems for this SRM were quite hard  only 75% of participants were able to solve the easy in both divisions, and the medium in Div 1 also was a tough test for most coders. One challenge helped wata to win an incredibly close race over blueblimp by and rem, with the third place being within 6 points of the win. The next trio of Petr ainu7 pmnox was packed as well, with less than point separating pmnox from making the top5. Division 2 was a relatively easy win for smilitude  elcaru got +225 during the challenge phase and still was more than 70 points behind. The ProblemsCreateGroupsUsed as: Division Two  Level One:
Let N denote the number of schedules. It is easy to see that the problem has no solution if and only if the total number of students is either too big (i.e., there are more than maxSize*N students) or too small (less than minSize*N). Otherwise, there are two ways to calculate the minimal number of reassignments. The first one is to simulate the reassignments. On each step, we find the largest group, the smallest group, and reassign some students from the largest group to the smallest. The second approach has been used by the majority of coders. It calculates the result in linear time and works in the following manner:
Used as: Division Two  Level Two: Used as: Division One  Level One:
One can prove that number y is a solution of the given equation if and only if y has zeroes in all positions where x has ones (in binary notation, of course). In other words, we need to determine the digits of y for positions where x has zeroes. For instance, if x = 1001101001 in binary (617 in decimal notation), then the last ten digits of y must be y= 0**00*0**0, where '*' denotes either zero or one. Also, we can pad any number of any digits to the beginning of the number, since all higher bits are zeroes. Any replacement of all '*' by binary digits gives us a solution. Clearly, the smallest nonzero solution can be received by replacing asterisks by "00001" for the asterisks, so it will be 1001101011 (or 619 in decimal). The second smallest solution replaces asterisks by "00..00010", the third  by "00011", and so on. In other words, the Kth smallest solution can be received by replacing all asterisks in x by digits of binary representation of number K. See lukasP's solution for a clear implementation of this. ImageTradersUsed as: Division Two  Level Three:
Probably, experienced coders didn't need much time to determine this one is a DP problem. The state of the problem can be represented by a triple (mask, i, p), where the image is ownded by trader i, who bought it for price p, and only traders from mask didn't own the image yet. For example, state (0010110, 3, 5) means that trader 3 owns the image, bought it for price of 5 and he may sell it to traders 3, 5 and 6. Since each trader can sell the image to maximum of N traders, each such a subproblem can be solved in linear time. Using memoization instead of DP provides some advantages to implement the idea above. See smilitude fastest solution as a short implementation of this. TwinTownsUsed as: Division One  Level Two:
DP again! The key constraints here are the total number of towns (at most 10) and the maximal partners which a town may have (at most 3). The state of the problem will be P[f_{1},f_{2},...,f_{n}]  and the answer for this state will be the maximal number of twin towns, if f_{i} is the maximal number of partners allowed for the ith city. Clearly, the initial problem is equivalent to P[maxPartners, maxPartners, maxPartners,...,maxPartners]. We will solve each subproblem P[f_{1},f_{2},...,f_{n}] in the following way:
Used as: Division One  Level Three:
The key idea is to divide the players into two groups of the same size. Lets put the first N/2 players to the left group, and other N/2 players to the right group. Now, we generate each possible assignment in the left group and each possible assignment in the right group. In both cases, we'll check exactly 2^{N/2} possibilities. For each possibility we keep a bitmask of the assignment and its score difference. For example, if a possibility is (01011,8), this means the first and third player were assigned to the team of the first captain, and the score difference between the teams is 8 (second team is 8 points better). Now we are to combine the assignments for left part with the assignments for the right part. Let left[i] be an array containing all those assignments for the left part, which put exactly i players into the first team. Similarly, let right[i] contain assignments for the right part with exactly i players being in the first team. It is clear we have to combine the possibilities from left[i] with the possibilities from right[Ni]. Lets forget for a second about the need for the lexicographically first solution. Sort all arrays left[i] by score differences and similarly sort right[i] by score differences. For instance, the left part contains score differences (8,3,+2,+7,+9) and the assignments for right part (7,5,1,+3,+6). Now one can easily use the two pointers technique to find the pair of numbers with sum as close to 0 as possible. To do that, set A to 0 and B to the last element of right[Ni]. Compute the sum S = left[i][A] + right[Ni][B]. If S < 0, then, since you want to move S as close to 0 as possible, you need to make the sum bigger. Therefore, you increment A. If S > 0, you want to decrease S and therefore decrement B. As soon as either A or B go outside the array limits, you are done and return the best achieved S. To find the lexicographically first answer, you need to modify the sort algorithm, order the equal elements of left[i] by their corresponding masks in ascending order, and order equal elements of right[] arrays by masks in descending order. The overall time complexity of this algorithm is O(N*2^{N/2}). 
