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
hintCreate 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?
750C - New Year and Rating
hint1Let 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?
hint2For 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.
750D - New Year and Fireworks
hint1Since 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?
hint2If 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(1502) interesting cells. Use backtrack with memoization. Think about possible states.
solutionAs 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
hint1The intended solution is also able to process queries of form "change the i-th digit to x". This is a big hint.
hint2Build a segment tree to answer queries in . What should be stored in such a tree?
hint3Imagine 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?
hint4In 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
hint1The intended solution is deterministic (it doesn't use any randomization).
hint2Start from some vertex and try to find a path to any leaf. Knowing such a path, do we know in which direction we should go to find the root?
hint3It's actually more useful to find a path between two leaves.
hint4If you slightly exceed the number of queries allowed, try to get rid of some unnecessary queries at the end.
Also, the solution description of this problem is split into parts hidden in ,,spoiler'' tags. At any moment you can stop reading and try to finish the solution on your own.
750G - New Year and Binary Tree Paths
hint1A path consists of LCA and two sides.
We can iterate over the depth of LCA and the two ends of a path. The depth can be up to O(log(S)) ≈ 50.
Actually, it's enough to iterate over lengths of sides (the distance from LCA to each end of a path).
hint2It turns out that knowing the value of s and the lengths of sides is enough to compute the exact value of LCA. Try to find a formula yourself.
Now we can subtract something from s and assume that we count paths with LCA equal to 1, still with the chosen length of the left side and the right side.
hint3The sum of vertices from vertex 1 to vertex x is roughly equal to 2·x. What is the exact formula?
hint4It is 2·x - popcount(x). Try to use it to solve the problem of counting paths with LCA equal to 1 and some fixed lengths of sides.
hint5Dynamic programming on bits.
750H - New Year and Snowy Grid
hint2For 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.
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
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 ti kilometers to the North increases the distance from the North Pole by ti, while moving South decreases that distance by ti. 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
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
A trivial O(2n) solution is to simulate the whole process and mark visited cells. Thanks to a low constraint for ti, a backtrack with memoization has much better complexity. Let's understand the reason.
Parts of the firework move by ti 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(2n) approach (TLE): 24070543
the same code with memoization (AC): 24070548
faster memoization without logarithm (AC): 24070567
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
part1The goal is to find a vertex with exactly two neighbours — this will be the root.
Also, let's notice that for a leaf we would get a list of exactly one neighbour. So we will know if we asked about the root or a leaf.
part2The solution is deterministic.
Any randomized solution would likely fail — there are 500 test cases per test file, and usually there are 30-100 tests for a problem, so you must pass around 25,000 test cases. That's bad if you ask too many queries even with a small probability.
part3You can ask about a vertex (say, A), then ask about one of its neighbours (say, B), then ask about one of neighbours of B, and so on, until you get a leaf. The sequence of visited vertices (A, B, ...) is a path in the tree.
How can this path look like in the whole tree? Do we know the distance from A to the root of the tree?
part4To be able to say where exactly the path is in the tree, we should do one extra step.
From the initial vertex A, choose some other neighbour B2 and go from there again until you get a leaf. Now we have path between two leaves. The middle vertex on the path is the LCA and we know its distance from the leaves, so we also know its distance from the root.
In this case, vertex B1 turned out to be the middle of the path:
Where should you go now to find the root?
part5Let's call that "middle vertex of the path" as P. We asked a query about P already, so we know its neighbours. Two neighbours are on the path, and the third one (the one not yet asked/visited) must be the parent of P. Let's go to that parent (so, ask a query about it) and then again continue until you find a leaf.
Where should we go now?
part6We know that we went from P to its parent, then maybe again to a parent, but eventually we started going down.
If we know the numbers of steps it took us to get to a leaf (so, the length of the blue path), we can calculate the number of steps we went up. So we know what is the current LCA of asked/visited vertices and we can go up from there.
Alternatively, we can notice that we have a new longer path between two leaves (marked green below). Let P2 be the midddle of the path. P2 must be the vertex closest to the root (so, LCA of everything we asked/visited so far).
We repeat the process, until we get the root of the tree (so, a vertex with two neighbours). What is the number of queries we can ask up to that moment?
part7In the worst case, we start from P0 being a leaf, and then the i-th new path will have i + 1 vertices. The following drawing shows the visited (asked) vertices in the worst case for h = 5. The not-yet-visited neighbour of P3 must be the root.
For height h, we can ask up to 1 + 2 + 3 + ... + (h - 1) queries, which is . The limit from the statement is 16, while for h = 7 we get up to 21 queries. We are close to the solution. Do you see how to get rid of a few queries?
part8If the parent of a current Pi is within distance 2 from the root, we can just check all vertices within distance 2 (red vertices on the drawing) and we will find the root there.
The number of queries needed now is 1 + 2 + 3 + 4 + (1 + 6) = 17, where "1+6" represents the "PARENT" and the red vertices. We exceed the limit just by 1 now. How to get rid of one query?
part9If you already asked about all red vertices but one, the last one must be the answer. We don't have to ask a query about it.
That's it, we use at most 16 queries.
Iterate over L and R — the length of sides of a path. A "side" is a part from LCA (the highest point of a path) to one of the ends of a path.
For fixed LCA and length of sides, let the "minimal" path denote a path with the minimum possible sum of values. In each of the sides, this path goes to the left child all the time:
If the LCA is x, the smallest possible sum of vertices on the left side of the minimal path has the sum of vertices:
SL = 2·x + 4·x + ... + 2L·x = (2L + 1 - 2)·xWe can find a similar formula for the minimum possible sum of the right side SR. For fixed L, R, x, the total sum of any path (also counting LCA itself) is at least:
SL + LCA + SR = (2L + 1 - 2)·x + x + ((2R + 1 - 2)·x + 2R - 1)From this, with binary search or just a division, we can compute the largest x where this formula doesn't exceed the given s. This is the only possible value of LCA. Larger x would result with the sum exceeding s. Smaller x would result in too small sum, even if a path goes to the right child all the time (so, the sum is maximized). Proof: every vertex is strictly smaller than the corresponding vertex in the "minimal" path for the computed largest possible x:
So, from L and R we can get the value of LCA.
Let's assume that the computed value of LCA is 1. For any other value we know that the value of vertex on depth k would be greater by (x - 1)·2k compared to LCA equal to 1, and we know depths of all vertices on a path, so we can subtract the sum of those differences from s, and assume the LCA is 1.
The sum of vertices from 1 to a is 2·a - popcount(a). Proof: if the binary representation of a has 1 on the i-th position from the right, there will be 1 on the (i - 1)-th position in the index of the parent of a and so on. So this bit adds 2i + 2i - 1 + ... + 1 = 2i + 1 - 1 = 2·2i - 1, so everything is doubled, and we get "-1" the number of times equal to the number of 1's in the binary representation of a. Thus, the formula is 2·a - popcount(a).
If endpoints are a and b, the sum of vertices will be 2·a - popcount(a) + 2·b - popcount(b) - 1 (we subtract the LCA that was counted twice). Since popcounts are small, we can iterate over each of them and we know the left value of equation:
s' + popcount(a) + popcount(b) + 1 = 2·(a + b)Here, s' is equal to the initial s minus whatever we subtracted when changing LCA from the binary-searched x to 1.
The remaining problem is: Given binary lengths L and R of numbers a and b, their popcounts, and the sum a + b, find the number of such pairs (a, b). This can be solved in standard dynamic programming on digits.
To slightly improve the complexity, we can iterate over the sum popcount(a) + popcount(b) instead of the two popcounts separately. The required complexity is or better.
Let's solve an easier problem first. For every query, we just want to say if Limak can get from one corner to the other. He can't do that if and only if blocked cells connect the top-right side with the bottom-left side — this is called a dual problem.
On the drawing above, the top-right side and bottom-left side are marked with blue, and blocked cells are black. There is a path of blocked cells between the two sides what means that Limak can't get from top-left to bottom-right corner. The duality in graphs changes the definition of adjacency from "sharing a side" to "touching by a corner or side" — the black cells on the drawing aren't side-adjacent but they still block Limak from passing through. Similarly, if Limak was allowed to move to any of 8 corner/side-adjacent cells, black cells would have to touch by sides to block Limak from passing through.
The idea of a solution is to find CC's (connected components) of blocked cells before reading queries, and then for every query see what CC's are connected with each other by temporarily blocked cells. To make our life easier, let's treat the blue sides as blocked cells too by expanding the grid by 1 in every direction. Then for every query, we want to check if new blocked cells connect the bottom-left CC and top-right CC.
Before reading queries, we can find CC's of blocked cells (remember that a cell has 8 adjacent cells now!). Let's name those initial CC's as regions. When a temporarily blocked cell appears, we iterate through the adjacent cells and if some of them belong to initial regions, we apply find&union to mark some regions as connected to each other (and connected to this new cell that is a temporary region of size 1). This can be done in where k is the number of temporarily blocked cells. This solves the easier version of a problem, where we just check if Limak can get from one corner to the other — if the two special regions are connected at the end then the answer is "NO", and it's "YES" otherwise.
What about the full problem? Limak wants to move to the opposite corner and back, not using the same cell twice. If you treat a grid as a graph, this means checking if there is a cycle passing through the two corners (a cycle without repeated vertices). It's reasonable to then think about bridges and articulation points. An articulation point here would be such a cell that making it blocked would disconnect the two corners from each other — it's a cell that Limak must go through on both parts of his journey. Our dual problem becomes: check if the two sides are almost connected i.e. it's enough to add one more blocked cell to make the connection (that cell must be an articulation point). The previously described solution needs some modification.
We did F&U on regions adjacent to temporarily blocked cells. If some region was connected with some other region in the current query, let's call it an interesting region — there are O(k) of them. If we preprocess the set of pairs of regions that are initially almost connected (it's enough to add one more blocked cell to make them connected), we can then for a query iterate over pairs: a region connected to the bottom-right side and a region connected to the other side, and check if this pair is in the set of almost-connected regions. There are O(k2) pairs and if any of them is almost-connected, we have an almost-connection between the two sides and we print "NO", because Limak can't avoid revisiting cells.
My code: 50164800.