Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### sum's blog

By sum, history, 8 months ago,

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

## Solutions

Hint 1
Solution
Code
Hint 1
Hint 2
Solution
Code
Hint 1
Hint 2
Solution
Code
##### 1920D - Array Repetition
Hint 1
Hint 2
Solution
Code (iterating over second type operations)
Code (repeated binary searches)
Hint 1
Hint 2
Hint 3
Solution
Code
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)
• +314

 » 6 months ago, # |   +3 Good round. Had fun solving A, B, C. Kudos for fast editorial!
 » 6 months ago, # |   +16 Thank you for the great contest, the DP recurrence for E was a bit trivial but OK for Div2E.
 » 6 months ago, # |   +1 Thanks for the fast editorial!
 » 6 months ago, # |   0 Speed Forces!
 » 6 months ago, # |   +5 Thanks all for the super fast editorial
 » 6 months ago, # |   0 light speed editorial
 » 6 months ago, # |   0 Problem C: why we take GCD of all value? we can take m=2 to check instead?
•  » » 6 months ago, # ^ |   +33 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.
•  » » » 6 months ago, # ^ |   +5 Thank!
 » 6 months ago, # |   0 was going to submit b part but time over..matter of seconds lol
 » 6 months ago, # |   +1 Can someone explain to me why O((n+logn)*max divisors of n) is fast enough to pass the tests?
•  » » 6 months ago, # ^ |   0 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
•  » » 6 months ago, # ^ |   +26 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.
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 No, it's $O(e^{\ln(\ln(n))^{1.8}})$.
•  » » » » 6 months ago, # ^ |   0 How can you prove this? Thank you in advance!
•  » » » » » 6 months ago, # ^ |   +3 You can read details here: link
•  » » » » » » 6 months ago, # ^ |   0 the link doesn't have a proof
•  » » » » » » » 6 months ago, # ^ |   0 Graph is a proof, lol. What proof do you want?
•  » » » » » » » » 6 months ago, # ^ |   0 O(f(n)) has definition. You should prove that f(n) satisfy the definition.
•  » » » » » » » » » 4 months ago, # ^ |   0 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)
•  » » » » » » » » » 4 months ago, # ^ |   0 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.
•  » » » » » » » » » 4 months ago, # ^ |   0 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...
•  » » » » » » » » » 4 months 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 $\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.
•  » » » » » » » » » 4 months ago, # ^ |   0 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.
•  » » » » » » » » » 4 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   0 it is about 200000*160=3.2*10^8 which can pass in 3 sec
 » 6 months ago, # |   +8 Thanks for fast tutorial.
 » 6 months ago, # |   +15 Wow, Problem C and Problem D are pretty cool. Loved the questions. Thanks !!!!!!!!
•  » » 6 months ago, # ^ |   +6 Absolutely Correct!!
 » 6 months ago, # |   0 Loved task B, Thanks for this high quality round.
•  » » 6 months ago, # ^ |   0 #include using namespace std; int main() { int t; cin >> t; while (t--) { int n, k, x; cin >> n >> k >> x; vector 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 { vectorb=a; while (k != 0) { // k--; // cout<x) { vectorb=a; vectorc=a; reverse(b.begin(),b.end()); reverse(c.begin(),c.end()); vectorans; // for(auto it:b) cout<=n) {ans.push_back(0);break;} for(int j=i;j
 » 6 months ago, # |   0 if there are more than one occurence of type 3 constraints with the same x,some solutions may be hacked!!
•  » » 6 months ago, # ^ |   +8 "no two constraints are the exact same." So there can't be more than one occurence of the same type with the same x
•  » » » 6 months ago, # ^ |   0 i misinterpreted in hurry..thanks
 » 6 months ago, # |   +2 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
