Match Editorial

Match summary

The last SRM in the year, authored by Petr , attracted 1359 participants. In Division 1, coders faced a very tough 1100-point problem which eventually no one managed to get right. Thus, the first place went to gevak with 2 solved problems and strong performance during the challenge phase. ACRush and vlad89 took the 2nd and 3rd places, respectively.

In Division 2, 28 coders solved all three problems correctly. AlixM won the Division with 3 correct problems and 4 successful challenges. He was followed by kefir and B.Good .

The Problems

Value	250
Submission Rate	636 / 702 (90.60%)
Success Rate	566 / 636 (88.99%)
High Score	jackson.liao31 for 248.88 points (1 mins 54 secs)
Average Score	204.53 (for 566 correct submissions)

This problem can be solved in the straightforward way, by reading the signs one by one and updating the current speed limit ant city bounds information. Thus, we need just two variables to keep the current state of the road: an integer speed limit and a boolean flag which holds true value when we are inside a city and false otherwise.

Java solution follows.

public class RussianSpeedLimits {

    private int getDefaultLimit(boolean isInCity) {
        return isInCity ? 60 : 90;
    }

    public int getCurrentLimit(String[] signs) {
        boolean isInCity = true;
        int speedLimit = getDefaultLimit(isInCity);
        for (String sign : signs) {
            if (sign.equals("default")) {
                speedLimit = getDefaultLimit(isInCity);
            } else if (sign.equals("city")) {
                isInCity = !isInCity;
                speedLimit = getDefaultLimit(isInCity);
            } else {
                speedLimit = Integer.parseInt(sign);
            }
        }
        return speedLimit;
    }
}

For a similar C++ implementation, see dcp 's solution.

Value	500
Submission Rate	437 / 702 (62.25%)
Success Rate	344 / 437 (78.72%)
High Score	ankit.pruthi for 497.95 points (1 mins 49 secs)
Average Score	302.85 (for 344 correct submissions)

Value	250
Submission Rate	554 / 565 (98.05%)
Success Rate	522 / 554 (94.22%)
High Score	bmerry for 244.17 points (4 mins 24 secs)
Average Score	196.24 (for 522 correct submissions)

The first thing to notice about this problem is that the number of space characters between any two consecutive words in the aligned line of text can be calculated by dividing the total number of spaces in the line by the number of word-separating space intervals. Here, the number of spaces is equal to the line width minus the total number of letters in the given words array, and the number of space intervals is equal to the number of words minus one. If such division produces no remainder, then all the space intervals are equal and we only need to format the answer by inserting the corresponding number of spaces (i.e., underscores) between consecutive pairs of words. Otherwise, the two possible space interval sizes can be calculated by rounding the division result up and down:

int totalSpaces = width - <Total number of letters in words>;
int numIntervals = words.size() - 1;
int shortInterval = totalSpaces / numIntervals;
int longInterval = totalSpaces / numIntervals + 1;

The exact number of space intervals of each size can be found using the fact that there are numIntervals in total and the total number of space characters is totalSpaces.

int numLongIntervals = totalSpaces - shortInterval * numIntervals;
int numShortIntervals = numIntervals - numLongIntervals;

Now we need to decide which intervals should be short and which should be long. Taking into account that the resulting line must be the lexicographically smallest one, we want to place long intervals before words starting from a lowercase letter and short intervals before words starting from an uppercase letter, as long as we haven't used all the intervals of the corresponding length.

A C++ solution implementing this approach follows.

string justifyLine(vector words, int width) {
    int totalLetters = accumulate(words.begin(), words.end(), string()).size();
    int totalSpaces = width - totalLetters;
    
    int numIntervals = words.size() - 1;
    int shortInterval = totalSpaces / numIntervals;
    int longInterval = shortInterval + 1;
    int numLongIntervals = totalSpaces - shortInterval * numIntervals;
    int numShortIntervals = numIntervals - numLongIntervals;
    
    string line = words[0];
    for (int i = 1; i < words.size(); i++) {
        // We will use the short interval if any of the following conditions 
        // is true:
        // a. The word starts from an uppercase letter 
        //        AND we haven't used up all short intervals.
        // b. We have used up all long intervals.
        if ((words[i][0] < '_' && numShortIntervals > 0) 
                || (numLongIntervals == 0)) {
            line += string(shortInterval, '_');
            numShortIntervals--;
        } else {
            line += string(longInterval, '_');
            numLongIntervals--;
        }
        line += words[i];
    }
    return line;
}

Note that the number of long intervals can also be calculated using the division remainder operator, as did KOTEHOK in his Java solution.

Value	1000
Submission Rate	159 / 702 (22.65%)
Success Rate	31 / 159 (19.50%)
High Score	Tanaeem for 791.21 points (15 mins 28 secs)
Average Score	574.69 (for 31 correct submissions)

Since we need to represent the numbers as the sum of an arithmetic progression, let's first calculate that sum using the well-known formula:
(x) + (x+d) + (x+2*d) + ... + (x+(k-1)*d) = k * x + k * (k-1) / 2 * d
Now, we can introduce two new constants for convenience:
A = k
B = k * (k-1) / 2
and redefine the problem as follows: How many integers between left and right can be expressed in the form A * x + B * d, where x and d are some positive integers?

Obviously, any number not divisible by GCD(A, B) can not be represented as A * x + B * d, so we can divide A, B, left, and right by GCD(A, B) and get the same problem with A and B being relatively prime. (Notice that left should be rounded up and right should be rounded down after the division.)

