In my opinion, all of the problems have a very simple solution and actually require no special data structure at all. To demonstrate the point, I will also use EvErYoNe'S fAvOrItE lAnGuAgE: **Pascal**.

I will also include some notes, which are not related to the solution at all, but I find them interesting, so I will also include them in.

## A. Robot Cleaner

Obviously, the problem is solvable using simulation. But it is solvable in $$$O(1)$$$ time as well, and I will discuss it.

**Tutorial**

**Problem note**

Pascal solution: 140968868. C++ solution: 140968900

## B. Game On Ranges

There are a lot of solutions to this problem. The solution I described below might be the simplest in my opinion.

**Tutorial**

**Problem note**

Pascal solution: 140968967. C++ solution: 140968942

## C. Balanced Stone Heaps

**Tutorial**

There is not much to note about this problem.

Pascal solution: 140968985 C++ solution: 140969004

## D. Robot Cleaner Revisit

**Tutorial**

**Problem note**

Pascal solution: 140969014 C++ solution: 140969025

## E. Middle Duplication

**Tutorial**

**Problem note**

Problem C was very nice

Funny thing, I tried something like an $$$O(n^2)$$$ solution for B but after getting TLE I misread the constraints and thought an $$$O(n log n)$$$ solution was required lmao.

My solution is basically to sort all ranges in decreasing order, then for each range, the answer is the biggest element in the range that has not yet been picked. This is easy to accomplish with sets.

Code

I choose the smallest element in the range that has not yet been picked.And I got runtimeerror.

Had the same problem, basically I had a bug in the compare function that I gave to sort() (my idea was to sort by increasing range "length" (r-l+1) and then select for each range the first number in it that I haven't used in a previous range).

The bug was in :

This worked :

My solution got accepted doing that

I almost did the same, but I first assigned the values to those range whose start and end values are same and then I sorted them in increasing order of end of ranges.

My solution for B was completely different from other solutions. My solution was to sort the ranges based in ascending order for first element and descending order for second element. If both numbers in the range were the same, then obviously we have to pick that number as d. Otherwise, for every adjacent pair of ranges, if both of the first element are same, we take min of second element + 1 as $$$d$$$, if both of the second element are same we take max of first element-1. Complexity is $$$O(NLogN)$$$ I think.

Here is my solution — 141339457

Can you please explain why your approach for Problem B is working, I am not able to prove it myself

Another $$$O(N^2)$$$ solution for B (see 140909239): keep track of how many intervals each number is part of, and for each interval pick the number in [l,r] that intersects the least intervals. This number must be the split point, as all other numbers in [l,r] will appear at least once more in the resulting intervals after splitting.

Bringing this to $$$O(NlogN)$$$ can be done by doing the first phase on its finite differences (so +1 at l and -1 at r+1), then calculating the prefix sum of the array to get the real counts. The second phase can then use a segment tree on top of the array to get the position of the minimum

Hey, I referred to a solution in this video — https://www.youtube.com/watch?v=FI8p-DEglxU&t=1s, I understood the solution easily but is the solution in this video also a O(NlogN) solution. Can somebody clarify the same.

Yeah that looks like an $$$O(NlogN)$$$ solution as well

I think the description in problem A has a little difficulty in reading

I am sorry for long statement. Everything written in the statement are just for formality. The parts of the statement are:

Without the parts above I think it is also hard to understand the statement. Maybe you have some suggestions?

Ahhh yes, here he is, the classic darkkcyan.

O(1) solution of problem A is cool~

DP solution for problem D: Let's define the state:

`dp[i][j][di][dj]`

means that we area at the (i, j) cell and our direction is (di, dj).It matters which direction we will go rather than which direction we are from when we are at some cell. So we use the direction we will go as (di, dj) when we are at (i, d) cell. For each state, its next state is very clear, such as

`(1, 1, 1, 1)`

-> (`2, 2, 1, 1`

). Let`f(s)`

be the next state to state`s`

. Therefore,`dp[s] = (100 - p)/100 (1 + dp[f(s)])`

, in which`p`

is the probability the cell of`s`

can clear the target.We want to get

`f(r, c, 0, 0)`

, but there's a cycle. So we represent every`dp[s]`

with the coefficient of`f(r, c, 0, 0)`

and a constant. After that, it only remains to solve a linear equation of one variable.refer to: 140973956

There's another way to solve problem E, but it's pretty complex :)

