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**

Create a variable that will denote your current distance from the North Pole. What are allowed values of this variable? When can't we go West or East?

**hint1**

Let *x* denote the initial rating (or his final rating, whatever is easier for you to think about). The information that Limak is in some division in the *i*-th contest gives us some inequality for *x*. Can you see it?

**hint2**

For every contest we know that the current rating is *x* increased by some prefix sum of c_i (changes of rating). If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum. If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is x <= 1899-prefSum. From this set of inequalities, your task is to find the biggest *x* satisfying all of them.

**hint1**

Since constrains are quite low, the firework won't visit cells far away from the initial cell. There aren't that many cells that can be visited. How can we use this fact?

**hint2**

If the initial cell has coordinates (0, 0), we are interested only in cells with coordinates up to MAX_N * MAX_T that is equal to 30·5 = 150. So there are *O*(150^{2}) interesting cells. Use backtrack with memoization. Think about possible states.

**solution**

As a state you should keep: x-coordinate, y-coordinate, the current direction of this part of firework, and the recursion level (it says how much time this part will live). You can keep everything in C++ set, or use a big boolean array to make your solution faster.

750E - New Year and Old Subsequence

**hint1**

The intended solution is also able to process queries of form "change the i-th digit to x". This is a big hint.

**hint2**

Build a segment tree to answer queries in . What should be stored in such a tree?

**hint3**

Imagine going from left to right over a substring, maybe removing some digits. What is important in every moment is: what prefix of "2017" we already got as a subsequence. How to apply it to segment that should be merge in the segment tree?

**hint4**

In the segment tree store matrices of size 5 x 5, where *t*[*i*][*j*] means: the minimum number of digits to remove so that if there it was already possible to get prefix of "2017" of length *i*, then with this segment of digits it will be possible to get prefix of "2017" of length *j* (*i* ≤ *j*).

750F - New Year and Finding Roots

**part1**

