Match Editorial

Match summary

In both divisions competitors faced relatively strightforward easy and medium problems, but tough hard problems which only elicited a single passing submission between them. The only passing hard submission from zhuojie handed him the win in division 1. An excellent performance from redocpod in only his fifth rated event put him in second place, with Rizvanov_de_xXx completing the top three. In division 2, fast submissions on the easy and medium problems with a couple of successful challenges won ahmed_aly the division by a comfortable margin, with xgy coming second and nike third.

The Problems

Value	250
Submission Rate	579 / 795 (72.83%)
Success Rate	488 / 579 (84.28%)
High Score	nitdgp for 247.21 points (3 mins 1 secs)
Average Score	160.05 (for 488 correct submissions)

This restaurant operates a first-come, first-served policy on its tables and you are tasked with working out how much business they will lose with this policy. As with many division II easy problems, the solution simply involves carefully simulating the process to arrive at the answer. Step through the arrivals in sequence and as each group arrives determine which table it should be allocated. A useful trick is to maintain a list of the times at which each table will become available. This is set to the departure time of the group to which the table is allocated. It is then very simple to determine whether a table is available at a given time.

Value	500
Submission Rate	154 / 795 (19.37%)
Success Rate	63 / 154 (40.91%)
High Score	ahmed_aly for 458.37 points (8 mins 43 secs)
Average Score	267.78 (for 63 correct submissions)

Value	250
Submission Rate	444 / 557 (79.71%)
Success Rate	315 / 444 (70.95%)
High Score	krijgertje for 247.42 points (2 mins 54 secs)
Average Score	172.71 (for 315 correct submissions)

First notice that if we know the time that we start filling in the forms, then solving this problem is very simple: just fill in every form as soon as you have received it and get it approved at the first point in time when the embassy is open after you have finished filling it in. But how do we know when to start? With a day being potentially 10⁶ time units long, a brute force over start time will work if it is efficiently implemented. However, there is a much more efficient solution, which is nearly as easy to implement. The key here is noticing that there is always an optimal solution where some form is approved just as the embassy is opening. This is straightforward to prove: take any optimal solution where this isn't the case. If at any point you had completed a form before the embassy had opened, you would be waiting and would get it approved right as the embassy opens. Otherwise, you never have to wait and such a solution can be shifted back in time, without changing the length of time it takes until the point where some form is filled out right at the opening time.

We therefore have a maximum of 50 starting times, so we can try them all. Assume for simplicity that the embassy opens each day at time 0 and closes at time openTime. Initially set the starting time to zero, then for each form, first shift the starting time back by the length of time it takes to fill it in, so that we arrive at the embassy just as it opens, then simulate the whole process. The optimal time is just the minimum over all the starting times you try. A helpful trick in this problem is noticing that you can work modulo dayLength, which makes it easy to work out whether the embassy is open or not.

Value	1000
Submission Rate	6 / 795 (0.75%)
Success Rate	0 / 6 (0.00%)
High Score	No correct submissions
Average Score	No correct submissions

This question asks you to canonicalize the description of a 3D volume. Such a canonicalization might be useful if you wanted to check whether 2 shapes were the same, for example. Unfortunately, this was rather tricky for a division 2 problem and nobody managed to get a working solution during the contest.

The first step is to realise that there are only a finite number of rotations the we need to consider, 24 to be exact. We can therefore simply try every possible rotation and take the one that gives the lexicographically minimum description. However, generating all 24 rotations is a tricky little problem in itself. The are many different ways to do this, such as by successive rotation around each coordinate axis, but you have to be very careful to ensure you generate all the possible rotations. A simpler and less error-prone way of generating the rotations is to use vectors. Notice that rotating the shape is the same as describing the shape in a rotated set of axes. However, we are only interested in coordinate systems whose axes are parallel with the current axes. We can therefore pick any two non-parallel directions out of the 6 axis directions to be our new i and j axes and then calculate k to form a right-handed set. We then resolve the shape into this new coordinate system. This sounds an awful lot more complicated than it actually is, particularly if you have a pre-written 3D vector class. c++ pseudocode follows.

