Due to my poor understanding ability, I can't totally understand official editorials of some problems, even after got AC. So I plan to rewrite some of the editorials.
Some principles:
Divide and conquer. Divide a large, hard problem into several smaller, easier problems.
For ease of understanding, use visual expressions as much as possible.
The shorter the better.
If you have any other problems you'd like me to rewrite the editorial for, feel free to let me know in the comments. Also, I believe writing an editorial with your own understanding is a great way to make progress.
Let's go.
Rating: $$$2500$$$
Assume that the number of colors $$$c$$$ is fixed. Let $$$mx[i][j]$$$ represent the length of the continuous path ending at node $$$i$$$ with color $$$j$$$. How do we construct $$$mx$$$?
Let's try some approaches. For the connected component formed by the first $$$k$$$ nodes, we can use color 1 for all of them. In this case, the $$$i$$$-th node's $$$mx$$$ array (for $$$1 \le i \le k$$$) would be:
$$$mx[i] = [ i-1 ,0, \dots, 0]$$$.
For the $$$(k+1)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes. Thus, the $$$(k+1)$$$-th node's $$$mx$$$ array would be:
$$$mx[k+1] = [0, 1, 0, \dots, 0]$$$.
For the $$$(k+2)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes and color 1 to connect node $$$k$$$. In this case, the $$$(k+2)$$$-th node's $$$mx$$$ array would be:
$$$mx[k+2] = [1, 1,0, \dots, 0]$$$.
At this point, you might realize: The $$$i$$$-th node's $$$mx$$$ array is exactly the $$$(i-1)$$$ in base $$$k$$$ as a mask!
Claim $$$1$$$: for two indices $$$i$$$ and $$$j(i<j)$$$, $$$mx[i] \neq mx[j]$$$.
Proof $$$1$$$: if we use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$, $$$mx[i][k]+1=mx[j][k]$$$ must hold.
So we can assign values to each node's $$$mx$$$ array using a $$$k$$$-base mask from $$$0$$$ to $$$n-1$$$, which gives us a lower bound on the answer.
Claim $$$2$$$: we can always reach this lower bound.
Proof $$$2$$$: for two indices $$$i$$$ and $$$j(i<j)$$$, find $$$k$$$ such that $$$mx[i][k]<mx[j][k]$$$, then use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$.
2.Codechef Simultaneous Robots
Rating:???
$$$a[1][2]=a[2][1]=a[n-1][m]=a[n][m-1]='.'$$$ must hold.
We can simply find the shortest path using BFS.
Robot B can follow behind Robot A. That is, Return to $$$(1,1)$$$ in two steps, then "track" A. So the lower bound of our answer is the shortest path length+2.
The only remaining problem is: how to find two disjoint shortest paths?
To to find two disjoint shortest paths, we have a classic idea: only walk along the edge of the shortest path tree.
That is, note $$$dis[x]$$$ as the distance from $$$s$$$ to $$$x$$$, we only remain edges $$$u \rightarrow v$$$ such that $$$dis[u]+1=dis[v]$$$.
Official editorial said:
Once all cells on the shortest path are known, sort them by their distance to $$$(1, 1)$$$, i.e., $$$d_1(x, y)$$$ values. Now, if there’s any “level” of the shortest path that contains exactly one cell, every shortest path much pass through this cell and two disjoint paths cannot exist. Otherwise, a valid pair of paths will always exist.
I am confused about how to prove this. After thinking, I came up with a rigorous proof using the maximum flow minimum cut theorem.
The Max-Flow Min-Cut Theorem states that in a flow network, the maximum flow from the source to the sink is equal to the capacity of the minimum cut that separates the source and sink.
What is cut? A cut in a graph is a way of dividing the set of vertices into two disjoint subsets. Note them as $$$S$$$ and $$$T$$$, where $$$s$$$ (source point) must belong to $$$S$$$ and $$$t$$$ (sink point) must belong to $$$T$$$. The edges that connect a vertex in one subset to a vertex in the other subset are called the cut edges. The minimum cut is the cut that has the smallest total capacity of these cut edges.
Since each node can be visited at most once, we need to split node $$$x$$$ into $$$x$$$ -> $$$x'$$$ when constructing the flow graph. Let's say $$$dis[x]=dis[x']$$$.
What I want to prove is that if the number of nodes at all "levels" is greater than $$$1$$$ (except for $$$s$$$ and $$$t$$$), then for all cuts, the number of cut edges is always greater than $$$1$$$.
Let $$$D[i]$$$ be the set of all nodes $$$x$$$ such that $$$dis[x] = i$$$.
Assume we can find a $$$D[i]$$$ satisfying there are two nodes $$$u,v∈D[i]$$$, such that $$$u∈S$$$ and $$$v∈T$$$ (let's call it "impure"). According to our assumption, there are at least two pairs of $$$x$$$->$$$x'$$$ in $$$D[i]$$$. We will discuss three cases.
Case $$$1$$$: $$$x$$$ and $$$x'$$$ are from different $$$S/T$$$ sets. In this case, $$$x$$$->$$$x'$$$ is already a cut edge.
Case $$$2$$$: $$$x$$$ and $$$x'$$$ are both from $$$S$$$. In this case, by following the successors of $$$x'$$$, we can always find a cut edge.
Case $$$3$$$: $$$x$$$ and $$$x'$$$ are both from $$$T$$$. In this case, by following the predecessors of $$$x$$$, we can always find a cut edge.
In this way, we can always find at least two different cutting edges. Q.E.D.
If we can't find "impure" $$$D[i]$$$, this case is easier — we can find two cutting edges between some $$$D[i]$$$ and $$$D[i+1]$$$. The proof are left to you :)
Note $$$|D[i]|$$$ as the number of nodes of $$$D[i]$$$($$$s$$$ and $$$t$$$ are excluded). If $$$min(D[i])=k$$$, can we find $$$k$$$ disjoint shortest path for any $$$k$$$?
No. It only holds when $$$k=2$$$.
The following is the counter case for $$$k=3$$$:
After retaining only the edges on the shortest path tree, we can run a maximum flow algorithm to check if the maximum flow is $$$2$$$. Due to the special nature of the graph, the time complexity is equivalent to performing two BFS traversals on the graph.
Rating: $$$2200$$$(easy)/$$$2500$$$(hard)
We construct the Cartesian tree of the array, where $$$maxa$$$ is the root.
We can think of the process of merging numbers as one slime eating another slime.
If you are at slime $$$a[x]$$$, what would you do? First, you can definitely eat the subtree you are in. After that, you try to eat your parent. If you can do so ($$$subtreesum[x] \ge a[fa[x]]$$$), it is equivalent to being in the position of slime $$$fa[x]$$$. Otherwise, mark the edge $$$(x, fa[x])$$$ as a "blocking edge." We use DSU to link all non-blocking edges, and the size of the set containing the root is the answer.
Maintain the Tree with Data Structures.
We first construct the Cartesian tree for $$$a[1...n]$$$, using a segment tree to maintain its Euler sequence. Some arrays and DSU also needed. Afterward, we "clear" it—set all values in the segment tree to 0, and disconnect every point in the DSU. Then, we add the nodes one by one.
We can also use arrays $$$fa$$$, $$$lc$$$, and $$$rc$$$ to maintain the current parent-child relationships in the tree. When adding $$$a[i]$$$, we set the value at position $$$i$$$ in the segment tree to $$$a[i]$$$ and check whether the edge between $$$i$$$ and its child(at most two children) is a "blocking edge". If it is not, we use DSU to merge $$$i$$$ and $$$a[i]$$$. This step is not hard.
Additionally, all edges on the path from $$$a[i]$$$ to the root may change from being "blocking edges" to "non-blocking edges" (but "non-blocking edges" will never become "blocking edges"—think about why). We check all edges on the path from $$$a[i]$$$ to the root and update them using DSU.
In DSU, for the nodes in the same set, we can maintain the point with the smallest depth in that set. This allows us to quickly skip over many consecutive "non-blocking edges".
For a "blocking edge", it may be checked many times. If there are many "blocking edges" on a path to the root, and after checking they do not change, could we check $$$O(n^2)$$$ times?
No. For a path to the root, there can be at most $$$O(\log n)$$$ "blocking edges."
Why? Let's review: a "blocking edge" $$$(x, fa[x])$$$ is an edge that satisfies $$$subtreesum[x] < a[fa[x]]$$$. Each time we pass through a "blocking edge", the subtree sum at least doubles. Therefore, there can be at most $$$O(\log n)$$$ "blocking edges."
Rating: $$$2000$$$
Consider a fixed interval $$$[l, r]$$$.
We find that if $$$a[r]$$$ is neither the maximum nor the minimum value, then performing $$$r--$$$ will increase the answer by $$$1$$$.
Thus, $$$a[r]$$$ must either be the maximum value or the minimum value; similarly, the same holds for $$$a[l]$$$.
We only need to calculate the answers where $$$a[r]$$$ is the maximum value and $$$a[l]$$$ is the minimum value. Afterward, we reverse the array $$$a$$$ and calculate again.
Consider a fixed $$$r$$$. We can separate the terms related to $$$r$$$ and those related to $$$l$$$, obtaining the following answer:
Maintaining "$$$a[l]$$$ is the minimum value in $$$a[l...r]$$$" seems difficult. Can we change it to "$$$1 \leq l \leq r$$$"? Yes, we can. Although this will count some "invalid" answers, these answers will never be the maximum value (think why).
Consider using a segment tree. If we have information for $$$[L, M]$$$ and $$$[M+1, R]$$$, how can we merge this information to obtain the information for $$$[L, R]$$$?
To find the answer that spans two intervals:
$$$\max_{r \in [M+1, R]} (a[r] - r) - \min_{l \in [L, M]} (a[l] - l)$$$
This can be maintained on a segment tree.
Rating: ???
Since $$$m$$$ is small, we can enumerate $$$2^m$$$ cases and record their AND values.
Thus, we can easily obtain an array $$$mn[i][j]$$$: the minimum value of $$$a[i]$$$ after $$$j$$$ operations.
DP seems hard. How to solve this?
We observe that for a fixed $$$i$$$, $$$mn[i][j]$$$ is a convex function. In other words, $$$mn[i][j] - mn[i][j+1]$$$ is monotonically decreasing.
Thus, the problem is equivalent to a classic problem: choosing the top $$$k$$$ largest values from $$$n$$$ monotonically decreasing sequences. This part is the same as an old problem https://mirror.codeforces.com/contest/1428/problem/E.
We only need to focus on the highest changing bit. It is easy to see that, as $$$j$$$ increases, the highest changing bit decreases.
Formally, define
as the highest differing bit between x and y. We have:
Consider a proof by contradiction. Suppose:
Let
, and we can find an $x[k]$ such that the $$$b$$$-th bit of $$$x[k]$$$ is $$$0$$$.
We insert this $$$x[k]$$$ into the first $$$(j+1)$$$ operations, and the result will be strictly smaller than the current $$$mn[i][j+1]$$$. This contradicts the minimality of $$$mn[i][j+1]$$$.
Thanks for the proof for the Codechef problem today! After some googling, it seems like it's generalized by the vertex-connectivity version of Menger's theorem.
Hi, the maximum number of non-intersecting path is the maximum flow. And Menger's theorem is the same as maximum flow minimum cut theorem.
Yeah, but the vertex-connectivity version of Menger's theorem is more immediately useful — all that's needed to prove the problem is to notice that the shortest path DAG can't have a min-vertex-cut of size 1 if there's at least 2 vertices in each level (besides source and sink).
You don't have to think about constructing the flow graph with 2 new vertices per original vertex anymore, and can think in terms of min-vertex-cuts instead of min-edge-cuts.
In Simultaneous Robots :
a[n-1][m] = a[n][m-1] = '.'
Can anyone explain why this part should be true for the answer to exist because in the case where the first robot follows the second robot (for d + 2 seconds as answer) then they both can make the exit through one of a[n-1][m] , a[n][m-1].
Just do a simulation, you will understand.
Think how it is possible for them to reach a cell simultaneously.
If it didn't have two exits,both robots can't reach last cell simultaneously.
I initially thought the goal was to reach a[n][m], but I realized my mistake.
For those brainstorming a solution to this question, here's an explanation:
If there is a shortest path to a[n][m] that passes through a[n][m-1], then the following sequence of events will occur:
1) At time d, Robot 2 will reach a[n][m]. 2) At time d+1, Robot 1 will move to a[n-1][m], while Robot 2 will move to a[n][m-1]. 3) At time d+2, both robots will arrive at a[n][m] simultaneously.
I hope this clears up any confusion!
D. Gifts Order
E. Kevin and And
Can you rewrite for these two problems?
Thanks in advance!
Rewrited
Thanks for writing. Btw, for the Simultaneous Robot's problem, I first found a shortest path. Then I blocked all the squares in the shortest path except top left and bottom right. Then I ran bfs again and if I find another shortest path of same initial length then I conclude there exists two disjoint shortest paths. I can prove till this part. However, if the second bfs can't find shortest path of same initial length, I don't understand why we can say that there exists no two disjoint shortest paths. However, this logic got AC when I submitted. Can you please prove this or it's weak testcases? TIA:)
I also did the same thing and I think this works because there are only 4 directions to walk and every time your order of preference for the direction is same. i.e. dx dy arrays. This makes sure that you are going through corners whenever possible => choosing same direction whenever possible leads you to reach boundaries faster. Hence, your first path cannot cut your to be second path so you can find it just by simulation.
you got AC? i don't think it should work. i can give you an example where it does not work.
..##
..##
....
....
preferences of directions are down, right, up, left.
i even tried to give different preferences to my directions. i did not get an AC. could you share your code?
https://www.codechef.com/viewsolution/1125149231.
Help me with this -
Why are we checking for this - if(grid[0][1] == ‘#’ || grid[1][0] == ‘#’ || grid[n-1][m-2] == ‘#’ || grid[n-2][m-1] == ‘#’) for unavailability of path.
Instead of this - if(grid[0][1] == ‘#’ || grid[1][0] == ‘#’ || (grid[n-1][m-2] == ‘#’ && grid[n-2][m-1] == ‘#’))
Let’s consider a case - n = 3 m = 3; grid = [[. . #] [. # #] [. . .]] In this case, the answer should be 6, the robot 1 will follow the path of — (0,0)->(1,0)->(2,0)->(2,1)->(2,2) and robot 2 will follow — (0,0)->(0,1)->(0,0)->(1,0)->(2,0)->(2,1)->(2,2) so the answer should be 6 in this case. But the solution its accepting returns -1 for this case. We should only have to check for the starting position because on the first time we move, the robots should be on different cells but for destination we have to check for at least an adjacent open cell of destination cell.
Robots are in the same position after 2 seconds.
See it like this, if we have to move from starting point (0,0) to (n-1,m-1) and if there's path from starting point to destination point or there's many paths but we have to take the shortest one right? So, if there's at least 2 paths of same shortest length then the answer will be the shortest path length 'D' but if not then the other path will be of length 'D+2' as the grid is a kind of bipartite graph.
After 2 seconds, the robot1 will already move to its path and the robot 2 in that scenario will be at (0,0) and the robot1 will wait for robot2 at the ending cell.
If I understand correctly, you are saying this:
Robot 1 moves to (N,M) in D seconds. Robot 2 starts from (1,1) after 2 seconds, following the same path.
This does not work. Try simulating the idea; you will know why. They will always meet after D+1 seconds.
Can you help me like in the test case which I gave initially or similar test cases like that — after 2 seconds, robot1 will be at (2,0) and the robot2 will be at (0,0) is it incorrect?
No, it is correct. Take your example and simulate the process.
in Simultaneous Robots i don't understand, how we can get 2 disjoint shortest paths using shortest path tree. please explain?
You only need to determine the existence of 2 disjoint shortest paths. If you want to construct them, you can use the maximum flow algorithm.
before Patch for official editorial (the most interesting part) in a classic trick you mentioned -> To to find two disjoint shortest paths, we have a classic idea: only walk along the edge of the shortest path tree.
i have not read below that section.
Thanks for the explanation of problem Codechef Simultaneous Robots. I tried solving it using Denic's Algorithm and got stuck with TLE here. With the given constraint, the runtime on bipartite graph is $$$O(V\sqrt E)$$$. In one of the worst case we have a grid $$$10^{3}*10^{3}$$$ where total nodes are $$$10^{6}$$$ and total edges(if all paths possible) just $$$4*10^{6}$$$. With these constraints, I don't think it would pass but am interested if anyone solved it using Network Flow Algorithms.
I solved the problem with distance technique shown in the editorial above and thanks for the counter example for $$$k=3$$$ but this is like a trick that you have to remember with limitation $$$k<=2$$$. Network flow logic is more intuitive for me(maybe skill issue XD).
PS: Take everything I said with a huge grain of salt as this is my first time coming across Network Flow.
I wish you would write explanation of 1209E1. I still can't understand official editorial.
E. Exposition
This one please