421A - Pasha and Hamsters

For each apple you just need to determine who like it. If Alexander likes apple, then he should eat it, if Artur likes the apple, then he should eat it. If they both like the apply anyone can eat the apple.

420A - Start Up

One should firstly recognize that the required string should be palindrome and each character of the string should be symmetric. All the symmetric characters are — AHIMOTUVWXY.

420B - Online Meeting

Firstly lets add to the answer all the persons, that didn't appear in the log messages. Then we should consider two cases:

1) If there is a person (with number i), that the first log message with him is in form  - i. We will call such persons X-persons.

Consider all X-persons. Pick the one from them that has the last first occurrence in the sequence of messages. This person can be a leader, all others cannot be. Now we should check if the picked person is a leader or not. For that reason we will use the algorithm that is described below. This algorithm works fine only on special sequences of messages. So, we need to add all the X-persons to the beginning of the our list in the order they appear in input (in the resulting sequence the picked person should be the first).

2) There is no X-persons.

That case only the first person from the list can be a leader. Others cannot be. Check that person with the algorithm described below.

The Algorithm of check:

The algorithm is very simple. Just to iterate throughout the sequence of messages and maintain set-structure for the persons that are currently on the meeting. If we consider log-on message, add the person to the set, if we consider log-off message, erase the person from the set. Each time we perform an operation with set, we should check: either the set is empty or the leader is in set.

The most tricky cases are 33 and 34. Will look at them, the 33-th test:

4 4

+ 2

- 1

- 3

- 2

Here the leader can be only 4-th person. Others cannot be.

The 34-th test:

3 3

- 2

+ 1

+ 2

The answer for that test is only the 3-rd participant.

420C - Bug in Code

Lets construct an undirected graph, the vertices of the graph are the persons, there is an edge between two persons if there are claim of some person about these two persons. Now we can describe the problem on this graph. We need to find the number of such pairs of vertices that at least p edges are adjacent to them.

How to count such pairs. Just for each vertex v to calculate the number of vertices u such that d[v] + d[u] ≥ p, then we should consider all the adjacent vertices correctly. Iterate through all the edges and subtract such the vertices from the answer. Then iterate through adjacent vertices and add only such of them that is needed to be added.

Pay attention to multiple edges, they should be considered very carefully.

420D - Cup Trick

The solution consists of two parts.

1) Find the valid permutation.

Let's go through the given queries. Suppose the current query tells us that the number a is placed on b-th position. If we already met a then we are going to skip this query. Otherwise let's find the position of a in the sought permutation.

Suppose we already know that in the sought permutation the number a₁ is on position b₁, a₂ is on position b₂, ..., a_k is on position b_k (b₁ < b₂ < ... < b_k). After every query the number from that query goes to the begging of the permutation, so all a_i (1 ≤ i ≤ k) are already placed to the left of a before the current query. But some of these a_i stood to the left of a in the sought permutation, and the other stood to the right of a, but went forward to the begging. Let's find the number of these numbers. In order to do this we should find such position p, that is not occupied by any of a_i and p + x = b, where x is the number of such b_i that b_i > p.

We can do it by using the segment tree in the following manner. Let's store in the vertex of segment tree the number of already occupied positions on the correspond subsegment. Suppose we want to find p in the some subtree. Let's find the minimal position in the right subtree p_rg and the number of occupied positions x_rg there. So if p_rg + x_rg ≤ b then we should continue finding p in the right subtree. Otherwise we should decrease b by x_rg and try to find p in the left subtree. When we find p we need to check that p + x = b. If this equation isn't correct then the answer is  - 1.

2) Check that the sequence of the operations is correct.

Let's consider i-th query. Suppose it tells us that a is placed on position b. We should check whether it is correct. If we haven't already seen a in queries then this statement is correct because we checked it in the first part of the solution. Otherwise, let's find the such maximal j < i that it is given the position of a in j-th query. After j-th query a goes to the begging of the permutation and the other numbers can move it to the right. Let's find the number of such different numbers on the queries' segment [j + 1, i - 1]. We should get exactly b - 1.

