AleXman111's blog

By AleXman111, history, 9 months ago, In English
Tutorial is loading...

Authors: AleXman111, sdryapko

author's solution: 100959880

Tutorial is loading...

Author: Vladik

author's solution: 100960218

Tutorial is loading...

Author: Vladik

author's solution: 100960332

Tutorial is loading...

Author: Vladik

author's solution: 100960452

Tutorial is loading...

Authors: AleXman111, sdryapko

author's solution: 100960607

Tutorial is loading...

Author: AleXman111

author's solution: 100960771

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

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

B was so similar to this

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    also an easier version to problem https://codeforces.com/problemset/problem/1393/D

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I think your task is a classical example of this algo: https://e-maxx.ru/algo/maximum_zero_submatrix

    The contest's task is more original statement (who doesn't like Christmas trees:)))

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 3   Vote: I like it -15 Vote: I do not like it
      string ans = "";      // problem A
      for(int i = 0; i < N; ++i) 
          ans += ((char)('a' + i%3));
      cout << ans << endl;
      

      why is it wrong?i'm so confused.... is there something wrong about "std::string"????

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

        You output an extra space, so the checker thinks it doesn't consist of abc.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you so much!!!! -,- i forget my costom "#define", thank you!!!

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

    Video Editorial Problem C: Random Events

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Thankyou

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thank you , but tbh you could have helped more by making video editorial on E and F . Most can solve C,D from editorial itself .

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why is this so heavily downvoted?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I feel it's because of the color. Need to get back to CM maybe.

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        I have same question... He didn't do anything wrong, just posted a comment with a video link which most probably he put some efforts to make and also which might help others.
        On the other hand shitty memes gets 100s of upvotes. I sometimes really wonder why is it so, what do people think before deciding to upvote or downvote.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        I think it is because that he commented under someone else and his comment is totally unrelated to the original comment.

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

      That Decision-tree you made was so helpful . Thanks !

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it using DFS Here

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was thinking of another approach for E.
For x<y, what if we change the problem a bit? I mean now instead of filling on starting of day, we fill at the end of day. And now initial k=r-k+l and we swap(x,y).

Now we have a similar problem where y<=x, and the only change is that we are now filling at the end of the day. Would this work?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This won't work since you are required to subtract x at the end of each day but you may or may not add y. But if you swap x and y, you will be essentially adding the original y every day.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the space complexity in Problem D?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it -37 Vote: I do not like it

    Sorry, my bad

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$O(n\log n)$$$

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do we find it?

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +22 Vote: I do not like it

        Sorry, it's $$$O(n)$$$. The time complexity is $$$O(n \log n)$$$.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thanks....any idea about the maximum size of the set or map used to store all possible sums?

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
            Rev. 3   Vote: I like it -13 Vote: I do not like it

            Wrong thought

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

            In the worst case when all the sum are different in the tree then it would be approximately $$$2 * n - 1$$$.

            Let's think about a perfect binary tree. Let's say there are $$$n$$$ leaf nodes. Then number of node will be $$$1 + 2 + 4 + 8 + 16 + ... + n = 2*n - 1$$$.

            If our tree is not a perfect binary tree then there will be more than $$$2*n - 1$$$ nodes.

            When I need to define an array for non-perfect binary tree I declare the array of size $$$4*n$$$. Because there are always atleast $$$4*n$$$ nodes in the tree.

            So, the space complexity is $$$O(n)$$$

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why time complexity is $$$\mathcal{O}(n \log n)$$$? I think it is $$$\mathcal{O}(n \log n \log A)$$$, because we have $$$\mathcal{O}(\log A)$$$ recursion depth, and in each level we have less than $$$n$$$ subsegments. We can get subsegment sum for $$$\mathcal{O}(1)$$$ and check it in HashMap for $$$\mathcal{O}(1)$$$. But each time we are going to next level, we need to find middle position using binary search for $$$\mathcal{O}(\log n)$$$ so it will be $$$\mathcal{O}(n \log n \log A)$$$ time, and $$$\mathcal{O}(n)$$$ space.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it -7 Vote: I do not like it

    Yep, wrong thought, so sorry

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have done the same way as editorial by calculating all possible sum but i am getting tle. how?? link to my code : https://codeforces.com/contest/1461/submission/126734496

»
9 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

There are quite a few O(n*m) solutions for problem B , not sure why O(n*m*m) is the intended solution. I will share approach i have used .

Let dp[i][j] be the number of spruces having (i,j) cell as the bottom center point of the spruce . then dp[i][j] = min(dp[i — 1][j] + 1, min(left[i][j], right[i][j])) . Here left[i][j] is the number of * to the left of (i,j) and right[i][j] is the number of * to the right of cell (i,j) . Both left and right can be easily computed in o(n*m) . The final answer is simply sum of all dp[i][j]