The intended solution is deterministic (it doesn't use any randomization). There is just enough queries to always find the root. So, you can't waste even one query. After asking about the first vertex, you should start moving from there, asking about its neighbour and its neighbour again, till you get a leaf. After getting a leaf let's start again from the first vertex and go in some other direction, again till you find a leaf. Now you have a path between two leaves. Draw it on paper. Where you should now go, to find a root?

**part2**

You should find LCA of the found path and go from there to a neighbour that wasn't yet visited. Then again go till you find a leaf (because what else could we do?). Draw on paper a situation after finding some new leaf. You should see that again we should choose LCA of some path and go in some particular direction. How many queries do we need to find the root?

**part3**

We need queries at most, what happens if me always go from LCA to its parent and then unfortunately we start moving down. You are close to the solution now!

**part4**

If our current LCA is close to the root (we know that when it's far away from leaves), instead of going blindly in some direction to get a leaf after ~6 queries, we should check only vertices close to the LCA. After going from LCA to its last unknown neighbour, we should check that neighbour's neighbours and also their neighbours (in total, checking all vertices withing distance 2). The root must be there! This approach needs 1 + 2 + 3 + 4 + 1 + 2 + 4 = 17 queries. Can you get rid of one more query in some easy way?

**part5**

If you already used 16 queries, instead of asking about one more neighbour, you should say that it's the root. It's the last candidate so it must indeed be a root.

750G - New Year and Binary Tree Paths

**hint1**

All paths consists of LCA and two sides. It's hard to iterate over LCA in this problem so try to iterate over length of sides.

**hint2**

It turns out that lengths of sides are enough to compute exact value of LCA. Find a formula on paper or see my code (the top of this page). Now you can subtract something from *s* and assume that we count paths with LCA equal to 1, still with fixed length of left and right sides. Now some observation is needed.

**hint3**

What is the sum of vertices on a path from 1 to *x*? It's almost 2·*x*, right?

**hint4**

It is 2·*x* - *popcount*(*x*) (maybe - 1 or + 1). Try to use it solve solve the problem of counting paths with LCA equal to 1 and some fixed length of sides.

**hint5**

If endpoints are *a* and *b*, the sum of vertices will be something like 2·*a* - *popcount*(*a*) + 2·*b* - *popcount*(*b*). Since popcounts are small, we can iterate over them. Then we know that 2·*a* - *popcount*(*a*) + 2·*b* - *popcount*(*b*) = *something* means 2·*a* + 2·*b* = *something* + *popcount*(*a*) + *popcount*(*b*), so we know how big *a* + *b* should be. What remains is to quickly solve the following problem: Count the number of pairs (*a*, *b*) with fixed length of binary representations, fixed sum and fixed total number of 1's in the binary representation.

**hint6**

Dynamic programming on bits.

750H - New Year and Snowy Grid

**hint1**

Duality

**hint2**

For every query we must say if the top-right side is almost connected with the bottom-left side. Here, "almost connected" means that they would be connected after adding at most one more vertex (cell). With preprocessing, you should find CC's (connected components) in the dual problem. Remember that now from one cell you can go in 8 directions. Also find pairs of CC's that are almost connected.

It is deleted

Yes it can be, it says so in statement, and you can look at worse rating to confirm :)

thanks, I just reread the statement :'( and worse has no rating :v

I think, you mean worse.

I think, you mean worse

Oh Coach Ray

could you please attach this tutorial to the contest materials? I haven't found it till now! thanks.

Didn't get the last part "solution" of editorial of E-problem. If someone can explain it again with an example it would be great :)

Consider the regular expression

`.*2.*0.*1.*7.*`

and build its automaton:It's evident that if the requested (sub)string matches this expression, then it contains the "2017" subsequence. Now we are to delete some letters from it to exclude the "2016" sequence.

Weigh the automaton transitions:

`W(0 -> 0 with '2') = 1`

,`W(1 -> 1 with '0') = 1`

, etc — to stay in the current state when receiving a letter which moves us to the next one, we should delete this letter. Also,`W(3 -> 3 with '6') = 1`

and`W(4 -> 4 with '6') = 1`

— if we've already taken "201" or "2017", we must drop every '6' we encounter. Other edges not mentioned above have weight of 0.Define a 5x5 matrix

`m`

for a string`s`

, such that`m[i][j]`

(`i <= j`

) is a minimal cost to get from state`i`

to state`j`

, feeding the automaton with`s`

's characters.Suppose we have two strings,

`p`

and`q`

, and their matrices,`mp`

and`mq`

. We can easily merge them, obtaining a matrix for their concatenation (looks similiar to Floyd's algorithm).Notice that matrix merging operation is associative. So, we can build the RMQ on it.

When using segment tree, we gain

`O(n*log n + q*log n)`

time and`O(n)`

space solution, online.23454158

~~It could be improved up to~~`O(n + q)`

using RMQ to LCA conversion and some`O(n)/O(1)`

(precalc/query) LCA algo (e.g., Schieber-Vishkin).thanks :)

Hey , I have a doubt , have a look http://pastebin.com/TwgNC70X

For "1", the matrix should look like:

For "6":

And for "16":

I implemented the idea as per your explanation, but getting TLE. 23502332. Any suggestions?

It seems that you store too much data at a single node of the segment tree. There are only 14 numbers need to be take care of. (Pay attention to the constraint j>=i)

15, actually. However, it is possible to get AC even without this optimization.

Seems that you allocated too few nodes.

`1 << 19 < 4 * 2e5`

.I guess number of nodes in segment tree is at most 2^(ceil(log2(n))+1) = 2^19. Please correct me here.

Oh, you are right! Always thought that the upper bound is

`4 * n`

. Thank you!There are plenty of ways to optimize your code.

`std::array`

or just plain arrays wrapped with a`struct`

) will prevent your program from using dynamic memory. Heap manager would be just happy.`cin.tie(nullptr);`