420E - Playing the ball

Let's claim that we have ray and the infinite number of balls on it in this problem. The k-th ball is placed on the distance k·d from the begging of the ray. Let's note that in the answer must be the ball which is placed on the border of some cirlce. The second observation is the following. Let's consider any circle. The number of angles, on which we can rotate our ray so that any ball will be on the border of this cirlce, doesn't exceed 4 * r / d. Let's call these angles critical.

Let's put all critical angles from each circle to the array B and sort. After that let's consider every cirlce one-by-one. When we consider some cirlce we are going to find all critical angles and sort them. So the number of balls, which will be inside of the cirlce, will be the constant if we rotate our ray on every angle between the two neighbour critical angles. Let's find k — the number of these balls.

Let's create array C, where C_i is the answer value if we rotate the ray on the angle B_i. So after we find k and the positions of neighbour critical angles in B we need to perform add on the segment query in C. After we processed all critical angles of all circles the maximum in the C will be the answer.

412A - Poster

One of the optimal solutions is the following. If k - 1 ≤ n - k then firstly let's move ladder to the left by k - 1 positions. After that we will do the following pair of operations n - 1 times: paint i-th symbol of the slogan and move the ladder to the right. In the end we will paint the last symbol of the slogan. If k - 1 > n - k then we will move the ladder to the right by n - k positions. After that we will also paint symbol and move the ladder to the left. Our last action will be to paint the first symbol of the slogan. Total number of sought operations is min(k - 1, n - k) + 2·n - 1.

412B - Network Configuration

In this task you should sort array in descending order and print k-th element. Due to the weak constraints you could also solve the problem in the following manner. Let's brute ans — the value of answer and calculate how many computers already have Internet's speed not less than ans. If there are not less than k such computers then the answer is acceptable. Let's find the maximum among acceptable answers and it will be the sought value.

412C - Pattern

Let's find the answer symbol-by-symbol. Let's consider i-th symbol. If there are two different symbols differ from '?' on i-th positions in the given strings then we must place '?' on i-th position in the answer. If there are '?' on i-th positions in all string then we can write any symbol. Obviously, it is better to write not '?' but any letter, 'x' for example. Lastly we should consider the case when there are only '?' and one the same letter on i-th positions. In this case we should find this letter and put it to the answer.

412D - Giving Awards

Let's build sought permutation by adding employee one-by-one. Let's we already define the order of the first k employees: a₁, a₂, ..., a_k. Let's place k + 1-th after a_k-th. If a_k-th employee owe money to k + 1-th then we will swap their positions (and will get permutation a₁, a₂, ..., a_k - 1, k + 1, a_k). If a_k - 1-th employee also owe money to k + 1-th then we will also swap their positions and so on. If all first k employees owe money to k + 1-th then k + 1-th employee will be placed first in permutation. This algorithm has time complexity O(m), where m is the number of the debt relationships.

412E - E-mail Addresses

Let's consider position i such, that s_i = '@'. We are going to calculate the number of such substrings that are correct addresses and the symbol '@' in them is s_i. Let's go to the left from i until we find '@' or '.' — the symbols that aren't allowed to be to the left of '@'. Let's calculate cnt how many letters on the segment we went through. This letters can be the first symbols of the correct addresses. Let's now move to the right of i while considered symbol is letter or digit. If we stopped and the string is over or the following symbol is '@' or '_' then there aren't correct addresses. If the following symbol is '.' then let's go to the right of it while the considered symbols are letters. The correct address can finish in every such position, so we should add cnt to the answer. In the described solution "move" means "brute by cycle for". We can do this because we will go through each symbol not more than 2 times. Total time complexity is O(n).

404A - Valera and X

In this problem it was needed to check the constraints described in statement. You can use two sets here. You should insert diagonal elements of matrix into the first set, and the other elements into the second. Element a_i, j belongs to the main diagonal if i = j and belongs to the secondary diagonal if i = n - j + 1. After you split all elements into sets you should check if the sets sizes are equal to one and the elements from this sets differ from each other.