Link : https://codeforces.com/contest/1461/submission/100925269

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

If i am passing a new vector in each new recursive call in D then what is space complexity for it.. How should i Calculate time complexity for this??

Link- https://codeforces.com/contest/1461/submission/100962372

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Since any element of your initial input array can appear in at most $$$O(log(n))$$$ different vectors , the total space complexity would be $$$O(n*log(n)).$$$ The question should now be : Why would an element be in $$$O(log(n))$$$ vectors in the worst case? Think about the number of your recursive calls. In the worst case it's $$$O(n)$$$ because we might have leaf nodes for all the $$$n$$$ elements in our recursion tree and the number of internal nodes in such tree is $$$n-1$$$, which overall concludes to $$$2n-1$$$ nodes. Coming back to the real question, in a recursive call, an element will either go to the left or to the right vector and in our recursion tree (in the worst case) this element will appear over all the corresponding $$$O(log(n))$$$ nodes (this indeed happens when all the elements in the array is some sort of permutation) and generalizing this for all elements in the input array , we need $$$O(n*log(n))$$$ space. But please note that this $$$O(n*log(n))$$$ space complexity can be further reduced to $$$O(n)$$$ with only passing indexes of your input array to your recursive function.

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

In problem D,What can be the maximum size of the set or map used to store all the possible sums?

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I am sure many contestants wouldn't able to solve c if only one example was given. (including me :>)

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

    I didn't even look examples but again C was not hard

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

What's the complexity of problem E? Where is the proof it can pass in time? Is it obvious?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    It's $$$O(x)$$$, because we visit each state of $$$k\mod x$$$ from $$$0$$$ to $$$x − 1$$$ at most once.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      Right!! I was thinking x could be up to 10^18 xD There were so many variables I didn't see the 10^6 constraint :(

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

    It takes $$$O(1)$$$ time to lower the level as much as possible then add $$$y$$$. Realize that we only add $$$y$$$ $$$a$$$ times where $$$ a \cdot y \equiv 0 \mod x $$$. After this we are back to where we were at in the beginning, so we can stop checking. This takes $$$ a = \frac{x}{gcd(x,y)} $$$ iterations. So it's $$$O(x)$$$.

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting solution for E.

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

https://codeforces.com/contest/1461/submission/100953014

What is wrong with this solution? (problem C)

»
9 months ago, # |
  Vote: I like it -16 Vote: I do not like it

My unnecessarily over-optimized solution to problem D for anyone interested.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It ran for almost 0.8 seconds. I don't think it was over-optimized lol.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Looks like you judge optimality of code by its runtime XD XD ...... If you know how to compute and compare complexity you'll understand hopefully.
      PS: I removed fast io for readability. Check this code with fast IO.

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

        Yeah, I was just kidding XD, my code is exactly the same.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

100958922 Can someone tell me, why it is giving TLE in pretest 1, in single for loop... Though giving correct answer..

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You forgot to put return in line 40. The code will get stck in infinit loop.

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

C was nice

»
9 months ago, # |
Rev. 5   Vote: I like it +41 Vote: I do not like it

My solution for E is O(1). It's a bit complicated to explain but if interested, you can see the code here.

Edit 2: It turns out that my algorithm was incorrect at the last step after one user hacked my submission. Read this comment below.

Edit: After some people asked, I decided to give a rough idea of my solution. I strongly suggest you to draw a number line on a paper while reading my solution. $$$[x]$$$ represents $$$floor(x)$$$.

I am calculating the max number of days for which it is possible to maintain the water level between $$$l$$$ and $$$r$$$, and storing this value in $$$num$$$ which I will later compare with $$$t$$$ to output "Yes" or "No". If initially $$$k-x < l$$$ and $$$k+y > r$$$ then clearly $$$num = 0$$$ and the ans is "No".

If $$$x = y$$$, then we can maintain the water level indefinitely and the answer is "Yes", no matter what $$$t$$$ is.

If $$$x > y$$$, then the water level must decrease every day at least by an amount of $$$x-y$$$. Assuming $$$k+y \le r$$$, $$$num = \left[\frac{k-l}{x-y}\right]$$$. However if $$$k+y > r$$$, then $$$k-x$$$ must be greater than or equal to $$$l$$$ and so in the first day, we don't add $$$y$$$ and our new $$$k$$$ becomes $$$k-x$$$. Then using the same logic as above, $$$num = 1 + \left[\frac{k-l}{x-y}\right]$$$ (here $$$k$$$ is the new $$$k$$$).