at the beginning of`main`

to prevent from flushing stdout whenever you read something.I suppose using any of these (probably, except the last one) should be enough to get AC. Applying all these techniques together, I managed to get AC in less than 400 ms: 23491398.

Thanks, got AC with applying 1 and 2. 23512670. Also, it was the first time, I heard of non-recursive segtree. Thanks for that too!

Nice solution! Help me a lot! Thank you very much!

Can C be solved using Binary search ? If YES , then how ?

Yes

Binary search over the rating before first round

Check if it's possible to have that rating without problems/conflicts in divisions at the start of all contests

if no problems try bigger numbers

if there are problems like:

1: rating is < 1900 and we are supposed to be in div1 in current contest: try bigger numbers

2: rating is > 1899 and we are supposed to be in div2 in current contest: try smaller numbers

The answer is infinity if all contests are in div1

Solution Link

The tricky thing here is the upper limit on t-s.

Since the firework cannot fly further that |kt| from the startpoint after k iterations, you'll find yourself in the (2nt)^2 square that is equal to 300 * 300.

Hence O(n * 2^n) turns to O(n^3 * t^2)

I tried to implement his solution. It's giving me the right output of course but I am getting TLE on higher recursion levels since as you have pointed out, it's exponential(at least my code). Can someone help me out?

There can be at-most

`2^29`

particles after`N`

explosions. If you consider a state of the particle in terms of Grid,Level,Direction`(X,Y,T,Dir)`

from`Pigeon Hole Principle`

there must exist (at some point`2^k > 321^2 * 30 * 3^2`

) two or more particles starting in the same Grid, moving in the same direction at the Same level. For these kinds of particles,`you only need to track one instance`

of it. By this way you wont be keeping track of more than`321^2 * 8`

particles at an instance.This leaves you with a complexity of

`O(Height*Breadth*Levels*Distance*Directions)`

`O(N^2 * 30 * 5 * 8)`

`O(N^2)`

In a way, I had a very similar solution to the intended solution for E. Instead of a segment tree storing a 5*5 matrix, I implemented a sparse table to the same effect (23455422). As a result, the memory limit acted and I had to make a last-minute compression to take out the cases where

`i>j`

. I wonder if the memory limit was imposed to prevent the sparse table solution.I can't figure out what's wrong with my submission for C : 23443890

Where is the mistake in the code ?

lower must be -inf

Thanks a lot. My bad — I thought ratings couldn't be negative. Figures. If ya think ratings are low now — they can always go lower. Reminds me to read the question properly and never take anything for granted.

Still can't understand E.. How by removing digits we can get longer segment? (about T[i][j]).

I understood it as while merging segments, T[i][j]= min(left.T[i][k]+right.T[k][j]); So T[i][j] for some segment represents the minimum chars to be deleted to produce substring i+1..j of 2017. This also means that the 0..i part of 2017 will be taken from the left of this segment.

Look at my submission to see the assignment of matrix for leaf nodes. Lets say we encounter a 0, then mat(1)(2) becomes 0 as if we are taking 2 from left side, then this segment can provide 0 to complete 20. If we skip this 0, then it allows 2 to be taken from left side of this segment, and to skip 0, mat(1)(1)= 1. It wasnt very clear to me in beginning how its working but give it some time and then it would be clear.

Perfect example would be something like 20110667.Here optimal solution is to remove the zero at second place.For the segment(20) in the tree t[0][1]=1(we will have to delete 0).Although t[0][2]=0 but when it propogates upwards it is not optimal because we will either have to delete 2 1's or 2 6's

thanks!

In problem E, I stored another kind of information in the segment tree.

Suppose we have some string s1 ("2017", for example) and some other string s2 ("2016", for example). We want our current segment to contain s1 as a subsequence and do not contain s2 as a subsequence. What is the minimum number of deletion we have to make?

This information could be updated using the answers of the node's children in the segment tree.

For example, let s1 = "2017", s2 = "2016".