404B - Marathon

Let's notice that after Valera run 4·a meters he will be in the same point from which he started. Valera will have run i·d meters before he gets i-th bottle of drink. Let's calculate the value — how many laps he will run. Then he have already run L = i·d - c·4·a meters on his last lap. It is easy to get Valera's position from this L. For example, if 2·a ≤ L ≤ 3·a then Valera will be in the point with coordinates (3·a - L, a). You can consider the other three cases in the same manner.

404C - Restore Graph

First of all let us notice that it must be only one 0 in d. Also d[start] = 0 means that start is the vertex from which Valera calculated the distance to the other vertices. Let's notice that every vertex u with d[u] = i must be adjacent only to the vertices v such that d[v] ≥ i - 1. Besides there is always must be such neighboor v₀ of u, that d[v₀] = i - 1. Let's build sought graph by adding one vertex to the existing graph. We will add vertex in order of increasing their distance to start. Initially, we have one vertex with number start in our graph. When we add vertex u with d[u] = i let's consider such vertices v that d[v] = i - 1. Let's choose the vertex with minimal degree among them. If this value is equal to k, then there is no solution. In other case let's add u to our graph and add the edge (u, v) to the answer. If there are no vertices with distance i - 1 to start then the answer is also  - 1. If everything fine we will get the answer which is tree, so the number of edges in it equals n - 1 ≤ 10⁶.

404D - Minesweeper 1D

This problem can be solved by using dynamic programming. Let's calculate d[i][type] — the number of correct ways to fill the prefix of length i so that the last filled cell has one of the 5 types. These types are the following:

1. the cell contains "0"

2. the cell contains "1" and the cell to the left of it contains bomb

3. the cell contains "1" and the cell to the left of it doesn't contain bomb

4. the cell contains "2"

5. the cell contains bomb

When we try to fill next cell we check two conditions. Firstly value of the filled cell in given string must be equal to either what we want to write or "?". Secondly new prefix must remain filled correct. For example, if we are in state (i, 1) (it means that the cell i contains "0") then we can fill next cell by "0" and go to the state (i + 1, 1) or fill next cell by "1" and go to the state (i + 1, 3). We cannot write "2" because both neighbours of the cell with "2" must contain bomb. Obvious, we cannot place bomb after "0". Note that, when we place "1" after "0" we go to the state (i + 1, 3), but when we place "1" after bomb we go to the state (i + 1, 2). You can consider other ways of going from one state to another in the same manner.

404E - Maze 1D

Let's consider the case when the last move of the robot is equal to "R". If the last move is equal to "L" then we can replace all "L" by "R" and vise versa and the answer doesn't change. Let's show that Valera doesn't need more than one obstacle. Suppose Valera placed obstacles somewhere. We will say that the number of obstacle is the number of cell containing it. Let's consider the rightmost obstacle obs1 among the obstacles with negative numbers and the leftmost obstacle obs2 among the obstacles with positive numbers. Obvious robot cannot go to the left of obs1 and to the right of obs2. So the needed number of obstacles is not greater than two. Let's show that Valera doesn't need to place obstacles to the cells with numbers greater than zero. Suppose he place obstacle to the cell with number a > 0. If robot doesn't try to go to this cell then its obstacle is out of place. If robot try to go to this cell then it will visit finish cell more than once. It is because robot needs to go to the right on its last move, but it can't do it from cell a - 1 and it has already visited all cells to the left of a. So Valera doesn't need more than one obstacle and its obstacle must have number less than zero.

Let's now check if Valera can do without obstacles. If so the robot won't skip moves and will stop in some cell. Than Valera can choose this cell as finish and the answer will be one. We have to consider only one case when Valera must place one obstacle.