The difficult case is when $$$y > x$$$. Note that if at any point, if $$$k$$$ takes a value in the interval $$$[r-y+1, l+x-1]$$$ then we cannot maintain the water level for another day. So if the interval itself does not contain any integer points, then we can safely say the answer is "Yes". This happens when $$$(r-y+1) - (l+x-1) \ge 1$$$, or equivalently, when $$$x+y \le r-l+1$$$. Otherwise, there is a "danger zone" (i.e. the interval $$$[r-y+1, l+x-1]$$$) where we don't want to step in. If we are on the right side of that danger zone, it means we cannot add $$$y$$$ and on the left side, we cannot subtract $$$x$$$. Inside the danger zone itself, we cannot do either. If we are on the right, we subtract $$$x$$$ as many times as possible which is equal to $$$\left[\frac{k-l}{x}\right]$$$. After doing this, our $$$num$$$ becomes $$$\left[\frac{k-l}{x}\right]$$$ and we reach $$$k = k - \left[\frac{k-l}{x}\right]\cdot x$$$. If we reach the danger zone (can be checked by checking if $$$k+y \le r$$$ is false), then we are done. Otherwise, we must be on the left side of that danger zone and now we need to add $$$y$$$ to our $$$k$$$. If $$$x$$$ divides $$$y$$$, then we can repeat this process indefinitely (adding $$$y$$$ and subtracting $$$x$$$ multiple times) and in that case, our answer will be "Yes" (I have set t = -1 in the code because I am comparing num with t at the end). If there is some non zero remainder, call it $$$rem$$$. After adding $$$y$$$ and subtracting $$$x$$$ $$$\left[\frac{y}{x}\right]$$$ times, we will reach at $$$k = k + rem$$$. We keep doing this until we are outside that danger zone i.e. $$$\left[\frac{r-y-k}{rem}\right]$$$ times. We add $$$\left[\frac{r-y-k}{rem}\right]\cdot\left[\frac{y}{x}\right]$$$ to $$$num$$$ and add $$$\left[\frac{r-y-k}{rem}\right]\cdot rem$$$ to $$$k$$$. After taking another step (1 step = $$$\left[\frac{y}{x}\right]$$$ days), either we can land inside the danger zone meaning we are done, or, we can cross over that danger zone. If we land in the danger zone, then we just simply add $$$\left[\frac{y}{x}\right]$$$ to $$$num$$$ and we are done. Otherwise, we reach at $$$k = k + rem$$$ which lies on the right of danger zone. Since $$$rem < x$$$, subtracting $$$x$$$ will surely take us to the left of danger zone and that too on a location which is left to our original location (before taking the step). The "decrease" in our position after $$$\left[\frac{y}{x}\right]+1$$$ days is $$$x-rem$$$. We can afford to let it decrease only $$$\left[\frac{k+rem - (l+x)}{x-rem}\right]$$$ times and that consumes another $$$\left[\frac{k+rem - (l+x)}{x-rem}\right]\cdot(\left[\frac{y}{x}\right]+1)$$$ days. After another $$$\left[\frac{y}{x}\right]$$$ days, we finally land inside the danger zone and we are done.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Seeing your code, maybe I need that “complicated explanation “ lol

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Respect ++

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please explain if you could, I think $$$O(x)$$$ is not very hard to come up, but I have been trying $$$O(1)$$$ for some time now

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have updated my comment.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I think you have a typo, should be ..

        the difficult case is $$$y > x$$$

        Now reading and understanding rest of comment!

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, Can you please explain the if (rem) block of your code. Thanks.

    PS. Those trying to understand problem E try to think of it as, given two points l and r on x-axis and a starting position k, you're allowed to move x units backward and y units forward.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have updated my comment.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Coming up with danger zone interval was pretty neat. Thanks for the detailed explanation.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    The solution is broken with this case 3 1 17 inf 8 10 The process can go on forever

    3 -> 13 -> 5 -> 15 -> 7 -> 17 -> 9 -> 1 -> 11 -> 3 -> ...

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

      Thank you for pointing this out. Upon hand-tracing my algorithm on your example, I realized that the issue is at the last step. I assumed that after another $$$\left[\frac{y}{x}\right]$$$ days, we will surely land in the danger zone (last line). However, this is wrong since the value of $$$x-rem$$$ can be larger than the length of our danger zone and we may skip over it. To make the algorithm correct, we need to repeat the process all over again with new $$$x = x-rem$$$ and keep doing this until either we reach the danger zone or get $$$rem = 0$$$. In the worst case, $$$x$$$ may only decrease by $$$1$$$ in each iteration and therefore the algorithm becomes $$$O(x)$$$.

      This was very unfortunate though :/

»
9 months ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