•  » » 6 months ago, # ^ |   +69 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
•  » » » 6 months ago, # ^ |   +17 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
•  » » » » 6 months ago, # ^ |   +14 For future reference, most of the time it's ok to assume max # of divisors is around N ^ (1/3)
•  » » » » » 6 months ago, # ^ |   +3 Thanks! I already knew that but apparently not well enough..
•  » » » » » 6 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.
•  » » » » » 6 months ago, # ^ |   0 Okay, I'll bite. how cube root?
•  » » » » 6 months ago, # ^ |   0 What is this 2 root(n) bound about , I am still confused
•  » » » » » 6 months ago, # ^ |   +16 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}$
 » 6 months ago, # | ← Rev. 2 →   +31 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.
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   +15 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).
 » 6 months ago, # | ← Rev. 2 →   0 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] — (pref[i] — pref[x]) 
 » 6 months ago, # |   0 Thanks for the fast editorial and a wonderful contest!
 » 6 months ago, # |   0 Damn thought about gcd in C but could not get it. I need to work on my Maths skills lol. Problem B was good.
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 Felt the same way for B problem, was kinda of hard for me. Looks like a need some more practice.
 » 6 months ago, # | ← Rev. 4 →   0 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
•  » » 6 months ago, # ^ |   +8 It gives me 2 when I run it
•  » » » 6 months ago, # ^ |   0 My bad. Sorry
 » 6 months ago, # |   0
•  » » 6 months ago, # ^ | ← Rev. 3 →   +1 arsi[i-1]*(b+1)>=1000000000000000001 i think this can lead to overflow
•  » » » 6 months ago, # ^ |   0 So I added other constraints (ars[i-1]*(b+1)
•  » » » » 6 months ago, # ^ |   0 I think ars[i-1]<=1e18/(b+1) is better than ars[i-1]*(b+1)=ars[i-1]
•  » » » » 6 months ago, # ^ |   0 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!
•  » » » » » 6 months ago, # ^ |   +3 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 
 » 6 months ago, # |   +1 Fast Editorials :)
 » 6 months ago, # | ← Rev. 2 →   0 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
•  » » 6 months ago, # ^ |   +6 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 )
•  » » » 6 months ago, # ^ |   +3 Thanks, good to know! Actually, my solution did get hacked. Seems like the system tests were weak.
•  » » 6 months ago, # ^ |   0 I'm not able to observe. Could you please elaborate a bit more on why this works?
•  » » 6 months ago, # ^ |   +7 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.
 » 6 months ago, # | ← Rev. 5 →   -26 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.
•  » » 6 months ago, # ^ |   0 -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.
•  » » » 6 months ago, # ^ |   0 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?
•  » » » » 6 months ago, # ^ |   0 the other elements before it? it's a prefix sum. if you basically subtract a number you're subtracting everything before it as well
•  » » » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 I had the idea for B but my implementation was just terrible
•  » » 6 months ago, # ^ |   0 Same, took me much time to realize that using a for loop is way better than a while ;-;
 » 6 months ago, # | ← Rev. 3 →   0 was WA on pretest 3 on D meant to catch any known error or just a random case? ;( not able to find my mistake
 » 6 months ago, # | ← Rev. 4 →   +5 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
 » 6 months ago, # |   +1 I have a question how problem C O(n2) solution is being getting accepted ?
•  » » 6 months ago, # ^ |   0 I think you mean O(n*(2Sqrt(n))? if you're talking about the gcd.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 241481930 that's my submission, otherwise it's impossible to get accepted I think ;-;
•  » » » » » 6 months ago, # ^ |   0 No Worries :) Thank you for sharing your solution
•  » » » » 6 months ago, # ^ |   0 Can you link one such $O(n^2)$ solution which got accepted?
•  » » » » » 6 months ago, # ^ |   0 Sure, Here is that: https://codeforces.com/contest/1920/submission/241451239
•  » » » » » » 6 months ago, # ^ |   0 damn I thought you were trolling lol, how did this get accepted jfl (he's an lgm tho)
•  » » » » » » » 6 months ago, # ^ |   0 I am also shocked b/w the time limit given was 3 seconds. I think it can get accepted due to that as well.
•  » » » » » » » » 6 months ago, # ^ |   0 No that's at most 3e8 I think, turns out it was If(n%k==0) lol
•  » » » » » » 6 months ago, # ^ |   0 There is a check if(n%k==0) inside the loop, so the complexity is the same as in the tutorial.
•  » » » » » » » 6 months ago, # ^ |   0 Damn fr ;-; so it's O(n*2Sqrt(n))?
•  » » » » » » » » 6 months ago, # ^ |   0 Nice :) You are correct Now I observed this thing :) Thanks to you guys !!
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » » » » 6 months ago, # ^ |   0 there's the check part n%i
 » 6 months ago, # |   0 can any one give me explanation of problem B?
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 I can't justify my D-time complexity. this is my D
•  » » 6 months ago, # ^ |   0 solution for problem D**
•  » » » 6 months ago, # ^ |   0
•  » » » » 6 months ago, # ^ |   0 No it was a joke nvm lol
 » 6 months ago, # |   0 https://codeforces.com/contest/1920/submission/241478736 what is wrong in this code for problem C?
 » 6 months ago, # |   0 can someone explain ans = max(ans, A[n] — 2 * A[min(i + x, n)] + A[i]); in part b?
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 y why does he multiply by 2?
•  » » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +6 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.
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ |   0 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
•  » » » 6 months ago, # ^ |   0 Oh got it thanks
 » 6 months ago, # |   +2 Am I the only one who found majority of the problems in this contest to be filler?
 » 6 months ago, # | ← Rev. 2 →   +11 F2 can be solved in $O(nm\cdot\alpha(nm)+q)$ with offline LCA.
 » 6 months ago, # |   +18 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!
