TheScrasse's blog

By TheScrasse, history, 5 months ago, In English

1485A - Add and Divide

Author: TheScrasse
Preparation: MyK_00L

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232596

1485B - Replace and Keep Sorted

Author: TheScrasse
Preparation: Keewrem

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 107232462

1485C - Floor and Mod

Authors: isaf27, TheScrasse
Preparation: Keewrem

Hint 1
Hint 2
Solution

Official solution: 107232416

1485D - Multiples and Power Differences

Author: TheScrasse
Preparation: MyK_00L

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232359

1485E - Move and Swap

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232216

1485F - Copy or Prefix Sum

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232144

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

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

Love editorials with hints! Also a good but not great contest!!

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

Video editorial for C Floor and Mod: https://youtu.be/ap-q_wQn7BE Solution in O(sqrt(x)).

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

    please do videos in english fully.so that everyone can benefit

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

Can anyone explain the hint A problem to me

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

    The idea is to first increase b as much as you want then perform operation 1. The reason is :- Lets say you divide first and then increase b, our a will be floor(a/b) and b will be b+1. If we increase b first then finally a will be floor(a/(b+1)) and b will be b+1. You can similarly prove for more number of operations. So once you know that we have to increment b first, the question is by how much. You will see that if we start with b and increment b till it reaches b+k ( k steps ), you will now need to integer divide a by b+k until a != 0. Lets call the number of steps to do so to be 'l'. So total number of steps will be l+k. I observed that we dont need to go very far away as that would increase k by very much but l wont be affected that much. So I started with b and went until b+100 and took the minimum value of l+k for every b in this range. P.S : Sorry I dont know how to use mathematical symbols

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

      Sorry ,but i dont get,how do u know to increase b only to a 100????

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

        Its pure intuition,as you can see in the editorial, it turns out that we dont even need to increase above 30. To get b->b+k we need k steps and to get a->0 we need O(log(a)) steps where base is b+k, we can observe that as b+k increases, the function log(a) doesnt decrease very fast and thats why I thought we dont need to increase b by a lot as that would increase total number of steps more than what log(a) would decrease and the net effect would be that we would require more steps.

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

          I also didnt get how 30 comes...and how should I even realize that...:( Bad Problem

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

            I approached in this way: Let's not keep track of count of type2 operation before doing type1 operation.

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

            You cant understand solution --> bad problem.

            Amazing logic

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

              XD...was waiting for this comment to appear...no not understanding the editorial is not the reason to consider it a bad problem...

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

                OK, understand you :)

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

            If you will check for a=1,000,000,000 and b=2 the ans is 30 So,increasing b to b+30 is enough to check.

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

          we need almost 30 operations when it s 2 I agree. but how is it related to incrementing b by only 30 times and checking the minimum possibility scenario of each incremented b. why not more than 30 increments of b?

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

            Because if you use 30 steps for incrementing then you need one more step for dividing, making it totally 31 steps. Instead of that you could have.simply used 30 steps all in dividing, which would have brought a down to 0 already.

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

              Nice One this is what I was looking for Thanks Bro.

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

              Good explanation

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

              Thank you for this response — was mad confused but this was helpful :)

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

        We can rewrite the question as min(x-b+(ln(a)/(ln(x))) for all x>=b. Of course, there is some rounding off business, which we do at last. So consider this fnc, if we differentiate this function, we get 1-(ln(a)/x), so we get a minimum at x=ln(a), but it may be also possible that ln(a) is less than b, so if we take the worst possible ln(a) it won't cross ln(10^9), which comes around 25. So we can iterate x from b to ln(a)+5, and obtain a minimum value. Well, this analysis is rough. So b we can increase up to up to 25 or so, but the editorial gives a better limit.

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

          You differentiated it incorrectly:

          $$$d_x \frac{ln(a)}{\ln(x)} = - \frac{\ln(a)}{x \ln^2(x)}$$$

          Therefore after differentiation you must get the equation

          $$$1 - \frac{\ln(a)}{x \ln^2(x)} = 0$$$

          The upper limit for $$$a$$$ is $$$10^9$$$. Therefore we arrive to

          $$$x \ln^2(x) = 9 \ln(10)$$$

          The left part is strictly less than $$$0$$$ for $$$x \leqslant 6$$$ and it becomes positive for $$$x \geqslant 7$$$, where $$$x \in N$$$.

          As the minimum of $$$f(x) = x - b + \frac{\ln(a)}{\ln(x)}$$$ is somewhere between $$$6$$$ and $$$7$$$ we suffice with at most $$$6$$$ iterations provided that we start from $$$b = 1$$$ (ending up at $$$7$$$).

          Otherwise we need to iterate upwards only until $$$b >= 7$$$. So that if you start with $$$b = 10$$$ you do zero iterations!

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

      You can type $...$ to insert math, where "..." is latex math expression. Common examples:

      $a_{1} + a^{2}$ --> $$$a_{1} + a^{2}$$$

      $\frac{a}{b}$ --> $$$\frac{a}{b}$$$

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

    It wants to say that we should increment $$$b$$$ first as much we want and then do the divide operations . Because that way number of division operations would be less.

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

    Problem A can also be done with Ternary Search on total operations.

    But I can't formally prove that this function will have a global minima.

    Can somebody help ? Submission

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

Why solution of problem E's complexity is $$$O(n\log n)$$$?

upd:now it's ok

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

Good contest but I think first 4 problems were all heavily based on Maths (except B).Would have been great contest if atleast one was from another topic making problemset more balanced.

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

    B,C,D involved math but some ideas outside math was also required . Like binary search in C (not necessary though) , prefix sum in B , chess coloring in D. Also though i didn't read E,F they are tagged as DP and data structures.

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

Thanks for the interesting problems and the fast editorial!

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

Very nice problems. Every problem had something to offer at least till D(didn't see E and F). I wish I could upvote more for the nice editorial with hints. Looking forward to more contests from the authors.

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

I solved A but don't know why it worked , now i am reading editorial of A, lol

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

Thanks for fast editorial

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

I love math forces! Thanks for great editorials. This round is my favorite.

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

Can someone please tell why this code for problem C is giving TLE, inspite of O(sqrt(x)) solution? Code: 107231229

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

    Because in works in O(min(x, y) — sqrt(x, y)) >= O(sqrt(x, y))

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

    Is it O(sqrt(x))? Because I think you are iterating from sqrt(x) to x, which I think is O(x).

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

I see what you did there ;) oie-h-Rh1llj1l-GLh

Problem — Floor and Mod

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

The contest was really enjoyable! Thanks for the fast editorials!

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

was a good contest .. good work authors ...and editorial with hints is really a good idea :)

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

