Artyom123's blog

By Artyom123, history, 9 months ago, In English

1928A - Разрез прямоугольника

Solution
Code

1928B - Уравняй

Solution
Code

1928C - Урок физкультуры

Solution
Code

1928D - Подземелья Одинокой горы

Solution
Code

1928E - Модообразная последовательность

Solution
Code

1928F - Цифровые узоры

Solution
Code
  • Vote: I like it
  • +127
  • Vote: I do not like it

»
9 months ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it
  1. Why do the authors set $$$\sum c_i\le 2\cdot 10^5$$$ in problem D? There exists both $$$\mathcal O(n\log \max c_i)$$$ and $$$\mathcal O(n\sqrt{\max c_i})$$$ solutions.

  2. Why do the authors set $$$\sum s \le 2\cdot 10^5$$$ in problem E? A init function can precalc the dp array. And the limit for $$$\sum s$$$ made it hard to hack brute-force solutions, for example, just simply do dfs. And the tests are quite weak that some dfs solutions passed the ST. Most of them can be uphacked with the test:

1
673 0 1 200000

However, we can't hack 245835914 with the test above, can anyone help to hack it? :)

Anyway, I found most of the problemset nice. Kudos to the authors & coordinator!

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it +32 Vote: I do not like it
    1. Because the $$$O(n \log {\max c_i})$$$ solution with binary search is hard to prove. This works, but we didn't expect contestants to prove it during contest.
    2. I agree, maybe removing $$$\sum s \leq 2 \cdot 10^5$$$ would have been better.

    Anyway, the difficulty of problems D and E as they are seems adequate for their position.

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

      is the link you provided correct? is seems to be a diffrent problem. is the problem simular to problem d?

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

        Yes, the formula used in that problem is the same up to rescaling.

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

      I think nobody proved, frankly it was incredibly intuitive for me.

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

        not to me sadly :( can you explain how you thought of it? I guessed it was convex of course, but i couldn't feel that with my heart.

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

          Me too, but then I wrote linear search and I looked every k, it seemed it was convex. I tried and it worked.

          Also, you can see my first linear search submission which gets TLE.

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

            did u solve as indicated in tutorial and got tle?

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

        Bruh ur rating chart is kinda unique tho :)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. Isn't that precisely the issue? When you set a problem with a correct solution that is easy to come up with and hard to prove you are rewarding the people who implemented without proving it. Which probably shouldn't be the case?
      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Is it even possible to prevent solving problem without proving? besides, there is time penalty for WA verdict. especially in cp, almost no one tries to prove the logic. I think it's the contestant's job to keep the balance between intuition(for time) and proof(to reduce risk of WA, stupid impl) while competing

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

      Perhaps it's difficult to definitively prove it, but it's quite intuitive. One increasing function is how much the power increases, another is how much it decreases, added together they make a convex function.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 4   Vote: I like it +4 Vote: I do not like it
      1. Nope. We can prove the ternary search solution more easily. Suppose the number of squids is $$$x$$$. The contribution of each $$$c_i$$$ is a convex function of $$$x$$$. Since the sum of several convex functions is also convex, the statement is proved.

      Additionally, the $$$\sum c_i\le 2\cdot 10^5$$$ allowed a brute force to pass the problem — just by noticing that there are at most $$$\mathcal O(\sqrt{n})$$$ different $$$c_i$$$-s.

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

        Yes, but why is the contribution of each $$$c_i$$$ convex? The only proof we found is the one in the linked comment.

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

          I thought it was well known (I also missed the $$$\sum c_i$$$ constraint), for example, here goes:

          Let $$$f(k) = (c \% k)\left\lfloor\frac{c}{k}+1\right\rfloor^2 + (k - c \% k)\left\lfloor\frac{c}{k}\right\rfloor^2$$$ be the function that we want to prove being convex. If we replace $$$c\% k$$$ with $$$c - k\left\lfloor\frac{c}{k}\right\rfloor$$$, then we can consider this as a function not of positive integers, but of positive reals. I claim that this function is now piecewise linear, continuous, and convex.

          Indeed, if $$$k\in \left(\frac{c}{a+1}, \frac{c}{a}\right]$$$ for some nonnegative integer $$$a$$$, then $$$\lfloor c/k\rfloor = a$$$, and $$$f(k) = ka^2 + (c - ak)(2a + 1)$$$ is linear in $$$k$$$ on this half-interval with the slope $$$-a(a + 1)$$$. Therefore, if we prove that $$$f$$$ is continuous, then it's convex because the slopes are nondecreasing.

          To prove that it's continuous it suffices to check that $$$f(c/a - 0) = f(c/a + 0) = ac$$$ (exercise for the reader).

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

            I think in this problem $$$f(k)=\binom{c \bmod k}{2}\left\lfloor \frac{c}{k} + 1 \right\rfloor^2 + \binom{k - (c \bmod k)}{2}\left\lfloor \frac{c}{k} \right\rfloor^2 + (c \bmod k)(k - (c \bmod k))\left\lfloor \frac{c}{k} + 1 \right\rfloor \left\lfloor \frac{c}{k} \right\rfloor$$$, but I think your proof still works.

            And to prove the function is continuous, I think we should check if $$$\lim_{x \to (c/a)^+} f(x) = f(c/a)$$$.

            And thanks for the proof anyway, it was very enlightening.

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

              Your expression is how much each race contributes to something that we want to maximize. You can notice that if we split $$$c$$$ guys of a certain race into groups $$$c_1$$$, $$$\ldots$$$, $$$c_k$$$ (in our case they are almost equal), then your value is

              $$$\sum\limits_{i<j}c_ic_j = \frac{1}{2}\left(c^2 - \sum\limits_i c_i^2\right),$$$

              so I minimize (not maximize!) the sum of squares instead.

              About proving the function is continuous, in this case we should check $$$\lim\limits_{x\to c/a+0} f(x) = f(c / a)$$$, because we already know that the function is continuous from the left at $$$c/a$$$. However, for the same reason we can as well check $$$\lim\limits_{x\to c/a+0} f(x) = \lim\limits_{x\to c/a-0} f(x)$$$, which will in the end turn out to be the same, but here the function could as well be continuous from the right and this would still be the criteria.

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

                How to be you

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

    I only solved D, so I am replying to problem D only.

    I think it affects the difficulty of the problem significantly.

    I came up with an easy solution that depends on the array's maximum number of different elements, which is feasible due to this constraint.

    My idea is that the maximum number of different elements would be achieved by an array that looks like 1 2 3 4 5 .... n. which would sum to n*(n+1)/2. So using the summation constraint you can easily prove that the max number of different elements is about 700.

    Which makes trying each possible squad size for every element feasible.

    Here is a link to my solution, I hope it helps someone.

    https://codeforces.net/contest/1928/submission/245866373

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

    Can you share O(nsqrt(max ci)) solution ?

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

