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://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 > 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)

Its missing this tc: 1 2

Both are text understanding problems in first place, so it is arbitrary which one feels more or less complecated.

use binsearch bro

I have tested with some other submissions from ao35612:

TLE with pypy3-64: https://codeforces.com/contest/1623/submission/140938214

AC (much less than TL) with pypy3: https://codeforces.com/contest/1623/submission/140948424

and n0k:

TLE with pypy3-64: https://codeforces.com/contest/1623/submission/140916043

AC (much less than TL) with pypy3: https://codeforces.com/contest/1623/submission/140948345

geranazavr555 or anyone can advise on this issue for python users?

Nice, my simple solution for A got TL:

L = lambda: sys.stdin.readline().rstrip("\r\n")
Ns = lambda: list(map(int, L().split()))
def solve():
    n, m, rb, cb, rd, cd = Ns()
    dr, dc = 1, 1
    curx, cury = rb, cb
    ans = 0
    if rd >= rb:
        ans = rd - rb
    else:
        ans = n - rb + n - rd
    if cd >= cb:
        ans = min(ans, cd - cb)
    else:
        ans = min(ans, m - cd + m - cb)
    print(ans)

Wow! Thank you for participating and feedback! I really appreciate it. <3

Here was my solution:

We only ever have the possibility of cleaning the target, if we are at the same row or column as the target. When we start traversing the matrix as given in the statement, we end up with a graph which has a chain of vertices (possibly of size 0) followed by a cycle.

For the chain and the cycle, let's store the number of moves we took to reach a vertex $$$v$$$, for all vertices $$$v$$$ such that $$$v$$$ is at either the same row or same column (or both) as the target. I call these vertices "potential vertices".

Say the chain had some potential vertices $$$c_1, c_2, \dots c_k$$$ at distances(moves) $$$d_1, d_2 \dots d_k$$$.

Also, say the cycle had potential vertices $$$C_1, C_2 \dots C_K$$$ at distances $$$D_1, D_2 \dots D_K$$$.

Let us consider only the cycle first. Once we have entered the cycle, the expected time to clean the target is:

Now, the total expected time:

yeah in prob C dumb me always thought of a solution preceding "3 --> n" but the key was to start from the end.

Thank you so much for participating and feedback! Yes, the library is called Manim. I will also public the source code for animation in the editorial.

What?

Okay, definitely not — 1rst case scenario

step 1. function "check" to answer the question, is it possible to get the minimum value M for the source array. check it in one pass of the array from last elem to first

step 2. get a estimate for the minimum and maximum of M (minimum is min elem of source array, maximum is min(a[i] + a[i+1]/3 + a[i+2]/3*2)

step 3. binary search — check with M=(min + max)/2. if true, move min, if false, move max

based on latest contests, binary search will be in mediun task with 90% propability)

More generally, if you can show the monotone of the function that you are checking (that is, before some value, the checking function returns false, and after that, it returns true), then you can always do binary searching. There are problems that ask to maximize the minimum (or minimize the maximum) that do not involve binary search, especially when the function is not monotonous.

Lmaooo

It seems to be unrated, cause I opened my unrated contest section at my profile and I found it at there