Then we have to consider the following values:

AnswerOfTheLeftChild("", "2") + AsnwerOfTheRightChild("2017", "2016")

AnswerOfTheLeftChild("2", "20") + AsnwerOfTheRightChild("017", "016")

AnswerOfTheLeftChild("20", "201") + AsnwerOfTheRightChild("17", "16")

AnswerOfTheLeftChild("201", "2016") + AsnwerOfTheRightChild("7", "6")

AnswerOfTheLeftChild("2017", "2016") + AsnwerOfTheRightChild("", "6")

I generated all of such pairs (s1,s2) ad figured out, that there are only 14 of them. So it is possible to store 14 values in the segment tree node.

I managed to solve problem C with a different approach.

Keep two variables:

`from`

denoting the smallest possible value for the rating, and`to`

denoting the highest possible value for the rating.if at some point you were in a div2 contest and your smallest possible rating is larger than 1899 print Impossible, or if you were in a div1 contest and your highest possible value is less than 1900 print impossible.

Otherwise, if you are at a div2 contest then

`to = min(to, 1899)`

, or if you are at a div1 contest then`from = max(from, 1900)`

, then increase (or decrease) both variables by the amount of points you earned at the current contest. If at some point`from`

was higher than`to`

print Impossible.At the end, the rating is equal to the highest possible value which is

`to`

.Unfortunately, during the contest I was hacked because I forgot that the initial rating can be negative :(

Accepted Code

You just explained how to solve inequalities from the editorial.

I have an alternative solution for problem C. For the most part of the contest, I simply missed the simple solution.

Here's what I did instead.

Thread separately the cases when I have only one type of divisions (either div1 or div2). (Actually, solving the case when I have only div2 contests should have given me a huge hint for the simple solution earlier in the contest, but I had a bug in my logics).

Now, there will be at least one contest when I'll change my division (from div2 to div1 and vice-versa). Let's take the first one and suppose I changed from div1 to div2 (the other case is identical). Then, rating[i — 1] + change[i — 1] = rating[i].

But rating[i] <= 1899, so rating[i — 1] + change[i — 1] <= 1899. So rating[i — 1] <= 1899 — change[i — 1]. (change[i — 1] is negative, since I fall in div2, so no problem here). rating[i — 1] will be between 1900 and 1899 + abs(change[i — 1]).

But abs(change[i — 1]) <= 100, so actually rating[i — 1] can take maximum 100 values. After I know that rating[i — 1] has a certain value, everything else is uniquely determined, so I can just simulate the values.

This gives me a O(max(changes) * n) solution. The implementation is pretty painful, but this is the price I payed for missing the simple solution: 23459419. Lesson learned, next time spend more time thinking for something simpler, it will pay off :) Good to know retrograd still loves me despite my newbie performances. <3 <3 <3

An alternative solution for D:

We again use the observation that only cells within 150 can be coloured so there are at most 300*300 cells to keep track of.

Suppose we are finding which squares are coloured by some firework of depth k, and we already know which squares are coloured by everything in the right 'subtree' (note there are at most 300*300). Then to get which squares are coloured by the left subtree, we can simply reflect them about the line formed by the the current firework.

Thus we can colour any single path in the 'firework tree' (for example we could just dfs, recursing on only the right subtree every time) and then reflect the tree as we go back up.

Then, the complexity, where S is the grid size, is O(S^2 * depth).

A last detail is how do we do the reflection? There are only 4 types of flips depending on which way the current firework is going: up/down, left/right and the two diagonals. So we can just do some slight case bashing with the coordinates...

Code: http://codeforces.com/contest/750/submission/23437226

I stucked and tried to solve third problem C "New Year and Rating" in the competetion. However, I couldn't solve. My codes reach 100 lines, but when I look the top-tier programmer from Final Standings, they solved about 10-15 line of code. It is clear that I have a trouble in way of thinking.

