Get Time
statistics_w  Match Editorial
SRM 307
Wednesday, June 14, 2006

Match summary

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

BootsExchange rate it discuss it
Used as: Division Two - Level One:
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;
PartSorting rate it discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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(n2), where n is the size of the given array.

PreprimeNumbers rate it discuss it
Used as: Division Two - Level Three:
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 p1a1p2a2 ... pkak, 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) {
                        t /= i;
                    if (t == 1) {
            if (divs[i] == 2) {
        return i - 1;
TrainRobber rate it discuss it
Used as: Division One - Level Two:
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);
The next robber position on the train is equal to the sum of his current position and
carriagesAdd * length
. The next absolute position of the robber is equal to the position of the next bridge.

SplitAndMergeGame rate it discuss it
Used as: Division One - Level Three:
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.

By Mike Mirzayanov
TopCoder Member