Now, it can be proven that any number greater than or equal to 2 * A * B can be represented as A * x + B * d. Here is a hint for the proof: for every such number N,
N mod A = (B * d) mod A
N mod B = (A * x) mod B
and since A and B are relatively prime, we can find values for x and d such that 1 ≤ d ≤ A and 1 ≤ x ≤ B that satisfy those two equations.
To find out if the numbers less than 2 * A * B can be represented in the form A * x + B * d, we can use the fact that for every such representation we can reduce x by B and correspondingly increase d by A to get the same sum. Thus, we only need to check values from 1 to B for x.

The C++ solution follows.

bool canRepresent(int A,int B,int N) {
    for (int x = 1; x <= B; x++) {
        if (A * x >= N)
            return false;
        if ((N - A * x) % B == 0) {
            return true;
        }
    }
    return false;
}

int howMany(int left, int right, int k) {
    int A = k;
    int B = k * (k - 1) / 2;
    int D = GCD(A, B);
    A /= D;
    B /= D;
    left = (left + D - 1) / D;
    right /= D;
    int ans = 0;
    while (left <= right && left < 2 * A * B) {
        ans += canRepresent(A, B, left++);
    }
    ans += right - left + 1;
    return ans;
}

Value	500
Submission Rate	295 / 565 (52.21%)
Success Rate	200 / 295 (67.80%)
High Score	Zuza for 458.70 points (8 mins 41 secs)
Average Score	279.73 (for 200 correct submissions)

As it is said in the problem statement, rotating a room twice does not change the orientation of the room's doors. That is why the complete state of the maze can be described by two vectors of boolean values, rows and columns, where rows[i] is true if row number i has been rotated an odd number of times, and false otherwise; the columns vector stores the similar information about the columns. Given these two vectors, we can get the current type of the room in row i, column j using the following rules:

• If the initial type of the room is either 'A' or 'B', the current type is the same.
• If exactly one of the values rows[i], columns[j] is true, room type 'C' changes to 'D' and vise versa; otherwise, the current room type is the same as the initial one.

Now, the adventurer's state at any moment of time can be fully described by his two coordinates and the two vectors describing the maze's state. From the current state <x, y, rows, columns>, the adventurer can either go to one of the neighbouring rooms, provided that both the current and the neighbouring rooms have the necessary doors, or press the button and change the state of the maze. Thus, each state can have at most 5 adjacent states.

It is convenient to represent the vectors rows and columns as integer variables, each bit of which corresponds to a boolean value in the vector. Then the initial state can be represented as <0, 0, 0, 0> and the final state is <M - 1, N - 1, X, Y>, where M is the number of rows in the maze description, N is the number of columns, X is any number between 0 and 2^M - 1 and Y is any number between 0 and 2^N - 1, inclusively. To find the path from the initial state to the final one in the graph of states, a breadth-first search algorithm can be used. The total number of states is equal to 7 * 7 * 2⁷ * 2⁷ = 802,816, and a good BFS implementation should run in time. For an example of solution using the BFS algorithm, see Zuza 's fastest C++ solution or the similar Java solution by Im2Good .

Value	1100
Submission Rate	10 / 565 (1.77%)
Success Rate	0 / 10 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Before trying to find the three requested strings, we can cut off some cases in which the answer can not possibly exist based on the given numbers. Note that the LCM of any two given numbers should be divisible by the third number. For example, if LCM(sum, op1) is not a multiple of op2, then the string of length op2 is periodic with period LCM(sum, op1) mod op2. Therefore, if a solution exists for the given values of sum, op1, and op2, then LCM(sum, op1, op2) = LCM(sum, op1) = LCM(sum, op2) = LCM(op1,op2).

Next, we get a system of linear equations with variables being the values of the three strings' characters (i.e. there are sum + op1 + op2 variables in total) and the equations of form
S[i mod sum] = P[i mod op1] + Q[i mod op2] (mod 26)
where i = 0, ..., LCM(sum, op1, op2) - 1.
That's pretty much everything coherent I can tell you about this problem, so the further several paragraphs will be based on the author's explanation.
As Petr explains, we can not solve the equation system modulo 26, so we should solve it twice, modulo 2 and modulo 13, using Gaussian elimination, and get a set of free variables, which can be assigned any values, and all other variables expressed linearly in terms of the free ones. (It turns out that the set of free variables is the same for solutions modulo 2 and modulo 13.) At that, each variable should depend only on those located before it in the answer format (that is, a variable representing a letter in S depends only on free variables representing the earlier letters in S; a variable representing a letter in P depends on the free variables representing the earlier letters in P or any letters in S, etc.) That can be achieved by running the Gaussian elimination from the last variable's column to the first one.

Having solved the equation system, we try all possible letter values for each free variable in turn, until we find a value that can lead to a valid solution, then go on to the next variable in the format order, and so on, until we get all the values. For each set of assigned free variables we verify that those values do not break any of the equations and that the resulting solution can be non-periodic.

We check that each of the strings S, P, and Q can be non-periodic separately; moreover, it turns out that we can even perform the check for each specific period g (where g is a divisor of the corresponding string length) separately from other periods. Thus, for each period g we try to find two variables with distance g between them that are expressed by different linear functions of the remaining free variables.

You can check out the solutions of the few brave TopCoders who dared to implement the described approach in the practice room.
And here comes the solution for mere mortals.
If you are not satisfied with the above explanation, here is another approach that should be easier to understand and implement. Notice how in every example, the first string (S) contains only characters 'A', 'B', and 'Z'. (Well, there are not many examples in the problem statement for this observation to be convincing enough, but you could generate more test answers using any slow brute force solution.) Furthermore, it turns out that the second string contains only characters 'A', 'B', 'Y', and 'Z', with the exception of 'C' appearing in the last position in some rare cases. So, using these two observations, we can get a pretty fast brute force solution. I think its correctness could even be proven, but we will leave the proof as an exercize for the reader.