sum's blog

By sum, history, 11 months ago, In English

Information about the round

Rating predictions (inspired by BucketPotato's editorial)
Who did what

Solutions

1920A - Satisfying Constraints
Hint 1
Solution
Code
1920B - Summation Game
Hint 1
Hint 2
Solution
Code
1920C - Partitioning the Array
Hint 1
Hint 2
Solution
Code
1920D - Array Repetition
Hint 1
Hint 2
Solution
Code (iterating over second type operations)
Code (repeated binary searches)
1920E - Counting Binary Strings
Hint 1
Hint 2
Hint 3
Solution
Code
1920F1 - Smooth Sailing (Easy Version)
Hint 1
Hint 2
Solution
Code
1920F2 - Smooth Sailing (Hard Version)
Hint 1
Hint 2
Hint 3
Solution
Code (small to large)
Code (LCA queries)
  • Vote: I like it
  • +314
  • Vote: I do not like it

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

Good round. Had fun solving A, B, C. Kudos for fast editorial!

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

Thank you for the great contest, the DP recurrence for E was a bit trivial but OK for Div2E.

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

Thanks for the fast editorial!

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

Speed Forces!

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

Thanks all for the super fast editorial

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

light speed editorial

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

Problem C: why we take GCD of all value? we can take m=2 to check instead?

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

    It is possible that m=3 works while m=2 doesn't, for example [2, 3], [5, 6] are the same for m = 3 but not m = 2. So you have to use gcd to find the largest m that works.

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

was going to submit b part but time over..matter of seconds lol

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

Can someone explain to me why O((n+logn)*max divisors of n) is fast enough to pass the tests?

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

    upper bound fornumber of divisors is o(n ^ 1/3) then o(n + logn) * n ^ 1/3) which can be consdered o(n ^ 4/ 3) where the time limit is 3 seconds and n <= 1e5 thats fast enough

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

    The sum of n over all tests does not exceed $$$2 \cdot 10^5$$$, and the maximum divisors a number less than or equal to $$$2 \cdot 10^5$$$ can have is not more than $$$200$$$ (I think it is around $$$160$$$ or something). So in the end this is small enough to pass the problem.

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

    You can practically check that for all numbers $$$N$$$ not greater 200000, the number of divisors is actually $$$O(\sqrt[3]{N})$$$, so the author solution would not take too much operations

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

      No, it's $$$O(e^{\ln(\ln(n))^{1.8}})$$$.

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

        How can you prove this? Thank you in advance!

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

          You can read details here: link

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

            the link doesn't have a proof

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

              Graph is a proof, lol. What proof do you want?

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

                O(f(n)) has definition. You should prove that f(n) satisfy the definition.

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

                  may be this is proof by example, they tested it over large number, found the relation between number of devisors verses N, it roughly approximate to O(N^1/3)

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

                  There is no such thing as a proof by an example. There is only disproof by a counter example. I believe in the case above there is a proof, it's just not what is linked.

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

                  density of primes for given N is 1/log(N) , that relations is also found by only by plotting the graph and there is no exact proof for it...., and we use it very often,

                  so this relation is also same way found I think...

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

                  There is a proof. Several of them. Google "prime number theorem" for more details. "The elementary proof of the prime number theorem: an historical perspective" (by D. Goldfeld) has elementary proof that $$$\pi(n)$$$ is $$$O(\frac{n}{\log n})$$$ on pages 1 and 2 which is really really easy, but this statement is not the same as prime number theorem itself.

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

                  There's no sense of proofing it in the context of competitive programming. In every real case the precision of this approximation will be sufficient.

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

                  without proof it may be a lie. O() is fact, or not. You can't say it's O() if it's not, except if you ok with a lie. Regarding demands of proof: I didn't demand. I just wanted to stress out that the page doesn't have a proof. And claim that it has a proof is a lie.

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

    it is about 200000*160=3.2*10^8 which can pass in 3 sec

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

Thanks for fast tutorial.

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

Wow, Problem C and Problem D are pretty cool. Loved the questions. Thanks !!!!!!!!

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

