
Match Editorial 
SRM 350Wednesday, May 23, 2007
Match summary
Division 2 was marked with a tricky medium and quite a straightforward
hard. This led to many coders solving the hard one but failing the medium. Thus
a plan of skipping the 500pointer and moving straight to the 1000pointer really
paid off. However, all three correct submissions were crucial in order to
guarantee oneself a comfortable place at the very top. Division 2 was won by
voidProject, who achieved an impressive score of 1706.50
with the help of 6 successful challenges, while codenameHarmony and
Torax took second^{} and third^{}
place respectively.
Division 1 was another story, though the medium was again trickier than the
hard. The challenge bait was the 250pointer and the 500pointer as all the
corner cases of the 1000pointer were covered in the examples.
ACRush submited the hard problem for an amazing
amount of 952.28 points early in the Coding Phase. Alas, he had to resubmit but
despite this managed to finish third ^{}. With the fastest
submission of the hard, Petr won the match with a comfortable lead on
gawry, who took the second prize. This SRM brought
Petr really close to the alltime rating record,
which also belongs to him.
The Problems
DistanceBetweenStrings
Used as: Division Two  Level One:
Value

250

Submission Rate

500 / 521 (95.97%)

Success Rate

301 / 500 (60.20%)

High Score

marutiborker for 248.61 points (2 mins 8 secs)

Average Score

206.12 (for 301 correct submissions)

This problem was quite straightforward; the major bugs were in
misunderstanding the definition of the distance between two strings and
handling the casesensitiveness.
As uppercase and lowercase letters were regarded the same, and letterSet
contained only lowercase letters, it was convenient to turn both given strings a
and b into lowercase at the very beginning. Next, as all
the letters in the letterSet were guaranteed to be distinct,
we just had to calculate the distance between a and b
with respect to each of them and sum the obtained distances to get the answer.
Java code implementing this approach follows.
public int getDistance(String a, String b, String letterSet)
{
a = a.toLowerCase();
b = b.toLowerCase();
int ans = 0;
for(int i = 0; i < letterSet.length(); i++) {
int occa = 0, occb = 0;
char temp = letterSet.charAt(i);
for(int j = 0; j < a.length(); j++) if(a.charAt(j) == temp) {
occa++;
}
for(int j = 0; j < b.length(); j++) if(b.charAt(j) == temp) {
occb++;
}
ans += (occa  occb) * (occa  occb);
}
return ans;
}
SumsOfPerfectPowers
Used as: Division Two  Level Two:
Value

500

Submission Rate

147 / 521 (28.21%)

Success Rate

55 / 147 (37.41%)

High Score

danielrocha for 449.98 points (9 mins 41 secs)

Average Score

268.01 (for 55 correct submissions)

Used as: Division One  Level One:
Value

250

Submission Rate

380 / 465 (81.72%)

Success Rate

313 / 380 (82.37%)

High Score

Triple_M for 245.18 points (4 mins 0 secs)

Average Score

174.00 (for 313 correct submissions)