int Axis1 [] = {1,0,0,-1,0,0};
int Axis2 [] = {0,1,0,0,-1,0};
int Axis3 [] = {0,0,1,0,0,-1};

vector <vec3> vShape;
// vShape stores the coordinates of the cubes as 3D vectors

for (int i=0;i<6;i++)
    for (int j=0;j<6;j++)
        if ((i%3) != (j%3)){ // 2 non-parallel directions

            // i, j and k need to form a right-handed set
            vec3 iAxis(Axis1[i], Axis2[i], Axis3[i]);
            vec3 jAxis(Axis1[j], Axis2[j], Axis3[j]);
            vec3 kAxis = iAxis.cross(jAxis);

            // Resolve the shape into the new axes
            vector <vec3> rShape(vShape.size());
            for (int k = 0;k<vShape.size();k++)
                rShape[k] = (vShape[i].dot(iAxis),
                                    vShape[i].dot(jAxis), vShape[i].dot(kAxis));

            ... process the rotated shape ...
        }

That's all there is to generating the rotations. So we have our rotated shape, what now? We need to generate the lexicographically minimum description of that shape under some translation. Firstly, notice that we can always get some x-coordinate to beome 0, since if every coordinate is greater than 0 (we can't have any negative coordinates in our answer), we can always translate the entire shape in the negative x-direction until some x-coordinate becomes 0. So let's work out which x-coordinate will become 0 first and translate the entire shape to make that happen. It now helps to do the same for the y- and z-coordinates. This means that any further translation in the negative x-, y- or z-directions would lead to some coordinate becoming negative, so we only have to consider positive translations. Put differently, we can now increase the coordinates in our shape without limit, but from this point on we can't reduce them any further.

int xmin = INF, ymin = INF, zmin = INF;
for (int k=0;k<rShape.size();k++){
    xmin = min(xmin, rShape.x);
    ymin = min(ymin, rShape.y);
    zmin = min(zmin, rShape.z);
}
for (int k=0;k<rShape.size();k++){
    rShape.x -= xmin;
    rShape.y -= ymin;
    rShape.z -= zmin;
}

So now for the lexicographical minimization. For this we need to minimize the first element of the return, then the second element and so on. However, in this case it is sufficient to only consider the first element. Why? Because the only weapon in our armory is to translate the shape around and no two translations will cause some cube to have the same string representation. So, whichever cube is in the first position of the array will have some translation that minimizes it, and that translation will then determine the positions of the rest of the cubes as well. Consider, therefore, the cube in the first position of the array. Remembering that we can only increase the value of its coordinates, what translation causes it to become lexicographically minimal? It is easy to see that for each coordinate, we need to find the lexicographically minimum number that is greater than, or equal to it. For a number X, the number with this property is either X, if X is 0 or 1, or the smallest power of 10 that is greater than or equal to X. To see that we always end up with a power of 10, just consider the digits in order: unless X is 0, the first digit must be greater than 0, so we look for solutions where this digit is 1. We can always find some number greater than X whose first digit is 1. Similarly, considering the remaining digits, we can always find some number greater than X where each successive digit is set to 0. Therefore, we are always looking for a power of 10.

So now our translation is fully specified and we can apply it to the whole shape. We can then convert each of our cubes to the string representation and sort these in ascending order to given the overall lexicographically minimum array. However, we need to backpedal a bit: how do we know which element is going to end up in the first position? Since there are at most 50 cubes in the shape, we can just try every cube in the first position and take the lexicographically minimum description that results. If the cube that we have tried doesn't actually end up in the first position after sorting, it doesn't matter, as there is no way it could be the first element of the return anyway, because the translation that causes it to become lexicographically minimal causes another cube to be lexicographically less than it.

