darkkcyan's blog

By darkkcyan, 2 years ago, In English

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

Pascal solution: 140969053 C++ solution: 140969037

  • Vote: I like it
  • +221
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
2 years ago, # |
Rev. 3   Vote: I like it +37 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

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

    • Definition of a floor.
    • Definition of a position.
    • Moving rule explaination.
    • Cleaning rule explaination.
    • The actual problem.

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

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I will also use EvErYoNe'S fAvOrItE lAnGuAgE: Pascal.

Ahhh yes, here he is, the classic darkkcyan.

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

O(1) solution of problem A is cool~

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 )

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no bro. i think its invalid

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
2 years ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

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){

if(rb==rd || cb==cd) break;

        else if(rb=n ){
            dr=-1;
        }
        else if(cb=m ){
            dc=-1;
        }
        rb+=dr;
        cb+=dc;
        cnt++;
    }
    cout<<cnt<<endl;

}

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--){

}
return 0;

}

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Regarding problem D, I have two doubts -

  1. 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?

  2. 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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    1. I don't think that there will be a case where all of the states can be visited. This can be proven as follows. If there is a cycle containing all states, it should also contain 4 corners. But the maximum number of corners that can be contained will be at most 2. Without loss of generality, let's just start at one corner. Once we meet another corner, our path is tracing back, therefore we can only visit the cells that we have already visited, and when we came back to the started corner, the robot bounces back as well. So no, there is no configuration that the robot can visit all of the possible states.
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 !

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

bool check(vector<ll> stones, ll d, ll n) {
 for (ll i = 2; i < n; i++) {
    ll req = 0;
    if (min(stones[i - 1], stones[i - 2]) >= d)
        continue;
    if (stones[i - 1] < stones[i - 2]) {
        req = (d - stones[i - 1]);
    } else {
        req = ceil((d - stones[i - 2]) / 2.0);
    }
    if (stones[i] < 3 * req) {
        req=stones[i]/3;
    }
    stones[i] -= 3 * req;
    stones[i - 1] += req;
    stones[i - 2] += req * 2;
}
for (ll i = 0; i < n; i++) {
    if (stones[i] < d)
        return false;
}
return true;

}

Here is the submission

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Very nice editorial. Had fun reading it :)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hey darkkcyan in the editorial of C I think it should be d = $$$\dfrac{h_i - x}{3}$$$ instead of d = $$$\dfrac{h_i}{3}$$$ .

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are right! My bad. I will fix it.

    Thank you for your report!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

Formula
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The solution of problem C uses

int mid = l + (r - l + 1) / 2;

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...

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This contest was unrated?

»
2 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Very nice editorial. Learning a lot from it

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand why to take (hi'-x) in C and how we know that binary search used here ?? Can anyone explain

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For binary search, the question that needs to be asked in this problem is

    If we have a number $$$x$$$, can we, somehow, make all the heap not less than $$$x$$$?

    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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 75

We 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 10

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    robot-cleaner-revisit-5-5-1-3-2-2

    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:

    $$$ \begin{cases} x_1 = 1 + x_2 \\ x_2 = 0.9 \times (1 + x_3) \\ x_3 = 1 + x_4 \\ x_4 = 1 + x_5 \\ x_5 = 1 + x_6 \\ x_6 = 0.9 \times (1 + x_7) \\ x_7 = 1 + x_8 \\ x_8 = 0.9 \times (1 + x_1) \end{cases} $$$

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

    $$$ x_1 = x = 1 + 0.9 \times (1 + 1 + 1 + 1 + 0.9 \times (1 + 1 + 0.9 \times (1 + 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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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)

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No, that is the totally wrong way to 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.

            1. You go from the initial position to the cell $$$(2, 4)$$$. There, you got a opportunity to clean the dirty cell, and the chance is $$$10\%$$$. So you can expect, $$$1$$$ out of $$$10$$$ time running the robot, it will cleans the dirty cell.
            2. Otherwise, the robot continues its journey. When it is at the position $$$(4, 2)$$$, it has another opportunity to clean the dirty cell. The chance is the same, it is $$$10\%$$$. So you can, again, expect $$$1$$$ out of $$$10$$$ time running the robot that has failed to clean the dirty cell from the step 1 (or, in other word, $$$10\%$$$ of $$$90\%$$$, or $$$9\%$$$ of the running time), the robot can clean the dirty cell at this step.
            3. Otherwise, the robot continues its journey to the position $$$(2, 2)$$$. The reasoning is the same, $$$1$$$ out of $$$10$$$ time running the robot that has failed to clean the dirty cell from the step 2 (or $$$90\% \times 90\% \times 10\%$$$ chance), the robot can clean the dirty cell at this step.
            4. Otherwise, it continue its journey to the cell $$$(2, 4)$$$, where it has another opportunity to clean the dirty cell, ....

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

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

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

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

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Your reasoning only works with geometric distribution. In other word, if the duration between 2 events are the same, then you can safely use 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, are different, 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.

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you for answer, but i have one more questions. How i can get 332103349 from 25.6420664207 at c++. Operator % doesn't work.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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}$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                  Rev. 3   Vote: I like it 0 Vote: I do not like it

                  look, if we take x * y1 ^ -1 and mod this 1e9 + 7, then we have 25.6421 cout<< fmod (pow((double) 271, -1) * (double)6949, (double) 1e9+7);

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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 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 modulo is 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 do in 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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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)

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it +15 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

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

»
2 years ago, # |
Rev. 5   Vote: I like it +11 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 type of 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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't have enough information to determine. But if you have another solution, that you can prove, I would like to hear it.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A small first step for proving is 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 correct solution. 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. This tip is 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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like 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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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