With many coders in both divisions overlooking the possibility of
overflowing the 32bit integer variables, or loathing to implement an array of
5000000 booleans, this problem turned out to be a tricky one.
To begin with, let us calculate all the perfect powers that do not exceed
5000000 and store them in an array s. 0 and 1 are
clearly perfect powers so put them in s. Determine
the remaining elements of s iterate through all the
integers greater than 1 and less than 2237 (2237^{2} > 5000000) and,
given such integer, put all its integer powers not exceeding 5000000 into
s. To avoid duplicate elements in
s use an array of 5000001 booleans to look up whether a
certain number is already in s:
vector<int> s;
boolean lookup[5000001];
for(int i = 0; i <= 5000000; i++) lookup[i] = false;
s.push_back(0);
s.push_back(1);
lookup[0] = true;
lookup[1] = true;
for(int i = 2; i < 2237; i++) {
long long a = i;
while (a <= 5000000) {
a *= i;
if (!lookup[a]) {
s.push_back(a);
lookup[a] = true;
}
}
}
To this point many coders failed by declaring
a in
the above code as an int. This would lead to an overflow when i = 2236 since 2236
^{2} < 5000000 but 2236
^{3} is
too big for 32bit integers.
Secondly, iterate through all pairs of elements of
s
and mark their sum in the
lookup as
true if it does not exceed 5000000 (we can still use
lookup since every perfect power is clearly the sum of
two perfect powers – zero and itself):
for(int i = 0; i < s.size(); i++)
for (int j = 0; j <= i; j++)
if (s[i] + s[j] <= 5000000)
lookup[s[i] + s[j]] = true;
It is hard to determine the exact maximal size of
s
from scratch but one may convince oneself in many ways that it does not exceed
3000 so the above code will not time out.
At the current moment
lookup is
true for exactly those i which are representable as the
sums of two perfect powers. All that remains is counting such i between
lowerBound and
upperBound, inclusive:
int ans = 0;
for(int i = lowerBound; i <= upperBound; i++)
if (lookup[i])
ans++;
return ans;
For the complete implementation of this approach consult
ploh's
code.
BagsQuiz Used as: Division Two  Level Three:
Value

1000

Submission Rate

164 / 521 (31.48%)

Success Rate

92 / 164 (56.10%)

High Score

punzki for 926.11 points (8 mins 9 secs)

Average Score

604.68 (for 92 correct submissions)

The problem was quite easy for a Division 2 hard and hence the number of
coders solving it correctly was rather high.
To solve it note that the inside relation suggests that
storing for every bag i the number of the bag j such that i is inside
j might be helpful. Indeed, let's denote inside[i]=j
in this case, where inside[i]=0 if the bag i is
currently lying on the floor. Initially all the bags are on the floor so the
array inside is filled with zeroes. Analyzing the
elements of actions one by one and altering
inside accordingly is now the core of the solution. The
updating of inside depends on the action encountered:
 If it is "PUT i INSIDE j" check if either
inside[i] or inside[j] is nonzero.
If so, return 1, else set inside[i]=j.

If it is "SWAP i WITH j" check if either
inside[i] or inside[j] is
nonzero. If so, return 1. Else iterate through all the bags and if you find a
bag k such that inside[k]=i then set
inside[k]=j and vice versa.

If it is "SET i LOOSE" then check if
inside[i] is nonzero. If so, return 1. Else iterate
through all the bags and if you find a bag k such that inside[k]=i set inside[k]=0.
After the analysis of the contents of
actions is complete
one must check if the obtained configuration is proper. To do this simply
iterate through all the bags and if you find any i such that
inside[i] is nonzero and
inside[i]
return 1, since then bag i would lie
inside a bag with a
smaller number. Else the obtained configuration is a proper one and to count
the number of bags lying on the floor iterate through all of them to find the
number of such i that
inside[i] is zero. For the
implementation of this approach see
Torax's
solution.
Analyzing the elements of
actions requires some
string parsing skills, which can be honed
here.
StarsInGraphs Used as: Division One  Level Two:
Value

500

Submission Rate

288 / 465 (61.94%)

Success Rate

128 / 288 (44.44%)

High Score

ACRush for 464.74 points (7 mins 56 secs)

Average Score

307.53 (for 128 correct submissions)