We find which node should be duplicated as the tutorial said. We can do DFS on the tree using the order this problem mentioned. And then check whether duplicate nodes one by one.

We define

`cost(x)`

means if we duplicate this node, how many nodes(its ancestors(includes itself) that have not been duplicated) will be duplicated.We use some data structure maintain the

`cost(x)`

, such as "heavy path decomposition".But there remains a special case: if a previous node shouldn't be duplicated, every node in its subtree shouldn't be duplicated. So we have to use some data structure maintain this information, such as "Fenwick Tree". This solution is quite straight forward, but it needs many data structure.

140929530

This Editorial says that there is an O(nlogn) solution of problem B. Can anybody tell that if my submission to this problem is O(nlogn)? I think mine is O(logn). I would be thankful if anybody clears my confusion.

1623B - Game on Ranges

140929468

I think your solution is O(n^2). It seems like you have to go through every cell of matrix n*n, and your output is clearly n * n loop.

Your solution is $$$O(N^2)$$$, the $$$O(NlogN)$$$ solution uses sorting.

nope. yours one is not $$$O(log n)$$$. it is $$$O(n^2)$$$. the loop in foo() function can run n times in worst case. also you are printing answers by $$$O(n^2)$$$ operations (as two nested loops).

You can refer to this solution, easily explained here https://www.youtube.com/watch?v=FI8p-DEglxU&t=1s

How problem C is reversed ? Thing is say i index, you get d from i+1 index and 2*d_ from i+2 index. Now in optimal case say in total if i index got x stones. now x = d + 2*d_. When the problem is reversed, d must be equal to d_. Which is not always the case. darkkcyan

Did you see the code? I was also not very sure about editorial solution after reading it but once I saw the code, it made complete sense. Please see the implementation once.

yes mister_bull d & d_ will be different.

way you can look at when moving from 0 to n-3, index i gets d from i+1 and 2*d_ from i+2

but when we look at the same problem moving in reverse order from n-1 to 2 we can try moving maximum stones to i-1 and i-2 after leaving atleast x at index. so max that can be moved is min( original_hi/3, (rolling_hi-x)/3 )

O(n^2 *logn) solution should also pass for B. Why am getting TLE (BFS type sol,) Link : https://codeforces.com/contest/1623/submission/140934881

I have a question. In problem B, I don't understand. Is the test case 1 5 1 1 1 2 5 5 3 3 1 5 valid?

no bro. i think its invalid

I found that in range 1 1, I choose 1. In range 1 2, I have to choose 2. 3 3 I choose 3. And 5 5 I chosse 5. So finally, I have to choose 4 in range 1 5. It's the only way. So why?

When you choose 4 in the range 1-5 then two new ranges (1-3) and (5-5) are formed. I don't see the range 1-3 anywhere in the testcase.

can anybody pl tell why this code is giving TLE.

include include <bits/stdc++.h> using namespace std; define Code ios_base::sync_with_stdio(false); define By cin.tie(NULL); define Shubh cout.tie(NULL); define ll long long define fl(i,n) for(int i=0;i<n;i++) define rl(i,m,n) for(int i=n;i>=m;i--) define ff first define ss second define pb push_back define mp make_pair define pi 3.141592653589793238 define vr(v) v.begin(),v.end() define rsv(v) v.end(),v.begin() ll mod=1000000007; define vec vector define endl "\n" // Robot Cleaner void solve(){ int n,m,rb,cb,rd,cd,cnt=0,dr=1,dc=1,d=-1,c=-1; cin>>n>>m>>rb>>cb>>rd>>cd; bool got=true; while(got){

}

int main(){ Code By Shubh int t;cin>>t; while(t--){ solve(); } return 0; }

## include

## include <bits/stdc++.h>

using namespace std;

## define Code ios_base::sync_with_stdio(false);

## define By cin.tie(NULL);

## define Shubh cout.tie(NULL);

## define ll long long

## define fl(i,n) for(int i=0;i<n;i++)

## define rl(i,m,n) for(int i=n;i>=m;i--)

## define ff first

## define ss second

## define pb push_back

## define mp make_pair

## define pi 3.141592653589793238

## define vr(v) v.begin(),v.end()

## define rsv(v) v.end(),v.begin()

ll mod=1000000007;

## define vec vector

