You can download my codes to all problems here.

I will write a full editorial in the next few days. Now you can read hints and short solutions.

750B - New Year and North Pole

**hint**

**hint1**

**hint2**

**hint1**

**hint2**

**solution**

750E - New Year and Old Subsequence

**hint1**

**hint2**

**hint3**

**hint4**

750F - New Year and Finding Roots

**part1**

**part2**

**part3**

**part4**

**part5**

750G - New Year and Binary Tree Paths

**hint1**

**hint2**

**hint3**

**hint4**

**hint5**

**hint6**

750H - New Year and Snowy Grid

**hint1**

**hint2**

# 750A - New Year and Hurry

Do you see what is produced by the following piece of code?

```
int total = 0;
for(int i = 1; i <= n; ++i) {
total += 5 * i;
printf("%d\n", total);
}
```

We iterate over problems (a variable `i`

denotes the index of problem) and in a variable `total`

we store the total time needed to solve them. The code above would print numbers 5, 15, 30, 50, ... — the *i*-th of these numbers is the number of minutes the hero would spend to solve easiest *i* problems.

Inside the loop you should also check if there is enough time to make it to the party, i.e. check if `total + k <= 240`

.

simple C++ code:24067296

shorter but harder C++ code: 24067301

python: 24067479

# 750B - New Year and North Pole

Our goal is to simulate Limak's journey and to check if he doesn't make any forbidden moves. To track his position, it's enough to store one variable denoting his current distance from the North Pole. To solve this problem, you should implement checking three conditions given in the statement.

Updating `dist_from_north`

variable is an easy part. Moving *t*_{i} kilometers to the North increases the distance from the North Pole by *t*_{i}, while moving South decreases that distance by *t*_{i}. Moving to the West or East doesn't affect the distance from Poles, though you should still check if it doesn't happen when Limak is on one of two Poles — you must print "NO" in this case.

Let's proceed to checking the three conditions. First, Limak can't move further to the North if he is already on the North Pole *"at any moment of time (before any of the instructions or while performing one of them)"*. So you should print "NO" if `direction == "North"`

and either `dist_from_north == 0`

or `dist_from_north < t[i]`

. The latter case happens e.g. if Limak is 150 kilometers from the North Pole and is supposed to move 170 kilometers to the North — after 150 kilometers he would reach the North Pole and couldn't move further to the North. In the intended solution below you will see an alternative implementation: after updating the value of `dist_from_north`

we can check if `dist_from_north < 0`

— it would mean that Limak tried to move North from the North Pole. Also, you should print "NO" if `dist_from_north == 0`

(i.e. Limak is on the North Pole) and the direction is West or East.

You should deal with the South Pole case in a similar way. Limak is on the South Pole when `dist_from_north == M`

.

Finally, you must check if Limak finished on the North Pole, i.e. `dist_from_north == 0`

.

There were two common doubts about this problem: 1) *"Limak is allowed to move 40 000 kilometers to the South from the North Pole and will be again on the North Pole."* 2) *"Moving West/East may change the latitude (equivalently: the distance from Poles) and this problem is hard 3d geometry problem."* Both doubts make sense because they come from misinterpreting a problem as: Limak looks in the direction represented by the given string (e.g. to the North) and just goes straight in that direction (maybe after some time he will start moving to the South but he doesn't care about it). What organizers meant is that Limak should be directed in the given direction at any moment of time, i.e. he should continuously move in that direction. It's a sad thing that many participants struggled with that. I should have written the statement better and I'm sorry about it.

C++ code: 24067685

python code: 24067669

# 750C - New Year and Rating

We don't know the initial or final rating but we can use the given rating changes to draw a plot of function representing Limak's rating. For each contest we also know in which division Limak was.

Red and blue points denote contests in div1 and div2. Note that we still don't know exact rating at any moment.

Let's say that a *border* is a horizontal line at height 1900. Points above the border and exactly on it should be red, while points below should be blue. Fixing the placement of the border will give us the answer (because then we will know height of all points). Let's find the highest blue point and the lowest red point — the border can lie anywhere between them, i.e. anywhere between these two horizontal lines:

Small detail: the border can lie exactly on the upper line (because rating 1900 belongs to div1) but it can't lie exactly on the lower line (because 1900 doesn't belong to div2).

