Match Editorial

SRM 274 was won by Petr with 1862.76 points, with the second-fastest time on each of the three problems, and 5 successful and 2 unsuccessful challenges. Zis took second on 1602.75 points and MikeMirzayanov third with 1542.67.

In Division Two, newcomer zhuzeyuan had a clear victory with correct solutions to the three problems in 3 minutes, 5 minutes and 20 minutes respectively, and a flawless 6 challenges for a total of 1755.04 points. m4t3o was second with 1305.38 points and another newcomer rkistner took third with 1300.73.

The writer for this match's problems was Andrew_Lazarev.

The Problems

Value	250
Submission Rate	306 / 323 (94.74%)
Success Rate	275 / 306 (89.87%)
High Score	CoreDumped for 248.01 points (2 mins 32 secs)
Average Score	206.54 (for 275 correct submissions)

This problem was a simple exercise for the Division Two coders. Given a list of integers, remove all but the last occurrence of every integer that occurs more than once, and return the result.

To solve this we can consider each element of the list in order, check if the same integer occurs later in the list, and add it to a second list if it doesn't. We then return the second list.

This problem had a very high success rate, but some coders still failed the problem, either failing to understand the question, not planning out a proper algorithm, or in one unfortunate case, passing the wrong parameters to the memset() library function.

Value	500
Submission Rate	237 / 323 (73.37%)
Success Rate	138 / 237 (58.23%)
High Score	zhuzeyuan for 488.46 points (4 mins 23 secs)
Average Score	344.21 (for 138 correct submissions)

Value	250
Submission Rate	248 / 249 (99.60%)
Success Rate	227 / 248 (91.53%)
High Score	Per for 247.14 points (3 mins 3 secs)
Average Score	217.93 (for 227 correct submissions)

In this problem we have to form a palindrome, a string that does not change when reversed, by rearranging a given string of letters. In particular, we want the lexicographically-minimum such palindrome.

It is easy to check if this is possible. If there's an even number of each letter, then we can keep taking two of a letter out of the input string and put one on each end of the output string. Since we want the lexicographically minimum string, we choose the letters later in the alphabet first, and finish with the earlier letters so that they occur first in the output string.

If one letter occurs an odd number of times, then we can simply remove one of these letters from the input string, form the minimum palindrome, and then put the odd letter back in the middle.

If more than one letter occurs an odd number of times, then we cannot form a palindrome from the input string, and we return the empty string as the problem requires.

The most common way to solve this problem was to first build an array of 26 integers which contains the number of times each letter occurs, then check if there are zero, one or more letters that occur an odd number of times, and then construct the output string from this array.

Value	1000
Submission Rate	133 / 323 (41.18%)
Success Rate	11 / 133 (8.27%)
High Score	RangerXL for 719.84 points (19 mins 22 secs)
Average Score	559.07 (for 11 correct submissions)

This is a variation of the "stamp problem." We have an unlimited supply of two types of bills, one worth p1 dollars and one worth p2 dollars. We want to find the minimum dollar value that is at least D that we can construct from the two types of bills.

Equivalently, we want to find the minimum E, where E>=D and the equation X * p1 + Y * p2 = E can be solved where X and Y are non-negative integers.

The largest sensible value of X to try is D/p1, rounded up, since with that many p1-dollar bills we will have a total of at least D dollars.

We can try each value of X from 0 to D/p1+1, and for each of these we find the total when we add enough p2-dollar bills to bring that total up to at least D. Then we take the minimum of these totals.

If we make p1==1 a special case, then this can be implemented just barely fast enough in C++.

A further observation will allow us to bring the run time down significantly. p2 bills of value p1 dollars each are interchangeable with p1 bills of value p2 dollars each.

So if we have a solution where X is at least p2, then we can replace p2 of those p1-dollar bills with p1 p2-dollar bills. So we do not need to consider values of X larger than p2, as any value we can create with X p1-dollar bills can be created with (X-p2) p1-dollar bills.

So the maximum value of X we need to consider is min(D/p1+1,p2). If we ensure p1 is greater than p2, swapping the two if necessary, then this will be at most about sqrt(D) iterations, which is easily under time.

Here is a short solution by misof, written after the contest. An explanation of how it works is left as an exercise to the reader!

#define X approximate
int X(int D, int p, int q) {
	return D/p>=q ? q ? X(D,q,p%q) : (D+p-1)/p*p : D>0 ? p<q ?
		X(D,q,p) : ( p+X(D-p,p,q) <? (D+q-1)/q*q ) : 0;
}

Value	500
Submission Rate	131 / 249 (52.61%)
Success Rate	58 / 131 (44.27%)
High Score	ivan_metelsky for 474.80 points (6 mins 36 secs)
Average Score	295.35 (for 58 correct submissions)

Here we are given a Dyck path as a string of 'X's and 'Y's. We are told that two Dyck paths are equivalent if we can turn one into the other by a series of operations where we swap two adjacent substrings which are each Dyck paths. We must find the lexicographically-minimum Dyck path that is equivalent to the input string. If the input string is not a valid Dyck path, we return "".

Dyck paths are equivalent to rooted ordered trees. We can form the tree by beginning at the root, and taking each letter of the string in sequence. For each 'X', we draw a new edge down from the current node and create a new node. For each 'Y', we follow the edge from the current node up to its parent. We can reverse this process to form the string from a tree. If the children of a node are equivalent to the strings (S1),(S2),...(Sn), then that node is equivalent to the string X(S1)YX(S2)YX(S3)Y...X(Sn)Y.

In this rooted tree, the operation of swapping adjacent Dyck paths is equivalent to swapping two adjacent children of the same node. Therefore we can reorder the children of any node. So to find the tree corresponding to the lexicographically-minimum string, we want to recursively transform each child of the root node into the minimum equivalent node, and then sort the children in lexicographic order.

Here is psuedocode for this function:

min(S)
	decompose S into Dyck paths XS1Y, XS2Y, ... XSnY
	for i=1..n
		Si=min(Si)
	sort(S1..Sn)
	return XS1YXS2YXS3Y...XSnY

dyck(S)
	X=0,Y=0
	for each s in S
		if(s=='X')
			X++
		else
			Y++
		if (Y>X) return false
	if(X!=Y) return false
	return true

Value	1000
Submission Rate	79 / 249 (31.73%)
Success Rate	48 / 79 (60.76%)
High Score	rem for 967.66 points (5 mins 13 secs)
Average Score	744.57 (for 48 correct submissions)

In this problem, we clearly can't simulate the process N times, since N can be up to one billion.

If we consider the circle of numbers to be a vector, then performing one summing operation is equivalent to multiplying the vector by this matrix:

    [1 1 0 0 0]
    [0 1 1 0 0]
S = [0 0 1 1 0]
    [0 0 0 1 1]
    [1 0 0 0 1]

S^2 = S * S
S^4 = S^2 * S^2
S^8 = S^4 * S^4
S^11 = S * S^2 * S^8.