I know how can problem B be solved with Dynamic programming, but the explanation in the editorial does not explain 1 single thing about the usage of DP in the problem and why we should use DP instead of just simulating the explanation.

Very poor explanation with very low effort.

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

    The tags say it can be done using brute force but giving WA and TLE. Can someone help me with that.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the rating changes will be published ???

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how to solve the question B ? The solution given in editorial is not clear to me. Thanks

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    My solution to B is a 2D DP. The total complexity is O(NM) and i guess it is easier to understand too.

        int n, m; cin>>n>>m;
        int dp[n+2][m+2];
        mem(dp,0);
        bool block[n+2][m+2];
        REP(i,1,n) {
            REP(j,1,m) {
                char ch; cin>>ch;
                if (ch=='*') block[i][j]=1;
                else block[i][j]=0;
            }
        }
        ll ans=0;
        for (int i = n; i>=1; i--) {
            for (int j = m; j>=1; j--) {
                if (!block[i][j]) continue;
                dp[i][j]=block[i][j]+min(dp[i+1][j],min(dp[i+1][j-1], dp[i+1][j+1]));
                ans+=dp[i][j];
            }
        }
        cout<<ans<<endl;
    
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -15 Vote: I do not like it
      if (!block[i][j]) continue;
                  dp[i][j]=block[i][j]+min(dp[i+1][j],min(dp[i+1][j-1], dp[i+1][j+1]));
                  ans+=dp[i][j];
      

      Please explain these steps. Thanks.

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        If the symbol at (i,j) != '*' we skip as no spruce tree with that as top can be formed else we do the dp thing. The dp thing is actually we are seeing what max height trees can be formed by the (i+1,j)(i+1,j-1),(i+1,j+1) as the top and the max height tree that can formed by (i,j) will be min of them+1. You will get the intuition when you draw a few cases and we can further prove it by induction.

        dp[i][j] = hieght of max height tree with (i,j) as top

        The main idea here is that the height of max height tree that can be made with (i,j) as the topmost piece == no of trees that can be made with (i,j).

        Finally that ans is answer to our problem that is the total no of spruce trees = sum of spruce trees with top (i,j) for all i, j.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is this downvoted? I just tried to help this guy. Is it ratism? If no please tell me how can I improve my comments and what is wrong in this one?

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

        I dont know why others are downvoting your answer as well as my questions too , your explanation was quite good , I had upvoted your answer.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No man, don't take it in another way... It's just because you directly pasted comment(code) that makes this blog messy...Always put your codes in spoiler and enjoy green color besides your contribution. :P

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain E? I get the initial part where y<=x.

Otherwise, let's note, when we use the rise in water level, we change the value of the expression k mod x. At each step of the algorithm, we will lower the water level as many times as we can, and then raise the level.

What does this mean? What exactly is the value k mod x. And why do we lower till the time we can and not add y litres of water somewhere in between of this process?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this statement can be helpful to explain the editorial of E: Statement: If some solution exists, there exists a solution in which we add water to the cooler only on days when this is necessary (otherwise, the level of water at the end of the day will be lower than l).

    Proof.

    Let’s consider some solution to the problem. If this solution adds water only when needed – nothing to prove. If not, consider the first day t0 when the water was added, but this was not necessary. Let’s not add water at the beginning of t0. If this did not break the solution – nothing to prove. What if it broke the solution in some day t1 > t0? The only way we could break the solution at day t1 – we don’t have enough water is the cooler at the end of day t1. Let’s note that it means that we did not pour any water in the cooler at the beginning of t1 (since y>x). Let’s just do it – pour y liters of water into the cooler at the beginning of t1. The solution is fixed on t1, but it is also fixed for all the further timestamps (because for all the t > t1, moving the action of pouring y liters of water into the cooler from t0 to t1 changes nothing). Let’s continue this process until we only pour the water into the cooler when it is necessary. The resulting sequence of actions is a solution, in which we pour the water into the cooler only when necessary.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm thinking another approach for E:

Determine a range [r-y+1,l+x-1], if we reach this range at the beginning of day, its impossible.

Then use extended euclidean to find the minimum number of days to reach each number in this range

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem b to decrease the complexty you need to the bigest sprcues for every position and add to the (weidgh-1)/2 to answer and add the number of * to do that you will need to use binary search or memoistion the number of * before the curent index so the complexty will be n * m * log(n)

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it
A formal proof of the editorial solution of problem A. just for my practice!
»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

EDIT: My question (for F) was resolved -- My example in the previous post was wrong -- now makes sense that the case with * and — is very easy as was mentioned in the editorial.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

plz explain problem e editorial in detail

»
9 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