Loved task B, Thanks for this high quality round.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            int n, k, x;
            cin >> n >> k >> x;
            vector<int> a(n);
            for (int i = 0; i < n; i++)
                cin >> a[i];
    
            sort(a.begin(), a.end());
    
            long long s = 0;
            for (auto it : a)
                s += it;
            if (k == x)
            {
                if (k == n)
                    cout << 0 << endl;
                else
                {
                    vector<int>b=a;
                    while (k != 0)
                    {
                        // k--;
                        // cout<<k<<endl;
                        b.pop_back();
                        k--;
                        // cout<<k<<endl;
                    }
                    reverse(b.begin(), b.end());
                    for (int i = 0; i < x; i++)
                        b[i] =b[i] * -1;
                    int s = 0;
                    // for(auto it:b) cout<<it<<" ";
                    // cout<<endl;
                    for (auto it : b)
                        s += it;
                    reverse(a.begin(),a.end());
                    for(int i=0;i<x;i++) a[i]=a[i]*-1;
                    int s1=0;
                    for(auto it:a) s1+=it;
                    cout << max(s1,s) << endl;
                }
            }
            else if (k < x)
            {
                while (k != 0)
                {
                    a.pop_back();
                    k--;
                }
                int s = 0;
                for (int i = 0; i < a.size(); i++)
                    s += a[i];
                cout << -s << endl;
            }
            else if(k>x)
            {
                vector<int>b=a;
                vector<int>c=a;
                reverse(b.begin(),b.end());
                reverse(c.begin(),c.end());
                vector<int>ans;
                // for(auto it:b) cout<<it<<" ";
                // cout<<endl;
                int i=0;
                // 3 3 3 7 15 32
                bool flg=false;
                while(i<k){
                    int s1=0,s2=0;
                    if(i+x>=n) {ans.push_back(0);break;}
                    for(int j=i;j<i+x;j++){
                        s1+=b[j];
                    }
                    for(int j=i+x;j<b.size();j++){
                        s2+=b[j];
                    }
                    ans.push_back(s2-s1);
                    s1=0;s2=0;
                    i++;
                    
                }
                sort(ans.begin(),ans.end());
                // for(auto it:ans) cout<<it<<" ";
                // if(flg) cout<<0<<endl;
                // else 
                cout<<ans[ans.size()-1]<<endl;
    
                // int l=k;
                // while(l!=0)
    
                
            }
        }
        return 0;
    }
    
    

    Hi can u help me out in rectifying the error in this code

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

if there are more than one occurence of type 3 constraints with the same x,some solutions may be hacked!!

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

    "no two constraints are the exact same." So there can't be more than one occurence of the same type with the same x

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

Do you expect people to know that the number of divisors of $$$n$$$ is small in Div2C? It took me a while to realize that you can just check each divisor in $$$O(n)$$$, I bet there were a lot of people who just submitted it without understanding why it works fast

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

    It's a pretty common idea in problems and well known enough

    I think most people at least know that the number of divisors is at most 2sqrt(n), and even if you use this extreme bound, O(n sqrt(n)) still passes under the constraints

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

      Oh, forgot about $$$2\sqrt{n}$$$ bound, yes that makes much more sense... I'm now even more ashamed of spending so much time on this problem

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

        For future reference, most of the time it's ok to assume max # of divisors is around N ^ (1/3)

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

          Thanks! I already knew that but apparently not well enough..

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

          You can get the exact bound by finding the number of divisors of the greatest highly composite number less than the constraint. You can find these numbers in this series on oeis https://oeis.org/A002182. These could also be useful when writing tests/hacks for problems.

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

          Okay, I'll bite. how cube root?

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

        What is this 2 root(n) bound about , I am still confused

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

          If $$$d | n$$$ then either $$$d$$$ or $$$\frac{n}{d}$$$ is $$$\leqslant \sqrt{n}$$$ (since $$$d \times \frac{n}{d} = n$$$) so there are no more than $$$\sqrt{n}$$$ divisors that are $$$\leqslant \sqrt{n}$$$ and no more than $$$\sqrt{n}$$$ divisors that are $$$> \sqrt{n}$$$

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