So, I wanna ask, why I couldn't? Do I need to work some algorithm design topics or just is it about experience?

This one's quite ad-hoc to be honest. With this problem, you should go by the concept of intersecting ranges, which are determined by the inequalities x <= 1899-c[i] or x >= 1900-c[i]. If you go by that concept, your code should be very short like the top tier guys. Not to toot my own horn, but my code for this problem was also around 10-15 lines ;).

Most of this ability to think of simpler solutions comes from experience and practice. The more problems you've done, the more likely you will have seen the techniques used in a contest problem.

I felt the same after the contest.

I wanted to ask about it in a blog post, but I think this is a good place.

Does anyone know any similar problem that is solved with

min/max?this

Can someone explain me this testcase of problem B(New Year and North Pole). 1 80000 South. Answer for this case is NO. But as for me we start at North Pole, go south 40k,implying we are at North Pole,again go south 40k, we end up at North pole Right.

Thank you.

First, you have to go 20k, when you reach the South pole. However, you can't go south from the South pole.

"If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North." So after having completed 20000 km of journey, Limak is now at South Pole, but from South Pole you can only go North, but the instruction had said about going South, thus the description is no longer valid. So answer will be NO.

The important thing which many of us missed is to also check the validity of the instructions.

Hi, Please anyone help .. My submission on Problem E is getting Runtime Error.. here is my code

The array size for segtree.

yeah.. I got it.. thanks

very good style of editorial

Can someone explain the problem G? It is not clear. Thanks in advance.

http://codeforces.com/contest/750/submission/23469026

Can someone please spend some time and help point out where did I made a mistake? I think I should've blocked all causes of Idleness TLE but it doesn't.

Can somebody explain me the concept of duality? Or at least what I need to know about it for solving H? I know about duality and the dual plan from the voronoi diagram but I don't see any correlation. Thank you in advance!

So... what's the complexity of solution in G problem? I've accepted

O(log^{6}), but I had some hard times trying to optimize it. My dynamic part worksO(log^{4}) and I'm not sure how to do it faster :'(O(log^{5}): fix the sum of popcounts of a and b rather than fixing each popcount separately and then do dp bit by bit, keeping track of current sum of popcounts and making sure a+b is equal to something.I suspect it can be done in

O(log^{4}) if we don't fix the popcount sum but I'm not able to work out the details."It turns out that lengths of sides are enough to compute exact value of LCA. Find a formula on paper or see my code (the top of this page)"

Can anyone provide me a paper write about that or give me a hints to prove its correctness. It is still not clear to me.

Many thanks.

Same, need help here :(

Let's fix lengths of sides (

l_{a}andl_{b}), and let's denote LCA byv.Then,

s=av+b, whereadepends only onl_{a}andl_{b}.bdepends on actual nodes chosen but you can see that 0 ≤b<aalways.From discrete mathematics (or common sense) we know that given

m> 0, every numberxhas unique representationx=pm+qsuch that 0 ≤q<m.Therefore, there is only one possible set of values for

vandb: andb=s-av.Errichto, can you please point some problems that inspired problem E's solution? Thanks in advance! (It would be very useful if problem authors could point some similar problems to those they just made for the round. There are some pretty cool recurrent-but-not-so-famous techniques that just won't stop showing up!)

+1 to you. While looking upon solutions, almost everybody who solved it had a similar approach. They have come across this before.

Some similar problem please ?

http://codeforces.com/group/BDIXyZZHhT/contest/205914/problem/F

The solution for this problem has a similar merge function (not sure if there's another solution). The limits allow SQRT-Decomposition to pass. There are only update queries, but the same idea solves the range query version.

Do you know "calculate n-th (

n≤ 10^{18}) Fibbonacci number" problem?Yes, with fast exponentiation. Solutions for problem E use fast exponentiation?? (I still haven't had time check the solutions, but this is a surprise to me, because I have solved some tough matrix exponentiation problems and this idea didn't show up to me during the contest... Actually, the idea of using matrices didn't cross my mind in the first place)