Could somebody explain the following, please? If the product of numbers is greater than or equal to 10^16, then it is beneficial for us to put the multiplication sign everywhere.

  • »
    »
    9 months ago, # ^ |
    Rev. 18   Vote: I like it +42 Vote: I do not like it

    I discussed with some other people on discord, and I’ll give credit to DreamingLeaf and tfg for some of the ideas.

    Consider an optimal assignment of operations in the array. Let the array have length $$$n$$$. We will have that the operations in the array will be in the form

    $$$(d_{11} * d_{12} * d_{13} * … ) + 1 + 1 + … 1 + (d_{21} * d_{22} * …) + 1 + 1 + … + (d_{k1} * d_{k2} * …)$$$

    where the first and last element of each block of $$$*$$$ are both $$$>1$$$. For each $$$i$$$, let $$$a_i = d_{i1} * d_{i2} * …$$$. Then, we have that the product of all the elements in the array is $$$a_1a_2…a_k$$$. Let this product be $$$P$$$. Suppose $$$P \geq 2n, k \geq 2$$$.

    Corrected proof (thanks DreamingLeaf!), also changed the bound to $$$2n$$$:

    We first want to show that $$$\sum_{i=1}^k a_i \leq 2 + P / 2$$$.

    If $$$k = 2$$$, then we have that $$$a_1 + a_2 = a_1 + \frac{P}{a_1} \leq 2 + P / 2$$$. For $$$k > 2$$$, we have $$$\sum_{i=1}^k a_i \leq (\sum_{i=1}^{k-2}a_i) + a_{k-1}a_{k}$$$ (a sum of $$$k - 1$$$ terms with product $$$P$$$) and can thus inductively show that the cost is $$$\leq 2 + P / 2$$$.

    We have that the cost of the current configuration is $$$\leq$$$ $$$\sum_{i = 1}^k a_i$$$ + (number of ones) $$$\leq 2 + P / 2 + n - k \leq P / 2 + n$$$. This is less than or equal to $$$P$$$ whenever $$$P \geq 2n$$$.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought AM-GM tells us that $$$\sum_{i=1}^{k} a_i \geq 2\sqrt{P}$$$, and not the other way around.

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

        Thanks for pointing that out. Also i think it should be n * nth root() -- i had improperly tried to generalize from k = 2. I guess there's a hole in my proof hmm... let me think about this

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually I messed up my some calculation, but it directly tells us that $$$\sum_{i=1}^{k} a_i \geq k \cdot P^{1/k}$$$.

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

      Let's assume a[i] <= a[i+1]. Let's say we can group those without regards to the 1's (so we can group them out of order). Group a2..ak, we get C = a1 + a2*a3*...*ak + n (n is the number of 1's in between). C is obviously an upper bound for the answer of grouping K-1 or less groups since ai >= 2. We want to prove a1*a2*...*ak >= a1 + a2*a3*...*ak + n for some condition. This actually reduces to a1*a2 >= a1 + a2 + n. The maximum a1+a2 happens when a1 = 2 and a2 = P/2 so: P >= P/2 + 2 + n, P/2 >= 2 + n, P >= 2*n+4. Here, n is the number of 1's, so we can take N = n+k where N is the actual size so P >= 2*N >= 2*N+4-2*k.

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

    Assume u are combining 2 numbers x and y from addition to multiplication. The amount gained is x * y — x — y = (x — 1) * (y — 1) — 1. Now assume we are able to take the first some amount of numbers in segment such that they are greater than 10^16, let that be x, and y is the next number greater than 2 after some 1s in between. Obviously, (10^16 — 1) * (2 — 1) — 1 = 10^16 — 2 is the minimum amount we could gain by ignoring the 1s and multiplying the two numbers, and that is much greater than the amount gained by adding the 1s obviously. In fact, you could have product much less than 10^16 too i believe, it should only be like n probably.

    Obviously not formal, but you can do an inductive proof on value of consecutive group multiplied to formalize it. My reasoning though is more intuitive and what I used in contest.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 6   Vote: I like it +11 Vote: I do not like it

      I use the formula $$$(A-1)(B-1)-1-x$$$ (where $$$x$$$ is number of 1s between the components) as the prize from merging 2 'components' too.

      If $$$A$$$ reaches $$$N+1$$$, where $$$N$$$ is the length of whole sequence, merge anything with that component will always get zero or positive prize (a.k.a. benefit) because $$$x$$$ cannot exceed $$$N$$$. That means the optimal decision to do then is merging the whole sequence.

      Therefore, if the optimal answer is not multiplying the whole sequence, then each separated component in the optimal answer must have the multiplication of all its number at most $$$N$$$

      Using this logic,

      1. there can be at most $$$N$$$ components
      2. each component's all-number-multiplication is at most $$$N$$$
      3. there can be at most $$$N$$$ numbers of '1'

      Therefore, the maximal value you can get without multiplying the whole sequence is at most $$$N^2+N$$$

      In conclusion, if multiplying the whole sequence is larger than $$$N^2+N$$$, it is already optimal, else we can solve it using DP.

      The proof above has shown tighter bound that $$$2N$$$ is already enough, but I think it is more intuitive this way.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please help in B(find the spruce)?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Find the maximum height of the spruce that can be obtained from each (x,y). (cell)

    The maximum height of the spruce at (x,y) depends on the

    1) maximum height of spruce that can be got at (x-1,y) (the cell above (x,y))

    2) the number of * to the left of (x,y)

    3) the number of * to the right of (x,y).

    So, we can iterate over the grid, fix each cell (x,y), find the maximum height of spruce that can be obtained if (x,y) is origin (center of the spruce). Sum all the values. You get the answer.

    To fit this in the time limit, you can use prefix sums, dp, binary search.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please explain how to use binary search in that problem, I know the other two.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        binary search on the maximum height at every cell.

        Check out my submission 100949094

        Binary search is absolutely not necessary as O(N^3) is allowed.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The simplest solution I can think of is to do a dp iterating from the bottom row up. Let dp[i][j] = the max height of a spruce. Then the answer is just the sum of all dp[i][j]. Start with all dp[i][j] = 1 if there is a '*' at i,j otherwise dp[i][j] = 0. If there is a '*' at i,j then dp[i][j] = 1 + min(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]) otherwise dp[i][j] = 0. This dp relation can be seen easiest via a picture.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me why my code get wrong answer at pretest 2?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me in figuring out on which test case my code for problem B failed on system test.