//Game on Ranges ll power(ll a, ll b){ // a raised to power b ll res=1; while(b){ if(b&1) res=(res*a)%mod; b>>=1; a=(a*a)%mod; } return res; }

int main(){ Code By Shubh int t;cin>>t; while(t--){

}

fix you comment plz

You can refer to the solution here, the code is well explained https://www.youtube.com/watch?v=FI8p-DEglxU&t=1s

thank you

Regarding problem D, I have two doubts -

How do we claim the maximum length of the cycle is 4*n*m? Is it because there are 4 directions to leave every cell? Can someone share a sample testcase where this maximum cycle length is observed?

Per the editorial, how do we claim that 4*(n-1)*(m-1) guaranteed to be a multiple of the longest cycle length?

Please correct me if my doubts themselves reflect any incorrect understanding.

And for the second question. Rather than proving that $$$4 (n - 1) (m -1)$$$ is the multiple of the cycle length, let's just prove that after $$$4 (n - 1)(m - 1)$$$, the robot came back to the initial position.

Let's first think about why there is $$$-1$$$ in the formula. It is because from $$$1$$$ to $$$n$$$ the robot can move exactly $$$n - 1$$$ steps, and similarly, $$$m - 1$$$ steps for $$$1$$$ to $$$m$$$.

We can see that after each $$$2 (n - 1)$$$ steps, the robot can go back to its original row with the original vertical direction, and after $$$2 (m - 1)$$$ steps, the robot can go back to its original column with the original horizontal direction. So after $$$4 (n - 1) (m - 1)$$$ steps, the robot must have the same row, the same column, and the same direction as it initially has.

Your reply has been very helpful to me.

Problem D : let call time(i) is i-th time the robot have same col or row with dirt. ip=(100-p)/100; P=p/100; therefor i think answer is : ans+=time(i)*(ip^(i-1))*P with i from 1 to k. but if i increase k answer is change. what wrong ?? i need help !

can someone please tell me what is wrong with this check function of problem c?

}

Here is the submission

You should iterate from back to front of the vector because if you go from front to back you won't know how much the next element will give you.

can you please give me a sample test case?

This case

You code output is 25, but the solution is 28.

thanks buddy

In problem C's editorial, why they are making cur_h array? I mean what's the intuition. I think it's just a copy of original array. Please anyone clear.

`cur_h`

is the array we are working on, and we will modify it while we are doing the process, in the editorial, that is the $$$h'[]$$$ array. The`h`

array, on the other hand, will remain unchanged, since I also wanted its original value while doing calculation, as well as using it for the future call of the function.Yeah got it, thank you very much. Can you please once tell me how we're finding d? "int d = min(h[i], cur_h[i] — x) / 3", why we're subtracting x?

What we want is to make every heap

not less than $$$x$$$. So when $$$cur_h[i]\ge x$$$, we can say that we have $$$cur_h[i]-x$$$ stones to spare, and we should just give away those stones.Ohh yes, got it thank you.

Very nice editorial. Had fun reading it :)

Thank you so much! I really appreciate it.

I have tried to use 2 functions for problem C, one gives WA and other passes , can some1 explain why https://codeforces.com/contest/1623/submission/140962174

Hey darkkcyan in the editorial of C I think it should be

d =$$$\dfrac{h_i - x}{3}$$$ instead ofd =$$$\dfrac{h_i}{3}$$$ .You are right! My bad. I will fix it.

Thank you for your report!

Can anyone pls tell me whether my derived formula for problem D is right or wrong as i am getting wrong answer so i want to know whether there is any implementation error or my formula is wrong.

FormulaThat looks good, if t_n is the length of the cycle. You can then simplify that expression to get a closed form:)

n is length of cycle and t_n is the time to reach to the last cell in a cycle from where the dirty cell can be cleaned.

oh ok, I think you need to replace t_n in your formula with the time it takes to reach the starting position again. Imagine that we are in the second round of the cycle, then the time t_n * x + t_i will not be right since you have skipped the interval from t_n to the time it takes to reach the starting position.

Thanks now i found the mistake thanks for your reply :)

You're welcome:)

The O(1) solution explanation for the first one — Robot cleaner is awesome! Also in the pascal solution, I appreciate the usage of the function solve_single.

The solution of problem C uses

to get mid. I know l + (r — l) / 2 can avoid crossing the boundary (also it is no need, because 2e9 is inside of int) but I cant understand why +1.