•  » » 6 months ago, # ^ |   -8 precompute divisors SMH
 » 6 months ago, # |   0 Thanks for the clear and short conditions!
 » 6 months ago, # |   0 I personally think C is harder than D. Maybe swap them is better?
 » 6 months ago, # |   +3 I misunderstood E's "substring" as "subsequence" and wrote a wrong DP.Now feeling I'm a noob :(
•  » » 6 months ago, # ^ |   +4 it happens (I'm actually a noob)
 » 6 months ago, # |   0 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) ?
 » 6 months ago, # |   0 Negative time to editorial publish
 » 6 months ago, # |   0 For problem C: I Need some help to figure out what the complexity of this solution is: 241500814It 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??
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 n^1/3
 » 6 months ago, # |   0 C was a bit standard, but great contest overall.. thank you.
 » 6 months ago, # |   0 Its not necessary to use prefix sum for problem B ryt?
 » 6 months ago, # | ← Rev. 3 →   0 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.
•  » » 6 months ago, # ^ |   -14 you cant expect samples to cover everything, and in this case, repeated indices isnt an edge case for 99.9% of solutionsToday's contest had way stronger samples than usual (and imo way stronger than should be)
 » 6 months ago, # | ← Rev. 2 →   0 Please Anyone help me Find out Why my Solution is failing on some testcases! Problem D — My submission — 241508049
 » 6 months ago, # | ← Rev. 2 →   0 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.
 » 6 months ago, # |   0 241515808 please tell why is it giving run time error
 » 6 months ago, # | ← Rev. 2 →   0 Excellent round. C is good and standard. However I stuck in the gap between C and D so the round go speedforces for me :(((((
 » 6 months ago, # |   0 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
 » 6 months ago, # |   0 use GCD for c number problem
•  » » 6 months ago, # ^ |   0 yep you are right i also done this problem using __gcd. Thank You for sharing your idea
•  » » » 6 months ago, # ^ |   0 thankyou dear.❤️
•  » » » » 6 months ago, # ^ |   0 okk
 » 6 months ago, # |   0 That was an amazing contest with some cool problems like C and E
 » 6 months ago, # |   0 Problem C was cool, I learned so much
 » 6 months ago, # | ← Rev. 2 →   0 Good round!
 » 6 months ago, # |   0 Can anyone explain why calculating gcd of series of numbers take n+logn and not nlogn timeAlthough i solved ABC but i wasn't aware of this