thanks for fast editorial

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

Great problems overall, but felt that statements were often convoluted and difficult to comprehend. Still, thanks for the great contest.

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

can anyone hack my solution?

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

    no, it is correct solution (hint: $$$f(k) - f(k-1) \geq f(k+1) - f(k)$$$)

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

Thanks for fast editorial! :)

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

bad F :(

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

    Peopls disliking bro's cmnt thinking that he is a newbie

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

      well aren't the people right?

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

        Tell me you are clown, without telling me you are clown.

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

Can we solve D by binary search?

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

    yes we can do that take minm squads as 1 and maximum can be max(c[i]) then we can easily see that value of our predicate function first increases and then decreases so it's like we have to find peak value in rotated sorted array which could be solved by binary or ternary search ,here is model solution using ternary search https://codeforces.net/contest/1928/submission/245874386 hope it helps

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

      Let's say that we have to calculate the max value of h(k)

      where h(k) = f(arr, k)-g(k)

      g(k) = (k-1)*x

      f(arr, k) is the total number of pairs after optimal distribution.

      I get that k will be in the range: [1, max(arr[i])] but cannot understand why h(k) will be a unimodal function. Can you prove?

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

        for each element i of the array (lets name it arr), when you increase the number of squads k, you are distributing the creatures more and more, which means that you are increasing the total number of pairs.

        On the other hand, when x is greater than 0, it keeps decreasing the score when k increases.

        So, you can see the score as a combination of an increasing function and a decreasing function.

        One last thing to observe is that when k increases, the increasing function will increase slower and slower. This is because, for every element i of arr, we cannot distribute the creatures in more than arr[i] squads. Meanwhile, the decreasing function is always constant.

        As a conclusion of this, the total score function will either be always decreasing (when the decreasing function keeps decreasing faster than the increasing function even from k=1) or will increase then stop and start decreasing.

        I hope this helps you.

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

          While your statements don't imply that the function is unimodal, they still prove why ternary search works(f(x) = f(x + 1) is only possible for x where f(x) is maximum). Thanks a lot!

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

            could you precise why it doesn't imply that the function is unimodal? is there anything wrong? or is it because I didnt formulate my statements well?

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

              Unimodality requires precisely one 'x' for which the function monotonically increases and decreases before and after.

              Consider a case where increasing bins adds exactly k to the answer. (For example, take k = difference due to increasing the number of pairs for some x bins). In this case, f(x) = f(x + 1), which means f(x) is not unimodal.

              This wouldn't generally work for ternary search because if f(x) = f(x + 1) for some point other than maxima, we might remove the region of interest in the answer. However, since it only happens at maxima in the question(your statement proves this), we never remove the region of interest and ternary search works!

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

                Okay I get it.

                I personally used binary search to solve this problem and it worked fine. Why is everyone using ternary search tho?

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

          I understood it in a different way.

          h(k) = f(arr,k) + g(k)

          We know that f(arr,k) is a concave function. (it inc. and stays const., and never decreases)

          g(k) = (1-k)*x, which is a straight line (also a concave function).

          the sum of several concave functions is also a concave function.

          the sum of several convex functions is also a convex function.

          We can use ternary search on concave/convex functions to find max/min.

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

    It's an upside-down parabola. So ternary search.

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

is there any way to download the test case where answer is getting wrong ?

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

    one hack is to just output the test case which is causing problem

    For example: if test-case 3213 is causing problem

    cin>>t while (t--) if (t==total-3213) cout<<input<<endl;

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      signed main()
      {
      #ifndef ONLINE_JUDGE
          freopen("input1.txt", "r", stdin);
          freopen("output1.txt", "w", stdout);
      #endif
          fast_io;
          int t;
          cin >> t;
          while (t--)
          {
              if (t==total-3) cout<<input<<endl;
              solve();
      
          }
      #ifndef ONLINE_JUDGE
          cout << endl;
          cout << "Finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
      #endif
      }
      

      something like this? this solution (1928B — Equalize) getting WA on testcase 3

      (i have tried above written code bot it is giving error)

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

        You need to read input has well in the if case then output that input on stdout, also while printing on stdout, make sure there are no spaces, you can put some special character like ':', ',' as delimiter, otherwise CF judge will not show you what's after whitespace

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

          Can you please give me an example Actually I can't understand the syntax

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

            Suppose input is a string and your program fails at tc=3213 and there are 10000 test cases cin>>t; while (t--) { if (t==10000-3213) { string s; cin>>s; cout<<s; // when this is printed CF online judge will give wrong answer } }

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

              thanks brother hope this will help me a lot

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

Thanks for fast editorial ! I find my bad math for c question :(

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

Thank you for crushing my spirits

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

Problem C: "To consider the second case, it is necessary to proceed similarly with the number n+x−2"

How does it come (n+x-2) for the second case !

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

D using ternary search: solution

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

Problem B: the difference between the maximum and minimum does not exceed n−1 , can become equal.. Is any mathematical proof available to prove that all such sets can always be satisfied?

P.S. Thank you for the fast editorial

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

    We can add permutation of $$$1..n$$$.

    $$$max(1..n) - min(1..n)=n-1$$$ $$$\blacksquare$$$

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

thanks, it was a very good contest

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

Can someone help me look at problem B? I can't find my mistake 245895448

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

Artyom123 Code for problem B has two main functions, probably you could edit that. Thanks for the tutorial!

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

Please explain C. I have been trying it for like 2 hours and dont get it. The editorial is so unclear

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

    and yeah i HATE the code for it. Was it really necessary to write this way?

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

      The problem could be simplified to "count the number of distinct integers which divide n — x and n + x — 2".

      My submission: 245894639

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

        yeah thanks, gonna try it tomorrow

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

        Can u explain why are we checking if factor is greater than x * 2 — 2?

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

    I did it using periodicity of the function. You can see that the whole pattern $$$1,2,3,..,k,k-1,...,2$$$ starts repeating after $$$2k-2$$$ terms. So basically, the graph looks like:

     where $$$t$$$ axis denotes the person number $$$(1,2,..)$$$ and $$$y$$$ is the label assigned. So, now for this graph to have intersection with $$$y=x$$$ one condition will be: $$$k \ge x$$$. Now, we have two cases:

    $$$1.$$$ $$$x=n$$$ is in one of such "rising" lines. From this, we get an equation like: $$$x+p \cdot (2k-2) = n$$$, where $$$p \in \mathbb{Z}$$$, from here we simply get $$$(2k-2) | (n-x)$$$, now you can find all factors of $$$n-x$$$, and impose two conditions, first it should be even (as $$$2k-2$$$ is even), and second, that $$$k = (f+2)/2 \ge x$$$.

    $$$2.$$$ If $$$x=n$$$ in one of the "falling" lines, then you will get $$$2k-x + p \cdot (2k-2) = n$$$, which again can be manipulated as $$$(p+1) \cdot (2k-2) = n+x-2$$$ (not so trivial like the first case) $$$\implies (2k-2) | (n+x-2)$$$, then again you have to check for factors of $$$n+x-2$$$ and do the same thing as in case $$$1$$$ !

    I think I thought very mathematically but I guess the logic should be clear to you now!

    My submission: 245852020

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

      can you please explain how did you get this equations in brief.Please

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

        It's just applying definitions of a periodic function: $$$f(x)$$$ is periodic with periodicity $$$T$$$ if $$$f(x+n \cdot T) = f(x)$$$ for any $$$n \in \mathbb{Z}$$$.

        Now onto my solution: The $$$t$$$ axis is the person number and $$$y$$$ axis is the label assigned (I have shown a continuous graph, but actually it will have points). Now, according to the question we want $$$f(n) = x$$$, where $$$f(1) = 1,..., f(k) =k,...,f(2k-2) = 2, f(2k-1) = 1,..$$$ so you can see $$$f(t+(2k-2)) = f(t) \, \forall t \in \mathbb{N}$$$, so $$$2k-2$$$ is precisely the periodicity of the given function. Now, if I have $$$k < x$$$, then this can never have intersection with the line $$$y=x$$$, hence we need to have $$$k \ge x$$$. After this condition is imposed, if I look in the interval $$$[1,2k-2]$$$, I have two "principle" solutions namely, $$$t = x$$$ and $$$t = 2k-x$$$ (As it is symmetric about $$$t=k$$$). Thus, for the two cases we get two different set of solutions:

        1. $$$x + p \cdot (2k-2) = n$$$

        2. $$$2k-x + p \cdot (2k-2) = n$$$

        where $$$p \in \mathbb{Z}_{+}$$$

        Side note: $$$sinx$$$ is a periodic function, so the solution for the equation $$$sinx =1$$$ is in an infinite set {$$$\frac{\pi}{2} \pm n \cdot 2 \pi \, ; n \in \mathbb{Z}$$$}, where $$$2 \pi$$$ is the periodicity of $$$sinx$$$ and $$$\frac{\pi}{2}$$$ is a principle solution.

        I think, this is the greatest depth I can explain my solution in, if you are still not sure, I would recommend you to read about periodic functions.

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

      Those who might be confused why we need to check two conditions.

      1. 2k-2 is an even divisor you can't express any odd number by this expression.

      2. k=(f+2)/2≥x

      Assume, we have n = 100, x = 10 for k = 2: 1 2 1 2 1 2 ... for k = 3: 1 2 3 2 1 2 3 ... so on, can we get x number? No.

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

Can anyone please point out the error in my logic to find out the maximum length of the subarray? Even after doing multiple dry runs i am not able to figure out the logical error. 245902899

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

    On the line 26 of your solution,replace arr with v.

    It seems that you confuse arr with v

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

P.S. A solution in $$$O(q\sqrt(n))$$$ will not work due to a large constant. I tried very hard to rule it out :D.

My (n+m+q)(log(n)+log(m)) collaterally died :(

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

I had a question regarding problem D. Lets call the array containing count of races "cnt" and sort it. Lets say cnt[3]=3 and cnt[4]=6 in a given test case. Is it ever beneficial for us to select number of squads=4 or 5? What I want to know is that is it ever beneficial for us to choose number of squads!= some cnt[i].

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

Great solution for D!

Sadly I didn't solve it,I'm too bad:(

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

any one can help and explain how did they reach the solution of problem B not the solution but how did you reach to that solution?

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

    you need to add a permutation to an array, and you want to maximize the number of equal elements. Since all elements in a permutation are distinct, there is no need to keep duplicates in our intiial array.

    Now, suppose we have extracted all distinct elements from our initial array. if we take a look at two different elements at indexes i and j (1<=i,j<=n). if arr[i]<arr[j], we need to add a number x to arr[i] and another number y to arr[j] so that we obtain arr[i]+x=arr[j]+y. Thus, x-y=arr[j]-arr[i]. So, we need to add two numbers x and ythat have the same difference between them as between arr[i] and arr[j].

    Now, since we are adding a permutation to our initial array, we are not free to choose any x or y. x and y should be between 1 and n. This implies that x-y<=n-1. since s-=arr[j]-arr[i], then : arr[j]-arr[i]<=n-1.

    In conclusion, our task is to calculate the maximum number of distinct elements that have a difference less than or equal to n-1.

    Hope that you find this helpful.

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

In C why divisors of n+x-2

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

I will appreciate if someone could either prove or hack this greedy solution to E

https://codeforces.net/contest/1928/submission/245926933

See https://codeforces.net/blog/entry/125652?#comment-1115429 for an explanation of the greedy approach.

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

Two main functions in solution of B??

signed main() {
    int q = 1;
    cin >> q;
    while (q--)
        solve();
    return 0;
}


signed main() {
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

:(

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

Curious to know why there are couple of comments as "bug1" and "bug2" in the code solution of 1928C — Physical Education Lesson. Are there any flaws in the code implementation ?

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

245940869 my $$$q\sqrt n$$$ works (:

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

    Someday I will definitely learn how to cut off the $$$\sqrt n$$$ ones. The battle is lost, but the war is not over.

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

For the code solution to problem B, the code contains 2 instances of signed main() Just a minor typo though.

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

Another approach for Div2 D [ Note that this approach does not rely on the sum of $$$c_i$$$ being bounded by $$$2e5$$$ ]

Let's notice the formula for a particular $$$c_i$$$ if $$$k$$$ (number of squads) is fixed. If $$$q = c_i / k$$$ and $$$r = c_i \mod k$$$, then the number of extra pairs is $$$c_i(c_i - 1) / 2 - [(k-r)*q*(q-1)/2 + r*q*(q+1)/2]$$$ [Idea: Subtract the bad pairs from total number of pairs). We need to sum this up for all $$$i$$$ from $$$0..(n-1)$$$

The first term is easy, we can precalculate the sum and store it. Focus on the next two terms inside square bracket. Upon simplification: $$$k*q*(q-1)/2 + qr$$$. We have to sum this for each $$$i$$$.

Let's fix $$$k$$$ and all multiples of $$$k$$$ [This can be done easily]. Consider the multiple $$$mk$$$. For all values of $$$c_i$$$ in the range $$$[mk ... (m+1)k)$$$ the quotient is $$$m$$$ and the remainder is $$$c[i] - m*k$$$. We just have to sum them up by plugging in the formula above. The term $$$k*q*(q-1)/2$$$ is easy. It is constant. For $$$q*r$$$, we will need prefix sums of $$$c$$$. Locating the values of $$$c$$$ in the range can be done using binary search

Time complexity: $$$O(\max{c_i} \log (\max{c_i}) \log n)$$$. Iterating through the multiples and doing binary search to find the range of c.

Submission: https://codeforces.net/contest/1928/submission/245957808

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

What is the name of the category in which problems like D — > Lonely Mountain Dungeons lies? Can someone please share a list of problem of similar nature for practice?

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

.

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

P.S. A solution in $$$O(q\sqrt{n})$$$ will not work due to a large constant. I tried very hard to rule it out :D.

Sorry, I didn't know (I think it would be faster if didn't choose a random block size)

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

    Can you explain your solution? Could it be that there will be $$$O(q \sqrt[3]{n})$$$ real calculations here?

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

      As in the official solution, we have some (multiset $$$H$$$ of) horizontal blocks and some vertical blocks $$$V$$$. The answer is then

      $$$\displaystyle\sum_{s=1}^{\infty}\sum_{x\in H}\max(0, x - s + 1)\sum_{y\in V}\max(0, y - s + 1).$$$

      For each $$$s$$$, I maintain $$$h_s = \sum_{x\in H}\max(0, x - s + 1)$$$ and $$$v_s = \sum_{y\in V}\max(0, y - s + 1)$$$, as well as the $$$\sum h_iv_i$$$. Sometimes I have events of sort "one horizontal/vertical block of length $$$x$$$ appeared/disappeared". Each such event is equivalent to the query "for each $$$i$$$ from $$$1$$$ to $$$x$$$, add $$$sgn\cdot (x + 1 - i)$$$ to $$$h_i$$$/$$$v_i$$$", where $$$sgn = \pm 1$$$.

      So first I wanted to maintain it with segment tree, storing in each node the following: if the corresponding (horizontal/vertical) blocks on this segment are $$$a_0$$$, $$$\ldots$$$, $$$a_{l-1}$$$, then I store $$$\sum a_i$$$ and $$$\sum i\cdot a_i$$$, and also the dot product $$$\sum h_iv_i$$$. But then it occurred to me that pushing delayed operations is kinda nontrivial. That's why I split everything into blocks of $$$K$$$, and each event is now "add some arithmetic progression to about $$$n/K$$$ whole blocks, and also maybe on the prefix of another block". This can be done quite easily, if we remember for each block the current arithmetic progression to be added (and also what I wanted to store for the segment tree). So yes, this works in something like $$$O(q(n/K + K)) = O(q\sqrt{n})$$$, and I just set $$$K = 300$$$ and submitted. I think $$$K = 600$$$ or so would probably be better, idk.

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

Can anyone explain what is my mistake in task B? 245838570

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

    You skip too much possible left ends with k = i

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

      I don’t understand what you mean, can you give me some kind of test?

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

      Thank you!

      I realized my mistake!

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

I was looking at the code for problem C (physical education lesson). I think there's a mistake. while populating the unordered_set answer, it should be answer.insert((i + 2)/2).

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

    (i + 2)/2 and 1 + i / 2 are identical:

    $$$\displaystyle\frac{i + 2}{2}$$$

    $$$= \displaystyle\frac{i}{2} + \frac{2}{2}$$$

    $$$= \displaystyle\frac{i}{2} + 1$$$

    $$$= \displaystyle 1 + \frac{i}{2}$$$

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

      Why are we populating with 1+i/2 at the first place, could you please explain that ? Thank you

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

        we need to count the # of distinct k's we can get by using divisors that can be written in the form 2k — 2

        so rewrite 2k — 2 as 2(k-1), and now we know the divisor must be even.

        for each i that divides (n-x) or (n+x-2), make sure it's even

        if it is, then we know i can be written in the form 2(k-1)

        so i = 2(k-1)

        i / 2 = k-1

        k = i / 2 + 1

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

for question B

int l=a.size(); int d=n-1; int s=0,e=l-1;

while(s<=e){
    if(a[e]-a[s]<=d)break;
    int d1=a[s+1]-a[s];
    int d2=a[e]-a[e-1];
    if(d1>=d2)s++;
    else e--;


}
cout<<e-s+1<<endl;

in this code a is the sorted array of elements after removing repeated elements . why does this give wrong answer in test 3 . logic is to shorten the array from the side having greater difference between consecutive element to accomodate maximum elements within the difference range p.s. int here is long long int

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

in the problem tag in problem D: there is ternary search. How can we use it in Problem D??

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

Can anyone check my submission in problem D? I cannot demonstrate my solution clearly.

Thank you and have a good day!

My submission: 245993112

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

Can someone prove that the function for D is unimodal?

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

not even kidding , problem 3 was running correctly in contest just because of a single if condition (if divisor is less than x than its possible) , accepted after contest.

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

Does not the solution to the problem B yield n^2 complexity? Like, for the test case where n = 2x10E5 and a = [1, 2, 3, ... , 2x10E5].

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

    No, in your case the code

    while(a[i] - a[pnt] >= n) {
                pnt++;
            }
    

    will not run.

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

Problem C video Editorial : Youtube Video Link

If you are not able to understand the Editorial then you can refer to this video....I have explained the complete solution in Hindi

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

I wrote an in-depth, beginner-friendly solution for 1928A — Rectangle Cutting, complete with detailed explanations and diagrams: https://notes.yxy.ninja/cp/number_theory/(CodeForces)-Rectangle-Cutting. Hopefully someone finds it useful.

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Another solution to Problem B if you missed max — min observation

Here is a version of the binary search solution to Problem B, since nobody has written it in the comments even though binary search tag is present.

Basic intent: for a given $$$endpoint\;value$$$, our task is to look at how much we will have to add to each $$$a[i]$$$ to attain the endpoint value. That, is look at differences $$$(endpoint - a[i])$$$. Then, pickup up all unique and eligible differences, i.e differences in range $$$[1,n]$$$. This is the best possible answer for the chosen endpoint.

Issue: We don't know what the best/optimal endpoint that we should choose is.

Greediness: All $$$a[i]$$$'s bigger than a chosen endpoint are simply irrelevant since there is no way to decrement anything. Among all $$$a[i]$$$'s that are smaller than chosen endpoint, it makes sense(greedily) that we will always be adding lesser to the $$$a[i]$$$'s closer to the endpoint and more to the $$$a[i]$$$'s that are farther (or much smaller) than chosen endpoint. Thus chosen endpoints are always of the form $$$(a[i] + 1), \forall i$$$.

Resolution to Issue: If we can somehow reuse the differences we calculated for one chosen endpoint, then we can try out all endpoints while only adding a linear factor to our time complexity.

Combining Everything: Lets sort all $$$a[i]$$$. And, lets begin by considering the max element as the chosen endpoint, i.e $$$endpoint = (a[n] + 1)$$$. Evaluate and store all differences $$$(endpoint - a[i])$$$.

How to reuse differences evaluated: Purely mathematical. In our sorted array of $$$a[i]$$$'s, lets say we transition chosen endpoint from $$$(a[j] + 1)$$$ to $$$(a[k] + 1)$$$ for any $$$(j > k)$$$. Also, lets call $$$a[j] - a[k] = delta$$$.
Then, all differences are related as: $$$endpoint_j = (endpoint_k + delta)$$$.
Also, it follows that if the eligible range of differences that we can pickup are related as: $$$if\; eligible_j = [low,high], \;then\; eligible_k = [low+delta, high+delta]$$$. Thus, we can simply binary search with modified limits in the already calculated differences.

Code1: 246326560

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

nice contest

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

How to solve E using graphs?

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

I wrote an in-depth, beginner-friendly solution for 1928B — Equalize, complete with detailed explanations: https://notes.yxy.ninja/cp/greedy/(CodeForces)-Equalize. Hopefully someone finds it useful.

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

.