Firstly let's notice that if Valera place obstacle to some cell, the finish cell can be restored uniquely. It means that the number of ways to choose where to place obstacles and finish cell is equal to the number of ways to choose one cell to place one obstacle. Suppose Valera placed obstacle in the cell with number b < 0 and robot completed its instructions successfully. Notice, that in that case robot skipped some moves of type "L", completed all moves of type "R" and went to the right on its last move to the unvisited cell. If we shift Valera's obstacle to the right on one cell then robot is going to skip not less moves of type "L" than in the previous case. It means that the finish cell can either go to the right or remains the same. But last time robot visited this cell on its last move, so it is going to visit a new finish cell on its last move either. This means that there is such cell p < 0 that if Valera place obstacle to the cells c ≥ p then robot will be able to complete its instructions successfully, but if Valera place obstacle to the cells d < p then robot will not. This cell p can be found by using binary search and simple simulation on each iteration. Time complexity is O(n log n).

Hi to all!)

Regular round Codeforces #237 for participants from 2 division will take place tomorrow March 19, 19:30 MSK. Traditional, participants from 1 division can take part out of the competition.

The problems were prepared by Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Also thanks to Michael Mirzayanov (MikeMirzayanov) for very cool system Codeforces and Mary Belova (Delinur) for translating the problems into english.

We wish everyone good luck, high rating and excellent mood)

UPD: Score distribution will be standard 500 — 1000 — 1500 — 2000 — 2500.

UPD 2: The contest is over, thanks to all participants.

Congratulations to the winners:

1. Pkqs09
2. juggler
3. zstu_bobo
4. kevinswat
5. Salvare004

UPD3: You can find the tutorial here

353A - Domino

Let's denote the sum of numbers on the upper halves of pieces as s₁, and the sum on the lower halves — s₂. If this sums are even, than the answer is obviously 0. Note, that if the numbers on both halves of piece have the same parity, than parity of s₁ and s₂ won't change after rotation this piece. If the numbers on halves have different parity, than parities of both s₁ and s₂ will change after rotation. Therefore, if s₁ and s₂ have different parities, than the answer is  - 1. If both s₁ and s₂ are odd, than we should check, if there is a piece with numbers of different parities. If so, the answer is 1, otherwise, the answer is  - 1.

353B - Two Heaps

Let's say for shortness, that we put numbers, that are painted on cubes, in piles, instead of cubes themselves.

Note, that the answer is the product of c₁... c₂, where c_i is the number of different numbers in the i-th pile. Let's consider that all numbers are different. In this case the answer is n². Now, let's suppose that we have two equal numbers and all the other are different. Then, if we put them in different piles, the answer will be n², but if we put them in one — n·(n - 1). Obviously, the first case give greater product.

Thinking in similar manner, you can conclude, that we should do the following. Take numbers, that appear more than once, and put one of them in the first pile, one of them in the second pile and the other put aside. After that, divide the numbers, that appears once, in two equal part and put the first part in the first pile and second part in the second pile. Finally, take the numbers, that we put aside, and separate them in two pile in any kind.

353C - Find Maximum

Let's see on the highest bit of m. If it equals to zero, than for any there is a zero on the (n - 1)-th position, so a_n - 1 doesn't affect the answer and we can put it aside and find the answer for smaller number of elements.

If the highest bit of m equals to 1, than a_n - 1 for some x will present in f(x), but for some will not. Let's consider such x, that a{n - 1} will present in f(x) with zero coefficient. It is obvious that . In this case f(x) will have maximum value when x = 2^n - 1 - 1. Try to update the answer by this value.

Now we should analyze the case, when , find the maximum value of f(x) for all such x and try to update the answer by this value. Let's note, that in all such x there is 1 in (n - 1)-th position. Therefore we can find the maximum value of f(y) for all and add a_n - 1 to it.

353D - Queue