First, note that the star number of a vertex is a monotonously increasing
function of its degree. This is clear – the more outgoing edges there are, the
more possibilities to combine a set of them into the rays of a star.
Second, let us determine the star number of a certain vertex of degree D.
To do so note that the star centered at this vertex is uniquely determined by
the set of its rays. Since the empty set and the sets having cardinalities 1 or
2 must be discarded, the star number of such vertex is 2^{D} – D*(D –
1)/2 – D – 1. Knowing how to calculate the star number of a vertex given its
degree we may find the maximal degree maxDeg that gives
this number <= C, i.e. the maximal degree of a vertex
that may appear on a starry path.
Knowing maxDeg we may forget about the star numbers –
the problem becomes finding the longest path in which the first vertex has a
degree not less than 3 and not more than maxDeg and
every subsequent vertex has a degree not less than its predecessor and not more
than maxDeg.
From this point on a multitude of different approaches arise. Alas, as shown
by a great amount of failed submissions, some of them are quite bugprone or
even incorrect. Though the plain vanilla version of Depth First Search (DFS) is
doomed to time out one may still insist on using DFS with memorization.
However, the most elegant, in my opinion, solution uses BellmanFord algorithm or its
variations.
We use BellmanFord on each vertex satisfying the degree condition
simultaneously – initialy all the distances to vertices with a degree in the
range [3; maxDeg] are set to 1. The distances to other
vertices are equal to infinity.
We treat every edge in our graph to be of weight 1. Thus after n (n is the
number of vertices in our graph) steps 2 described in the above link we must
perform step 3 to determine whether we have a negative cycle and, if this
is not the case, find the minimum distance to a single vertex and return minus
this quantity.
For a detailed version of this solution see Petr's solution.
PlaneDivision Used as: Division One  Level Three:
Value

1000

Submission Rate

50 / 465 (10.75%)

Success Rate

31 / 50 (62.00%)

High Score

Petr for 730.15 points (18 mins 47 secs)

Average Score

593.55 (for 31 correct submissions)

What we have in this problem determined by the lines is a planar graph
and we have to determine the number of its finite faces. This suggests that
Euler's formula for planar graphs V + F – E = 2 may come in handy. Here V is
the number of vertices of the graph, F – the number of its faces (both finite
and infinite) and E – the number of its edges. If you are unfamiliar with
this formula and the concept of planar graphs cast a glance here.
First, we would want to know the total number of vertices V in our planar
graph. To find it we will find all the intersection points of the given lines
(V will be equal to this number plus 1, which stands for the vertex 'at
infinity' through which all the lines pass). Intersection points can be stored
in many ways:
 As a pair of indices (i, j) of lines that
intersect in that particular point.

As a 4tuple of integers (a, b, c, d) where the
intersection point coordinates are a/b and c/d respectively. (It is easy to see
that the lines may only intersect at points with rational coordinates).

As a pair of doubles (x, y) where x and y are
the respective coordinates of the intersection point. For this to work one had
to note that the constraints were too low for two intersection points to get
really close, so choosing adequate precision for comparing whether two
intersection points are actualy the same was enough.
Initially the set of intersection points is empty. For each intersection
point we store it (in either of the aforementioned ways) and the set of lines
that pass through it. We process each pair of two distinct given lines one by
one and determine whether their intersection point coincides with any of the
points that we already have. If so, we update the set of lines that pass
through this point, else we add a new intersection point and mark that these
two lines pass through it. To accomplish this we need to know how to determine
the coordinates of the intersection point of two lines and how to determine
whether the two given lines are parallel (in this case their intersection point
does not exist). This is a standard procedure and to inspect it in further
detail see the geometry tutorial
here.
Now that we have determined the intersection points we have to distinguish
between two cases. In the first one, the set of intersection points is empty,
i.e. we have a bunch of parallel lines. Clearly we have no finite regions then
and return 0. In the second one, this set is nonempty. To determine the total
number of edges it is convenient to examine the given lines one by one. Since
there exist two intersecting lines in this case we easily see that every line
must intersect at least one other line. If the number of intersection points
that the line pass through is
a, then the number of edges
lying on this line is clearly
a + 1. Hence the total number
of edges E will be the sum of such (
a + 1)'s for all given
lines. To find
a for a certain line iterate through all the
intersection points to see through how many of them the line passes.
Now that we have V and E we may find F from the aformentioned Euler's
formula: F = 2 + E – V. All that is left is to determine the number of infinite
regions, which is 2n (n is the number of given lines) in this case. A rigorous
proof of this fact goes by induction and is left to reader. Hence the required
answer is F – 2n.
For a clear implementation of this approach see
Petr's
solution.