•  » » 6 months ago, # ^ | ← Rev. 2 →   +11 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)$.
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 Thanks for the reply Problems were good hope to see more contests from you in future
 » 6 months ago, # |   +11 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.com/contest/1920/submission/241529452
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Complexity analysisWe can modify your code to slow down, but it will be easier to estimate. int eval(int n, vector &primes, int mn = 0, int gg = 0) { int ans = 1; int q, g; for (const auto &k : primes) { q = n / k; if (q == 0) q = 1; g = gg; for (int i = 0; i < n; i++) { g = __gcd(g, abs(a[i] - a[i % q])); if (g == 1) break; } if (k >= mn && n % k == 0) { if (g != 1) ans += eval(q, primes, k, g); } } return ans; } Lets describe changes. We always use all primes of initial n. We check k >= mn only after gcds. This makes our code always calculate for gcd for each prime factor (not only larger ones). We check n % k == 0, because it may not happen in this version. We start with i = 0 , this makes few useless g = gcd(g, 0) calls, but this is easier to estimate.Those modifications makes eval be called for each divisor of initial $n$, and single call without recursive calls takes $O(prime.size()\cdot (n + \log(\text{initial_n})))$, here $n$ is what passed into function. We can estimate $prime.size()$ as a $\log(n)$.So, overall complexity is: $O\left(\sum\limits_{d|n}\log(n)\cdot(d+\log(n))\right)$ $O\left(\left(\log(n)\sum\limits_{d|n}d\right)+\left(\log^2(n)\sum\limits_{d|n}1\right)\right)$There are two common definitions: $\sigma(n)=\sum\limits_{d|n}d$ $d(n) = \sum\limits_{i|n}1$So, we get $O(\log(n)\sigma(n) + \log^2(n)d(n))$. Next, we can plug in some upper bounds. For example: $\sigma(n) < e^\gamma n \log \log n+\frac{0.6483n}{\log \log n}, \text{where } n \geq 3$ $d(n)\text{ is } O(\sqrt[3]{n})$Plug in those: $O\left(\log(n)e^\gamma n \log \log n+\frac{0.6483 n\log n}{\log \log n} + \log^2(n)\sqrt[3]{n}\right)$Simplify, using rules of big O notation. $O\left(n\log(n) \log(\log n)\right)$Leave a comment if you found mistakes.Non-modified code is faster. But it's really hard to estimate its complexity. And if you use k <= mn instead, it even more faster. Because it reduces size of n by larger factors first.
•  » » » 6 months ago, # ^ |   0 Thanks For the analysis <3
 » 6 months ago, # |   0 Damn, I didn't see the constraints for 1920B - Summation Game and solved by considering negative numbers as well XD, submission.
 » 6 months ago, # |   0 First approach of problem D is really new learning to me. Thanks.
 » 6 months ago, # |   0 Can anyone explain what is wrong in this code for D 241534324
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ |   +21 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.
•  » » » 6 months ago, # ^ |   0 That makes sense. Thanks very much.
 » 6 months ago, # |   +8 Problem CFor 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, .. , akNow 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+7GNow for m = G you get the same remainder for this sequence: a1%GNow 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!
 » 6 months ago, # |   0 Can someone please explain the formula used in B solution in the editorial? I cannot wrap my head around it. Thanks in advance.
•  » » 6 months ago, # ^ |   0 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+rS'-S = (-e+r)-(e+r)= -2e
•  » » » 6 months ago, # ^ |   0 thanks alot!
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   0 [1,1,2,2,1,1,2,2] can't be split on any primes, but does split on k = 4.
 » 6 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1920/submission/241572267Can someone explain why this solution of task D gets accepted on visual c++ 2017, and gets a time limit on g++20?
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   +8 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)$.
 » 6 months ago, # |   0 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.com/contest/1920/submission/241579138Accepted solution — https://codeforces.com/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 )
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   0 What's the time complexity in C?O(n*n)
 » 6 months ago, # | ← Rev. 3 →   0 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
 » 6 months ago, # |   0 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) 
•  » » 6 months ago, # ^ |   +1 Python 3 is too slow. Use PyPy3 to submit your code.Your accepted solution.
 » 6 months ago, # |   +1 https://codeforces.com/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.
 » 6 months ago, # | ← Rev. 2 →   +11 I have solution for 1920F2 - Smooth Sailing (Hard Version) in $O(nm\cdot\alpha(nm) + q)$. SolutionIt's basically similar idea as in the editorial. But... with a few differences.First one: instead of parity, I'm using angles. I think you can exchange those. So, in DSU I maintain for each node angle to its root, if I walk there cell by cell in MST. Then, to check is there round trip I check all cycles if total angle of circle > pi / 2. Why pi / 2? Well, I thought it's enough :DSeocond one: why is the complexity different? Well, each time I find a cycle I answer on all cells within the component. Not taking into account are they listed in queries or not. How do I keep list of cells within a component? I maintain other tree -- binary tree with new node added when two component joined, and this node I have two children representing joined components. In this way I can use dfs to traverse all cells within component. And after I do it, I clear list of component cells, it's same as marking component as having round trip. First I thought to make linked list, but I thought it would be troublesome.So, complexity consists of: $O(nm)$ joins in DSU, which leads to $O(nm\cdot\alpha(nm))$ and traversing components when cycle is found, which is $O(nm)$. Calculating angles adds time for calculating arc sin, but you may consider it as a constant. If you dislike it, you can use parity approach I guess.Here is the code 241633554