for (int first=0;first<rShape.size();first++){

    // Find the translation that we want
    int dx = rShape[first].x == 0 ? 0 : 1;
    int dy = rShape[first].y == 0 ? 0 : 1;
    int dz = rShape[first].z == 0 ? 0 : 1;
    while (dx < rShape[first].x) dx *= 10;
    while (dy < rShape[first].y) dy *= 10;
    while (dz < rShape[first].z) dz *= 10;
    dx -= rShape[first].x;
    dy -= rShape[first].y;
    dz -= rShape[first].z;

    // Generate the translated shape
    vector <vec3> tShape(rShape.size());
    for (int k=0;k<rShape.size();k++)
        tShape[k] = vec3(rShape[k].x+dx, rShape[k].y+dy, rShape[k].z+dz);

    // Generate the lexicographically minimum string representation
    vector <string> stringShape = toString(tShape);
    sort(stringShape.begin(),stringShape.end());

    ... store the lexicographically minimum answer that we find ...
}

Value	500
Submission Rate	417 / 557 (74.87%)
Success Rate	285 / 417 (68.35%)
High Score	LayCurse for 488.65 points (4 mins 20 secs)
Average Score	363.54 (for 285 correct submissions)

This problem seems to be a simple ordering problem at first glance, but it has a boundary case that requires a little thinking. Most competitors realised very quickly that the solution is to work from the start of the string and add a single letter at a time. Since we need to minimize the first letter, we choose the smallest first letter out of the words in W, remove it from that word and add it to the return string. We then have a slightly smaller set of words and can simply repeat the process for the remaining letters. Simple, isn't it? Well, not quite, since we also have how to handle the case where 2 or more words start with the same letter. Which word should we choose to remove the first letter from? It seems intuitive that if the first letters are the same, then we should compare the second letter and if they're the same, compare the third letters and so on. This looks very similar to a lexicographic ordering, but there is one very important difference, as we will see later. First of all, let us take a look at why this intuition is correct.

Consider 2 words S₁ and S₂, with some maximal shared prefix P, where the letter following P in S₁ is x₁ and the corresponding letter in S₂ is x₂. Now consider some final interspersal in which c₁ occurs before c₂: what we can show is that we can always generate this exact string up to and including c₁, by choosing the first letter of S₁ first. This is because the prefix of both strings is the same, such that corresponding letters are interchangeable between the strings without changing the result. So if any block of characters from S₂ is chosen before the characters from S₁, when can simply swap them over and choose that block of characters from S₁ first. This is most easily demonstrated by example. If the strings are S₁ = "COMMONPREFIXA" and S₂ = "COMMONPREFIXB" with lexicographically minimum interspersal "CCOMMOMMONONPPREFIREFIXAXB", interspersed as follows:

C    OMM  ONP     REFIXA
 COMM   ON   PREFI      XB
CCOMMOMMONONPPREFIREFIXAXB

There are two blocks here where a letter of S₂ is chosen before a letter of S₁, shown in red and green above. Note that a "block" here is a sequence of consecutive letters in one of the generating strings, which might not be consecutive in the interspersal. Since the blocks are the same in each string, we can simply swap them over:

C OMM   ON  P REFI    XA
 C   OMM  ON P    REFI  XB
CCOMMOMMONONPPREFIREFIXAXB

Now every letter in S₁ (including the first) is chosen before the corresponding letter in S₂. The other thing to notice is that if we swapped the strings entirely and chose every letter from the other string, then the resulting interspersal wouldn't change before the original position of c₁, but rather than c₁ appearing there c₂ would appear in its place. This means that c₁ must be alphabetically earlier than c₂, since otherwise we could generate a lexicographically smaller interspersal just by swapping the strings in the input. So what we have shown is that for any two strings, the alphabetically earlier character in the first position at which they differ will come earlier in the resulting interspersal, and it is always possible to achieve this by choosing letters from the string that contains the earlier letter before the corresponding letters of the other string.

However, there is a catch: what if there are no differing letters and one string is a proper prefix of another? Actually, it's quite easy to extend the logic above to show that any interspersal can be changed to one where letters from the longer string are chosen first without changing the resulting string. This leads us to a "tie-breaking" rule that is the opposite of the standard lexicographical comparison.

