200A — Cinema

In this problem were given the field, which size is n × m, and k queries. Each query is the cell of the field. You had to find closest free cell for given one (there was used manhattan metric). Than found cell was marked as used. The time complexity of the solution is supposed to be . Firstly, we show the main idea, than we show why solution has time complexity .

First of all, if n > m, than rotate matrix by 90 degrees (than we explain purpose of this transformation). We will have two matrices, size of each is n × m. In this matrices we will maintain for each cell the nearest free one to the left and to the right. Suppose we have query — cell (x, y). Iterate d — how much rows we will go above or below. Suppose we fix d, than look at the row x - d, for example (also we should do same things for row x + d). Lets find in this row nearest free cells to the left and to the right of (x - d, y) by using our matrices and try to update answer. When d will be greater than current found answer we will stop, because answer won't update in this case. After we find the answer, we have to change value in some cells of our matrices. It can be done by using structure DSU for each row.

Lets show why this solution has time complexity . Suppose all queries are equal, for example each query is (x, y). Than if field is big enough, all points will be placed in form of square, which is rotated by 45 degrees and have center in point (x, y). Also the side of the square will have length . Than diagonal will have length too. It means that we see rows in each query and we do O(1) operations in each row. If the square doesn't fit into the field, than field is too thin verticaly or horizontaly. So we will have figure looks like rectangle, and one side of this rectangle will be less than . In this case rotate field so, than least side of rectangle means rows. Than we will see not greater than rows in each query and will perform not greater than O(1) operations in each row.

This problem is supposed to be the hardest problem of the contest.

200B — Drinks

This problem was the easiest problem of the contest. There you had to find average of the given numbers. The most participants solved this problem.

200C — Football Championship

In this problem was given description of the group stage of some football competition and scoring system. There were given results of all matches, excepting one, and you had to find result of the last match, satisfied some given criterias. Also Berland's team must be first or the second team of the group after than match.

Lets note, that in each finished match were not greater than 18 goals. It means that we can brute-force all results of the last match, when score is not greater than 200 goals, and find the best one. One of the easiest way is to fill table to the end (it means to change points value and balls value), than to sort teams according to the given rules and to check that Berland is the first or the second team of the group.

200D — Programming Language

In this task were given the list of template functions. Each function have its name and the list of types of arguments (also it can be used universal type). Also there were given set of variables and thier types, and some queries. Each query is function, which has name and list of arguments. For each query you had to find, how many functions from the given list fit to the function from query. There fit means that functions have the same name, same number of arguments and types of all arguments also equal.

For solving this problem it is needed to implement comparing of functions. Constrains gave the possibility to brute-force function from the given list and check if the names and arguments of functions are equal.

200E — Tractor College

In this problem were given four integer numbers c₃, c₄, c₅, s. You had to find 0 ≤ k₃ ≤ k₄ ≤ k₅ such, that c₃·k₃ + c₄·k₄ + c₅·k₅ = s and |c₃·k₃–c₄·k₄| + |c₄·k₄–c₅·k₅| is minimal.

Firstly, brute-force k₄ so, that s–c₄·k₄ ≥ 0. Than look at 4 cases, according to the sign of the value in each modulus.

Lets see the case, when c₃·k₃–c₄·k₄ ≥ 0 and c₄·k₄–c₅·k₅ ≥ 0. Than we have to minimize c₃·k₃–c₅·k₅. Also 0 ≤ k₃ ≤ k₄ ≤ k₅ and c₃·k₃ + c₅·k₅ = s–c₄·k₄. Lets see diofant equation c₃·k₃ + c₅... k₅ = s–c₄·k₄. It can be that this equation doesn't have solution. Lets see the case, when equation has solution. As c₃, c₅ ≥ 0, than for minimization c₃·k₃–c₅·k₅ we have to minimize k₃ and maximize k₅. All solutions of diofant equation c₃·k₃ + c₅·k₅ = s–c₄·k₄ can be described by using one argument k. Than we have to find such segment, that for all k from it, k₃ will fit above constrains, such segment, that for all k from it, k₅ will fit above constrains, find intersection of this segments and, if intersection isn't empty, choose such k, that k₅ is maximal.

Similar you have to manage remain 3 cases and choose optimal values k₃ and k₅ for fixed k₄. Also you can note, that in all cases minimized function is linear and in segment it has minimal value in one of its ends. So we can only find such segments, that for all k from that segments k₃, k₅ will fit above constrains, and calculate answer in the ends of this segments. If for all fixed k₄ diofant equation doesn't have solution, or intersections of the described segments are empty, than answer is IMPOSSIBLE, else we should find the best. So the time complexity is O(s·log(s)) — brute-force of k₄ and solving diofant equation for fixed k₄.