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 ProblemsBootsExchangeUsed as: Division Two  Level One:
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 Used as: Division Two  Level Two: Used as: Division One  Level One:
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^{2}), where n is the size of the given array. PreprimeNumbersUsed as: Division Two  Level Three:
Let integer number i have the canonical decomposition p1^{a1}p2^{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 ith 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; } }TrainRobber Used as: Division One  Level Two:
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 Used as: Division One  Level Three:
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 socalled "meetinthemiddle" 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. 