This was my FIRST Contest ever , I only managed to solve problem A , I tried solving B but could not figure out how would alice calculate which element to remove and which to not? At the end i got frustrated and left.

Honestly I loved the experience.

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

Who can explain the Kruskal tree method of problem F2, I thought of it for a long time but I don't know how to maintain.

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

    The KRT is a way to solve the subproblem in the editorial where you want to find the largest minimum edge on a path from (x, y, 0) to (x, y, 1). The graph you build on the $$$2nm$$$ nodes is exactly the same (each cell should have two nodes corresponding to the number of times you cross the ray). Then you will run Kruskal's MST algorithm before performing any queries and make a KRT as normal, and the queries will then be the LCA on the KRT between nodes (x, y, 0) and (x, y, 1).

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

Why does this not work for B? Am I stupid or is this not n log n? Sorry if it's unreadable did the prefix sum backwards.

def solve(k,x,nums):
    nums = sorted(nums, reverse=True)
    s = sum(nums)
    pref = [s]
    for num in nums:
        s -= num
        pref.append(s)
    biggest = func(x,0,pref)
    for i in range(1,k+1):
        curr = func(x,i,pref)
        if curr > biggest:
            biggest = curr
    return biggest

def func(x,i,pref):
    x = min(x + i, len(pref)-1)
    return pref[x] &mdash; (pref[i] &mdash; pref[x])
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial and a wonderful contest!

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

Damn thought about gcd in C but could not get it. I need to work on my Maths skills lol. Problem B was good.

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

Explain please, why everyone thinks A, B, C were good? I admit D was nice, though too hard for me. C was unnecessarily hard after incredibly stupid A and a little over-time-consuming B.

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

    Felt the same way for B problem, was kinda of hard for me. Looks like a need some more practice.

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

In problem C, for the 3rd sample test case (5 11111), the answer given is 2. But the tutorial code gives answer as 1.

We can make a single group of size 5 which will be counted as 1 point. Also we can groups of size 1 and take m as 2, which will also be counted as 1 point.

So,answer should be 2 points. Hence, I think tutorial code is wrong

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

    arsi[i-1]*(b+1)>=1000000000000000001 i think this can lead to overflow

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

      So I added other constraints (ars[i-1]*(b+1)<ars[i-1]) too.. Can that also lead to overflow..?

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

        I think ars[i-1]<=1e18/(b+1) is better than ars[i-1]*(b+1)<ars[i-1] .When you calculate ars[i-1]*(b+1) then it already overflow at some cases and it is possible that ars[i-1]*(b+1)>=ars[i-1]

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

        Yes, it may in some cases like in my submission: 241476717. you better use 1e18/(b+1) >= ars[i-1]. I still don't know why ars[i-1]*(b+1) < ars[i-1] can overflow, any explanation is appreciated!

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

          Try to run this code:

          long long a = 922337203685477632;
          cout << (a * 21);
          

          It overflows, a < 1e18 and result > a. Basic way to find out a similar to this is to solve: $$$x \cdot k = (2^{64}) + x$$$ Solution is: $$$\frac{(2^{64})}{k-1}$$$ I picked $$$k=21$$$ and python with its precision errors:

          >>> int((2**64)/20)
          922337203685477632
          
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Fast Editorials :)

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

Here's an alternate solution to problem C without GCD. Observe that if we need to pick some m such that a set of numbers are all congruent to each other modulo m, m is at most as large as the second smallest element in the set. The bound on m is small enough to bruteforce all k and all m and it somehow works.

Code: 241481077

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

    Excuse me but somehow your submission may TLE when the input is like :

    1
    200000
    30030 30030 30030 ... 30030 1
    

    (I wont submit since it's the same as the hack input for #241489844 )

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

      Thanks, good to know! Actually, my solution did get hacked. Seems like the system tests were weak.

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

    I'm not able to observe. Could you please elaborate a bit more on why this works?

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

    Someone send me this solution link in my live stream solution discussion.
    I hacked it live there :)
    The hack part starts at 1:01:16

    Since, you are iterating on all nos until upper, I chose thing = 2*p and upper = p, where p is a prime.

