Match Editorial

Match summary

It was the first SRM after the TopCoder Open, and coders weary from the TCO were greeted by a problem set hard enough to be used onsite. In both divisions nobody solved all three problems and only 144 Division 1 coders were able to solve at least one problem.

lyc1977, a yellow rated coder from Hong Kong, won the match in a close race with Triple_M from New Zeland and Krzysan from Poland. Two Russian coders - kia and Zhukov_Dmitry closed the top five in the first Division. Another notable finish was blueblimp, who managed to take the 40th spot without solving any problem thanks to his +300 in challenges!

Malkava regained his blue rating by winning second the Division with two solved problems and four successful challenges.

The Problems

Value	250
Submission Rate	439 / 490 (89.59%)
Success Rate	274 / 439 (62.41%)
High Score	DavidAlves for 248.23 points (2 mins 24 secs)
Average Score	197.76 (for 274 correct submissions)

This problem is about accuracy in implementing what you're asked for. You need to implement a function (or use standard), that replaces all occurrences of one subword with another word. After that you need to apply all the translation rules, in the order that they appear in the problem statement. It's easy to see that the order is important. For example, if you start with replacing all "at" by '@', the subword "ate" will never appear further, so the rule about '8' will be useless. Another tricky case is about subwords, which may appear after removing punctuation symbols. For example, "a.n.d" must be translated as "&".

For brief implementation, see DavidAlves's solution in Java and Malkava's solution in C++.

Value	500
Submission Rate	121 / 490 (24.69%)
Success Rate	3 / 121 (2.48%)
High Score	Rustyoldman for 246.85 points (38 mins 21 secs)
Average Score	224.88 (for 3 correct submissions)

Value	250
Submission Rate	331 / 392 (84.44%)
Success Rate	131 / 331 (39.58%)
High Score	Egor for 242.28 points (5 mins 6 secs)
Average Score	170.02 (for 131 correct submissions)

Consider some mark m. Let's denote its real value by r (i.e. m is the result of truncation r's decimal notation as it was described in the problem statement). r can be represented as a rational fraction, r = p/q. Here q is the number of the participants of the survey, and p is an integer in range from 0 to 10q.

The key observation is the following inequality: m ≤ p/q < m+0.001. In other words, 1000mq ≤ 1000p < (1000m+1)q.

Now we are going to fix some q and to check if there exists such p, that satisfies the inequality above. To avoid problems with precision, let's get rid of real-valued numbers: 1000m is always an integer in range from 0 to 10000, we'll denote it by n (The easiest way is just to remove all dots ('.') from the input and parse marks as integers.).

The inequality now will look as: nq ≤ 1000p < (n+1)q.

It's easy to see that the required p exists if and only if interval [nq; (n+1)q) (left bound inclusive, right - not) contains an integer that is divisible by 1000. Note, that if q ≥ 1000, such p always exists. In this case we need to check only denominators in the range from 1 to 999.

How to check if given interval [a, b) contains an integer, divisible by 1000? We need to check only two integers: ([a/1000])*1000 and ([a/1000] + 1)*1000. If one of them belongs to interval [a, b) the answer is yes, and no otherwise.

Value	1000
Submission Rate	21 / 490 (4.29%)
Success Rate	9 / 21 (42.86%)
High Score	ral for 631.28 points (25 mins 1 secs)
Average Score	511.68 (for 9 correct submissions)

This problem can be solved by modification of standard Kruskal algorithm of finding MST (minimal spanning tree) in undirected graph. Cities will be the vertice of that graph, and roads will be its edges. Each damaged road will provide the corresponding edge the weight that equals the cost of the reconstruction. Other (non-damaged) roads will have weight 0.

Now, let's sort all the edges in ascending order of their weights, and in the case of a tie - in the lexicographical order of their identifiers.

The Kruskal algorithm gives us the minimal spanning tree. Finally, to obtain the answer to the problem let's remove all edges that don't need to be reconstructed from MST. Don't forget to sort the remaining identifiers in the lexicographical order!

For implementation details see Zhomart's solution.

Value	550
Submission Rate	85 / 392 (21.68%)
Success Rate	27 / 85 (31.76%)
High Score	ahyangyi for 446.75 points (14 mins 21 secs)
Average Score	309.26 (for 27 correct submissions)

This problem can be easily reformulated in terms of bipartite graphs. But despite this, it shares nothing with the matchings.

First, note that the answer is "-1" if and only if there exists a man (or woman) that dislikes all people of the opposite gender. Therefore, we check that condition at the beginning.

Now, let's consider one special type of marriage: when a person marry himself. Such marriages are not allowed by the problem statement, but it's easy to see that they will never appear in an optimal solution. Therefore, allowing such strange kind of marriages won't change the answer to the problem.

Now, let's fix some subset of men, and some subset of women. We designate each of them to his (her) own marriage group and try to distribute all other people among those groups, if it's possible. As we'll show below, such check can be done at O(n), which provides us an O(n2^n) solution by bruteforcing for all the subsets (here n is the total number of men and women).

For a subset X of men (or women) we define D(X) as a subset of people of the opposite gender, such that each member of D(X) can marry with at least one member of X. Now, if we fix some subset X of men, and subset Y of woman we just need to check if X + D(Y) includes all men, and Y + D(X) includes all women. Such a check can be obviously done in O(n^2), and it can be improved to O(n) by storing preferences as a bit masks.

Also, there are two optimizations which will allow it to work much faster. Firstly, note that there always exist a solution with [n/2] marriages - we can select either all men, or all women. Now, if we have some current answer x, we'll consider only subsets X and Y, such that the cardinality of X+Y is smaller then x. This will allow us to consider at most half of the subsets in the worst case and much less on average.

Second, for fixed subset X we can calculate D(X) and consider only such subsets Y, that X+D(Y) includes all women. Being combined, the given two optimizations will allow us to fit the time limit with a huge gap.

Value	950
Submission Rate	92 / 392 (23.47%)
Success Rate	11 / 92 (11.96%)
High Score	Triple_M for 787.22 points (13 mins 30 secs)
Average Score	566.69 (for 11 correct submissions)

This problem can be reduced to a system of linear equations. First of all, let's check if there exists an exit, reachable from the starting position of a prisoner. If not, the answer is "-1", in the other case the expected number of moves is always finite.

Now, let's denote the expected number of moves to reach the exit from row i and column j by X[i][j]. If position (i,j) is the exit cell, X[i][j] equals to zero. In the other case it will satisfy the following linear conditions:

X[i][j] = 1 + (X[i + 1][j] + X[i-1][j] + X[i][j+1] + X[i][j-1]) / D[i][j],

where D[i][j] will be the number of free cells, adjacent to position (i,j). Also, we consider X[p][q] = 0 for occupied and non-existing cells. (i.e. if there is a wall at position (p,q) or if this position is outside the jail).

Combining such equations for every cell, reachable from the initial position of the prisoner, we'll obtain a system of linear equations that will give us an answer.

See kia's solution for clear implementation.