My code

Problem link

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't know dp but reading the comments I think I used a similar approach. I started counting stars from the last row if a star is present then +1 and if there is star just below it and there is a number on both sides below the current position I add the minimum. My solution: 100953260

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution of problem C Random Events??

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • Find the first index after which the array is sorted already. Ex- 3 2 1 4 5 . here the index is 3 (1-based indexing).
    • Now we know that any operation lesser than index won't be helpful in themselves Ex- 1 0.8 , 2 1 , 1 0.5 etc
    • So, we will consider only those operation where ri >=index. Ex- 3 0.8 , 4 1 , 5 0.3 etc
    • Now suppose we have two operation that can sort the array in themselves without requiring any further operations. Let's name them R1 P1, R2 P2. Now, what will be the probability that one of them sorts the array? It's P1+P2-(P1*P2) Known as Compound Probability.
    • You just need to find all those operations and apply the above mentioned formula.
    Code
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in C, why do we only need to check for the last unsorted element?

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

Please tell me how to solve E if $$$x \le 10^{18}$$$? The problem is that when $$$y > x$$$ then the lowest point may or may not be able to form full cycle (modulo $$$x$$$), how to check this for big $$$x$$$

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
sol

Why does my solution in D with Segment Tree simulation fail in 3rd test?

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

.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2 1

    2 1

    2 0.958222

    Is where your code fails not the one you mentioned. Check again

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, I noticed it. Unfortunately no option to delete the comment now

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

My answer to B was way simpler than the editorial. I just did this 2D DP

if (!block[i][j]) continue;
dp[i][j]=bock[i][j]+min(dp[i+1][j],min(dp[i+1][j-1], dp[i+1][j+1]));
ans+=dp[i][j];

where block[i][j]==1 if (i,j)=='*' else 0 The complexity of this solution is O(NM) so it is the best complexity you can get.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B: Time limit exceeded on test 3 in author's decision.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what am I doing wrong in this approach to F

