Match Editorial

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

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).

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)

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

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.

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[f₁,f₂,...,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 i-th city. Clearly, the initial problem is equivalent to P[maxPartners, maxPartners, maxPartners,...,maxPartners]. We will solve each subproblem P[f₁,f₂,...,f_n] in the following way:

• Pick a city i such that f_i is minimal, but greater than zero.
• Find partners for city i (it may have between 0 and f_i partners, inclusive).

1. The city i may have no twin. We set f'_i := 0 and solve the subproblem P[f'₁,f'₂,...,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 := f_a-1 and then and solve the subproblem P[f'₁,f'₂,...,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 := f_a-1, f'_b := f_b-1 and then solve the subproblem P[f'₁,f'₂,...,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 := f_a-1, f'_b := f_b-1, f'_c := f_c-1 and then solve the subproblem P[f'₁,f'₂,...,f'_n].

1. If f_i=1, it takes O(n) time, since we have up to n choices for a.
2. If f_i=2, it takes O(n²), since we have up to n² choices for a and b.
3. If f_i=3, it takes O(n³), since we have up to n³ choices for a, b and c.

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 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[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*2^N/2).