Editorial for Codeforces Round #919 (Div. 2)

Information about the round

Solutions

1920A - Satisfying Constraints

1920B - Summation Game

1920C - Partitioning the Array

1920D - Array Repetition

1920E - Counting Binary Strings

1920F1 - Smooth Sailing (Easy Version)

1920F2 - Smooth Sailing (Hard Version)

• 2 months ago, # ^ | 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.

  • 2 months ago, # ^ | Thank!

• 2 months ago, # ^ | 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

• 2 months ago, # ^ | The sum of n over all tests does not exceed , and the maximum divisors a number less than or equal to can have is not more than (I think it is around or something). So in the end this is small enough to pass the problem.

• 2 months ago, # ^ | You can practically check that for all numbers not greater 200000, the number of divisors is actually , so the author solution would not take too much operations

  • 2 months ago, # ^ | ← Rev. 2 →   0 No, it's .

    • 2 months ago, # ^ | How can you prove this? Thank you in advance!

      • 2 months ago, # ^ | You can read details here: link

        • 2 months ago, # ^ | the link doesn't have a proof

          • 2 months ago, # ^ | Graph is a proof, lol. What proof do you want?

            • 2 months ago, # ^ | O(f(n)) has definition. You should prove that f(n) satisfy the definition.

              • 4 days ago, # ^ | 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)

              • 2 days ago, # ^ | 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.

              • 2 days ago, # ^ | 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...

              • 44 hours ago, # ^ | ← Rev. 3 →   0 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 is on pages 1 and 2 which is really really easy, but this statement is not the same as prime number theorem itself.

              • 14 hours ago, # ^ | 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.

              • 9 hours ago, # ^ | 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.

• 2 months ago, # ^ | it is about 200000*160=3.2*10^8 which can pass in 3 sec

• 2 months ago, # ^ | Absolutely Correct!!

• 2 months ago, # ^ | #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

• 2 months ago, # ^ | "no two constraints are the exact same." So there can't be more than one occurence of the same type with the same x

  • 2 months ago, # ^ | i misinterpreted in hurry..thanks

• 2 months ago, # ^ | 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

  • 2 months ago, # ^ | Oh, forgot about bound, yes that makes much more sense... I'm now even more ashamed of spending so much time on this problem

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

      • 2 months ago, # ^ | Thanks! I already knew that but apparently not well enough..

      • 2 months ago, # ^ | ← Rev. 2 →   0 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.

      • 2 months ago, # ^ | Okay, I'll bite. how cube root?

    • 2 months ago, # ^ | What is this 2 root(n) bound about , I am still confused

      • 2 months ago, # ^ | If then either or is (since ) so there are no more than divisors that are and no more than divisors that are

• 2 months ago, # ^ | 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 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).

• 2 months ago, # ^ | Felt the same way for B problem, was kinda of hard for me. Looks like a need some more practice.

• 2 months ago, # ^ | It gives me 2 when I run it

  • 2 months ago, # ^ | My bad. Sorry

• 2 months ago, # ^ | ← Rev. 3 →   +1 arsi[i-1]*(b+1)>=1000000000000000001 i think this can lead to overflow

  • 2 months ago, # ^ | So I added other constraints (ars[i-1]*(b+1)<ars[i-1]) too.. Can that also lead to overflow..?

    • 2 months ago, # ^ | 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]

    • 2 months ago, # ^ | 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!

      • 2 months ago, # ^ | 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: Solution is: I picked and python with its precision errors: >>> int((2**64)/20) 922337203685477632

• 2 months ago, # ^ | 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 )

  • 2 months ago, # ^ | Thanks, good to know! Actually, my solution did get hacked. Seems like the system tests were weak.

• 2 months ago, # ^ | I'm not able to observe. Could you please elaborate a bit more on why this works?

• 2 months ago, # ^ | 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.

• 2 months ago, # ^ | -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.

  • 2 months ago, # ^ | 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?

    • 2 months ago, # ^ | the other elements before it? it's a prefix sum. if you basically subtract a number you're subtracting everything before it as well

      • 2 months ago, # ^ | 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.