I used the same logic in div2A. Can someone please help me where I went wrong?

Link to submission: https://codeforces.com/contest/1485/submission/107217438

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

    I guess it's because double are devil. On case 5 test 3 your l should be 3 but its just à little bit less because of approximation your flag isn't activated, rewrite without double and log and it should work

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

      Thanks, got it. I never knew this happened with log. Could you explain why exactly does this happen?

      PS. It's so annoying to get WA for such a silly mistake, could've been a specialist for the first time mayb :( .

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

Why does first solution in F has complexity O(N^2*log N)? Don't we have O(N^2) elements in map in worst case (if almost all subsegments have different sums) and get complexity O(N^3*log N)?

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

    The possible different sums for each length are $$$O(n)$$$, because they only depend on the rightmost $$$i$$$ such that $$$b_i = \sum_{k=1}^{i} a_k$$$.

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

In the editorial of problem A, it is given that even if we check the value of b up to 6 it will work. can someone explain why ?

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

    Not a formal proof, but here's an intuitive way to explain it: log(1e9)/log(b+1)+1<log(1e9)/log(b)

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

      I did not understand how it proves that, can you explain it?

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

        The number of moves needed without increasing $$$b$$$, is $$$\frac{log(a)}{log(b)}$$$

        So, if $$$\frac{log(a)}{log(b+1)}+1>\frac{log(a)}{log(b)}$$$, it means it's not convenient to increase $$$b$$$.

        For all $$$a$$$ up to $$$10^9$$$, this is true for every $$$b >= 6$$$, so it is never convenient to increase $$$b$$$ if it is $$$>=6$$$

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

          Yes, I got it now. Thanks a lot!!

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

          For all $$$a$$$ up to $$$10^9$$$, this is true for every $$$b>=6$$$, so it is never convenient to increase $$$b$$$ if it is $$$>=6$$$

          We can say this only by verifying or there is some short way to get the above conclusion using the formula in your comment ?

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

            Yeah, you can solve for $$$b$$$ in that inequality. Also, that inequality is just $$$log_{b + 1}a + 1 < log_ba$$$.

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

              Ok, so i think we need to first put the value of $$$a$$$ and then solve for $$$b$$$ .But to justify for all $$$a<=1e9$$$ using this formula , we need to iterate for all values of $$$a$$$.

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

                If you can justify it for a particular $$$a$$$, then it holds true for any $$$a$$$.

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

    It's trivial to prove that the answer is <= 31 because you can solve it with +1 to make it 2 and divide it by 2 30 times. So test it up until 31 if that makes you happy.

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

      yes this one I understood, but I wanted to know why 6 is enough and how you come up with that

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

can anyone can expalin the solution of C problem ,k^2 <kb+k=a≤x Hence k<=sqrt(x), i think it shold be k<sqrt(x),

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

I understood the O(n^2logn) solution of problem F. But I don't get how to get rid of first layer of dp. Specifically in the editorial —

Let's try to get rid of the first layer of the dp. It turns out that the operations required are....

can anyone explain this ?

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

Here are video solutions to all problems, a challenge version of E, and a lesson on how to misread problems (of course, the last two things are totally unrelated)

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

An easier solution for A with dp if you don't know how to prove your greedy solution, here. Dp state is represented by $$$a$$$ & $$$b$$$. At every stage we have two choices:
1) divide $$$a$$$ by $$$b$$$.
2) increase $$$b$$$ by 1.
Now take the minimum of these two at every state. Also in this way we can see that $$$b$$$ can go till 1e9, but we can observe that $$$a$$$ will be zero if we divide it once with atmost 13 consecutive numbers in worst case. So we can stop if $$$b$$$ goes beyond.(for safety i put it 20 instead of 13 in code).

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

    Hey I Tried the sama way but used the array and my bad we cant declare array of size 1e9

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