my code (just see the code in main)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone xplain the question A(string generation)??

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem: Given N and K. Generate a string of length N consisting of only 'a','b' and 'c' and the length of the longest palindromic substring(LPS) from the given string should be <=K. Ex aabc here length of LPS is 2 ("aa").

    Solution: As the length of LPS can be <=k. We can keep it 1 length as well. Now, How we can achieve that? obviously if we keep on repeting the pattern abcabcabcabcabc.... the LPS which we will get is of length 1 which is for <=k.

    long long N,K;
    cin>>N>>K;
    for(long long i=0;i<N;i++) cout<<(char)('a'+i%3);
    
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      string ans = "";
      for(int i = 0; i < N; ++i)
         ans += ((char)('a' + i%3));
      cout << ans << endl;
      

      why is it wrong,i'm so confused.... is there something about "std::string"????

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank u for the explanation..u xplained it very well

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to print a string of length 'n' only having {a,b,c} in it such that the number of palindrome in the string printed is less than or equal to 'k'. Now the easiest way to do that is to keep printing {a,b,c} (in the same order) unless the length of the printed string is 'n'. Using 'k' is meaning less coz no matter what is the value of 'k' the answer is always correct as its stated we may print {a,b,c} in any order. Eg. n=1 k=1 answer is "a" n=3 k=1 answer is "abc" n=7 k=3 answer is "abcabca" The answer is always "abc"s string of length 'n'

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1461/submission/100931552 Isn't this a simpler approach to B? Also I think it has O(n*m) complexity too.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, your solution is much easier to understand, but could you please explain what algorithm or what the logic behind it is?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I observed that all the smaller spruces combine to form a bigger spruce . So in order to have a height h spruce the bottom 3 element must have all at min. h-1 spruce.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not able to find why my solution is not working in problem B. Anyone can please help me to find what is wrong in my solution https://codeforces.com/contest/1461/submission/100955454 .

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of problem E , for y>x , how to justify that doing "we will lower the water level as many times as we can, and then raise the level" will be optimal ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because when you are not able to decrease any more, you can always save yourself with only one y and proceed, therefore there is no reason that you put water in other than that case.

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

      I found more concrete proof . For simplification consider $$$l = 0$$$.

      Suppose water level is at $$$p$$$ and $$$p<x$$$ i.e water level will go below 0 on that day .suppose $$$y+p>r$$$ then we cannot add water in morning. Thus $$$x+y>r$$$ , hence if we would have added extra water sometime before even when level was $$$p_1⩾x$$$ then $$$p_1+y>r$$$ and thus not possible to add. Hence we should lower the water as much as we can.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but I found cases where we could add y and use x everyday and it would be possible and still be in range. But if we follow this algorithm it says no. case is k=999984 le=1 r=1999966 t=999984 x=999983 y=999984 After first day we will have k=1 and after that we will just add y and use x and it is possible to remain in range. then why is your code optimal ?Because this case has a possible case but says wrong!

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

        Thanks a lot, that's a nice proof! rananjay23

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

        Proof for Case 3 when $$$x<y$$$:
        Let's say we are on $$$k \mod x = x_1$$$, and we have $$$m$$$ remaining days that we can go but instead we increase by $$$y$$$ (we assume that it is possible without exceeding $$$r$$$). So, we have two cases, first when we utilize current $$$k$$$ fully i.e. we decrease until we reach $$$x_1$$$, second when we increase it by $$$y$$$ now. Here $$$k+y \mod x = x_2$$$.
        $$$ans_1 = \dfrac{k-x_1}{x} + \dfrac{x_1 + y - x_2}{x}$$$, where $$$(k-x_1) \mod x = 0$$$ and $$$(x_1 + y - x_2) \mod x = 0$$$.
        $$$ans_2 = \dfrac{k+y-x_2}{x}$$$, where $$$(k+y-x_2) \mod x =0$$$.
        Now, we can see that $$$ans_1=ans_2$$$. So it doesn't matter if we increase by $$$y$$$ now or later. Hence our algorithm is correct.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how the time complexity for the author's solution for problem D does not get Time Limit Exceeded??

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, why do we make ans = 0.0, when last correct position is -1?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what's wrong with my code problem A i'm so confused......

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You cout ' ' and I think system checks with getline so you get wa if you cout without ' ' you will get ac

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you so much!!!! -,- i forget my costom "#define", thank you!!!

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey guys, so I made this screencast and solutions from A-D, hope you find it useful and am looking forward to honest feedback: https://www.youtube.com/watch?v=JsHC-GW8UVc

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So i had a terrible contest. (yet again!) My submission to C gets Wrong Answer on Test case 8 submission

However i can't see any flaw in my approach, guide me. I am maintaining a DP sort[i] if all elements till i are sorted, not_sort[i] otherwise. My recursion is this: where mp[i] is the probability of sorting operation.

if(arr[i]==i)
    sort[i] = sort[i-1] + not_sort[i-1]*mp[i];
    not_sort[i] = 1 - sort[i];
else
    sort[i] = mp[i];
    not_sort[i] = 1-sort[i];
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting wrong answer on 10th test case of B. can any body explain the error. https://codeforces.com/contest/1461/submission/100931109

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

    This codeing style is hard to read.

    while(t+i<n&&j+1+t<=m&&j>=t&&a[i+t][j+1+t]-a[i+t][j-t]==2*t+1)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for replying! I am looping through each and every n*m cells assuming them as origin of the spruce (obviously if it exist). t denotes height of the a spruce having origin as i,j. so t=0 means assuming height as 0 initially. Explanation of conditions :

      condition 1 : a[i+t][j+1+t]-a[i+t][j-t]==2*t+1 this checks if all cells ranging from j-t to j+1+t ( in total 2*t+1) at level t w.r.t. i,j are all * . because my array is prefix sum on every row.

      condition 2 & 3 : remaining condition they just take care if my while loop is not cheking any cell which is not possible. as a[i+t][j+1+t] -> i+t can be max n and j+1+t can me atmost m.

      Hope you understand.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There should be a check in the while loop condition that $$$j-t>=0$$$, or is this somehow included in the other conditions?

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

