Thursday, December 27, 2007 Match summaryThe last SRM in the year, authored by Petr , attracted 1359 participants. In Division 1, coders faced a very tough 1100point 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 ProblemsRussianSpeedLimitsUsed as: Division Two  Level One:
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. UnderscoreJustificationUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 wordseparating 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 Note that the number of long intervals can also be calculated using the division remainder operator, as did KOTEHOK in his Java solution. SummingArithmeticProgressionsUsed as: Division Two  Level Three:
Since we need to represent the numbers as the sum of an arithmetic progression,
let's first calculate that sum using the wellknown
formula:
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, 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; }TurningMaze Used as: Division One  Level Two:
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:
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 breadthfirst search algorithm can be used. The total number of states is equal to 7 * 7 * 2^{7} * 2^{7} = 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 . InfiniteAdditionUsed as: Division One  Level Three:
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 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 nonperiodic. We check that each of the strings S, P, and Q can be nonperiodic 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.

