Привет всем!↵
↵
**UPD:** Разбор постепенно появляется на английском языке.↵
↵
[problem:556A]↵
↵
If there still exist at least one $0$ and at least one $1$ in the string then there obviously exists either substring $01$ or substring $10$ (or both) and we can remove it. The order in which we remove substrings is unimportant: in any case we will make $min(#zeros,#ones)$ such operations. Thus the answer is $#ones+#zeros-2min(#ones,#zeros)=|#ones - #zeros|$.↵
↵
Time: $O(n)$.↵
↵
[problem:556B]↵
↵
Notice that after pressing the button $n$ times gears return to initial state. So the easiest solution is to simulate the process of pressing the button $n$ times and if at some step the active teeth sequence is $0,1,\dots ,n-1$ output "Yes" else "No". But this solution can be improved. For instance, knowing the active tooth of the first gear you can quickly determine how many times pressing the button is necessary, go to that state and check the sequence only once.↵
↵
Time: $O(n)$ or $O(n^2)$; solutions: [submission:11822751] ($O(n)$) and [submission:11822759] ($O(n^2)$)↵
↵
[problem:555A]↵
↵
Suppose we don't need to disassemble some sequence of dolls. Then no doll can be inserted into no doll from this chain. So we don't need to disassemble a sequence of dolls only if they are consecutive and start from $1$. Let the length of this chain be $l$. Then we will need to get one doll from another $n-k-l+1$ times. Now we have a sequence $1\to 2\to \dots \to l$ and all other dolls by themselves. $n-l+1$ chains in total so we need to put one doll into another $n-l$ times. $2n-k-2l+2$ operations in total.↵
↵
Time: $O(n)$; solution: [submission:11823230].↵
↵
[problem:555B]↵
↵
We can put a bridge between bridges $i$ and $i+1$ if its length lies in the segment $[l_{i+1}-r_i;r_{i+1}-l_i]$. Now we have a well-known problem: there are $n-1$ segments and $m$ points on a plane, for every segment we need to assign a point which lies in it to this segment and every point can be assigned only once. ↵
↵
Let's call a segment open if no point is assigned to it. Let's go through all points from left to right and at every moment keep all open segments that contain current point in a BST (std::set). When processing a point it should be assigned to the segment (from our set) that has the leftmost right end.↵
↵
This algorithm will find the answer if there is one. Suppose this solution is wrong and suppose there is a solution in which point $A$ is assigned to another open segment (there's no sense in skipping this point). Then some point $B$ is assigned to the segment which $A$ was assigned to. $B$ is to the right of $A$ so we can swap them and come to our answer again. ↵
↵
Time: $O((n+m)log(n+m))$; solution: [submission:11823764].↵
↵
[problem:555C]↵
↵
Let's solve this problem with two segment trees: we'll keep the lowest eaten piece for each column in one of them and the leftmost eaten piece for each row in another. Suppose we have a query $x$ $y$ $L$. Position where we'll stop eating chocolate is stored in the row segment tree so we can easily find the number of eaten pieces. After that we need to update both segment trees.↵
↵
$n$ is rather big in this problem. One way to deal with it is to use coordinate compression. Another is to use implicit segment trees.↵
↵
Time: $O(qlogq)$ or $O(qlogn)$; solutions: [submission:11824011] and [submission:11824029].↵
↵
[problem:555D]↵
↵
I call the length of the part of the rope from the weight to the last met peg the active length (denoted as $L_a$). After each met peg active length is reduced. Let's process queries separately: at each step we can find next peg with using binary search.↵
If active length becomes at least two times shorter we proceed to the next step. Otherwise say current peg is peg $i$ and the next one is peg $j$ (without loss of generality $i<j$). Then after peg $j$ the rope will again touch peg $i$ and the weight will again rotate around peg $i$. Indeed, $2(x_j-x_i) \le L_a$ so the weight will rotate around a peg not to the right to peg $i$. And either $i=1$ or $L_a \le x_i-x_{i-1}$ so it won't also rotate around a peg to the left to peg $i$. As long as $L_a \ge x_j-x_i$ the weight will rotate around these two pegs so we can skip through several steps momentarily. This way active length is shortened at least twice so there will be no more than $logL$ steps.↵
↵
Time: $O(mlogLlogn)$; solution: [submission:11824913].↵
↵
[problem:555E]↵
↵
First of all, let's reduce this problem to a problem on a tree. In order to achieve this let's orient edges in all biconnected components according to a DFS-order. We'll get a strongly connected component. Suppose it's false. Then this component can be divided into parts $A$ and $B$ such that there's no edge from $B$ to $A$. As initially there are at least two edges between $A$ and $B$ this situation is impossible because after entering $B$ in our DFS we'll have to exit via one of these edges. Contradiction. We can compress all biconnected components.↵
↵
Now we need to handle several queries "orient edges on a simple path in a tree" and to check if there are no conflicts. For this let's hang our tree and find LCA's for queries' pairs of vertices. Start another DFS and for every subtree count vertices in this subtree that are beginnings of queries' paths (call it $a$), that are ends of queries' paths (call it $b$) and that are precalculated LCAs (call it $c$). Now we can orient the edge connecting the root of the subtree and its parent: if $a-c$ is positive then it should be oriented up, if $b-c$ is positive then it should be oriented down, if both are positive there's no solution, if both are zeros the direction does not matter.↵
↵
Time: $O(nl_q)$ where $l_q$ is the time of calculating LCA per query; [solution](http://paste.ubuntu.com/11788459/) that uses slightly other method for the last part.
↵
↵
↵
If there still exist at least one $0$ and at least one $1$ in the string then there obviously exists either substring $01$ or substring $10$ (or both) and we can remove it. The order in which we remove substrings is unimportant: in any case we will make $min(#zeros,#ones)$ such operations. Thus the answer is $#ones+#zeros-2min(#ones,#zeros)=|#ones - #zeros|$.↵
↵
Time: $O(n)$.↵
↵
[problem:556B]↵
↵
Notice that after pressing the button $n$ times gears return to initial state. So the easiest solution is to simulate the process of pressing the button $n$ times and if at some step the active teeth sequence is $0,1,\dots ,n-1$ output "Yes" else "No". But this solution can be improved. For instance, knowing the active tooth of the first gear you can quickly determine how many times pressing the button is necessary, go to that state and check the sequence only once.↵
↵
Time: $O(n)$ or $O(n^2)$; solutions: [submission:11822751] ($O(n)$) and [submission:11822759] ($O(n^2)$)↵
↵
[problem:555A]↵
↵
Suppose we don't need to disassemble some sequence of dolls. Then no doll can be inserted into no doll from this chain. So we don't need to disassemble a sequence of dolls only if they are consecutive and start from $1$. Let the length of this chain be $l$. Then we will need to get one doll from another $n-k-l+1$ times. Now we have a sequence $1\to 2\to \dots \to l$ and all other dolls by themselves. $n-l+1$ chains in total so we need to put one doll into another $n-l$ times. $2n-k-2l+2$ operations in total.↵
↵
Time: $O(n)$; solution: [submission:11823230].↵
↵
[problem:555B]↵
↵
We can put a bridge between bridges $i$ and $i+1$ if its length lies in the segment $[l_{i+1}-r_i;r_{i+1}-l_i]$. Now we have a well-known problem: there are $n-1$ segments and $m$ points on a plane, for every segment we need to assign a point which lies in it to this segment and every point can be assigned only once. ↵
↵
Let's call a segment open if no point is assigned to it. Let's go through all points from left to right and at every moment keep all open segments that contain current point in a BST (std::set). When processing a point it should be assigned to the segment (from our set) that has the leftmost right end.↵
↵
This algorithm will find the answer if there is one. Suppose this solution is wrong and suppose there is a solution in which point $A$ is assigned to another open segment (there's no sense in skipping this point). Then some point $B$ is assigned to the segment which $A$ was assigned to. $B$ is to the right of $A$ so we can swap them and come to our answer again. ↵
↵
Time: $O((n+m)log(n+m))$; solution: [submission:11823764].↵
↵
[problem:555C]↵
↵
Let's solve this problem with two segment trees: we'll keep the lowest eaten piece for each column in one of them and the leftmost eaten piece for each row in another. Suppose we have a query $x$ $y$ $L$. Position where we'll stop eating chocolate is stored in the row segment tree so we can easily find the number of eaten pieces. After that we need to update both segment trees.↵
↵
$n$ is rather big in this problem. One way to deal with it is to use coordinate compression. Another is to use implicit segment trees.↵
↵
Time: $O(qlogq)$ or $O(qlogn)$; solutions: [submission:11824011] and [submission:11824029].↵
↵
[problem:555D]↵
↵
I call the length of the part of the rope from the weight to the last met peg the active length (denoted as $L_a$). After each met peg active length is reduced. Let's process queries separately: at each step we can find next peg with using binary search.↵
If active length becomes at least two times shorter we proceed to the next step. Otherwise say current peg is peg $i$ and the next one is peg $j$ (without loss of generality $i<j$). Then after peg $j$ the rope will again touch peg $i$ and the weight will again rotate around peg $i$. Indeed, $2(x_j-x_i) \le L_a$ so the weight will rotate around a peg not to the right to peg $i$. And either $i=1$ or $L_a \le x_i-x_{i-1}$ so it won't also rotate around a peg to the left to peg $i$. As long as $L_a \ge x_j-x_i$ the weight will rotate around these two pegs so we can skip through several steps momentarily. This way active length is shortened at least twice so there will be no more than $logL$ steps.↵
↵
Time: $O(mlogLlogn)$; solution: [submission:11824913].↵
↵
[problem:555E]↵
↵
First of all, let's reduce this problem to a problem on a tree. In order to achieve this let's orient edges in all biconnected components according to a DFS-order. We'll get a strongly connected component. Suppose it's false. Then this component can be divided into parts $A$ and $B$ such that there's no edge from $B$ to $A$. As initially there are at least two edges between $A$ and $B$ this situation is impossible because after entering $B$ in our DFS we'll have to exit via one of these edges. Contradiction. We can compress all biconnected components.↵
↵
Now we need to handle several queries "orient edges on a simple path in a tree" and to check if there are no conflicts. For this let's hang our tree and find LCA's for queries' pairs of vertices. Start another DFS and for every subtree count vertices in this subtree that are beginnings of queries' paths (call it $a$), that are ends of queries' paths (call it $b$) and that are precalculated LCAs (call it $c$). Now we can orient the edge connecting the root of the subtree and its parent: if $a-c$ is positive then it should be oriented up, if $b-c$ is positive then it should be oriented down, if both are positive there's no solution, if both are zeros the direction does not matter.↵
↵
Time: $O(nl_q)$ where $l_q$ is the time of calculating LCA per query; [solution](http://paste.ubuntu.com/11788459/) that uses slightly other method for the last part.