I got WA in Problem A because I used a log() function :((

for (int i = b; i < b + 50; i++)
        ans = min(ans, floor(log(a) / log(i)) + i - b);

107195035

When values are for e.g. a = 18^7 and b = 18, log(a) / log (b) returns 6.9999999999994... something. Does anyone know a better way to use log() and floor() to bypass this issue?

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

    temp = (log(a) / log(i));

    while(pow(i,temp) <= a ) temp++;

    ans = min(ans, temp + i — b);

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

    floor(log(a)/log(b) + 1e-11) should work

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

what is greedy solution in problem A and how to prove the last statement in editorial :

If we notice that it is never convenient to increase $$$b$$$ over $$$6$$$, we can also achieve a solution with better complexity.

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

    $$$a = 10^9, b = 1$$$

    $$$2^{30} > a, steps = 31$$$
    $$$3^{19} > a, steps = 21$$$
    $$$4^{15} > a, steps = 18$$$
    $$$5^{13} > a, steps = 17$$$
    $$$6^{12} > a, steps = 17$$$
    $$$7^{11} > a, steps = 17$$$
    $$$8^{10} > a, steps = 17$$$
    $$$9^{10} > a, steps = 18$$$
    $$$10^{10} > a, steps = 19$$$

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

      thanks , example can help to visualize . How to prove it formally ? Like for every $$$a,b <= 1e9$$$ ?

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

        1). $$$a = 10^9$$$, $$$b \in [1, 10^9]$$$

        As you can see before, the distribution converges at $$$5$$$ and diverges from $$$9$$$ for $$$b = 1$$$ the same holds for any $$$b$$$ cuz the difference stays the same.

        2). $$$a \in [1, 10^9], b = 1$$$

        Likewise, $$$\exists x \mid log_2a + 1 > log_3a + 2 > \dots > log_xa + x - 1 < log_{x + 1}a + x < \dots$$$.

        And I can state the same from above, the distribution converges at $$$x$$$ and diverges from $$$x + 1$$$ for $$$b = 1$$$ the same holds for any $$$b$$$ cuz the difference stays the same.

        Thus, $$$6$$$ is the upper-bound for this problem since $$$a$$$ can be at most $$$10^9$$$.

        P.S. The upper-bound could vary accordingly to $$$a$$$.

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