Moreover, what this problem bother me except how to know to consider the reversed problem is how to find the max value in desc array...

This contest was unrated?

Very nice editorial. Learning a lot from it

I don't understand why to take (hi'-x) in

Cand how we know that binary search used here ?? Can anyone explainFor binary search, the question that needs to be asked in this problem is

And we can see that, if the answer to this question is true for a number $$$x$$$, then for all number $$$y \le x$$$, the answer for that question is true as well, since we can use the same moving plan as if you are trying to make all the heap $$$\le$$$ x.

In other words, the "question" is a boolean function, which must be monotone for us to be able to do binary searching. For more details, I think you should read other articles about this topic.

For the question "why should we take $$$h'[i] - x$$$", I have answered one question above it. You can scroll up, or click the link here to jump to the answer https://codeforces.com/blog/entry/98463?#comment-872704

darkkcyan Thank you for such interesting problem set!

Can anyone please explain the example from D.

This is clear:10 10 1 1 10 10 75We do 9 steps from (1, 1) to (10, 10) so get 75/100.

So logically for me it's mean that we need to check how many steps we need to do clean the dirty once more. And it's 18. Since we have probability 75/100 and we have reminder 25/100.

We can answer: 9 + 18 * 25 / 75 = 15

And in case the fraction is reducible. So the number is understandable.

This is not clear at all:5 5 1 3 2 2 10How come we get: 332103349 and not 25?

If probability is 10/100, so I expected that 10 "clears" will do the answer for me.

Please explain if you understand why this don't work.

Note: I know what is reverse element modulo. I hope the answer will be helpful not only for me :)

Well, I purposely put that test there just to test the code, since that test is complicated enough. So, statistically, if you passed 2 last example test cases, then you have very high chance of being AC.

Everything I will do below will be the same as the "hand solving algorithm", described in the editorial. Let's see the animation.

If it is not playing for some reason, you can click here https://gifyu.com/image/SSFPl

The probability of cleaning is $$$10\%$$$, so the probability of not cleaning $$$\overline p$$$ is $$$0.9$$$.

The cycle length is 8. Let answer for each state be $$$x_1, x_2, x_3, \ldots, x_8$$$. The system of equations will be:

Substituting them back to back, we will have the equation for $$$x_1$$$.

You can solve this equation by hand, or slap it into WolframAlpha, and it will solve for you like this https://www.wolframalpha.com/input/?i=x+%3D+1+%2B+9+%2F+10+*+%281+%2B+1+%2B+1+%2B+1++%2B+9%2F+10+*+%281+%2B+1+%2B+9%2F10+*+%281+%2B+x%29%29%29

The answer for $$$x_1$$$ will be $$$\frac {6949} {271}$$$. And this is indeed $$$332103349$$$ modulo $$$10^9 + 7$$$.

P.S: I feel like you don't really read the editorial. Please read it first. It literally contains two examples of hand calculation. I did spend a little amount of time just for this answer, but I really feel like it is not worth it.

Hi, I understand that the formulas are very cool, but if you check the animation, you will see that each circle clears a dirty cell 3 times. One circle contains 8 seconds. And I agree with the previous statement. It need 25 seconds. May be i was rude (i know English very bad)

The animation (or rather, the cycle) is 8 seconds but it is not guaranteed that after 1 cycle the robot is going to clean the dirty cell. That is because of the probability. If it could not clean the cell in one cycle, it must of course continue its journey until the dirty cell is cleaned.

If you calculate the value of $$$\frac {6949} {271}$$$, you will get $$$25.6420664207$$$, which is IMO close to your intuition.

Do I understand correctly that if we have a 10% chance, then the mathematical expectation of cleaning will be in ten tries? If yes, then the correct answer is 25, because one circle is 8 seconds and 3 clears. 24 seconds — 3 circles and 9 cleanups, and at 25 seconds the required 10 iteration will occur.

No, that is the

totally wrong wayto understand it.Simply put, for this concrete example, the process is the following:

When you have an opportunity to clean the cell (that is, either the robot's row position is the same as the dirty cell's row position, or their column position are the same), you will roll a dice with 10 faces. If you rolled on $$$1$$$, you can clean the dirty cell and stop the process. Otherwise, if you rolled on on $$$9$$$ other faces, you must continue the clean up journey. And this process can actually take forever.

It will be better to write down the probability branch as follows.

