Me: Confused on if to upvote blog or upvote comment

omg tdpencil orz

Usually the score distribution comes shortly before the beginning of the contest__

I think you have commented on the wrong announcement.

wrong annoucement

It is written Codeforces Round #763 (Div. 2)...

True, but better keep the downvote button and hide the downvote count, where comments are still hidden when they got too many downvotes.

No, there will not be an interactive problem in the contest.

Picked the wrong day buddy.

How to become intelligent ?. life is hard

yes

I don't think there is any need for binlifting, it can be solved in O(N) I think (just find the next letter for each node and rest is just dfs).

Can you please explain how did you solve the problem with a binary lifting ?

Do you have any better proof? Those submissions look suspicious, but that's not a definitive proof.

yeah, neither of them matter, except (of course) for implementation details.

I guess that most participants have implemented methods in $$$O(n \log n)$$$ that works on general trees...

When I saw the particular structure of the tree, I guessed that there might be some method with better time complexity or lower implementation difficulty. But since the implementation of the generic algorithm is not complicated and can pass the constraints in time, I didn't bother to think about it anymore...

I am sorry to hear that. Initially, I wrote it as $$$n \times m$$$ but after some advice, it was changed to $$$n \cdot m$$$. But, well, the solution is solvable in $$$O(n + m)$$$ as well, which is implemented in my model solution, so maybe you can do a pro gamer's move and implement that solution :).

Short version:

You can realize the robot's pattern is cyclic, then every step can be mapped to one position of the and calculated using AGP.

Long version:

The state of motion of the robot can be uniquely represented by the tuple $$$(r, c, dr, dc)$$$, so a given pattern of motion will form a cycle of at most $$$4 \cdot n \cdot m$$$ steps.

Additionally for ease of implementation we can note that due to the grid formulation this cycle will never have a tail.

Suppose the cycle is of length $$$k$$$ and there are $$$l$$$ positions $$$x_1, x_2, \ldots x_l$$$ (0-indexed) in this cycle which share a row or column with $$$(r_d, c_d)$$$.

Then the expected time taken to clean this cell becomes the sum of:

where the probability in row $$$i$$$ and column $$$j$$$ represents the probability of the cell being cleaned from position $$$x_j$$$ during the $$$i$$$-th repetition of the cycle.

We can notice that the $$$j$$$-th column forms an infinite AGP with $$$A_1 = x_j$$$, $$$G_1 = p \cdot {(1 - p)}^{j - 1}$$$, $$$d = k$$$, $$$r = {(1 - p)}^l$$$. This can be calculated easily using the standard formula available from Wikipedia or elsewhere.

Submission — 140937671

Here is my solution. Let's build the graph where every node is a tuple (row, col, row_direction, col_direction). Obviously, this is a graph consisting of only one cycle and every node has only one outgoing edge. Each edge will have some weight indicating the probability of taking that edge. If a node is in the same row or column as the goal, its outgoing edge has weight $$$1 - p$$$, otherwise it has weight $$$1$$$.

Now, let's say the cycle has length $$$L$$$ and the product of its edges's weights is $$$P$$$. Let's also define $$$length(u)$$$ as the length (number of edges) of the path from the starting node to the node $$$u$$$, and $$$prod(u)$$$ as the product of the edges's weights on the path from the starting node to the node $$$u$$$.

Now, let's say our trip finishes at the node $$$u$$$, after traversing the cycle completely $$$k$$$ times. Then, the probability of such outcome is $$$P^k \cdot prod(u)$$$, and therefore the expected time to reach such outcome is $$$P^k \cdot prod(u) \cdot (L \cdot k + length(u))$$$.

Therefore, for every node $$$u$$$ in the cycle, the expected time of finishing there is:

Now, for every node $u$ not in the cycle, the expected time of finishing there is just $$$prod(u)\cdot length(u)$$$ — somehow, I forgot about this case when I was coding the problem, and still it passed the test cases, (it seems that the graph is always a cycle).

UPD: Thanks to PoIar_ for sharing a simple proof of why the graph is a simple cycle.

Now, for every node $$$u$$$ that is on the same row or column as the goal, we add the above formulas (depending if it's on the cycle or not) multiplied by $$$p$$$ (the probability of cleaning those row and column).

You calculate everything modulo $$$10^9 + 7$$$ (or whatever) and if you need to divide any time in your algorithm, just use Fermat's little theorem (so to calculate $$$\frac{a}{b}$$$ you calculate instead $$$ab^{10^9 + 5}$$$). The "irreducible" part doesn't really matter.

Do a binary search on the answer.

Let's do a binary search. We need to check if we can operate so that each pile of stones has at least $$$mid$$$ stones. Notice that if we traverse the pile of stones by their index, from largest to smallest, we can know how many stones can be removed from the pile at most. So we can just greedily move the stone forward.

Note that the number of stones that can be moved forward in the $$$i$$$-th pile cannot exceed the number of stones in the initial pile, so you need to update $$$d_i \leftarrow \min(d_i, a_i)$$$. The total time complexity will be $$$O(n \log V)$$$.

Submission: https://mirror.codeforces.com/contest/1623/submission/140945479

Use binary search.

Suppose you have a function f and it’s inverse f’. Suppose computing f is straightforward and easy but f’ is tough and you want to compute f’(x). Then sometimes it is easier to search for y = f’(x) such that f(y) = x.

Let us take an example for computing cube root of x. It is straightforward and easier to search for a number y such that y^3 = x than to compute x^(1/3).

I hope it helps.

you must check for min(cd-cb, 2*(n-rb)+rb-rd)) in the case where cb<cd and likewise when rb<rd

Each case should have some sort of min calculation. For example, in the (cb < cd) else case, you should still be checking (2*(n-rb)+rb-rd).

10 10 9 1 8 10 try this

You have the right idea, but you're not considering the case when the robot "bounces" on the horizontal side, and reaches the line of the dirty cell before reaching the column

As a side note, 2*(m-cb)+cb-cd could be simplified to 2*m-cb-cd

i simulated all the process using recursion, you can go check it out

Consider the interval $$$[1, n]$$$, and let's say Bob broke it in point $$$d$$$. If $$$d \gt 1$$$, then somewhere in the process the interval $$$[1, d-1]$$$ was chosen. Let's consider all intervals that start at $$$1$$$, and let $$$x$$$ be the largest index such that $$$[1, x]$$$ was chosen. Notice that no interval other than $$$[1, n]$$$ can contain $$$[1, d-1]$$$, and thus, we have that $$$x = d-1$$$. If $$$d = 1$$$, then the only interval that starts at $$$1$$$ is $$$[1, n]$$$.

Implementation:

I preprocessed a vector of sets ends, such that ends[i] is the set of all $$$x$$$ such that $$$[i, x]$$$ was chosen. I then sort intervals by their respective lengths, and process them in order. When processing the interval $$$[l, r]$$$, I remove $$$r$$$ from the ends[l] set, and see if the set is empty. If the set is empty, then $$$d = l$$$. Otherwise, $$$d$$$ is the largest number in the set

for (auto [s, l, r]: intervals) {
    ends[l].erase(r);
    if (!ends[l].empty()) printf("%d %d %d\n", l, r, *ends[l].rbegin() + 1);
        else printf("%d %d %d\n", l, r, l);
}

Why did you remove your test case? Looks legit to me.

There used to be another problem, but there was a problem with constant optimization solutions getting accepted, so it had to be scrapped.

Agree, as a 1900 level participant, I feel painful as I spent 1 hour getting the correct formula for problem D and realized I had no time to code it.

For n=2 there must be 1 2 range since set start from (1,n)