Note that if there are some girls in the begining of the line, they will never move. So let's remove them and will consider that the first schoolchildren in the line is a boy. Also note, the relative order of the girls doesn't change. Let's calculate for each girl such moment of time t_i, that after it she won't move forever. Note, that for i-th girl t_i ≥ t_i - 1. Let's calculate t_i in order from left to right. Let's denote y_i is the position in the line where i-th girl will stop, ans x_i is her current position. Therefore it is needed x_i - y_i second for girl to reach her finish position. So if x_i - y_i > t_i - 1, then t_i = x_i - y_i. Let's manage the case when x_i - y_i ≤ t_i. The girl with number (i - 1) will be on y_i-th position by t_i - 1-th second, so t_i ≥ t_i - 1 + 1. Let's consider such moment of time p, when i-th girl stand right after (i - 1)-th, but not on y_i-th position. After that, in (p + 1)-th moment of time (i - 1)-th girl and the boy standing in front of her will swap their positions, but i-th girl will save her position. Then since p + 2-th second till t_i - 1 both girls will change their positions. Finally, at (t_i - 1 + 1) - th second i-th girl will occupy her position. Therefore, t_i = t_i - 1 + 1 in this case.

353E - Antichain

Let's divide our graph on chains. Denote chain as the maximal sequence of the edges, which have the same direction. If there are more than 2 edges in each chain, then the answer is the number of such chains.

If there is a chain containing only one edge (u, v), then brute vertex, which we will take in maximal antichain (also consider the case, when we take none of them). Let's suppose we brute the vertex v. After that we put aside this vertex and all vertices, which is comparable with v. In received graph we can find the size of the maximal antichain by uning dynamic programming with O(n) time complexity. Let's show how to do this.

Write all remaining vertices in line and renumerate them from left to right by the numbers from 1 to k. After that we are going to calculate d_i — the size of the maximal antichain among vertices with numbers j ≥ i. So if i > k, then d_i = 0. In other case we can skip i-th vertex and try to update d_i by the value of d_i + 1. Also we can try to take i-th vertex to the answer. In this case we should skip all vertices, that are reachable from i-th, or the vertices, from which we can reach i-th, take the answer from the next vertex, add 1 to it and try to update the answer.

Hi to all!)

Regular round Codeforces #205 for participants from 2 division will take place today. Traditional, participants from 1 division can take part out of the competition.

The problems were prepared by Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Also thanks to Michael Mirzayanov (MikeMirzayanov) for very cool system Codeforces and Mary Belova (Delinur) for translating the problems into english.

We wish everyone good luck, high rating and excellent mood)

UPD: It is decided to use dynamic scoring system.

UPD 2: The contest is over, thanks to all participants.

Congratulations to the winners:

1. hos_epic
2. gzh1996n
3. I_LOVE_ELE

UPD 3: you can find the tutorial here

231A - Team

It is needed just to implement actions described in statement. You had to read data and to calculate number of members of team, which were sure about the solution, for every task. If this number is greater than one, the answer must be increased by one.

231B - Magic, Wizardry and Wonders

Let's see, what will be the last number of array after i iterations. After the first iteration it will be a_n - 1–a_n (and total number of elements will be decreased by one). After the second iteration the last number will be a_n - 2–a_n - 1 + a_n. It is not hard to see, that after n - 1 iterations remain a₁–a₂ + a₃–a₄ + ... + ( - 1)^n + 1·a_n. In a such way, our task is to put numbers from 1 to l in array so, that sum of numbers in odd positions minus sum of numbers in even positions will equal to given d. This means sum of numbers in odd positions must be equal . But the minimal sum can be , and the maximal — .

Because of this we should choose a_2·k so, that s fits the boundaries. Constrains allow to do it in a such manner. Firstly, put ones on the even positions. If s > maxv after that, the answer is  - 1. Otherwise, let's increase each a_2·k by one until s = minv. If we put l in all even positions and s < minv, than answer is  - 1 too. After we put numbers on even positions, let's write 1 in all odd positions, and while sum of this elements is less than s increase each one by fitting value.

231C - To Add or Not to Add

One of the main observations, needed to solve this problem, is that the second number in answer always coincides with someone a_j. Let's see why it is true. Suppose, the second number of the answer is a_j + d for someone j and a_j + d ≠ a_i for all i. This means, we increased some numbers, which is less than a_j, so that they became equal to a_j, and then all this numbers and some numbers, which is equal to a_j, we increased to a_j + d. But if we didn't increase all this numbers to a_j + d and remain they equal to a_j, we'd perform less operations and the answer would be better.