$$$5.$$$ and so on, ...

$$$69.$$$ and so on, ...

$$$420.$$$ and so on, ...

$$$\infty$$$. forever...

Your reasoning only works with geometric distribution. In other word, if the duration between 2 events are the same, then you can

safelyuse your intuition. In the second to last example, the duration between the starting moment and the first cleanup moment, the duration between the first and the second clean up moment, and the duration between the second and the third clean up moment, aredifferent, so you cannot use geometric distribution.The formula that I used in the tutorial are

actually one way to prove geometric distribution's mean formula, but in the case it is used in more general sense.Thank you for answer, but i have one more questions. How i can get

332103349from25.6420664207at c++. Operator % doesn't work.Well you should read the problem more careful. It said that the answer can be described as an irreducible faction $$$\frac x y$$$, and in this case $$$x = 6949$$$, $$$y = 271$$$. You need to print out the value $$$x \times y^{-1}$$$, modulo $$$10^9+7$$$, and here $$$y^{-1}$$$ is the modulo inversion of $$$y$$$. You can search it up on Google, or simply put, you must print $$$x \times y^{-1} \equiv x\times y^{10^9 + 7 - 2} \pmod {10^9 + 7}$$$.

look, if we take

x * y1 ^ -1and mod this1e9 + 7, then we have25.6421cout<< fmod (pow((double) 271, -1) * (double)6949, (double) 1e9+7);I think you still don't understand the modulo arithmetic, as well as the purpose of asking the answer under a modulo.

Why the hell a lot of problems ask to print the answer under a certain modulo?

First of all, the real answer might be hard to compute, as well as to check. If the answer is too big, the computing it requires a number with bigger precision, and it will take a factor of $$$O(|ans|)$$$ to $$$O(|ans|^2)$$$, based on implementation, where $$$|ans|$$$ is the length of the answer (in decimal presentation). This is also true when the answer is not an integer. Sure, we might ask to print, for example, $$$25.6412$$$, but that is imprecise, and there might be solution that actually use that imprecision fact to calculate the answer.

solution for imprecise answerSimulate the process, for example, $$$10^6$$$ steps. Each step we will jump to the next clean up position, using $$$O(1)$$$ solution from A. You can calculate the probability of clean up there, multiply it by the distance from the start, then add it to the result. There is no reason to go furthur, since the probability of not clean up after that many iterations is too small, therefore their contribution to the result is insignificant.

But, what if, we want the true answer?

One of the solutions for this imprecise problem is to use modulo arithmetic. In modulo arithmetic, the answer of the contestant might not also be correctly compute (since lots of number yield the same modulo), but we are now working with

small integers, and this time, the imprecise answer can be compensated with doing a lot of tests.Addition, subtraction and multiplication are the same, but not really for division. But mathematician came up with another solution, called

modulo inversion, multiply a number by with yield the same result as doing the real number (not under modulo). This inversion thing can be found really fast and easily, using another algorithm called binary exponentiation, if the modulois prime.So we have all operations, as well as a "fast" way for doing calculation and checking, therefore this is currently the way of doing thing in CP cometitions.

So, TL;DR: look up the modulo arithmetic and modulo inversion, as

I already told you to doin the last comment.This comment is only for the case, where people said that "oh no he wont explain. What a

~~ratist~~!". I know you would not say that, but you understand my point.No. Everything you need to learn is up there, on the internet. Please search them up before asking. And I would like to actually not reply anymore.

Thank you for such detailed description! I appreciate your comment(s).

I found why my approach is wrong thanks to you. I just needed to read about different distributions. (never heard about Geometric for example)

I think I am missing something, but why did you initialise $$$dr$$$ and $$$dc$$$ as $$$-1$$$ in your model solution (140969025)? The only reason I can think of currently is that the equation needs to be computed from the inside (so last to first), but I'm not really certain about the intuition behind. Can you briefly explain the idea behind why it has to be reversed? Thank you.

Also, is there a way to compute the answer after knowing the expected value after the 1st round and the probability that the dirty cell still hasn't been cleaned? It might be more annoying to compute, but it is more intuitive to me. Currently I have $$$\sum_{k=0}^{\infty} (Q^i)(x+(4(n-1)(m-1))k)$$$, where $$$Q$$$ is the probability that the cell still hasn't been cleaned ($$$=(1-\frac{1}{p})^{4(n-1)(m-1)}$$$) and $$$x$$$ is the expected value after the 1st round. Is it possible to use geometric sequences to solve this equation?