i wasted a lot of time in B then implemented using dp approach.it was so simple with dp;

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know if my method to solve F. Mathematical Expression was smart or dumb. If we observe that it is beneficial to multiply if the product is greater that size of the array. After that we can simply use bitmasking to solve and the complexity would be linear with respect to n.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is fabulous question.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in PROBLEM:E: do we have to minimize the number of times we add y? because the solution says we will lower the level as many time as we can ,but why can't we add y as many times as we can.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C using dynamic programming??

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

    I genuinely want to know where do you see optimal substructure and overlapping subproblems?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The overlapping is that a spruce of hight h is made of 3 spruces of hight h-1 plus the top cell.

      The optimal substructe is that we can iterate the rows bottom up to check the hights of the 3 spruces just below the current cell.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question d we have neglect the another half array but in editorial they are taking sum of both arrays i.e l-mid and mid+1-r.Please some one explain

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They just pre-calculated all the possibilities and stored the sum, at each step you have 2 choices either choose array with elements <= (max+min)/2 value or the other one, here they just tried both at each step. It's not mentioned whether to choose left array or right one.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

While solving problem E during the contest , what was train of thought which brought you to the conclusion that when y>x we need to decrease water level as much we can and then raise the level ? Was it simply guessing and then proving or there was some steps of thoughts after which you arrived to that conclusion .

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain D,i didnt got what is in the editorial

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain Problem E i didn't get what editorial wants to say

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can simply prove that the height of this tree does not exceed log(max). Since max(currenta)−min(currenta) after each operation of the section is reduced at least twice. Can anyone explain ,meaning of above lines in D

``

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

So i don't know why but my F doesn't work. My solution is this[submission:101137585].So the idea is pretty much the same except for the last part.We can watch every 2 subsequences of array which have 0's in between them. So the solution for subsequence is next: first because 1's on the start and end of subsequence cant help with product but can with addition we know that they must have a '+' sign in between them. So lets watch now for subsequence that starts and ends with numbers that are not 0 or 1. There are 2 cases:if me multiply every number in this subsequence or to multiply every subsequence of this subsequence that consists of numbers greater than 1 and to add the 1's(there is no point in adding any numbers but 1's (because if x, y != 1 then x + y < x * y so it would always be more beneficial to just multiply)).Example: for this subsequence 2 2 1 1 1 2 if we multiply every number we would get 8 but if we multiply the first 2 then add that to the ones and then add the 2 at the end we would get 9 which, indeed, is the best solution. So we are basicly looking for max(product of all elements, number of 1's + sum of products of all subsequences which dont have 1's). So if you can help me i would really appriciate it.

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

why is my o(n^2*m) solution giving TLE. I have used a 2d hash table to compute prefix sums. For each row and for each element a[i] calculated the number of spruce trees that can be formed in O(n) . solution

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the time complexity of author's solution for the problem B?

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

101364791 can you plz tell me what's wrong with the function build I have made in this submission. this submission is of problem d divide and submmarize.. im not able to figure out the mistake in my code. plz help !!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1461/submission/101645633 my code is failing in corner test case please help

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1461/submission/101669810

submission's complexity similar to that of tutorial still getting Time Limit Exceeded. Please someone check my solution thanks in advanced

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

problem E:

can someone explain why the answer for example 8:

"999999999999999998 3 999999999999999999 399999999999999998 5 999999999999999996" is Yes?

from what I see : [l, r] = [3, 999999999999999999] ; x = 5 ; y = 999999999999999996 ; k = 999999999999999998 ;

start : ---------

days | k-start day | is k in [l, r]? | k-end day | is k in [l, r]?

day-0 | 999999999999999998 | yes | k=k-x: 999999999999999993 | yes

day-1 | k=k+y: 1999999999999999989 | no !! | — k is out of range so no need to continue. ****

end . ----------------

m I understanding something wrong? since the water level is not in the range [l,r] all the time for the t=399999999999999998 days the answer should be "No" no?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain F? Its too difficult to understand from the editorial.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Vladik Can you please tell why I need to handle the separate case of $$$y<=x$$$? means where/how the remainder method will fail.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E: water level input: 7 1 10000 4 2 1 answer: YES

was this test case considered by the jury?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you are doing since ages but then also what rubbish question you make ..

Please don't make any from now .. bull shit