Due to this fact we can solve problem in a such manner. Sort array in non-decreasing order. Iterate over a_i and calculate, what is the maximal number of a_i we can obtain. For maximizing first number of answer, we must increase some lesser numbers to a_i and perform not greater than k operations. It is obvious that firstly we should increase such a_j that a_i–a_j is minimal. So, if we can solve problem in O(n²), we would iterate j from i to 0 and increase a_j to a_i, while we could. But the solution must be faster, and we will use binary search. We will brute the number of numbers, which we must do equal to a_i. Suppose we fix cnt this value. Now we have to check if we can do cnt numbers equal to a_i by not greater than k operations. For doing this, let’s calculate . If this value not greater than k, we can do it. For calculating sum quickly, we can save prefix sums and than s_{i - cnt + 1, i} = s_i–s_i–cnt. Finally we solved this problem in O(n·logn).

231D - Magic Box

The main subtask of this problem is to check whether we can observe the center of face of parallelepiped from point p = (x, y, z). Let’s see the case, when the face belongs to plane z = z₁. For performing all calculations in integer numbers, multiply all coordinates x, y, z, x₁, y₁, z₁ by 2. Take the point and normal to plane, containing the fixed face, which is directed out of interior of parallelepiped, that is . Also take vector . If undirected angle between this vectors is less than 90 degrees, we can observe a from p. For checking this we can use scalar product. If scalar product of and is strictly greater than zero, than that angle is fitting.

231E - Cactus

In this problem you should find the number of simple paths between some pair of vertices in vertex cactus. If you learn the structure of these graphs, it is not hard to see, that if we’ll squeeze each cycle in one vertex, we get a tree. So let’s squeeze all cycles in source graph and get this tree. Also every vertex of this tree we’ll mark, if it is squeezed cycle (let’s call this vertices 1-vertices) or single vertex in source graph (this vertices we’ll call 0-vertices).

Then, we’ll do the following to find the number of paths between vertices a and b in source graph. Suppose c is a vertex, corresponding to a in obtained tree (it can be a single vertex or a vertex, corresponding to a squeezed cycle with a), and d is a vertex, corresponding to b. Let’s denote deg is the number of 1-vertices in path from c to d in tree. Than it is easy to understand, that the answer for query is , because every cycle (1-vertex) increase the number of possible ways twice (you can go from one vertex to other by two ways in cycle).

It means that we need to count the number of 1-vertex on the path from one vertex to other in tree quickly to answer a query. We can do it in a following way. Hang our tree for one vertex, which we’ll call a root. Denote for every vertex cnt_v is the number of 1-vertex on the way to the root (including root and vertex itself). Suppose we want to find the number of 1-vertex on the path from a to b. Denote c is the least common ancestor of vertices a and b. Than number of 1-vertex on the way from a to b is equal to cnt_a + cnt_b–2·cnt_c, if c is 0-vertex and cnt_a + cnt_b–2·cnt_c + 1, if c is 1-vertex. The least common ancestor can be found by standard method — binary method recovery. Finally we have O(m + k·logn) solution.

Hi to all!)

Codeforces #143 for participants from second division is going to be today. I think, it is not necessary to remind, that coders with rating greater than 1699 will be able to take part out of the competition.

Problems' autors for this event are Kholkin Pavel (HolkinPV) and Kuznetsov Nikolay (NALP). Kudryashov Igor Igor_Kudryashov and Agapov Gerald (Gerald) helped in contest's preparation too. Special thanks to creator great resource Codeforces Mike Mirzayanov (MikeMirzayanov) and our translator Maria Belova (Delinur).

Score distribution will be determine later, monitor for changes).

We wish you enjoy participating this competition and want you to get something new and useful.

UPD: Score distribution will be standart 500-1000-1500-2000-2500.

UPD2: Round is over. Thanks to all for participating. Six first coders solved all 5 problems, congratulations.