»
10 months ago, # |
Rev. 5   Vote: I like it -26 Vote: I do not like it

A[n] — 2*A[min(i+x,n)] + A[i] is the Subarray sum. That saves time from O(n^2) to O(n).Prefix sum concept is used.

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

    -2* is because the sum added it already so he needs to subtract it once to get it normal (like without being added to the whole number) without the Bob things, and another time so it gets *-1.

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

      Yes! first X elements are removed from A[n] and bob decrease the sum by negatively adding those x elements again in the sum. But, why does A[i] added again?

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

        the other elements before it? it's a prefix sum. if you basically subtract a number you're subtracting everything before it as well

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

          now I got it. Thank you. i removed elements are not considered to be negatively added again.basically,right x elements of removed elements is bob's negative contribution. Now, I understand it.

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

I had the idea for B but my implementation was just terrible

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

    Same, took me much time to realize that using a for loop is way better than a while ;-;

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

was WA on pretest 3 on D meant to catch any known error or just a random case? ;( not able to find my mistake

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

Alternate Solution to problem C.
For a given divisor of N, its sufficient enough to check if there exists any prime which satisfies the given conditions ( Not so hard to prove why it is so ) . Since there are not many primes under 2.1e5 the solution easily passes for the given constraints . Submission 241489844. Edit: Lmao TL hacked

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

I have a question how problem C O(n2) solution is being getting accepted ?

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

    I think you mean O(n*(2Sqrt(n))? if you're talking about the gcd.

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

      No, I have seen many solutions which are O(n2) as well. They are getting accepted. How ? They are directly running for loop for findings divisors as well.

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

        241481930 that's my submission, otherwise it's impossible to get accepted I think ;-;

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

        Can you link one such $$$O(n^2)$$$ solution which got accepted?

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

            damn I thought you were trolling lol, how did this get accepted jfl (he's an lgm tho)

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

              I am also shocked b/w the time limit given was 3 seconds. I think it can get accepted due to that as well.

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

                No that's at most 3e8 I think, turns out it was If(n%k==0) lol

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

            There is a check if(n%k==0) inside the loop, so the complexity is the same as in the tutorial.

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

              Damn fr ;-; so it's O(n*2Sqrt(n))?

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

                Nice :) You are correct Now I observed this thing :) Thanks to you guys !!

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

            This is not $$$\Theta(n^2)$$$.

            The inner loop runs only if $$$k$$$ is a factor of $$$n$$$, i.e. $$$d(n)$$$ times, where $$$d(n)$$$ is the number of factors of $$$n$$$.

            The inner loop does $$$n-k \in O(n)$$$ iterations; each iteration calls gcd once which seems like it would be $$$n \log \max a$$$ in total, but since we calculate gcd with the previous result, the total runtime is $$$n + \log \max a$$$ (check this).

            Since the above is done $$$d(n)$$$ times, the time complexity is $$$O((n + \log \max a) d(n))$$$. For $$$n \le 2\cdot 10^5$$$, $$$d(n)$$$ is at most $$$160$$$ (this is reached for $$$n = 196560$$$; you can verify it yourself if you wish). This is fast enough.

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

            there's the check part n%i

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

can any one give me explanation of problem B?

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

    You need to find the maximum possible answer, after both alice and bob playing for one round, Alice, will try to remove K numbers at most to maximize the answer, and Bob will make X numbers negative to minimize the solution thus he'd choose the greatest numbers cause their negatives is the smallest.

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

I can't justify my D-time complexity. this is my D

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

https://codeforces.net/contest/1920/submission/241478736 what is wrong in this code for problem C?

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

can someone explain ans = max(ans, A[n] — 2 * A[min(i + x, n)] + A[i]); in part b?

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

    Since he added the sum, and wants to subtract it for bob part. he multiplied it by 2 so it subtracts not just not do anything... and he is getting the max, since Alice (Idk if I am saying the names flipped lol) wants to maximize the solution

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

      y why does he multiply by 2?

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

        Cuz he got the sum the first time Let's you have two numbers 1 and 2, if you want to multiply 2 by -1 after you takte the sum, the sum being 3. 3-2=1--> this is the first time you didn't multiply 2 by -1 you her just got back to the starting point 1-2 (multiplication by 2) = -1.

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

Here is an alternative solution for F1 (in practice: 241489058).

First, run a multi-source BFS from all volcanoes to determine the distance from every square to the nearest volcano.

Now, given a query, we run another kind of BFS from the given square. Let $$$d$$$ be the distance from this square to the nearest volcano. Instead of one queue, we maintain $$$d + 1$$$ queues: the squares reachable when the minimum distance to the volcanoes is $$$0, 1, 2, \ldots, d$$$. Initially, the $$$d$$$-th queue contains our starting square, and we process the queues in the order from highest to lowest.

The remaining issue is to detect when we made a turn around the island. For that, pick an arbitrary square of the island in advance. For each visited square, maintain a real value: how the polar angle changed when getting to that square. When the square was not yet visited, just record the current value. When we arrive at an already visited square: if the difference between the old and the new value is close to zero, do nothing; but if it is not (most probably close to $$$\pm 2 \pi$$$ then), we just found a round trip. What remains is to record the greatest possible distance from volcanoes when this happened.

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

Can someone please explain in problem B why nlogn is passing? Because number of testcases are 1e4 and n is 1e5 and k<=n so when k=1 and n=1e5 and t=1e4 will the nlogn solution will be accepted?

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

    It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

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

Am I the only one who found majority of the problems in this contest to be filler?

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

F2 can be solved in $$$O(nm\cdot\alpha(nm)+q)$$$ with offline LCA.

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

Hey,

I think the data for Problem C might have been a little weak. The following testcase:

1
100000
99997 99997 .... 99997 49998

Can hack solutions which use the heuristic that the GCD should be = 1 (if more than 1 then that GCD value itself works), and also that the only valid answer is 49999 (which is a large prime). Some solutions try all numbers from $$$2...10^5$$$ and that should usually be too slow, I think.

Thanks!

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

Thanks for the clear and short conditions!

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

I personally think C is harder than D. Maybe swap them is better?

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

I misunderstood E's "substring" as "subsequence" and wrote a wrong DP.Now feeling I'm a noob :(

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

Can someone kindly help with any simple test case for Problem D, for which my solution fails? Or, help me identify what mistake in my code (in Java — 241492905) ?

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

Negative time to editorial publish

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

For problem C: I Need some help to figure out what the complexity of this solution is: 241500814

It might be around O(N*log(N)) I guess, but I am not sure.

So, what I did is to first arrange all factors of n in a 2D vector (let's say V) s.t.

in any vector if the elements are like {a,b,c... x,y} then it holds that b%a=0, c%b=0.... y%x=0.

Once we have such arrays we can binary search on each of them to find out for how many of the factors in an array m>1 exists.

So if the size of this 2D vector is X, then the complexity would be something like: O(N*log(N)*X), but what will be the upper bound on X??

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

C was a bit standard, but great contest overall.. thank you.

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

Its not necessary to use prefix sum for problem B ryt?

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

This was a good round, but the only issue I had was that D had repeated occurrences of indices. I know it was never stated in the input that the indices had to be distinct, but I felt like it was obvious enough to assume haha. Well, at least I learned to be a lot more careful.

I do think that at least one of the examples should have featured repeated indices though.

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

    you cant expect samples to cover everything, and in this case, repeated indices isnt an edge case for 99.9% of solutions

    Today's contest had way stronger samples than usual (and imo way stronger than should be)

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

Please Anyone help me Find out Why my Solution is failing on some testcases! Problem D — My submission — 241508049

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

Please, someone, i beg you, tell me why this C++ solution fails Problem D test 3 241505744 . The same exact solution works in python. There were size issues in the beginning but i addresses them. Now I just don't know what it could be and i've been trying to fix this for over 3 hours. (the python was almost correct more than 3 hours ago, but after realizing the potential size of the accumulated array can be >>>>> 10**18, i made a small adjustment and it worked). But the c++ just won't and i'm just super frustrated... please :(

I'll just say briefly, there is a "recursive" class that holds the old array before multiplying (type 2 operation) by a factor, and it also holds the additions (type 1 operatoin) that happened since the last multiplication.

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

241515808 please tell why is it giving run time error

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

Excellent round. C is good and standard. However I stuck in the gap between C and D so the round go speedforces for me :(((((

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

1920B — Summation Game Follow this step. I think it will help to you : Input Handling , Sort, Calculating Initial Sum, Iterating to Maximize Sum and output here code -> https://ideone.com/kXKZYF

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

use GCD for c number problem

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

That was an amazing contest with some cool problems like C and E

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

Problem C was cool, I learned so much

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

Good round!

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

Can anyone explain why calculating gcd of series of numbers take n+logn and not nlogn time

Although i solved ABC but i wasn't aware of this

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

    If $$$gcd(a, b) = a$$$ or $$$gcd(a, b) = b$$$, the gcd algorithm will be $$$O(1)$$$. Furthermore, when we do cumulative gcd of all the numbers, our current gcd can only decrease $$$O(\log n)$$$ times (if it doesn't decrease, we have the case previously mentioned which is constant), which is why the check function runs in $$$O(n + \log n)$$$.

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

      Thanks for the reply

      Problems were good hope to see more contests from you in future

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

Problem C but with better time complexity. Haven't proved it mathematically but I think time complexity is n*log(n). Uses the fact that if 1, 2, 4, 8, ... are factors of 2^k == n than in worst case we need to check no more than 2^k + 2^(k-1) + 2^(k-2) ... which is 2*n numbers. And assuming gcds check are log(n) hence ig n*log(n). But math gets complicated when n is not pure power of any prime. So ig I will leave it for someone else.

https://codeforces.net/contest/1920/submission/241529452

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

Damn, I didn't see the constraints for 1920B - Summation Game and solved by considering negative numbers as well XD, submission.

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

First approach of problem D is really new learning to me. Thanks.

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

Can anyone explain what is wrong in this code for D 241534324

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

The editorial for F2 says that the time complexity of parallel binary search solution is $$$O((nm\cdot \alpha(nm)+q)\cdot (n+m))$$$. Here the $$$\alpha(nm)$$$ should from path compression in dsu, but I think we cannot use path compression since we need undo the operations, or can we?

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

    My parallel binary search solution just uses a regular DSU. You do $$$O( \log(n+m) )$$$ rounds of incrementally adding all potential edges between neighbours at the right times. At a certain point in this sweep you do one connectivity query for each of the queries, no need for undoing: 241434298 The only thing that does not quite achieve this time complexity is some sorting I call inside the parallel binary search, but it can of course easily be fixed.

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

Problem C

For people who didnt get why taking the gcd of difference of nos at all those positions works (found it a pretty cool idea):

Consider all the first nos from all partitions as:

a1, a2, a3, a4, .. , ak

Now if they have a difference which is multiple of a common number G, they can be written as: (say)

a1, a1+3G, a1-4G, a1+103G, .. , a1+7G

Now for m = G you get the same remainder for this sequence: a1%G

Now for the same no to appear at all such positions in all partitions, the required m will be the gcd of differences at all such positions.

I hope it makes sense now!

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

Can someone please explain the formula used in B solution in the editorial? I cannot wrap my head around it. Thanks in advance.

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

    Apparently goes like this. Let e be the element of the arr, r be the rest of the sum.

    To find the difference of sum. S = e+r S' = -e+r

    S'-S = (-e+r)-(e+r)= -2e

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

in problem c can someone tell that cant we just find all prime number lenghts(k) satsifying the condition (i.e m>=2) and then like we do in sieve find all the multiples of those lenghts and that will be the ans,TC of it will be n logn but idk why this approch 241560669 is failing

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

    [1,1,2,2,1,1,2,2] can't be split on any primes, but does split on k = 4.

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

https://codeforces.net/contest/1920/submission/241572267

Can someone explain why this solution of task D gets accepted on visual c++ 2017, and gets a time limit on g++20?

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

Hey! can someone please help me out with how to calculate the time complexity for Problem C. My doubt is why is not the code in the solution given not throw TLE, The code looks like a O(n^2) solution

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

    When we check some divisor $$$k$$$, it will take $$$O(n + \log n)$$$ time since we are taking cumulative gcd of $$$O(n)$$$ numbers. The reason why the code does not take $$$O(n^2)$$$ is because the number of divisors $$$x$$$ can have if $$$1 \leq x \leq 2\cdot10^5$$$ is pretty small, around 160. So the actual time complexity is closer to $$$O(n \cdot max divisors)$$$.

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

Had a doubt regarding problem D, would appreciate any help I could get for the same!

In the editorial I can see that they have used 2e18 as the upper limit, but since the max length index is 1e18, having (1e18+5) would work as well right?

I did something similar during the (virtual) contest, but initially gave 1e18+5 as the upper limit, which failed. then I gave 2e18+5 as the upper limit, and voila! it passed! Funny thing is that the test case it failed on didn't fail on my local with 1e18+5 limit!

Now I know that happens alot that a solution would fail on one IDE and pass on another, but I was unable to figure out why that happened in this case, any pointers would be highly appreciated!

Failed solution — https://codeforces.net/contest/1920/submission/241579138

Accepted solution — https://codeforces.net/contest/1920/submission/241583879

( PS : I know my both my solutions should have given TLE for a particular edge case, but I guess CF problem setters didn't think someone would be as stupid as me :P )

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

    1e18 will work for python, but cpp compiler cant precise the float value after big division(in my case), ex 1223333444333332.13 gives something like 12.23e14 or something, so the condition falls for that limit, so u have to take more bigger value

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

What's the time complexity in C?O(n*n)

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

can anyone help me with my approach for problem d ?
for op 2 I incremented x by x=(x-1)*(a+1)+1 (index of the next element) for op 1 I put the value in map map[x]=value and used lower bound to find the index in map and if not found then used while loop until found edit: solved it, didn't use the limit of 1e18 here is ac code 241701574

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

Can someone tell my why my Python code is getting a TLE for C. The logic seems identical to the C++ answer

from math import gcd
cases = int(input())

for _ in range(cases):
    n = int(input())
    nums = [int(x) for x in input().split()]

    ans = 0
    for k in range(1, n + 1):
        if n % k == 0:
            g = 0
            i = 0

            while i + k < n:
                g = gcd(g, abs(nums[i + k] - nums[i]))
                i += 1

            if g != 1:
                ans += 1

    print(ans)
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

https://codeforces.net/contest/1920/submission/241625518 Can anyone tell what is the problem with this submission? It is giving correct answer in my PC. But i guess while checking overflow there is a problem.

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

I have solution for 1920F2 - Smooth Sailing (Hard Version) in $$$O(nm\cdot\alpha(nm) + q)$$$.

Solution

Here is the code 241633554

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

How does the editorial for problem F2 account for a case like this?

https://imgur.com/a/W2gRkVa

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

    Round trip is a loop. We consider only loops. In vertical segment you have on pic, you would have to go up and down, or down and up, thus there is 3 intersections of round trip on the pic (if it's cycle).

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

      Thank you for your reply. I'm still confused about how there are 3 intersections to the right of the island — aren't we just counting how many blocks cross the dotted line? Additionally, how are we keeping track of if a component forms a round trip (or polygon) ?

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

in Problem C ,if m is gcd of m1,m2,... then all the divisor of m will also satisfy the condition of partitioning the array, then why we have only added 1 to our answer, we should add the count of divisor of m. If I am wrong please correct me?

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

    All the divisors of m also satisfy the condition, but that is only for a particular k. We add one point for each k for which there exists m >= 2.

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

I have another solution to F2 in $$$O(nm \cdot min(n, m))$$$ that doesn't use small to large or LCA.

My solution follows the editorial up to drawing the imaginary line. Then, I process all of the edges except those that cross the line in order of decreasing $$$d$$$.

After adding each edge, create a graph where the components in the DSU are nodes. For each edge that crosses the line, add an edge between the corresponding nodes. If there is a cycle of odd length in this graph, then that cycle and all nodes connected to it form a round trip (basically the same observation as in the editorial). We can now merge all of these nodes and make a note that this component is a round trip in the DSU.

If we choose our line correctly (either horizontally or vertically), this solution runs in $$$O(nm \cdot min(n, m))$$$. My code passes in 580 ms.

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

In D if solving by repeated binary search according to the editorial why is there dp[i]=((v+1)>2e18)? (ll)2e18: dp[i-1]*(v+1);

if i am doing dp[i]=dp[i-1]*(v+1) directly its giving wrong answer. can someone explain.

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

For B a more verbose sol. 242411746

Only reason "" pref[n] — 2 * pref[min(i+x,n)] + pref[i]"" works is because the prefix array starts with 0.

I hope someone finds it helpful. Because I got bricked reading that.

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

The LaTeX rendered like this, initially I thought it was something nobody bothered to fix.

Recently I found out that it is a Chrome issue — https://affinemess.quora.com/A-brief-PSA-about-reading-math-on-Quora

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

Can anybody the problem with my solution for Problem C ?

#include <bits/stdc++.h>
#define int long long
using namespace std;

set<int> fac(int n)
{
	set<int> ans;
	for(int i=1; i*i<=n; ++i)
	{
		if(n%i == 0)
		{
			if(n/i == i)
				ans.insert(i);
			else
				ans.insert({i,n/i});
		}
	}
	return ans;
}

void solve()
{
	int n; cin >> n;
	vector<int> arr(n);
	for(auto &x : arr)
		cin >> x;

	set<int> fct = fac(n);
	int ans = 0;

	for(auto &x : fct)
	{
		int cnt = 0;
		for(int i=0; i<n/x; ++i)
		{
			int val = 0;
			for(int j=0; j<x-1; ++j)
				val += abs(arr[((j+1)*(n/x))+i] - arr[(j*(n/x))+i]);
			cnt = __gcd(cnt,val);
		}

		ans += (cnt!=1);
	}

	cout << ans << "\n";
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int tc; cin >> tc;
	while(tc--)
		solve();
}
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why my code for problem D isn't working , it's working for small test cases but gives wrong answer for the 3rd example test case with big integers

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
long long find(long long idx,vector<ll> &b,vector<ll> &x,ll* sizes,int n){
   
    
    int val=(lower_bound(sizes+1,sizes+n+1,idx)) -sizes;
   
    if(b[val]==1) return x[val];
    else{
        // return find(idx%(sizes[val-1]),b,x,sizes,n);
        if(idx%sizes[val-1]){
            return find(idx%(sizes[val-1]),b,x,sizes,n);
        }
        else{
            return find(sizes[val-1],b,x,sizes,n);
        }
    }

}
void solve(){
    ll n,q;
    cin>>n>>q;
   
    vector<ll> b(n+1);
    vector<ll> x(n+1);
   // vector<ll> sizes(n+1);
   ll* sizes=new ll[n+1];

    sizes[0]=INT_MIN;
    sizes[1]=1;
    cin>>b[1]>>x[1];
    for(int i=2;i<=n;i++){
        cin>>b[i]>>x[i];
        if(b[i]==1) {
            if(sizes[i-1]+1>(ll)(2e18)){
                sizes[i]=sizes[i-1];
            }
            else{
                sizes[i]=sizes[i-1]+1;
            }
        }
        else{
            //sizes[i]=sizes[i-1]*(x[i]+1);
            if((x[i]+1)>=((ll)(2e18)/sizes[i-1])){
                sizes[i]=sizes[i-1];
            }
            else{
                sizes[i]=sizes[i-1]*(x[i]+1);
            }
        }
    }

    //cout<<"The final size is :  "<<sizes[n-1]<<endl;
    vector<ll> queries(q);
    for(int i=0;i<q;i++){
        cin>>queries[i];
    }
    cout<<"The answer is:-   ";
    for(int i=0;i<q;i++){
        int idx=queries[i];
        cout<<find(idx,b,x,sizes,n)<<" ";

    }
    cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was very intuitive. Loved the problem

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

why is time complexity of problem C { n+ log(n) }* max.diviosrs(n) and not n*log(n)*max.divisors(n) ?