P.S. The round was very well-prepared! The animations definitely made it easier for me to understand the problem.

For the first question. Yes, your reason is the whole point. You can see the equation again. It has the form of lots of brackets wrapping around the only variable $$$x$$$, and here I want to break those brackets out, so the final form of the equation can be $$$x = a + bx$$$.

For the second question. I think there might be one such solution, and I think the other participants have done so. But that solution I think is really annoying. Maybe you can rewatch Geothermal's stream on the round for more insight (I'm not tagging him here). Here is the link https://codeforces.com/stream/363. But that being said, I do think my solution is really, really simple :)

And I'm very glad that you like the round! :)

Although my solution to E was different from the editorial's when upsolving, I thought the problem was super beautiful nonetheless! idk if anyone will care, but here is my proof for the editorial's solution:

Suppose that there exists a lexicographically smaller string $$$s$$$ than the one which our algorithm came up with. Consider some set $$$S \subseteq \{ 1, 2, ..., n \}$$$ of duplicated vertices which yield $$$s$$$. Let $$$u$$$ be the earliest vertex in the tree's inorder traversal such that our algorithm duplicated $$$u$$$, but $$$u \not \in S$$$. Suppose that $$$S$$$ is a set which makes $$$u$$$ as late in the inorder traversal as possible.

Lemma: If there exists a $$$v \in S$$$ such that $$$v$$$ was not selected by our algorithm, $$$v > u$$$.

Let $$$P \subseteq S$$$ be the set of all duplicated vertices selected by our algorithm, which came before $$$u$$$. Let $$$Q \subseteq \{1, 2, ..., n \}$$$ be the set of vertices with labels corresponding to $$$u$$$'s segment of characters. It must be true that $$$(S - P) \cap Q \neq \emptyset$$$, or else our algorithm's string would be lexicographically smaller than $$$s$$$. Consider any $$$v$$$ in this set. Let $$$p = LCA(u, v)$$$. It follows that $$$v$$$ must be in $$$p$$$'s right subtree (and $$$u$$$ in the left), since otherwise from the above lemma, $$$v \in P$$$ (oops, forgot the case when $$$p = v$$$ but w/e things still work). Since all vertices lying along the path from $$$p$$$ to $$$u$$$ are in between $$$p$$$ and $$$v$$$ in the inorder traversal, they all must be in $$$Q$$$. Let $$$x > 0$$$ be the number of vertices along the path from $$$p$$$ to $$$u$$$ which are not in $$$S$$$.

There now exists a simple construction which produces a set of duplications which yields a string at least as good as $$$s$$$: take $$$S$$$, and repeatedly remove vertices $$$w$$$ such that $$$w \in S - P$$$ until $$$\#(S) + x \leq k$$$. Then add those $$$x$$$ vertices to $$$S$$$. Let the newly formed set be $$$S'$$$. Now, $$$P \cup \{u\} \subseteq S'$$$, which contradicts our supposition.

In Stone Heap Question’s solution, why is d written as

Int d = min( h[i],cur_h[i]-x )/3; ? Why do we need h[i]? And why not just

Int d = (cur_h[i]-x )/3;

Also why do we need a global h[i] and cur_h[i] arrays

Thanks in advance!!

You can actually try implementing that and that will not work with the example.

I already wrote about this in the editorial, but I will repeat it. The process we are doing is not backward. It is forward. By moving forward, the true limit for the number of moving stones is not

`cur_h[i]`

, but`h[i]`

. Therefore`h[i]`

must limit the number of moved stones.`cur_h[]`

array does not need to be global. It can be local. The only reason that we need 2 arrays, is because we need both of them to calculate`d`

, as you have written above.why 4(n-1)(m-1)is k — the cycle? help! lengthsince 4(n−1)(m−1) will always be the multiple of k — the cycle length.

You should have read the other comments first

https://codeforces.com/blog/entry/98463?#comment-872602

For problem D, is there any solid proof that the robot's path form a cycle and the starting point belongs to that cycle. I think the editorial takes this observation for granted.

Note: sorry it should answered by the above comment.Gotta hand it to codeforces community... seeing these comments trying to do their best inspires so much.

In C according to the tutorial

