JOIN
 Match Editorial
SRM 430
Saturday, December 20, 2008

## Match summary

The 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 top-5. 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 Problems

CreateGroups
Used as: Division Two - Level One:
 Value 275 Submission Rate 589 / 782 (75.32%) Success Rate 430 / 589 (73.01%) High Score wxGO for 274.61 points (1 mins 4 secs) Average Score 199.92 (for 430 correct submissions)

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:

1. Let consider schedules, where the number of students is greater than maxSize and calculate the total number of students needed to leave those groups (needToErase).
2. Then consider schedules, where the number of students is less than minSize. Calculate the total number of students needed to join them (needToAccept).
The answer to the problem, as can be easily proved, is the maximum of needToErase and needToAccept. See yeputons's solution for an example of a clear implementation of this.

BitwiseEquations
Used as: Division Two - Level Two:
 Value 500 Submission Rate 301 / 782 (38.49%) Success Rate 139 / 301 (46.18%) High Score yeputons for 468.12 points (7 mins 30 secs) Average Score 308.18 (for 139 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 653 / 679 (96.17%) Success Rate 489 / 653 (74.89%) High Score Petr for 247.83 points (2 mins 39 secs) Average Score 198.60 (for 489 correct submissions)

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 y0**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 non-zero 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 K-th 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.

Used as: Division Two - Level Three:
 Value 1000 Submission Rate 167 / 782 (21.36%) Success Rate 33 / 167 (19.76%) High Score smilitude for 901.09 points (9 mins 37 secs) Average Score 633.86 (for 33 correct submissions)

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.

TwinTowns
Used as: Division One - Level Two:
 Value 500 Submission Rate 320 / 679 (47.13%) Success Rate 63 / 320 (19.69%) High Score Petr for 363.32 points (18 mins 59 secs) Average Score 250.93 (for 63 correct submissions)

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[f1,f2,...,fn] - and the answer for this state will be the maximal number of twin towns, if fi is the maximal number of partners allowed for the i-th city. Clearly, the initial problem is equivalent to P[maxPartners, maxPartners, maxPartners,...,maxPartners]. We will solve each subproblem P[f1,f2,...,fn] in the following way:

• Pick a city i such that fi is minimal, but greater than zero.
• Find partners for city i (it may have between 0 and fi partners, inclusive).
What follows, we want to reduce the original problem to solve several subproblems in the form P[f'1,f'2,...,f'n].
1. The city i may have no twin. We set f'i := 0 and solve the subproblem P[f'1,f'2,...,f'n].
2. The city i may have exactly one twin. We go through each possible twin a for our town i and set f'i := 0 , f'a := fa-1 and then and solve the subproblem P[f'1,f'2,...,f'n].
3. The city i may have exactly two twins: We find all possible twins a, b for our town i. We set f'i := 0 , f'a := fa-1, f'b := fb-1 and then solve the subproblem P[f'1,f'2,...,f'n].
4. The city i may have exactly three twins: We find all possible twins a, b, c for our town i. Set f'i := 0 , f'a := fa-1, f'b := fb-1, f'c := fc-1 and then solve the subproblem P[f'1,f'2,...,f'n].
The last issue is the time complexity of this solution. Clearly, there exists at most 4n subproblems of the problem (since each fi may vary between 0 and 3). Now lets estimate the time needed to solve one subproblem.
1. If fi=1, it takes O(n) time, since we have up to n choices for a.
2. If fi=2, it takes O(n2), since we have up to n2 choices for a and b.
3. If fi=3, it takes O(n3), since we have up to n3 choices for a, b and c.
But how many subproblems require in O(n3)? We think this number can not be more than 2n, because this happens only if all f are either 0 or 3. Similarly, at most 3n subproblems take O(n2) time, and the rest of subproblems can be solved in linear time. Therefore, the overall time complexity is O(2nn3 + 3nn2 + 4nn). cafelier, gusakov and ardiankp use this idea (they don't take minimal "free" capacity, but its still fast enough). The rest of solutions is based on brutal n2 * 4n complexity.

PickingUp
Used as: Division One - Level Three:
 Value 1000 Submission Rate 62 / 679 (9.13%) Success Rate 15 / 62 (24.19%) High Score rem for 601.87 points (27 mins 14 secs) Average Score 521.94 (for 15 correct submissions)

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 2N/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[N-i]. 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[N-i]. Compute the sum S = left[i][A] + right[N-i][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*2N/2).

By Janq
TopCoder Member