We invite you to MosCode Festival and analyze the tasks of past years.
Hi, Habr! The IT Education Development Center of MIPT invites you to the MosCode Festival, the international student sports programming championship . This is a good opportunity to practice on the tasks of the ACM ICPC finals, along with participants from other countries. The contest will take place on March 31 (personal tour) and on April 1 (team tour) at the Skolkovo Technopark. Online selection will take place this Sunday, February 11, at 11:00 Moscow time. While you are thinking about registering , we are giving details and sharing the two tasks of last year with analysis.
MosCode Festival, formerly known as the Moscow Festival on Sports Programming Cup them. I.N. Vekua is a significant event in the world of olympiad programming. Last year, 200 people from 19 countries came to the festival, including teams from Australia, Japan and Spain for the first time. This year 360 students are expected from 40 countries. Currently, teams from Canada, India, Great Britain, China and Brazil have applied for participation.
And now warm up.
')
Task “Something with dots and rectangles”
Task "Playing on the field"
Task “Something with dots and rectangles”
Input File Name : Standard Input
Output File Name : Standard Output
Time limit: 3 seconds
Memory limit : 256 megabytes
A set of n distinct points with integer coordinates is given on the plane. We call a rectangle good if its angles are at points with integer coordinates, and all points with integer coordinates inside and on the border belong to the given set. Moreover, such a rectangle may be degenerate (have zero area). For each point you need to find the number of good rectangles to which it belongs.
Input Format
The first line contains the number n (1 ⩽ n ⩽ 10 ^ 5) - the number of points. The following lines contain the coordinates of the points (−10 ^ 5 ⩽ xi, yi ⩽ 10 ^ 5)
Output format
Print n lines. The i-th line should contain the number of good rectangles containing the i-th point.
Examples
| standard input | standard output |
|---|---|
| four -eleven -12 -2 -1 -2 -2 | four four four four |
| eight eleven 12 13 2 1 2 3 3 1 3 2 3 3 | five four five four four five four five |
Analysis of the task “Something with dots and rectangles”
Naive solution for O (n ^ 3) Let's look at two opposite corners of the rectangle, check that it is good. If good, then for each point we check if it belongs to this rectangle. If it belongs, increase the answer for a point by one.
Solution in O (n ^ 2) Briefly: we want to iterate through any horizontal segment from the points in the set and count in how many rectangles with a side equal to the length of the segment, it lies.
First, O (nlogn) is presumed to be for each point directly to the top, bottom and right neighbor. Then for the line we consider toright [i] = 1 + the number of points in a row to the right of the i-th point.
We iterate over the length of the segment len. We count the lines up [i] and down [i] for each point up [i] = 0 if toright [i] <len up [i] = 1 + the number of points in a row from the top with toright [i]> = len, otherwise down [i] is similar for points below. Then a horizontal segment of length len, starting at the i-th point, lies in up [i] * down [i] rectangles with a side len. How to recalculate the answer for all points on a segment? Let's keep the points sorted by (y, x) and then add on the segment using prefix sums.
Solution for O (n√n) We modify the previous solution. We will sort out not only horizontal, but also vertical segments. But it does not consider segments whose length coincides with the larger side of the rectangle. Consequently, we do not have to go through segments with a length greater than √n In this case, we must not count the squares two times. This can be done by running first on horizontal lines, counting squares, and then on vertical ones, not counting squares.
This complicates the formula for the number of rectangles. We need to count the number of rectangles, with a side not less than the fixed segment. So now we are given some numbers up, down, cut and need to count the number of pairs of integers (i, j), where 1 ⩽ i ⩽ up, 1 ⩽ j ⩽ down, i + j> cut
If cut ⩽ up, then for all i = cut, .., up, any j is suitable. Add to the answer (up − cut + 1) · down, assign up: = cut − 1 and then assume that up <cut ∑up i = 1∑down 1 (1, i + j> cut) = ∑up i = 1 max (0, down− (cut − i)) = ∑up i = max (1, cut − down) (down − cut + i)
Denote l = max (1, cut - down), r = up. If l ⩽ r, then add (r − l + 1) · (down − cut) + (r · (r + 1) / 2– (l − 1) · l / 2) to the answer
Solution in O (n ^ 2) Briefly: we want to iterate through any horizontal segment from the points in the set and count in how many rectangles with a side equal to the length of the segment, it lies.
First, O (nlogn) is presumed to be for each point directly to the top, bottom and right neighbor. Then for the line we consider toright [i] = 1 + the number of points in a row to the right of the i-th point.
We iterate over the length of the segment len. We count the lines up [i] and down [i] for each point up [i] = 0 if toright [i] <len up [i] = 1 + the number of points in a row from the top with toright [i]> = len, otherwise down [i] is similar for points below. Then a horizontal segment of length len, starting at the i-th point, lies in up [i] * down [i] rectangles with a side len. How to recalculate the answer for all points on a segment? Let's keep the points sorted by (y, x) and then add on the segment using prefix sums.
Solution for O (n√n) We modify the previous solution. We will sort out not only horizontal, but also vertical segments. But it does not consider segments whose length coincides with the larger side of the rectangle. Consequently, we do not have to go through segments with a length greater than √n In this case, we must not count the squares two times. This can be done by running first on horizontal lines, counting squares, and then on vertical ones, not counting squares.
This complicates the formula for the number of rectangles. We need to count the number of rectangles, with a side not less than the fixed segment. So now we are given some numbers up, down, cut and need to count the number of pairs of integers (i, j), where 1 ⩽ i ⩽ up, 1 ⩽ j ⩽ down, i + j> cut
If cut ⩽ up, then for all i = cut, .., up, any j is suitable. Add to the answer (up − cut + 1) · down, assign up: = cut − 1 and then assume that up <cut ∑up i = 1∑down 1 (1, i + j> cut) = ∑up i = 1 max (0, down− (cut − i)) = ∑up i = max (1, cut − down) (down − cut + i)
Denote l = max (1, cut - down), r = up. If l ⩽ r, then add (r − l + 1) · (down − cut) + (r · (r + 1) / 2– (l − 1) · l / 2) to the answer
Task "Playing on the field"
Input File Name : Standard Input
Output File Name : Standard Output
Time limit : 1 second
Memory limit : 64 megabytes
Innocent decided to play the following fun game: Given a field of N x M cells (height - N cells, width - M cells). Let cell (x, y) be the cell in the xth row and yth column (the rows are numbered from top to bottom, and the columns from left to right). Initially, S stones lie in the cage (1, 1) (S> = 4), these stones need to be moved to the cage (N, M). The game is divided into moves, each turn Innocent should move some part of stones from each cell of the field up / right / down / left 1 cell, and leave some part in this cell, parts can be zero (do not contain a single stone ), also the amount of the number of stones in the parts must be equal to the initial number of stones in the cage, and stones can not go beyond the field. It is worth noting that Innocent uses movement for all cells at the same time.
Formal rules : Let before making a move in the i-th row, the j-th column will be a [i] [j] of stones, and let the rule of moving stones for this cell be 4 numbers: b [i] [j] [0 ], b [i] [j] [1], b [i] [j] [2], b [i] [j] [3] - the number of stones that move from the cage (i, j) to the cage (i - 1, j), (i, j + 1), (i - 1, j), (i, j - 1) respectively (b [i] [j] [0] + b [i] [j] [ 1] + b [i] [j] [2] + b [i] [j] [3] <= a [i] [j]). Let after making a move in the i-th row, the j-th column will be with [i] [j] stones then
with [i] [j] = a [i] [j] - (b [i] [j] [0] + b [i] [j] [1] + b [i] [j] [2] + b [i] [j] [3]) + b [i + 1] [j] [0] + b [i] [j - 1] [1] + b [i + 1] [j] [2] + b [i] [j + 1] [3]. We assume that b [i] [j] [k] = 0, for i, j outside the limits (1..N) and (1..M), respectively. A game is considered to be won if there is a move with a number less than or equal to H, such that, on this move, b [N] [M] becomes equal to S, and after this move there will be no movements.
* The moves are numbered from 1st to Hth.
However, Innokentiy quickly realized that this game was too simple for him. And he came up with some restrictions for himself, to complicate the game. First, now instead of setting the rule for each individual cell, it now sets the rule for each possible number of stones in the cells, that is, for each z (number of stones in the cell), comes up with a rule consisting of 4 numbers: d [z] [0], d [z] [1], d [z] [2], d [z] [3]. And then on every move the stones move according to the “formal rules b [i] [j] [k] = d [a [i] [j]] [k] for all i, j, k. Also b [i] [j] [k] = 0, regardless of d [a [i] [j]] [k], if for the data i, j, k the cell where b [i] [j] should go [k] stones out of the field.
Soon, Innokentiya got bored with the game and with such restrictions, and therefore he wanted to deal with this game once and forever inventing such a strategy (that is, such d [z] [0], d [z] [1], d [z] [2 ], d [z] [3] for each z), which will win the game for all possible fields (that is, for all N, M: 1 <= N <= MAXN, 1 <= M <= MAXM), and for all possible initial quantities of stones (that is, for all S: 4 <= S <= MAXS).
Input Format
Nothing is input.
Output format
Print MAXS lines, i-th line should consist of 4 numbers separated by spaces: d [i]] [0], d [i] [1], d [i] [2], d [i] [3] . These strings should describe a strategy that will win the game for all the initial data, such that:
1 <= N <= MAXN
1 <= M <= MAXM
MAXN = MAXM = 50
4 <= s <= maxs
MAXS = 100 H = 300
Comment
An example of a possible strategy:
For all i: d [i] [0] = 0, d [i] [1] = i, d [i] [2] = 0, d [i] [3] = 0, this strategy sets the movement of all stones 1 cell to the right, it is easy to understand that this strategy is advantageous for all single-line fields, and losing for all the others.
Analysis of the “Play on the Field” task
In this problem, there are 2 different approaches to solving the problem.
1. Purely mathematical approach - trying to come up with some kind of strategy that will satisfy all conditions. There are a lot of data strategies, but most of them have many extreme cases that need to be processed separately. An example of one of the strategies, and the reasoning that led to its inventing are listed below.
2. Write a brute force strategy, with some cutoffs, and a tester that will check the correctness of the solution. In this case, the solution is quite quickly, and in addition, the correctness of the strategy is guaranteed.
Code :
An example of a winning strategy:
Code : Description: Let z be the number of stones in a certain cell. Consider a few considerations:
1. If z ⩾ 4, then from this cell the stones can move, only to the right and down, so, otherwise, with S = z, all S stones will never remain in the lower right cell.
2. If z ⩾ 4, then some non-zero part of the stones must go to the right, and some non-zero part must go down, as otherwise, with S = z, we lose in the tables consisting of 1 row, or 1st column.
3. If the number of stones lying initially in the left upper cell is ⩾ 4, then we can consider the values as 1, 2, 3 as some basic parts, with the help of which we will break up large parts.
Based on these considerations and some assumptions, you can come to the following strategy. The main part of the stones (let's call it T) goes down, and at each turn it separates several basic parts from itself. 1 and 2 will move completely to the right, and 3-ka will move all the way down, the idea of the strategy is to separate parts 1 and 2 from T, and 3-ki should be collected only on the right border, from where they will come to the bottom cell . Let T consisting of z stones be divided as follows:
• the main part goes down without 3 stones, that is, z - 3 stones;
• 2 stones go to the right;
• 1 stone remains in this cell.
Then the units and twos will go to the right until they gather in 3-ku on the right border. However, there are flaws in this strategy, namely, it will not work for small z. For example, because the 6-ka for this strategy is divided into 2, 1 and 3, and 3-ka will go down, although it is still on the left border, so you still need to carefully consider the number of stones from 4 to 6, and the rest will break up into basic parts and parts 4.
As a result, we get this strategy:
1. Purely mathematical approach - trying to come up with some kind of strategy that will satisfy all conditions. There are a lot of data strategies, but most of them have many extreme cases that need to be processed separately. An example of one of the strategies, and the reasoning that led to its inventing are listed below.
2. Write a brute force strategy, with some cutoffs, and a tester that will check the correctness of the solution. In this case, the solution is quite quickly, and in addition, the correctness of the strategy is guaranteed.
Code :
An example of a winning strategy:
Code : Description: Let z be the number of stones in a certain cell. Consider a few considerations:
1. If z ⩾ 4, then from this cell the stones can move, only to the right and down, so, otherwise, with S = z, all S stones will never remain in the lower right cell.
2. If z ⩾ 4, then some non-zero part of the stones must go to the right, and some non-zero part must go down, as otherwise, with S = z, we lose in the tables consisting of 1 row, or 1st column.
3. If the number of stones lying initially in the left upper cell is ⩾ 4, then we can consider the values as 1, 2, 3 as some basic parts, with the help of which we will break up large parts.
Based on these considerations and some assumptions, you can come to the following strategy. The main part of the stones (let's call it T) goes down, and at each turn it separates several basic parts from itself. 1 and 2 will move completely to the right, and 3-ka will move all the way down, the idea of the strategy is to separate parts 1 and 2 from T, and 3-ki should be collected only on the right border, from where they will come to the bottom cell . Let T consisting of z stones be divided as follows:
• the main part goes down without 3 stones, that is, z - 3 stones;
• 2 stones go to the right;
• 1 stone remains in this cell.
Then the units and twos will go to the right until they gather in 3-ku on the right border. However, there are flaws in this strategy, namely, it will not work for small z. For example, because the 6-ka for this strategy is divided into 2, 1 and 3, and 3-ka will go down, although it is still on the left border, so you still need to carefully consider the number of stones from 4 to 6, and the rest will break up into basic parts and parts 4.
As a result, we get this strategy:
| amount | To the right | Way down |
|---|---|---|
| one 2 3 four five 6 z ⩾ 7 | one 2 0 2 one 2 2 | 0 0 3 one 2 2 z − 3 |
Source: https://habr.com/ru/post/348646/
All Articles