int d = min(h[i], cur_h[i] — x) / 3; Whenever d is taking value (cur_h[i] — x) / 3, it is ok as we know that even after subtracting, we will be left with atleast x there but when d is h[i]/3, how are we dealing with that case can someone explain ? I think I am missing something, I know we are doing that because we don't have that much stones in it but how are we so sure that doing so will guarentee us atleast x stones in curr_h[i].

For problem c in editorial it is given that we binary search on x where a condition "every heap can be of size greater than or equal to x" is checked .

Is it necessary that, We can do binary search on x if and only if x continuously takes integer values from 1 to its maximum value(obeying the condition) and after the maximum value it should not obey condition ?.

If so does x takes integer values continuously from one to its maximum value (satisfying above condition) in this question??

Is there anything that we should note about x to do binary search on it?

The condition you have described is called monotone. Yes, the function is monotone, because if there is such a maximum number $$$x$$$ that the condition is satisfied, then for all numbers $$$y \le x$$$, the condition is also satisfied for them. That is because, we know that we can somehow make the condition satisfies for $$$x$$$, we can do the same so the condition is satisfied for $$$y$$$.

Based on the definition of the function described in the editorial, the function is obviously continuous on the positive integer domain, since it is monotone.

I'm not sure about the last question. Well, you should just do it in the value range of the heaps, and make sure that your calculation is not overflowing.

I cannot for the life of me figure out why my solution to C is timing out:

https://codeforces.com/contest/1623/submission/141359231

it is definitely an NLogN solution

In your code you are using

`accumulate(H.begin(), H.end(), 0)`

. The thing is, the type of the value for storing the answer will be the same as the typeof the 3rd argument, and in your code, it is`int`

, therefore it will be overflow! One fix is to change it to`0ll`

, or, you just take the max value instead of the average.Ah that’s definitely it, thank you!

For problem D,I can't understand the reason of 141635448(I copy other's code),I hope someone can help me explain. Thank you very much,I'm using arithmetic summation and dislocation subtraction,so I don't understand how this neat algorithm works.

Why do you need to reverse the heaps for problem C. Why can't you just greedily do it from left to right? Would that greedy not work?

For the first question. We do it in the reverse order since we have enough information to confidently determine the number of stones so that all the stones from the current position till the first position must satisfy our condition. If you still wonder why I think some of the comments above will give you some insight.

For the second question. What kind of strategy are you suggesting for the greedy approach? I mean, only "greedy" is not enough to tell how exactly we should determine the number of stones to move. A short answer to this question will be similar to the above: we

don'thave enough information to determine. But if you have another solution, that youcanprove, I would like to hear it.Thanks for responding so quickly! What I was thinking was the exact same approach you used, but going from 2 to n — 1. But I don't think I can prove it.

A small first step for

provingis to find a counter-example. If there is none then you can say that your greedy approach might work, at least with random cases.To find such an example, you can implement your own algorithm, and you also need a

correctsolution. Correct here means that you can take an AC code, or if you doubt those solutions, you can do brute-force. And the test cases can be randomly generated. You can run your algorithm against the correct one to see if they matched. Thistipis actually implemented by problem setters for checking their solution, as well as in real contests for the same purpose.But I will tell you that going from left to right is hard.

Thanks. I think I found a case where my algorithm broke.

Can you tell me(an example) exactly where left to right traversal fails ?

I'm not sure I remember, but I'm pretty sure it was something about not having enough stones to move.

Thanks anyway! I got it

Hello, I guess solution of B has an error--->>>> "vector mark" This is leading to compilation error. Correct me if I am wrong. Thank you

You must compile that solution with C++17. See the below comment (https://codeforces.com/blog/entry/98463?#comment-881218) for more details, since his question is more direct.

in the problem B i didn't understand how this line "vector mark(n + 1, vector(n + 1));" worked, can somebody please help me with this

That is C++17 features called "type deduction". One of the constructors of

`vector`

accepts the size and the initial value of the elements. Here the compiler actually knows the type of the second argument, so in C++17, it can deduce the type for the template parameter, therefore there is no need to declare the template parameter (again). This is huge compared to the previous versions of C++ since you can write multi-dimensional vectors more easily.That is so helpful. Thank you!

Thanks for the adaptive dark theme explanation on problem E! :)

This is a very good editorial , orz to the author! Well written explanations + liked the idea of "problem note".

There is nothing much in B is it overrated or is there any other way to do more efficently than using maps by bruteforce