The last step is to decide where exactly it's best to put the border. The answer will be 1900 + *d* where *d* is the difference between the height of the border and the height of the last point (representing the last contest), so we should place the border as low as possible: just over the lower of two horizontal lines we found. It means that the highest blue point should be at height 1899.

There is an alternative explanation. If Limak never had rating exactly 1899, we could increase his rating at the beginning by 1 (thus moving up the whole plot of the function by 1) and everything would still be fine, while the answer increased.

To implement this solution, you should find prefix sums of rating changes (what represents the height of points on drawings above, for a moment assuming that the first point has height 0) and compute two values: the smallest prefix sum ending in a div1 contest and the greatest prefix sum ending in a div2 contest. If the first value is less than or equal to the second value, you should print "Impossible" — it means that the highest blue point isn't lower that the lowest red point. If all contests were in div1, we should print "Infinity" because there is no upper limit for Limak's rating at any time (and there is no upper limit for the placement of the border). Otherwise we say that the highest blue point (a div2 contest with the greatest prefix sum) is a contest when Limak had rating 1899 and we easily compute the final rating.

*O*(*n*) code in C++: 24069564

code in C++, with binary search: 24069586

# 750D - New Year and Fireworks

A trivial *O*(2^{n}) solution is to simulate the whole process and mark visited cells. Thanks to a low constraint for *t*_{i}, a backtrack with memoization has much better complexity. Let's understand the reason.

Parts of the firework move by *t*_{i} in the *i*-th level of recursion so they can't reach cells further than from the starting cell. That sum can't exceed *n*·*max*_*t* = 150. We can't visit cells with bigger coordinates so there are only *O*((*n*·*max*_*t*)^{2}) cells we can visit.

As usually in backtracks with memoization, for every *state* we can do computations only once — let's think what that "state" is. We can't say that a state is defined by the current cell only, because maybe before we visited it going in a different direction and now we would reach new cells. It also isn't correct to say that we can skip further simulation if we've already been in this cell going in the same direction, because maybe it was the different level of recursion (so now next step will in in a different direction, what can allow us to visit new cells). It turns out that a state must be defined by four values: two coordinates, a direction and a level of recursion (there are 8 possible directions). One way to implement this approach is to create `set<vector<int>> visitedStates`

where each vector contains four values that represent a state.

The complexity is what is enough to get AC. It isn't hard to get rid of the logarithm factor what you can see in the last code below.

If implementing the simulation part is hard for you, see the first code below with too slow exponential solution. It shows an easy way to deal with 8 directions and changing the direction by 45 degrees — you can spend a moment to hardcode changes of *x* and *y* for each direction and clockwise or counter-clockwise order and then keep an integer variable and change its value by 1 modulo 8. You can add memoization to this slow code yourself and try to get AC.

too slow *O*(2^{n}) approach (TLE): 24070543

the same code with memoization (AC): 24070548

faster memoization without logarithm (AC): 24070567

# 750E - New Year and Old Subsequence

It's often helpful to think about an algorithm to solve some easier problem. To check if a string has a subsequence "2017", we can find the find the first '2', then to the right from that place find the first '0', then first '1', then first '7'. If in some of these 4 steps we can't find the needed digit on the right, the string doesn't have "2017" as a subsequence. To additionally check if there is a subsequence "2016", after finding '1' (before finding '7') we should check if there is any '6' on the right. Let's refer to this algorithm as *Algo*.

It turns out that the problem can be solved with a segment tree (btw. the solution will also allow for queries changing some digits). The difficulty is to choose what we want to store in its nodes. Let's first use the Algo to answer simpler queries: *"for the given segment check if it's nice"*.

There is only one thing that matters for segments represented by nodes. For a segment we want to know for every prefix of "2017" (e.g. for "20"): assuming that the Algo already got this prefix as a subsequence, what is the prefix we have after the Algo processes this segment. Let's see an example.

TODO