For F the editorial definition is slightly different from what I thought. Define dp[i][j] as the number of ways of using i numbers and getting j = CURRENT_SUM — sum[1....i]. Under this definition, taking a[i] = b[i] makes the next j be the same as j so if we do nothing we already do the transition. For the other transition, we make j = a[i] — sum[1...i] so we take the total number of ways we have so far and exclude the number of ways such that the sum is the same in this transition or simply override dp[i][j] with the total number of ways in i-1 as the official solution does. In the end the code is equal but this way of thinking seems slightly cleaner (in my opinion)

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

Very nice problems!! Sad on missing out on Master due to FST in problem B :(

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

Hi, I think that I might have a better solution for problem div2A. 107216266 I can't say what the complexity of my submission is with total certainty but I think that maybe it is better than that of the proposed solution. Basically, I try all possible divisors in increasing order while keeping track of the previous answer. When it gets to the point where the current solution is worse than the previous one, then it stops the loop and returns the previous answer.

I don't have a formal mathematical proof to state why this works, but it does. It would be great if someone could explain what the complexity of my code is :)

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

    No. Your solution also does the same as it mentioned in the editorial but without fixing any upper-bound. In the editorial, they take 30 as upper-bound and at last they say 6 is quite enough.

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

    Your solution is pretty much the same as the official solution, the complexity is $$$O(log(n))$$$, but it can be done in $$$O(1)$$$ if you use the builtin log function (paying attention to floating point errors).

    The reason why in the editorial we say our complexity is $$$O(log^2(n))$$$ is because we did not prove that the number of increases needed is $$$O(1)$$$ (it's not, it's prob something like $$$O(log(log(n))$$$, 6 for these constrains, but if $$$b$$$ is greater than that, than you don't need to increase at all), for simplicity we just proved it is $$$O(log(n))$$$

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

    A quick proof of correctness is to note that the number of steps required is the pointwise floor of a convex function.

    $$$ f(x) = \lfloor g(x) \rfloor \text{, where } g(x) = x-b + 1 + \frac{\ln a}{\ln x} $$$
    $$$ g'(x) = 1 - \frac{\ln a}{x \cdot (\ln x)^2} $$$

    $$$g'$$$ is obviously increasing, so that $$$f(x)$$$ is non-increasing for $$$x \cdot (\ln x)^2 \leq \ln a$$$ and non-decreasing for $$$x \cdot (\ln x)^2 \leq \ln a$$$. This also means that the optimal value of $$$x$$$ is of order $$$\frac{\log a}{(\log \log a)^2}$$$.

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

Great Contest, 1st, 2nd, and 4th questions were purely math-based. They should include problems from other topics as well.

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

all you have to do in D

just get the lcm for the numbers from 1 to 16

and get for every number from the 1 to 16 the multiple to it and call it x and the different between the lcm and x have 4'th sqrt (yeaaaaaaaaah all that just in 1 minute brute force in your local pc)

color the grid as a chess board

replace the black cells by the LCM

and replace the white cells by the answer that you got from the brute force

do you need a proof?

ok i don't give a sh....

i am just upset because I did not try in D in the contest :(

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

    How do you write a brute force efficiently?

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

      all that will just to get the answer for every number and take it by your hands

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

        Nvm, I misunderstood. I thought that you got the idea by bruteforcing the entire solution.

        By the way, you don't even need to brute force values on white cells, you can just put $$$720720 + a_{i, j}^4$$$.

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

          yp, i was in brain lag

          edit: i was thinking that the next number is lcm * aij^4 instead of lcm + aij^4 :(

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

Great problems+fast editorial with hints are the best combo.

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

For C I have good solution it don't requires math just logical binary search. See think of the graph of quotients plotting on (b) axis. For calcuating the peak of quotients basic observation will be for random number x on b-axis having remainders [a>=(x+1)(x-1)]=>>(a=x^2-1) =>>a+1=x^2.This equation comes from X=(Y.r)+r is now x=(y+1)r. So min value of(sqrt(a+1),b). Cool I got peak ! This is digram.. Now iterate from right end using binary search locate the location where quotient is still the same. And subtract both the points multiplying by number of quotients. In this keep way iterating to peak ((sqrt(a+1),b).

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

Can anyone tell me why this code for E gets WA on test 3? I followed the (alternate) strategy given in the editorial.

submission

EDIT : very dumb error

Here is the corrected implementation of the editorial approach, if it helps.

Corrected code

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

I have a different explanation for problem F , though the final approach is almost the same.

At each point we have two choices :

1) Make $$$a[i] = b[i]$$$

2) Make $$$a[i] = b[i]-$$$(prefix_sum up to $$$i-1$$$ elements in a[]).

So answer could have been $$$2^n$$$ except when both choices gives the same array.

When both the choices give the same array , prefix_sum of $$$i-1$$$ elements should be 0. This way I got 2 tasks , (1) Find the number of distinct arrays for first i elements : dp1 , (2) Find the number of distinct arrays for first i elements having sum 0 : dp2.

Then we directly have, $$$ dp1_i = (2*dp1_{i-1}) - dp2_{i-1}$$$.

To calculate $$$dp2_i$$$, we have one more observation that, when we do operation of type (1), $$$b[i]$$$ adds to the previous prefix_sum and for type (2), prefix_sum becomes $$$b[i]$$$. This tells us that, prefix sum of i elements in a[] will be a subarray of b ending at i.

So $$$dp2_i$$$ considers the smallest subarray of b ending at $$$i-1$$$ and having sum 0 (This is a standard task using hashmap). Let's say $$$[x,i-1]$$$. Then we take a unique subarray of $$$x-1$$$ elements, do a type 2 operation for x and do type 1 operation for elements in range $$$(x+1,i-1)$$$. This gives $$$dp2_i = dp1_{x-1}$$$.

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

In problem C, I'm not getting how we're getting the no. of special pairs just by counting the possible no. of b, because can't there be different a's for a fixed b and a fixed k? If so, then how are they being considered in our answer?

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

    $$$a = kb + k$$$.

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

      Smh. Thanks!

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

      In EDITORIAL Therefore, for any fixed k>0, the number of special pairs (a≤x; b≤y) is max(0,min(y,x/k−1)−k). Why we have subtracted k from min(y,x/k−1) and taken maximum of both to count special pairs???

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

        Let's look at the four inequalities required for solving this question:

        1. b > k (derived in the editorial)

        2. 1 <= b <= y (given in the question)

        3. 1 <= k(b + 1) <= x (derived in the editorial)
          Modifying equation 3, we get

        4. 1/k — 1 <= b <= x/k — 1

        5. 1 <= k < b (derived in the editorial)

        (Why k != 0? If k = 0, then a = k*(b + 1) = 0 but a >= 1, so the minimum value of k is 1)

        Now from equation 1, we know that the minimum value of b is greater than k and from equation 2 we know that the upper limit of b is y.

        So we get the following inequality if we merge equation 1, 2 and 4

        k < b <= min(y, x/k — 1)

        Now we got an open interval at the lower limit and closed interval at the upper limit, so the number of elements in the interval is Upper Limit — Lower Limt = min(y, x/k — 1) — k.

        Now the value of k can exceed the value of min(y, x/k — 1) since 1 <= k <= sqrt(x) and in this case, we will get negative number of elements in our interval which is not possible. So if we get negative number of elements, in such cases it means we have 0 elements. That is why we must take max(0, upper limit — lower limit).

        Example: If y = 2, x = 36, k = 6

        min(2, 36/6 — 1) — 6 = min(2, 5) — 6 = 2 — 6 = —4.

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

          Great explanation ! thanks a lot

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

          .

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

            By Division algorithm,

            $$$a = b \cdot \lfloor \frac a b \rfloor + r$$$ where $$$0 \leq r < b$$$

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

            a mod b = k, that is, k is the remainder when we divide a by b.

            Now applying Euclid's Division Lemma we can write

            a = bq + k, where q = $$$\lfloor{\frac{a}{b}} \rfloor$$$ = a mod b = k (Given in question)

            Since k is the remainder, we 0 <= k < b by Euclid's Division Lemma or b > k.

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

              Lol, As soon as I commented, This lemma stricked my mind that 0 <= r < b, remainder can't be greater than b. But thanks both of you guys for replying.. :)

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

          Thank You so much bro!

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

          Nice explanation , i understood the solution , thanks

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

          By that logic we can use equations 2 and 4 to get :
          elements in the interval is Upper Limit — Lower Limit = min(y,x/k-1) — max(1/k-1,1)) that should work right ?

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

    you dont need to know pairs explicity you can even use binary search to find if a pair exists for a particular remainder that's how I approached. https://codeforces.com/contest/1485/submission/107235525

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

      why are u subtracting remainder at last ?? from editorial what i understood is b*k+k=a. so for each k we are finding the range. I was not able to get the last part why substracting the remainder? can derive the formula?

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

        because for any remainder r value of b will obviously be greater than r so I check using binarysearch what is the max value that satisfies the condition and range of values of b will be then from r+1 to max found

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

          thanks. one more doubt how did you know it will be sqrt(x) i came to know to by doing it in pen and paper.Is there any formula to know?
          For example(x,y)-> (10,9) or (12,9) max remainder will be 3 by taking out all max remainder from 1 to 9 I get to know it will be 3 ?? but by formula how?

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

            I think it's because

            a=k*(b+1)

            k<=b-1=> b>=k+1=> b+1>=k+2

            a<=x

            Therefore,

            x>=k*(k+2)

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

            its more like k*(b+1)<=x this implies k^2<=k*(b+1) as b is greater than k so this mean k^2<=x hence k goes till sqrt(x)

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

            I wasnt able to figure it out during the contest l so got TLE later it striked me xD anyways its better we learn something from every contest ratings will come eventually.

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

        To understand the solution more clearly, I suggest you to watch the explanation of neal on his twitch, I liked it.

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

When I was reading problem "A"(A was way too hard in comparison to normal div.2's) and "B", I thought is this really a div.2 contest...I thought I was doing div.1 problems :(

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

In problem B , can anayone explain me this line from editorial

If al<x<ar, and x≠ai for all i in [l,r], you can either replace the rightmost bi which is less than x, or the leftmost bi which is greater than x (and you get 2 k-similar arrays). There are (ar−al+1)−(r−l+1) such values of x.

Thanks

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

I tried to calculate $$$Dp_i$$$ from bottom to top in problem E, but got wa on test 3. It works like this:

bool cmp(int k,int b){return a[k]<a[b];}
...
sort(stage[i].begin(),stage[i].end(),cmp);
ll Max=-Inf;
rep(j,0,stage[i].size()-1){
    int k=stage[i][j];
    f[fa[k]]=max(f[k]-a[k]+maxx,f[k]+a[k]-minn);
    f[fa[k]]=max(f[fa[k]],a[k]+Max);
    Max=max(Max,f[k]-a[k]);
}
Max=-Inf;
per(j,stage[i].size()-1,0){
    int k=stage[i][j];
    f[fa[k]]=max(f[fa[k]],Max-a[k]);
    Max=max(Max,f[k]+a[k]);
}

Where $$$i$$$ is the depth. The nodes in $$$stage[i]$$$ has the same $$$dis$$$ which is $$$i$$$.

$$$minn$$$ is the minimum of $$$a_i$$$ at the same stage, $$$maxx$$$ is similar to $$$minn$$$.

Could anyone explain that why it is wrong? The submission : 107250435

Thanks!

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

In Problem C, in the final expression, max(0,min(y,x/k−1)−k), Why are we subtracting k from min(y, x/k-1). Can someone please explain?

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

    x/k gives a count of numbers which can be our b but we need a remainder equal to k, that's why we decrease it by 1 (think?), if it is greater than y, we can take any number up to y as our b, but wait.... we can't take any b which is less than or equal to our remainder, therefore we again subtract k from it.

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

Can anyone tell why this binary search solution for A failed?

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

    Are you sure that the f is a decreasing function ? I think that it is a first decreasing and then increasing function.

    Ternary Search works for this kind of functions in O(log(n)).

    Submission

    But I can't prove that f is is a unimodal function !

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

      I got it my solution is wrong because f is monotonic.

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

        You mean not monotonic ?

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

          No monotonic, i.e it is nondecreasing first then nonincreasing. If f(mid) = f(mid + 1) before the minima then I would get the wrong ans.

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

            It's not that your solution is wrong cuz f is monotonic but it's not unimodal.

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

            I think your definition of monotonic is wrong. Google this.

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

              Yes, it is monotonic before the minima and after the minima.

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

          That's ternary search, not binary search, because you're looking at the slopes of adjacent elements. I'm not sure how to formally prove that the function is unimodal, but it's pretty easy to see intuitively.

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

            Yep, but I split the search space into halves at each iteration. Also, the function is not unimodal.

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

              It's still called ternary search, even though you're splitting the search space in half. See cp-algorithms for more detail. That's actually how I code ternary search if I'm not working with doubles (I actually did this solution in contest, so you can check my submission). Binary search only works with monotonic functions, but ternary search works with any unimodal function.

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

                It is Binary Search. Yep, F is monotonic.

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

                  Wow did you just make a Master angry ?

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

                  No u.

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

                  That example, is different, as you're not really searching on a function. You can read about monotonicity on boolean functions (functions used in binary search) here. If f was monotonic, it would mean that looking at a single value, it would be possible to determine whether to go to the right or to the left. Ternary search can essentially be viewed as binary search on the slopes of the function, instead of the values itself. That's what differentiates them. If you look at the slopes of unimodal function, and define $$$g(x) = f(x)-f(x-1)$$$, you can see that some prefix of a unimodal function will have some sign, and the suffix will have the opposite sign, which makes $$$g(x)$$$ monotonic, but $$$f(x)$$$ unimodal.

                  Btw, a function is unimodal if it first increases, then decreases (or vice versa). See here for more details.

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

                  A common definition is as follows: a function f(x) is a unimodal function if for some value m, it is monotonically increasing for x ≤ m and monotonically decreasing for x ≥ m. In that case, the maximum value of f(x) is f(m) and there are no other local maxima.

                  Yeah, I said f is not unimodal since, you can see four local minima here.

                  Arguing if my approach is binary search or ternary search is self-contradictory. I should've mentioned it Divide and conquer in general.

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

                  Those local minima you mentioned are also the global minima, so it still satisfies unimodality (it's decreasing instead of strictly decreasing for that segment). Because they are in the same contiguous segment, I think general consensus is that they are still global minima. At this point, we're really arguing about if it's convention to call a function which is decreasing but not strictly decreasing monotonically decreasing, and I guess it doesn't really matter. In general for ternary search/binary search purposes, I would call it unimodal/monotonic because it's still possible to binary search/ternary search over the functions.

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

                  Those local minima you mentioned are also the global minima, so it still satisfies unimodality (it's decreasing instead of strictly decreasing for that segment).

                  Oh, I thought if f(x) a global extremum, then it should be unique in the range.

                  Thanks.

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

      Bad interpretation of unimodal.

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

    It might not converge at the minimum. Store the minimum at each iteration.

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

Round was amazing

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

Shouldnt k <= root(x) for problem C be k < root(x)? Since if k^2 = x implies b=k-1 which is less than k

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

please , can anyone tell how we can use DP and define recurrence relations for 1485A - Add and Divide i.e . ADD AND DIVIDE problem. As it is an optimisation problem i am trying to think in DP way so please tell

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

For problem A, it says "Notice how it is never better to increase b after dividing (⌊a/(b+1)⌋≤⌊a/b⌋)."
Can anyone explain?

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

    its simple to see, if we have a/b and then keeping 'a' constant if we increase the value of b then the ratio a/b will decrease. so as we want to decrease a/b as much as possible..its better to increase 'b' first and then do a/b.

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

I have a question: In problem C's editorial, once "b" and "k" is fixed, is the value of "a" determined and unique?

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

How to prove the complexity for the O(n^2logn)-algorithm for prob F?

Thanks

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

    $$$dp_i$$$ contains at most $$$1$$$ more entry than $$$dp_{i-1}$$$.

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

In problem 1485A - Add and Divide, BFS was fast and memory-efficient enough to get accepted.

107307717

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

Can someone explain problem B editorial when x is in-between al and ar, this exactly "There are (ar−al+1)−(r−l+1) such values of x."

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

    There are $$$a_r - a_l + 1$$$ integers between $$$a_l$$$ and $$$a_r$$$. Since $$$x \neq a_i$$$, you have to subtract the $$$r-l+1$$$ integers already in the array, in the range $$$[l, r]$$$.

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

Hello. I've been trying to get "accepted" on problem C in Python3 but I get TLE while implementing the solution suggested here.

Here is the link to my submission: 107347518

I googled a bit and it turns out that the time limits don't seem to be language-specific, i.e. the same algo implementation might be passing in C but not in Python. link: https://codeforces.com/blog/entry/45228

Is this the case? Are some problems not meant to be solved as long as you don't write in the language intended or is something wrong with the submission I posted?

Thanks

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

    Check the following update to your code.

    107361634

    The same update ran in PyPy 3.7 more than an order of magnitude faster than it did in Python 3.9.

    107361941

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

      Thanks for the update!

      Yep, the code passes now at 1965ms and we have whole 35ms to spare!

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

        Yes, the speed difference between the Python interpreter and the PyPy compiler in running the same code is obvious.

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

          I guess it's the space/time trade-off as pypy3 seems to use 2mb of extra space. But still worth it!

          Thanks for the info!

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

There is a O(N) solution for F. Note that this solution uses a map. The solution is as follows -
Let f[i] denote the number of hybrid arrays of length i. Let g[i] denote the number of hybrid arrays of length i and sum of the array is 0. Given that we have a[0], a[1], a[2] . . . a[i-1] we have two options for the ith position — 1) Place b[i] 2) Place b[i] — (a[0] + a[1] + a[2] + . . . . a[i-1]) Now there will be over-counting when b[i] = b[i] — (a[0] + a[1] + a[2] + . . . . a[i-1]), or a[0] + a[1] + a[2] + . . . . a[i-1] = 0. Thus f[i] = f[i-1]*2 — g[i-1].

Now how to find g[i]? Observations — 1) The sum of the hyprid array 'a' of length i will always be a suffix of array 'b' ending at i. 2) Let j <= i be the maximum index where sum(b[j] . . . b[i]) = 0. Then for the sum of array 'a' to be equal to sum(b[j] . . . b[i]) = 0, we need two things — 2.1) a[j] = b[j] — sum(a[0] . . .a[j-1]) 2.2) For all j < k <= i, a[k] = b[k]. The array a[0]. . . a[j-1] can be anything we dont care. From 1 and 2 we can say g[i] = f[j-1]. 'j' can be found for every 'i' by maintaining map of prefix sums. 107307490

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

    This is exactly the official solution, and it's $$$O(n\log n)$$$ because of the map.

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

Hello, can anybody explain me div2-C, I'm not able to understand how is k<=sqrt(x)...Thanks in advance :)

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

in problem C (floor and mod) max(0, min(0, x/k — 1) — k). Why do we subtract k from min(0, x/k — 1)?

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

Can someone please explain me why my submission are getting TLE? I already try to optimize it but didn't work.

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

I'm a bit confused with where the factor of 2 comes from in B. Does someone have an explanation for this? Specifically, why it's $$$2((a_r-a_l+1) - (r-l+1))$$$. Thanks!

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

    I think I just understood it. I'll comment it here just in case someone else had the same question:

    consider the array [1, 2, 4, 5] for k = 5. Let $$$x = 3$$$. This mean that we could either replace 2 or 4. Similarly, $$$\forall x$$$ such that $$$a_l < x < a_r$$$ and $$$x \not= a_i$$$, it is the case that there will be two options for us to choose.

    The expression $$$(a_r-a_l + 1 - (r-l+1))$$$ counts the number of such $$$x$$$s. We just have to multiply that by two since for each such $$$x$$$, there are two options.