So the correct solution to this problem is as follows: define an ordering of the strings, where that a string S₁ occurs before a string S₂ if S₁ either has the earlier character at the first position at which they differ, or S₂ is a proper prefix of S₁. Then simply repeatedly extract the first letter of the earliest string under this ordering. There are a few other tricks that work as well, such as comparing S₁ + S₂ to S₂ + S₁ or padding the strings with very late characters (e.g. 'Z' + 1). Showing that the method that you employed is correct is homework.

Value	1000
Submission Rate	22 / 557 (3.95%)
Success Rate	1 / 22 (4.55%)
High Score	zhuojie for 427.89 points (50 mins 10 secs)
Average Score	427.89 (for 1 correct submission)

This was an innocuous, but actually quite tricky counting problem with an evil boundary case that knocked out all but one of the submissions. Many competitors counted the number of distinct lines that were formed, when you were asked for the number of distinct times. Certain tricky test cases lead to 2 disjoint alignments happening simultaneously, and most of the solutions double-counted these events.

The first step in solving this problem is to answer the question: given some subset of the planets, how often are they all aligned? We can find the pairwise alignments between the planets in the subset, then work out when they all happen simultaneously. Alternatively, another way to visualize this is to pick some planet in the subset and imagine that we are rotating around the star, such that to us, this planet appears to remain stationary. The advantage to this is that now, rather than having to consider that the planets have to line up along some arbitrary line, this planet is sitting on the same line constantly, so we only have to consider the points in time when the planets pass this stationary line. If we calculate the new periods of our planets in this rotating frame of reference, each planet will lie on this line every half a period. The new period of each planet is given by:

We now have to work out how often these crossings all happen simultaneously. This is simply the lowest common multiple (LCM) of all the periods divided by 2. However, the periods are all fractions, so we need to work out how we can calculate the LCM of a set of fractions. First of all write all the fractions in their lowest terms. Next, consider that we are looking for a set of smallest integers, such that we can multiply each fraction by its respective integer and we will arrive at the same value for each one. For this to be true, both the numerator and the denominator must be the same. Let's start with the denominator: when we multiply a fraction by an integer, the denominator only changes due to cancellation when it shares a factor with then number by which we are multiplying. We therefore need to cancel out factors of the denominators until they are all the same. The only factors that will be left will be those that are shared between all the fractions. The denominator of the answer is therefore the greatest common divisor (GCD) of the denominators of the original fractions. Now, once all the denominators are the same, we need to work out how to make the numerators the same. With the denominators the same, this is now just a standard LCM calculation. The LCM of a set of fully reduced fractions is therefore:

So now that we can work out the period of alignment of some subset of the planets, we simply take every k-sized subset, work out its period of alignment, use a simple division to work out how many of them occur in the specified time range and add them all together to get the total, right? Nearly, but not quite: the problem is that the sets of times that these alignments happen overlap and we are asked for the number of distinct times. We need some way of calculating the size of the union of a number of overlapping sets when the potential size of the answer is way too big to consider each time separately. Luckily, the inclusion/exclusion principle proves exactly such a method. This describes the size of a union of sets in terms of the sizes of their intersections, which are often much easier to calculate. An intersection here is the number of times within the specified time-period when two or more different k-subsets are aligned simultaneously. Noticing that each k-subset alignment is periodic with a fractional period and we want to work out how often several of them happen simultaneously. We see that this is exactly the same calculation that we have just performed with the pairwise planetary alignments. The inclusion/exclusion principle tells us to consider every possible subset of the sets we are trying to union and calculate the size of the intersection of these sets. If we have just chosen an odd number of sets, then we add this size to the total, otherwise we subtract it from the total. That's all there is to it!

A note on complexity: inclusion/exclusion takes time exponential in the number of sets. The worst case here is when we have the largest number of k-subsets, which happens when N is 5 and k is 2 or 3, where there are 10 subsets to consider. This is small enough that inclusion/exclusion easily works in time. With N = 6 it is very hard to write a solution that doesn't time out. Notice also that the constraints were carefully set so that none of the values in the calculation would overflow a 64-bit integer, so it is unnecessary to use library integer classes.