•  » » 6 months ago, # ^ |   +8 Here is parity version: 241636798
 » 6 months ago, # | ← Rev. 3 →   0 How does the editorial for problem F2 account for a case like this?https://imgur.com/a/W2gRkVa
•  » » 6 months ago, # ^ |   0 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).
•  » » » 6 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) ?
•  » » » » 6 months ago, # ^ |   0 Long explanationFirst, we use idea about odd number of intersections as a fact. If you're not convinced, look for information in the internet about checking whether point lies inside polygon.Next, we rephrase this criteria as follows: pick any loop with island inside. Pick any starting point on it. Let $p_1, p_2, p_3 \dots p_n$ to be points on the loop in order of round trip. Here $p_n = p_1$. Then, we define parity of index $i$ as the parity of intersection of the path $p_1,p_2...p_i$. We tie parity to index because points may coincide (ending points for example). Then, parity of index n should have 1.This shows us that if loop exists, then there is path from point to the same point but with parity 1. Similarly, if we assume we start with parity 1, then there is path to parity 0.Next step, we claim that this is not just "if then", but "if and only if". In other words. If there is a path from 0 to 1 to the same point, then there is a loop with odd number of intersections. For some (like me) it seems obvious. But I'll explain it anyway.Suppose we have a path $p_1,p_2,p_3\dots p_n$ where $p_1 = p_n$ and parity of index 0 is 0 and parity of index $n$ is 1. Then, if you forget about parity, then it is a loop, because $p_1 = p_n$. But if you recall about parity, then it has odd number of intersections.In other words, existence of path $\leftrightarrow$ existance of a round trip. Next, step... existence of path is the same as reachability. But to find out this kind of reachability, we define new graph. It has triples as a vertices. $(x, y, parity)$. So, for each original point, there are two "duplicates": $(x, y, 0)$ and $(x, y, 1)$. Then, all points are connected as before, except, if a single step from $(x_1, y_1, p_1)$ to $(x_2, y_2, p_2)$ crosses the line above certain rock cell, then $p_1 \neq p_2$ (parity changes). Otherwise $p_1 = p_2$.Then, if we have a path from $(x, y, 0)$ to $(x, y, 1)$ in this new graph then there is a round trip we want to find. Having path = reachability. So, if $(x, y, 0)$ and $(x, y, 1)$ within the same component, it means $(x, y, 1)$ is reachable from $(x, y, 0)$ and thus there is a round trip we looking for. Then, to answer a question about a given starting point, we should check is there some pair $(x, y, 0) (x, y, 1)$ within the same component as the given point.What about a distance we asked for? Well, we start from maximum distance, and decrease it. Each step we allow to walk in cells which has lower and lower distance, merging them in DSU which maintain reachability components.
•  » » » » » 6 months ago, # ^ |   0 very helpful!
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +16 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.
 » 6 months ago, # | ← Rev. 3 →   0 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.
 » 6 months ago, # |   0 For B a more verbose sol. 242411746Only 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.
 » 6 months ago, # |   0 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
 » 6 months ago, # |   0 Can anybody the problem with my solution for Problem C ? #include #define int long long using namespace std; set fac(int n) { set 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 arr(n); for(auto &x : arr) cin >> x; set fct = fac(n); int ans = 0; for(auto &x : fct) { int cnt = 0; for(int i=0; i> tc; while(tc--) solve(); } 
 » 5 months ago, # |   0 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 using namespace std; #define ll long long long long find(long long idx,vector &b,vector &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 b(n+1); vector x(n+1); // vector 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 : "< queries(q); for(int i=0;i>queries[i]; } cout<<"The answer is:- "; for(int i=0;i>t; while(t--){ solve(); } return 0; } 
 » 3 months ago, # |   0 Problem C was very intuitive. Loved the problem
 » 2 months ago, # |   0 why is time complexity of problem C { n+ log(n) }* max.diviosrs(n) and not n*log(n)*max.divisors(n) ?