Match Editorial

The overall level of the problem set this time was a bit higher than usual. It led to an interesting challenge phase and unexpected results after system test. This SRM had the most average value of challenges during the last half of the year. Egor was the first in Division 1 who submitted all problems on the 45th minute. But the division winner was marek.cygan, the only competitor who passed all three problems. Second place went to misof, and third to krijgertje.

The division 2 leaders are SpaceFlyer, DaTval and taruntheone. The only person who solved the hard problem is abi20sg.

The Problems

Value	250
Submission Rate	279 / 295 (94.58%)
Success Rate	187 / 279 (67.03%)
High Score	vlad_D for 248.77 points (2 mins 0 secs)
Average Score	206.84 (for 187 correct submissions)

The answer for this problem is the total number of pairs N subtracted by the number of already matched pairs. Clearly, if you remove all already matched pairs, all the remaining boots will be of different size. So either all left or all right shoes should be replaced.

Here is the sample code:

public class BootsExchange {
    static final int MAX_SIZE = 1000;

    public int leastAmount(int[] left, int[] right) {
        int n = left.length;
        int[] leftCount = new int[MAX_SIZE];
        int[] rightCount = new int[MAX_SIZE];
        for (int i = 0; i < n; i++) {
            leftCount[left[i] - 1]++;
            rightCount[right[i] - 1]++;
        }
        int same = 0;
        for (int i = 0; i < MAX_SIZE; i++)
            same += Math.min(leftCount[i], rightCount[i]);
        return n - same;
    }
}

Value	500
Submission Rate	207 / 295 (70.17%)
Success Rate	31 / 207 (14.98%)
High Score	DaTval for 468.51 points (7 mins 27 secs)
Average Score	304.26 (for 31 correct submissions)

Value	250
Submission Rate	278 / 293 (94.88%)
Success Rate	131 / 278 (47.12%)
High Score	ACRush for 246.92 points (3 mins 10 secs)
Average Score	188.15 (for 131 correct submissions)

The solution of this problem is pretty straightforward and based on the greedy approach. First we need to put at the first place the greatest number we can. To do this we need to choose the greatest element with index no more than nSwaps and move it to the first place using arbitrary amount of swaps. Decreasing nSwaps by the corresponding number of moves, repeat the process unless nSwaps will be zero or all the positions in the array will be processed.

Natural implementation of the described algorithm has the time complexity O(n²), where n is the size of the given array.

Value	1000
Submission Rate	54 / 295 (18.31%)
Success Rate	1 / 54 (1.85%)
High Score	abi20sg for 461.10 points (43 mins 23 secs)
Average Score	461.10 (for 1 correct submission)

Let integer number i have the canonical decomposition p1^a1p2^a2 ... pk^ak, where p1 < p2 < ... < pk are prime numbers and a1, a2, ..., ak are greater than zero. Let divs[i] be the sum of a1, ..., ak for the number i, in case of k=1 divs[i] should be decreased by one.

Obviously the number is prerime if and only if it is equal to the product of two distinct primes or to some prime raised to the third power. Therefore number i is prerime if and only if divs[i] is equal to 2.

Let's iterate through all numbers from 2, assuming the value of divs[i] is already calculated before i-th iteration -- hence if divs[i] is zero, the number i is prime. In this case increase divs[j] by corresponding value for all j divisible by i.

For clarification see the sample code below:

public class PreprimeNumbers {
    public static int MAX_VALUE = 6000000;
    public int nthNumber(int n) {
        int cnt = 0, i;
        int[] divs = new int[MAX_VALUE];
        for (i = 2; cnt < n; i++) {
            if (divs[i] == 0) {
                for (int j = 2 * i; j < MAX_VALUE; j += i) {
                    int t = j;
                    while (t % i == 0) {
                        divs[j]++;
                        t /= i;
                    }
                    if (t == 1) {
                        divs[j]--;
                    }
                }
            }
            if (divs[i] == 2) {
                cnt++;
            }
        }
        return i - 1;
    }
}

Value	500
Submission Rate	104 / 293 (35.49%)
Success Rate	10 / 104 (9.62%)
High Score	misof for 349.94 points (20 mins 33 secs)
Average Score	244.13 (for 10 correct submissions)

To solve this problem it is necessary to have a way to get bridges in order of appearance. Let's put first bridge from each sequence to the priority queue. The top bridge in the queue is the current one. After the retrieving of the current bridge from the queue, let's put the next bridge from the corresponding sequence to the queue. The position of the next bridge can be easily found by increasing the current position by the corresponding period. Knowing the current position of the robber on the train and his absolute position, it is easy to find the number of carriages he will be able to pass while the next bridge will be above him. Here is the sample java code doing this:

double carriagePassTime = (1.0 * length) / robberSpeed;
double timeAdd = (nearestBridge - posAbsolute) / (trainSpeed + robberSpeed);
int carriagesAdd = (int)Math.floor(timeAdd / carriagePassTime + EPS);

carriagesAdd * length

Value	1000
Submission Rate	44 / 293 (15.02%)
Success Rate	6 / 44 (13.64%)
High Score	marek.cygan for 724.12 points (19 mins 8 secs)
Average Score	561.12 (for 6 correct submissions)

Among all the shortest sequences of the moves exists at least one in which all operations of the merge precedes the operations of the split. Let's consider the sequence of the moves where some split stands before merge. We can't swap them if and only if the operation of the merge uses one of the resulting piles of the split operation. Among such pairs of split and merge operations let's choose one in which the distance between the merge and the split is the least. Let's denote the pile was split with a, the resulting piles with a1 and a2. Let pile b be merged with pile a1 and c is the result of this operation. So in two moves from the piles a and b we got the piles a2 and c. The same result can be achieved by merging piles a and b and then splitting the resulting pile to a2 and c. So we showed that it is possible to swap the split and merge operations without increasing the number of the moves.

Use so-called "meet-in-the-middle" technique to find the shortest sequence where all merges precedes the splits. With a brute force algorithm ,let's build a list of all states which can be reached from startState using only merge operations, and build a similar list of the states reachable from finishState. Find the common elements from both lists, state which has the maximal size, and call it greatestCommonState. Therefore the answer for the problem is

size(startState) + size(finishState) - 2 * size (greatestCommonState)

This problem has another solution based on DP.