1) teoy

2) gomineral02

3) mrNobody

4) Ryannnnnnn

5) marschenly

6) KuchumovIlya

Editorial will be published soon.

UPD3: Editorial is published, you can find it here

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₄.

Good afternoon, friends)

We introduce you Codeforces Round #126 (Div. 2). Please note, Codeforces Round #126 (Div. 2) will be only today and only today you will have unique opportunity to raise your rating in this competition (certainly, you will be able to solve problems virtually after round, but this doesn't change your rating). Also round will be unrated for participants from first division.

This round was prepared by students of Saratov State University: Nicolay Kuznetsov (NALP), Pavel Kholkin (HolkinPV), Igor Kudryashov (Igor_Kudryashov) and Gerald Agapov (Gerald). Also we thank creator of Codeforces Michael Mirzayanov (MikeMirzayanov) for amazing system, member of staff of Codeforces Mary Belova (Delinur) for great translation and Alexander Kuprin (Alex_KPR) for help in preparation of this round.

Note, today it is decided to use dynamic scoring system (Learn more about dynamic problem scoring).

Also problems will be placed in random order, it means they aren't sorted in increasing order of difficulty.

More right ideas and fine solutions to you.

UPD. Competition is over. Thanks for all who participated. We hope you enjoyed the participation, and round not passed in vain. Editorial will be posted soon. Congratulations to the winners:

1. Andreos

2. jma127

3. iensen

4. Spider-man

5. MrPapaya

Analysis of problem "E. Helper"

To solve the problem, firstly, it was necessary to carefully read the input data and convert all the time specified in the format day, hour, minute in a minute since the beginning of the session for convenience. This could be done by using formula newTime = (day - 1) * 24 * 60 + hour * 60 + minute.

Secondly, it is necessary to count the number of free minutes for solving the problems, which Valera has throughout the session. In addition, for every free minute j it is needed to determine t_j --- number of this minute since the beginning of the session.

Next, it is needed calculate the value of deadline_i for each student --- the latest free minute since the beginning of the session that if Valerie has finished to perform the task at that moment, he will receive the promised sum from the respective student. Obviously, if Valerie will not be sleeping or eating at the moment of i-th student begin to pass the exam, then deadline_i will be equal to a minute prior to the beginning of the exam, else deadline_i will correspond to the latest free minute prior to sleeping or a meal. In addition, if the free minute from the beginning of the session doesn't exist or Valera can not help i-th student, than we define deadline_i = -1 in this case. 

Then we will sort all the students in non-decreasing value of deadline and use the method of dynamic programming. The two parameters i --- amount of viewed students (i.e. those for which the problems is already solved) and j --- the number of free minute, from which Valera can begin to perform tasks for the next student will be the states of "dynamics". The value of the "dynamics" will be the maximum profit that Valerie can get when he will reach the respective state.

Obviously, there are two possible transition from state i, j:

1. in the state i + 1, j --- Valera will not solve the problems for the i-th student in this case
2. in the state i + 1, j + time[i] (where time[i] is the time required for solving problems of i-th student) --- Valera will solve the problem for i-th student in this case, and he will get sum of money this student is ready to pay. However, such a transition is possible only if t(j + time[i]) does not exceed deadline_i.

Once the value of dynamics for all possible values of i, j will be counted, the answer to the problem will be a maximum of n-th row of the array (where n --- the total number of students).

In addition, you should use an additional array of ancestors and accurately convert the time back to the desired form to restore the answer.

Analysis of problem "A. What is for dinner?"

The solution of the problem is rather trivial. It was needed to make an array, where for each row of teeth the value of residual viability of the sickest thooth in this row would have kept (sickest tooth in the row is called the one with the lowest residual viability).

Thus we define for each row of teeth the maximum number of crucians, which Valery able to eat, using this row (Valeria can not eat more crucians, because the residual viability of the sickest tooth will become negative).

Knowing these values, you just need to sum them and to give the minimum of the sum and total amount of crucians in Valerie's portion for dinner as answer.