Well, here you have not exponentiation but "product on the range [l;r]" (and with wierd multiplication)

And I call this thing multiplication, because it is similar in many aspects (what is important it is associative, but you may also "multiply" block matrix or "multiply by vector" etc)

This great post gave me the key idea to solving problem E. See also this article, which dives deeper and focuses on the implementation.

They also have Russian translations (well, the second one was originally written in Russian and then translated into English). Don't miss this nice article (Russian only, sorry).

Ok, I've just solved problem E and realized the real point of the exercise. The recurrent technique you should be familiar with is not only segment trees and monoids (the algebraic structures over which segment trees are built upon). You should also be familiar (at competitive programming level!) with DFAs/NFAs and their monoid behavior when represented by matrices. What I mean with "familiar at competitive programming level" is that you should be capable of adapting the representation/monoid to solve the problem (the solution is not a straightforward application of the technique).

Thanks to SirNickolas, the best reference: http://jkff.info/articles/ire/

My solution: 23493355

these kind of editorials are the best step by step hints rather than full blown solution.

i encourage codeforces to adopt spoilers inside the editorial

Can someone explain how we can get these convertions in D ?:

Set up two arrays of changes in y-coordinate and x-coordinate of the eight directions like this:

dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dx[8] = {0, 1, 1, 1, 0, -1, -1, -1} where -1 refers to North/West and 1 refers to South/East. So dy[0] and dx[0] means the fireworks moves towards North (0 degree), dy[1] and dx[1] means the fireworks moves towards North-East (45 degrees), etc.

When the fireworks splits, two new fireworks of +45 degrees and -45 degrees are formed, so you can get the new directions by moving your pointer to adjacent elements.

(dir+1) % 8 should be quite easy to understand (turning 45 degrees clockwise), but for anticlockwise turns we add 7 because (dir+7) = (dir+8-1).

Thanks a lot!

Can someone explain how to do G in O(log(s)^4). I could only come up with a O(log(s)^5) solution as described here.

What does it mean in F editorial? Can't get this part for hours >_<

You know that that max distance of the root from the LCA is atmost 3.

Go to the last unvisited neighbour of the LCA. Let it be v1 (v1 is at distance 1 from LCA). v1 has two unvisited neighbours. Let them be v2 and v3 (both are at distance 2 from LCA). Now, each of v2 and v3 have atmost two unvisited neighbours each. Let them be v4, v5, v6 and v7 (first two are connected to v2 and last two are connected to v3). All four of these v4, v5, v6 and v7 are at distance 3 from the LCA. The root is guaranteed to be one of these (from v4, v5, v6 or v7).

If you can't understand the above explanation, drawing a diagram might help. :)

Thanks, got that

Looking forward to a more detailed solution for problem H, or any materials about duality in this problem?

This duality is min cut max flow (you can see this problem for a similar idea: https://code.google.com/codejam/contest/3014486/dashboard#s=p2 ).

We want to know "is there a flow between the top left corner and bottom right corner with value at least 2?". Here, we have a grid graph, and we can only move in 4 directions. We can take the dual to convert it to "is there a cut with cost at least 2?". This is equivalent to finding "is there a cut with cost at most 1?" and negating the answer.

What is a cut of the grid graph? It turns out it is an 8-connected path from the bottom or left side to the top or right side (excluding the top-left corner and bottom-right corner).

Here, grid cells that are blocked cost 0, and grid cells that are empty cost 1, and we want to know if a path exists with cost at most 1.

Really helpful, thank you!

Can Someone explain the dp solution of the D problem. I'm not able to solve it

So in problem B, we can go west and east any number of kilometers, but we are not allowed to go 20,001 KM to the South for example ?

In other words, in this case

3 1 South 1000000000 East 1 North

I am allowed to go 1000000000 KM to the East.

But in this case,

1 40,000 South

I am not allowed to move around the earth :D logic xD