
Match Editorial 
SRM 356Monday, July 2, 2007
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
SMSLanguage
Used as: Division Two  Level One:
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++.
AverageProblem
Used as: Division Two  Level Two:
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)

Used as: Division One  Level One:
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 realvalued 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.
RoadReconstruction
Used as: Division Two  Level Three:
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 (nondamaged) 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.
MarriageProblemRevised
Used as: Division One  Level Two:
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.
EscapeTheJail
Used as: Division One  Level Three:
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[i1][j] + X[i][j+1] + X[i][j1]) / 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 nonexisting 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.