JOIN
Get Time
statistics_w  Match Editorial
Archive
Printable view
 Match Overview
Discuss this match
SRM 350
Wednesday, May 23, 2007

Match summary

Division 2 was marked with a tricky medium and quite a straight-forward hard. This led to many coders solving the hard one but failing the medium. Thus a plan of skipping the 500-pointer and moving straight to the 1000-pointer 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 250-pointer and the 500-pointer as all the corner cases of the 1000-pointer 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 all-time rating record, which also belongs to him.

The Problems

DistanceBetweenStrings rate it discuss it
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 straight-forward; the major bugs were in misunderstanding the definition of the distance between two strings and handling the case-sensitiveness.

As upper-case and lower-case letters were regarded the same, and letterSet contained only lower-case letters, it was convenient to turn both given strings a and b into lower-case 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 rate it discuss it
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 32-bit 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 (22372 > 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 22362 < 5000000 but 22363 is too big for 32-bit 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 rate it discuss it
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 non-zero. 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 non-zero. 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 non-zero. 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 non-zero 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 rate it discuss it
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 2D – 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 bug-prone 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 Bellman-Ford algorithm or its variations.

We use Bellman-Ford 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 rate it discuss it
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 4-tuple 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 non-empty. 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.

Author
By Xixas
TopCoder Member