• 2 months ago, # ^ | Same, took me much time to realize that using a for loop is way better than a while ;-;

• 2 months ago, # ^ | I think you mean O(n*(2Sqrt(n))? if you're talking about the gcd.

  • 2 months ago, # ^ | 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.

    • 2 months ago, # ^ | 241481930 that's my submission, otherwise it's impossible to get accepted I think ;-;

      • 2 months ago, # ^ | No Worries :) Thank you for sharing your solution

    • 2 months ago, # ^ | Can you link one such solution which got accepted?

      • • 2 months ago, # ^ | damn I thought you were trolling lol, how did this get accepted jfl (he's an lgm tho)

          • 2 months ago, # ^ | I am also shocked b/w the time limit given was 3 seconds. I think it can get accepted due to that as well.

            • 2 months ago, # ^ | No that's at most 3e8 I think, turns out it was If(n%k==0) lol

        • 2 months ago, # ^ | There is a check if(n%k==0) inside the loop, so the complexity is the same as in the tutorial.

          • 2 months ago, # ^ | Damn fr ;-; so it's O(n*2Sqrt(n))?

            • 2 months ago, # ^ | Nice :) You are correct Now I observed this thing :) Thanks to you guys !!

        • 2 months ago, # ^ | ← Rev. 2 →   +13 This is not . The inner loop runs only if is a factor of , i.e. times, where is the number of factors of . The inner loop does iterations; each iteration calls gcd once which seems like it would be in total, but since we calculate gcd with the previous result, the total runtime is (check this). Since the above is done times, the time complexity is . For , is at most (this is reached for ; you can verify it yourself if you wish). This is fast enough.

        • 2 months ago, # ^ | there's the check part n%i

• 2 months ago, # ^ | 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.

• 2 months ago, # ^ | 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

  • 2 months ago, # ^ | y why does he multiply by 2?

    • 2 months ago, # ^ | 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.

• 2 months ago, # ^ | It is guaranteed that the sum of over all test cases does not exceed .

  • 2 months ago, # ^ | Oh got it thanks

1
100000
99997 99997 .... 99997 49998

• 2 months ago, # ^ | precompute divisors SMH

• 2 months ago, # ^ | it happens (I'm actually a noob)

• 2 months ago, # ^ | ← Rev. 2 →   0 n^1/3

• 2 months ago, # ^ | 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)

• 2 months ago, # ^ | yep you are right i also done this problem using __gcd. Thank You for sharing your idea

• 2 months ago, # ^ | ← Rev. 2 →   +11 If or , the gcd algorithm will be . Furthermore, when we do cumulative gcd of all the numbers, our current gcd can only decrease times (if it doesn't decrease, we have the case previously mentioned which is constant), which is why the check function runs in .

  • 2 months ago, # ^ | ← Rev. 3 →   0 Thanks for the reply Problems were good hope to see more contests from you in future

• 2 months ago, # ^ | ← Rev. 2 →   0 Complexity analysis

  • 2 months ago, # ^ | Thanks For the analysis <3

• 2 months ago, # ^ | My parallel binary search solution just uses a regular DSU. You do 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.

  • 2 months ago, # ^ | That makes sense. Thanks very much.

• 2 months ago, # ^ | 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

  • 2 months ago, # ^ | thanks alot!

• 2 months ago, # ^ | [1,1,2,2,1,1,2,2] can't be split on any primes, but does split on k = 4.

• 2 months ago, # ^ | When we check some divisor , it will take time since we are taking cumulative gcd of numbers. The reason why the code does not take is because the number of divisors can have if is pretty small, around 160. So the actual time complexity is closer to .

• 2 months ago, # ^ | 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

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)

• 2 months ago, # ^ | Python 3 is too slow. Use PyPy3 to submit your code. Your accepted solution.

• 2 months ago, # ^ | Here is parity version: 241636798

• 2 months ago, # ^ | 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).

  • 2 months ago, # ^ | ← Rev. 2 →   0 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) ?

    • 2 months ago, # ^ | Long explanation

      • 2 months ago, # ^ | very helpful!

• 2 months ago, # ^ | 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.