### FelixArg's blog

By FelixArg, history, 3 weeks ago, translation,

Thank you for participating! I hope you enjoyed the tasks.

One of the testers (redpanda) did a wonderful video analysis tasks A-C, I highly recommend watching it.

1982A - Soccer

Tutorial
Solution (74TrAkToR)

1982B - Collatz Conjecture

Tutorial
Solution (FelixArg)

1982C - Boring Day

Hint 1
Hint 2
Tutorial
Solution 1 (FelixArg)
Solution 2 (74TrAkToR)

1982D - Beauty of the mountains

Hint 1
Hint 2
Tutorial
Solution (FelixArg)

1982E - Number of k-good subarrays

Hint
Tutorial
Solution (FelixArg)

1982F - Sorting Problem Again

Hint
Tutorial
Solution (FelixArg)
• +123

 » 3 weeks ago, # |   -75 First. good problems I think.
•  » » 3 weeks ago, # ^ |   0 I'm sorry that the good problems failed to appear in the contest, hope that we can see the problems later:)
 » 3 weeks ago, # | ← Rev. 2 →   -14 Thank you fast editorial
 » 3 weeks ago, # |   +2 C. Most of the people have done this using dp. I didn't get the dp logic, but I tried it another way. For each position i, check the nearest position(let's say idx) on the right side which gives sum>=l (this can be done with lower bound and prefix sum, and also check if sum<=r). So you will have several i,idx intervals. Put them in a vector. Now all you need to do is find maximum non overlapping intervals, which is a standard leetcode problem.
•  » » 3 weeks ago, # ^ |   +10 that's cool! simple sliding window would suffice too
•  » » » 3 weeks ago, # ^ |   +6 I can't figure out why my solution wrong? Please help me. My submission link. 267434800
•  » » » » 3 weeks ago, # ^ |   0 Please try this dataset: 5 6 8 5 5 1 2 5 The correct answer is 2 by 5+1 and 2+5, but your program outputs 1?
•  » » » » » 3 weeks ago, # ^ |   +6 Note that it does not input the number of test cases T.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 5 →   0 Can you please figure out which test case my code isn't passing .Here is the submission id. 267473714
•  » » » » » » » 3 weeks ago, # ^ |   0 I don't quite understand Java programming, but your error seems similar to the original poster's error, both involving incorrect starting positions in a sliding window. For example, in this dataset (without T): 3 6 8 3 1 5, your output is 0, but actually 1 + 5 would achieve 1.
•  » » » » » » » » 3 weeks ago, # ^ |   0 thanks i got it
•  » » » » » » » » 3 weeks ago, # ^ |   0 can you tell me what is wong in my approach it seems correct to me https://mirror.codeforces.com/contest/1982/submission/267490137
•  » » » » » » » » » 3 weeks ago, # ^ |   0 This still seems to be an issue with handling the starting point, such as this group still lacking data for T: 5 6 8 4 1 4 1 9 The correct answer is 1, obtained by 1+4+1. However, in your program, when it first detects a sum greater than r, it encounters 4+1+4 during the process of moving the left pointer rightward, but since there is no value satisfying the condition within the [l, r] range, the left pointer moves to position 3, which is where the value 4 is located, instead of 1. This results in an incorrect answer of 0. In such problems, the left pointer typically moves to points that do not satisfy the current condition. Specifically, in this question, it should move to points that do not satisfy the condition of the interval sum > r, correct?
•  » » » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I understood what's the issue , and fixed the code , it's AC , but one thing i wanted to ask , that how do should i proove my greedy approach and check it is correct for every case , while doing greedy this is the mistake i do everytime i either do not take a case into consideration or i overthink cases and gets confused , btw thank you for your help
•  » » » » » » » » » 3 weeks ago, # ^ |   -10 It is possible to write a brute-force program to generate some data and compare the results with a non-brute-force program. This might take some time, but it can be quite useful in certain situations.
•  » » » » 3 weeks ago, # ^ |   0 okay the problem is that when the sum > r you are sliding the left side which is fine but you are not taking care — if after all the sliding the sum ends up lower than "l" and now your "sum =0" at the begining will discard the sum which could have been used
•  » » » » » 3 weeks ago, # ^ |   0 Thanks for the help. Got accepted 267452661
•  » » » » » » 3 weeks ago, # ^ |   0 :)np
•  » » 3 weeks ago, # ^ |   0 cool name.
•  » » » 3 weeks ago, # ^ |   0 thanks :)
 » 3 weeks ago, # |   0 Well done! Very fun contest and good problem set.
 » 3 weeks ago, # |   0 Thanks, it was a fun contest and nice problems + fast editorial
 » 3 weeks ago, # | ← Rev. 3 →   -8 Can someone please tell me what is the flaw in the logic of my solution for C (like a corner test case on which it fails). It shows WA on 475th case. #include using namespace std; using ll=long long; #define forn(i,n) for(int i=0;i>t; while(t--) { cin>>n>>l>>r; vector vec(n); forn(i,n) cin>>vec[i]; sum=0;ans=0; forn(i,n) { sum+=vec[i]; if(sum>=l and sum<=r) { ans++; sum=0; } else if(vec[i]>=l and vec[i]<=r) { ans++; sum=0; } else if(sum>r) { if(vec[i]
•  » » 3 weeks ago, # ^ |   0 Example : 1 3 5 6 1 2 4 Using your code, the output will be 0, but the output must be 1 because your code will compare vec[i]=4. Asn will not increase, but you must use two pointers so that you subtract vec[le]=1, so the sum will become 6 and increase by ans.
•  » » » 3 weeks ago, # ^ |   0 Ohhh got it now. Thanks a lot bro.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Your example is not valid, you are taking 1 3 5 6 1 2 4, if we try this then n=1, l=3, r=5. The cards will be only 6. 6 is greater than 5, hence 0 should be the output.
•  » » » » 3 weeks ago, # ^ |   0 test_cases=1,n=3,l=5,r=6
 » 3 weeks ago, # | ← Rev. 2 →   +28 Why would you set $n=5\cdot 10^5$ to a $O(n\log n)$ data structure problem?
•  » » 3 weeks ago, # ^ |   +16 Trying to differentiate log factor lol
 » 3 weeks ago, # | ← Rev. 2 →   -17 Great mathforces round! + fast editorial
 » 3 weeks ago, # |   0 Can anyone explain (?) me, In B, Why k%(y-1) and not k%y ?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 because y/y = 1and to go from 1 to y you need y-1 operations
•  » » 3 weeks ago, # ^ |   0 The number in the last part of the problem changes as follows:2-3-...-(y-1)-1-2-3-...-(y-1)-1-2-3-...-(y-1)The reason why $(y-1)$ is followed by $1$ is that the number is automatically divided by $y$ when it becomes $y$.
•  » » 3 weeks ago, # ^ |   0 Imagine you have y = 3, for example. If you get x to be 1, you spend two (y-1) more operations to come from 1 to 3 (and then to 1 again)
•  » » 3 weeks ago, # ^ |   0 Because once you reach 1 the value of x repeats every y-1 operations.
 » 3 weeks ago, # |   +5 Under what category does problems like 1982B - Collatz Conjecture come under?I always fail at making proper observations to such problems.Can anyone please suggest me a list of such past problems?Btw, I solved 1982C - Boring Day using sliding window technique. Code is quite simple and easily understandable. Codevoid testcase() { int n, l, r; cin >> n >> l >> r; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; deque dq; i64 sum = 0; int count = 0; for (int i = 0; i < n; i++) { dq.emplace_back(a[i]); sum += a[i]; while (!dq.empty() && sum > r) { sum -= dq.front(); dq.pop_front(); } if (l <= sum && sum <= r) { count++; sum = 0; dq.clear(); } } cout << count << "\n"; } 
•  » » 3 weeks ago, # ^ |   0 I think it's just that if you dry run for some cases you can see a cycle forming and then optimise
•  » » » 3 weeks ago, # ^ |   +3 I understand that. I just want few such problems to practice!!!
•  » » » » 11 days ago, # ^ | ← Rev. 3 →   0
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   0 great book that teaches you how to solve problems similar in nature to the aforementioned problem: https://www.softouch.on.ca/kb/data/Art%20and%20Craft%20of%20Problem%20Solving%203E%20(The).pdf
•  » » » » » 10 days ago, # ^ |   0 Thanks a lot ves for sharing the problems!!!
•  » » » 11 days ago, # ^ |   0 that wont work for every problem you come across
 » 3 weeks ago, # | ← Rev. 8 →   +35 In problem D, the generalized version of Bézout's identity is used. If you haven't already heard about Bézout's identity, it states that the equation $$$\ ax + by = d \$$$ has integer solutions if and only if $\displaystyle gcd(a,b)\mid d$.There are two ways to prove this: you can either use the extended Euclidean algorithm, or prove it via an existence proof that can be extended for $n$ variables instead of just $2$ (see the generalized version's statement here)Here's the proof for three variables (heavily inspired by the proof for two variables from MONT) which can be easily extended for an arbitrary number of variables:Let $S = { ax + by + cz \mid a, b, c \in \mathbb{Z} }$. Consider the smallest positive element $d \in S$, $d=ax_0+by_0+cz_0$. We want to show that $d=gcd(a,b,c)$. It is sufficient to show that $d\mid gcd(a,b,c)$ and $gcd(a,b,c) \mid d$. The second part is true since all of $\displaystyle \frac{a}{gcd(a,b,c)}, \frac{b}{gcd(a,b,c)}, \frac{c}{gcd(a,b,c)} \in \mathbb{Z}$. For the first part, we need to show that $d \mid a,b,c$.Let us do the following for each of $(a,b,c)$ (I will only do it for $a$): Assume that $d \nmid a$. Then $a=qd+r, 00,r •  » » 3 weeks ago, # ^ | 0 Small correction:$gcd(a,b)|d$•  » » » 3 weeks ago, # ^ | 0 Thank you, corrected! •  » » » » 3 weeks ago, # ^ | ← Rev. 2 → 0 Also I don't think "The second part is true since$a, b, c | d$" is correct. For example$2x + 3y + 5z = 1$does have integer solutions but neither a,b nor c divide 1. But the gcd part is correct because we can factor out$gcd(a, b, c)$from$ax+by+cz$. •  » » » » » 3 weeks ago, # ^ | ← Rev. 2 → 0 Oops lol, I had meant to type$\displaystyle \frac{a}{gcd(a,b,c)}, \frac{b}{gcd(a,b,c)}, \frac{c}{gcd(a,b,c)} \in \mathbb{Z}$, but instead ended up typing$(a,b,c)$and using$\mid$. Corrected this as well, thank you; please let me know if you find any other mistakes. •  » » 3 weeks ago, # ^ | 0 I think you can just use the result of 2 variable to proof$n$variable by induction, which would be more brain-dead to do so. •  » » 3 weeks ago, # ^ | 0 Hey another small correction: "Then$a=qd+r,00,r
•  » » » 3 weeks ago, # ^ |   0 Corrected, thanks again.
•  » » 3 weeks ago, # ^ |   0 A solution to a Diophantine equation is not unique, because we can form an infinite number of solutions if we know one solution. If a pair $(x, y)$ is a solution, then also all pairs $(x+ kb/gcd(a,b) ,y− ka/gcd(a,b) )$ are solutions, where $k$ is any integer.what happens when $n$ variables instead of 2?
•  » » » 3 weeks ago, # ^ |   0 That will also have infinitely many solutions since $c_1 x_1 + c_2 x_2 + ... + c_n x_n = 0$ has at least $1$ solution since $gcd(c_1,c_2,...,c_n) \mid 0$, and all scalar multiples of this solution will also be valid solutions. Then you can add any scalar multiple of any solution for $0$ to any solution for $c_1 x_1 + c_2 x_2 + ... + c_n x_n = d$.
•  » » » » 3 weeks ago, # ^ |   0 I mean for 4 variables suppose I have a solution (a,b,c,d) then how do you form other solutions?
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 (Note that this doesn't use a given solution to form infinitely many solutions, but instead directly forms infinitely many solutions)I guess one option you have is to reduce it to a diophantine.Like, for example, say I had $5a+15b+10c+25d=5$. Set $a=b=1$, then we have $10c+25d=-15$ and $c=-5n-4,d=2n+1$. We can choose any values we want for $a,b$ since $5a+15b$ will always be a multiple of the greatest common divisor of the coefficients.
•  » » » » » » 3 weeks ago, # ^ |   0 ok thanks for help
 » 3 weeks ago, # | ← Rev. 2 →   0 Problem C : Detailed Video Explanation (Greedy + Two Pointer) https://youtu.be/zAMyp0dXCKk
 » 3 weeks ago, # |   0 D is using something called Diophantine equation which I am very much unaware of From where should I learn these things and is it as scary as it sounds like
•  » » 3 weeks ago, # ^ |   0 You will find it in math olympiad books.
•  » » » 3 weeks ago, # ^ |   0 So should I just learn this identity and move on or should I go deep into this like looking for proofs and similar equations?
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I would say learn and move on (also do understand the proof imo, but it’s up to you)
•  » » 3 weeks ago, # ^ |   0 If you want to learn via Youtube. You can learn it from Vivek Gupta(As you are comfortable in Hindi). He has covered it
 » 3 weeks ago, # |   0 thanks for the fast editorial :)
 » 3 weeks ago, # |   0 can anyone tell me the test case where my code fails in prblm 3??267372328
•  » » 3 weeks ago, # ^ |   +1 14 5 53 1 2 3
•  » » » 3 weeks ago, # ^ |   +3 Yaa.. Got it missed one if condition.
 » 3 weeks ago, # |   +1 didn't aware the fact that gcd of set of integer S divides x iff x $\in$ span(S) 😭 cost me problem Dhow people solve this without knowing this fact?
•  » » 3 weeks ago, # ^ |   0 Proof by AC works i believe.
•  » » 3 weeks ago, # ^ |   0 proved it to myself during the contest by trying out some small cases
 » 3 weeks ago, # |   0 I have been trying problem D for quite a while now, I am using a 2D sliding window approach to calculate the number of "ones" that each submatrix would have. I observed that the difference changes by (k*k — 2*numberOfOnes) for each submatrix and can be either a positive or a negative change. However I do not understand where I am going wrong. Here is my submission https://mirror.codeforces.com/contest/1982/submission/267424514 Can someone please help point out the mistake or even a testcase where my solution would fail.
•  » » 7 hours ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } If I read your code correctly, it seems like you are translating the problem into the coin change problem. i.e. you have coins of denomination $a_1, a_2,\ldots$, check if there is a way to produce change of value $x$. Firstly the translation is not right. For example if you have $x=1$ and coin values $\{2, 3\}$ the coin change problem says no, but the answer should be YES as you can go from $1\Rightarrow -2 \Rightarrow 0$.But even if the translation is correct it's well known such greedy method as you use will not work for all kinds of coin systems, it only works for a subset of coin system called "canonical" (I do not know much about it but it seems interesting). Here's an example, $a=\{3, 5\}, x=8$. So greedily adding $3$ gets you to $6$ which fails, but adding $3$ once then adding to $5$ gives $8$.
 » 3 weeks ago, # |   0 I did not understand the D solution with GCD. I came out with the solution of finding the difference of ones and zeros for each submatrix using prefix sums (not fast enough to code it in the contest time though).What I thought is that if I have d1, d2, d3... dn, and I can find c1d1 + c2d2 + ... + cndn that is equal to D, than I can satisfy the conditions.Anyone can give some link to the proof of the last equation?
•  » » 3 weeks ago, # ^ |   0
•  » » 3 weeks ago, # ^ |   0 Bezout's lemma, you can look it up here- Wiki
•  » » 3 weeks ago, # ^ |   0 I have shown how to prove it in my comment above here.
•  » » » 3 weeks ago, # ^ |   0 Hey, I saw your explanation and it makes sense. I had however used the following to check whether or not it will be possible to make the difference zero. vectorv; for(auto &it: reduceBy) { v.push_back(it); } while(diff > 0 && !v.empty()) { if(v.back() != 0) diff -= (diff/v.back()) * v.back(); v.pop_back(); } if(diff == 0) cout << "YES" << endl; else cout << "NO" << endl;here the reduceBy is a set which contains the different impacts we can have on the difference. This however gives me a wrong answer and I don't understand why.
•  » » 3 weeks ago, # ^ |   0 Thanks, guys! I haven't realized that the constants c1, ..., cn could be negative, so I was confusing this with the coin problem (determine if N is achievable with coins [c1, ..., cn]).
 » 3 weeks ago, # |   0 Can someone explain why my submission for problem D (267400465) gives runtime error? It works correctly on my local machine.
•  » » 3 weeks ago, # ^ |   0 It does not work on cf but works on your machine due to undefined behaviour, in the end you have done *(s.begin()) assuming there are elements in s but that may not be true, in this case it's undefined behaviour as far as I am aware since whatever value is there may be picked up or a seg fault could occur. In your particular case it could have randomly turned up correct on your machine but on cf it could have given a seg fault or the random value could have been 0 giving a mod by 0 error.
 » 3 weeks ago, # | ← Rev. 2 →   -19 I am sorry, i got my mistake
•  » » 3 weeks ago, # ^ |   +2 No the error is indeed correct. You have added an if statement in your loop with a break the lack of which made the error happen in the first place and is the reason your after contest submission is correct while during contest is not.
 » 3 weeks ago, # | ← Rev. 4 →   0 After the contest I have seen the GCD approach to solve problem D. However I don't understand what's wrong with the following approach:I have used the following to check whether or not it will be possible to make the difference zero. vectorv; for(auto &it: reduceBy) { v.push_back(it); } while(diff > 0 && !v.empty()) { if(v.back() != 0) diff = diff % v.back(); v.pop_back(); } if(diff == 0) cout << "YES" << endl; else cout << "NO" << endl;here the reduceBy is a set which contains the different impacts we can have on the difference. Hence v is a sorted vector in increasing order. This however gives me a wrong answer and I don't understand why.
•  » » 3 weeks ago, # ^ |   0 v = [3,2] diff = 5 5%2 = 1 1%3 = 1 but it is possible
•  » » » 3 weeks ago, # ^ |   0 I apologize I forgot to mention that reduceBy is sorted in increasing order and as we are traversing from the last index, it would pass as v = [2,3] diff = 5%3 = 2 2%2 = 0 I’ll update the original comment that reduceBy is a set and v would be sorted in ascending order.
•  » » » » 3 weeks ago, # ^ |   0 well increase v to be [2,3,4] and diff=5. Now it does not pass.What you are doing is greedily trying to reach 0, however in this problem the greedy approach is not valid since firstly you are not accounting for negative values of c: For example let v=[4,7] and diff=3 you would assume this is impossible but you can do 3+4-7 to reach 0Secondly it isn't necessary that the biggest number will indeed be reduced from diff to reach 0, think coin dp problem.
•  » » » » » 3 weeks ago, # ^ |   0 That makes so much sense, and I feel dumb for not getting it myself. Thank you very much it’s clear to me why my submission was wrong.
 » 3 weeks ago, # |   0 In E there exists a solution with time complexity $O(T\log^2 n)$，using only DP. The main idea is trying to find every starting point of consecutive ones ($a_x=1$ if x is valid). You can see the implementation here.
•  » » 3 weeks ago, # ^ |   0 Can you please explain the states of your dp and recurrence relation. I have been trying to think of a dp solution from 3 hours but i am not able to.
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone please let me know me where my submission to problem C might be failing ?267403795edit: I got it..
 » 3 weeks ago, # | ← Rev. 2 →   0 Hi everyone!Can someone please point out why my submission 267373128 might be failing on the 475th test case of Test 2 of problem C. The following is the approach: I used a greedy approach for the problem. I declared two variables named sum and cnt (both initially set to 0). Then I started iterating over the array and check if sum + a[i] < l, then increased sum by a[i] and moved on to the next element. Else if sum + a[i] >=l && sum + a[i]<=r, that means this is the case when Egor would win. So I incremented cnt, set sum = 0 and move onto the next element. Else, which means sum + a[i] > r, then I have used a nested if else. If a[i] > r, then Egor cannot win if this element is included, so I set sum= 0 and moved onto the next element. Else if a[i]<=r, set sum = 0, but this time did not move to the next element as this element can contribute to forming a sum which is in the range. Any help will be appreciated!
•  » » 3 weeks ago, # ^ |   0 I also got the same WA on 475th case. Try your code for input n=3,l=5,r=6 and value of array as 1,2,4. The output should be 1 but my code was giving 0.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 In your 4th point, when a[i]<=r you can still win with that element if you move your left pointer to the right by some amount (possibly). That is to say, if I'm taking the sum from index 0 to index i and it's larger than r, I could take from index 1 to i and that could maybe work.Edit: a[i]<=r instead of >
 » 3 weeks ago, # |   0 in the first problem, the score if x1 > y1 and x2 > y2 and y2 > x1 in that case there is a possiblity that at some point the yt would have been equal to xt ??
•  » » 3 weeks ago, # ^ |   0 if x1 > y1 and x2 > y2 you could always increment x all the way and than y , remember we have to reach x2 and y2 eventually not that y2 is already there to hinder with x
 » 3 weeks ago, # |   0 hey , there are many telegram groups where solutions got leaked during contest please take some action. below is one groups where solutions and code was sharing during contest : https://t.me/codeforces_cp
•  » » 3 weeks ago, # ^ |   +1 yup, i to know a few grps A to D were discussed and shared during the contest :(
•  » » 3 weeks ago, # ^ |   0 ur prefix sum condition is wrong . it should be :- Spoilerprefix[i][j]=prefix[i−1][j]+prefix[i][j−1]−prefix[i−1][j−1]+arr[i][j] ​
 » 3 weeks ago, # |   0 Ayo can someone help my code debug for Problem D. It says Wrong Answer on 4th Test Case. 242nd Token differ. 267451989
•  » » 3 weeks ago, # ^ |   0 The problem is when both i>0 and j>0 you need to add v[i-1][j-1]
•  » » » 3 weeks ago, # ^ |   +1 Thanks!! You a big help. Totally forgot about that
 » 3 weeks ago, # |   0 Yo, in qA, the third test case, why cant the 1st team score a goal and then the score would have been equal??
•  » » 3 weeks ago, # ^ |   0 Yeah, Maybe But the problem is asking for "NO" iff you are sure the goals were equal at one point of time
 » 3 weeks ago, # |   0 can someone please give the 475th test case for problem C with n l and r?
•  » » 3 weeks ago, # ^ |   0 It is n=3 , l=3 , r=3 array : [1 1 2]
•  » » » 3 weeks ago, # ^ |   0 thanks garlic_bread_0204
 » 3 weeks ago, # |   0 Can someone please check what is wrong with this submission for D ?267454158
•  » » 3 weeks ago, # ^ |   0 You are missing a parenthesis when defining each pref1[i][j], just compare with the line above
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Just corrected it.. Also,how did you manage to come up with this gcd idea during the contest ? Is there any speicifc source from where you came to know about this Diophantine equation ?
•  » » » » 3 weeks ago, # ^ |   0 I have a background in math olympiads so when I started to get a picture of what the solution looked like it just came to mind. As someone else mentioned you can look at this https://en.wikipedia.org/wiki/B%C3%A9zout's_identity#Generalizations
 » 3 weeks ago, # |   0 I am getting a TLE(Case 10) in Problem C. https://mirror.codeforces.com/contest/1982/submission/267454949
•  » » 3 weeks ago, # ^ |   0 Your solution is O(n^2). Try to optimize it by using prefix sums
 » 3 weeks ago, # |   0 Could someone explain the editorial of E for me. It is still unclear for me, and what is the main point of the approach?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +16 Note that "Bit sequence" can be generated by following infinite process: void step(vector& a) { int sz = (int) a.size(); for (int i = 0; i < sz; i++) { a.push_back(a[i] + 1); } } vector a = {0}; while (true) { step(a) } i.e $[0] \to [0, 1] \to [0, 1, 1, 2] \to [0, 1, 1, 2, 1, 2, 2, 3]$ and so on.It's not hard to see that it's actually a bit sequence: on the $i$-th step, we record all integers from $[2^i, 2^{i+1})$. These integers have one bit for $2^i$, and the rest of the bits correspond to the number of bits in $[0, 2^i)$, which is indeed the current sequence. Therefore, on the $i$-th step, we clone our sequence with an increment to the end of the sequence.From this point of view, the periodic nature of this sequence is clearly visible. Imagine $x$ is a maximum integer, such that $2^x < n$. Then we can split the sequence $0...n-1$ into $0..2^x-1$ and $2^x...n-1$. As we can see, the second part is also a prefix of the sequence but with a +1 increment. Therefore, if $x > k$, we can just solve for the two parts independently and then sum up the answers (since no good segment crosses $2^x-1$). And if $x \leq k$, the answer is simply $\frac{n(n+1)}{2}$, except for the case when $x = k$ and $n = 2^{x+1}$, then it is $\frac{n(n-1)}{2}$. With these formulas, you can write a simple memoization solution. It's not hard to see that it works fast because there are $O(\log^2 n)$ special states, where $n$ is a power of two, and we are always recalculating from a special state and a state that lowers $n$ at least twice.Code: 267468663
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Nice Approach. But could you explain why you did k — 1 for the second array that is from [2^x to n — 1] ?Like I get it that for the array [2^x to n — 1], there is an 2^xth extra bit and just this set bit is added to the sequence [0 to 2^x — 1] and it becomes the same sequence. But why k — 1 ? Should it not be k + 1 as we increased one bit to the original problem ?
•  » » » » 2 weeks ago, # ^ |   0 Yes we increased one bit. Therefore condition turned to $bit(a_i)+1 \leq k \to bit(a_i) \leq k-1$. Like, after reduction to prefix we will actually have one bit more than on prefix. And in our world we want to count $\leq k$ therefore after reduction to prefix we need to count $\leq k-1$, so that with this extra bit it will be $\leq k$.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Ohh, now got it. Thanks a lot.Also the TC will be o(log^3n) right ?
•  » » » » » » 2 weeks ago, # ^ |   0 It's $O(M \cdot (\log^2n + T\log n))$, where $M$ denotes $map$ runtime. But note that it can be easily rewritten without map to be clear $O(\log^2n + T\log n)$. Here $O(\log^2 n)$ to calculate answers for all cases where $n$ is a power of two, and after this single testcase will take $O(\log n)$. The upside of using a $map$ is that you don't need to think about those special states, you can just write all transitions as it is, and $map$ will optimize it for you, for the cost of $map$ runtime. In this problem constraints and TL are pretty generous luckily, therefore $map$ is safe to use.
 » 3 weeks ago, # |   +1 This round helps a lot with my rating :)The problem D is pretty interesting I think.
•  » » 3 weeks ago, # ^ |   0 True , generally i am not able to get to D but this time it was from number theory which i am pretty comfortable with , hence got it done....
•  » » » 3 weeks ago, # ^ |   +1 Well,I think the problem D is more likely to be some ideas added together. Actually, These ideas are pretty common if you do more maths problems :)
 » 3 weeks ago, # |   0 https://mirror.codeforces.com/blog/entry/130861 Help me guys
 » 3 weeks ago, # |   0 please explain how I can withdraw my earnings Nears?
 » 3 weeks ago, # |   0 In soccer question 3rd example the output should be NO but it's given yes . for the test case 1 2 4 5 there will be a time when score will be 2 : 2 . so the output should be No , plz clarify my doubt.
•  » » 3 weeks ago, # ^ |   0 Read the Note provided in the question
•  » » » 2 weeks ago, # ^ |   0 could not understand, plz explain
 » 3 weeks ago, # |   0 Just wondering, what's the point of having multiple test cases in F if $t$ is so small ($t \leq 10$) and there are only three tests (#1, #2, #3) where $t > 1$? Personally, I prefer problems with only one test case, as I don't have to care about re-initializing variables.
•  » » 2 weeks ago, # ^ |   0 Could you explain Problem F. I am unable to understand the editorial.
 » 3 weeks ago, # | ← Rev. 2 →   +3 FelixArg , My solution for D shouldn't have passed the Final system test cases, but it did. I knew the current difference between type1Sum, and type0Sum. ( let's call it RequiredDifference ) I knew for each of the sub-rectangle of size k*k, what are achievable differences. Lets call them (d1, d2, d3 ... dk). I knew that I had to do a1 * d1 + a2 * d2 + a3 * d3 + ... ak * dk = RequiredDifferenceI didn't know how that gcd ( d1 , d2 ... dk ) | requiredDiff . But I knew, for ax + by = z , then gcd(x, y) | z. So I used this two variable equation property and passed test cases. Refer to my solution. The test cases were weak for D. Ideally my solution shouldn't pass. Thanks to djm03178, it was later hacked.Also, I honestly felt helpless during the contest because I didn't know this property gcd ( d1 , d2 , d3 ... dk ) | requiredDiff.
•  » » 3 weeks ago, # ^ |   +11 I wonder, does that solution have an actual counterexample? I'm stress testing a bunch of small cases but none are found yet. Anyways, to explain the TL hack, it looks something like this:$n=m=8$, $k=4$ 00000000 00000000 00000000 00001111 11110000 11110000 11110000 11110000 Expanding this pattern to $n=m=500$, $k=250$ makes 15281 distinct possible differences, so it's not feasible to perform gcd on every pair in 2 seconds. Since $k$ is even, the differences can only be even as well, so having an odd sum of $a_{ij}$ makes it impossible to find a possible way and therefore it can only realize that the answer is NO after running the whole loop.
•  » » » 2 weeks ago, # ^ |   +3 I got a counterexample, a=42 b=70,c=30, pairwise gcd are 14, 10,6 leaving out say 8 but gcd of all is 2 so all even numbers work.
•  » » » » 2 weeks ago, # ^ | ← Rev. 5 →   +3 I mean, finding three numbers for the counterexample is easy, but making an actual test for that is another story, because of how hard it is to obtain only the desired values and not undesired ones with the 'windows'.I think I have a brief idea for this though. We can have large enough $k = n \lt m$, and control the difference with each column, so only each pair of columns of distance $k$ can affect the values and nothing else.
•  » » » » 2 weeks ago, # ^ |   +3 Ohhh, I think it works but the other hack seems to be already doing the same thing. I didn't realize because the hacked solution has a slightly different approach, but I guess it essentially has the same condition.Here's the one I made: 1 14 16 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0011110001111111 0011100001111111 0011100001111111 0011100001111111 0011100001111111 0011100001111111 0011100001111101 0011100001111101 0011100001111101 0011100001111101 0011100001111101 0011100001111101 0011100001111101 0011100001111101 
•  » » » » » 2 weeks ago, # ^ |   0 Damn I'll come back to this 6 months later when I am hopefully a little better equipped to learn this stuff, haven't dipped into hacking yet and coming up with test cases rather than numbers immediately feels much harder. Either way cool that you were able to come up with this.
 » 3 weeks ago, # | ← Rev. 6 →   0 Anyone Can please figure out which test case my code isn't passing on 3rd.Here is the submission id. 267473714
•  » » 3 weeks ago, # ^ |   0 See this Testcase4 11 111 2 3 6Your program considering 1+2+3+6 > r then debunking all 1,2,3 and considering just 6 which gives 0 as answer.But what it should do is just take 1 in the first round and lose and take 2+3+6=11 on the 2nd Round which gives 1 as a answer
 » 3 weeks ago, # | ← Rev. 2 →   0 i tried to solve C problem by using prefix sum but i do not get what is wrong in my approach below i will attach my submissionhttps://mirror.codeforces.com/contest/1982/submission/267490137
»
3 weeks ago, # |
Rev. 2   0

# include <bits/stdc++.h>

using namespace std; using namespace chrono;

# define endl '\n'

int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

auto ssss = high_resolution_clock::now();
int T;
cin >> T;
for (int tc = 1; tc <= T; ++tc) {

cout << "Test Case #" << tc << ":" << endl;
int n , l , r;
cin >> n >> l >> r;
ll ans = 0 , sum = 0;
vector<int> a(n);
for(auto& x : a) cin >> x;

int index = -1;
for(int i = 0; i < n; ++i) {
sum += a[i];
if(sum >= l && sum <= r) {
sum = 0 , ans++;
continue;
}
else {
index = (index == -1) ? i : index;
i++;
while(i < n && sum  <  l) {
sum += a[i];
i++;
}

while(index  < i && sum > r) {
sum -= a[index];
index++;
}

if(sum >= l && sum <= r) {
sum = 0;
ans++;
index = -1;
}
i--;
}
}

cout << ans << endl;

cout << nn;
}

auto eeee = high_resolution_clock::now(); duration duration_sec = duration_cast<duration>(eeee — ssss); cout << "Total time taken: " << duration_sec.count() << " seconds" << endl; return 0; }

Can anyone tell me why this code is not getting selected o 3rd ??

 » 3 weeks ago, # |   0 In problem C my code 267502094 is showing TLE on 17th test case. My logic is simply to iterate till the segment sum is >= l. If its becomes greater than r then i'll just take nly the first card of that segment and chose to lose the round... starting the next round from the next card thus. Help me in finding my mistake.
•  » » 3 weeks ago, # ^ |   +1 just think of a case where l=1e6 and r=1e6 and the array be like 1.......(1e5) times and one more element at the end is 1e9 in this case your code will check and remove the first element step by step and by checking again whole segment to the last value will become o(n*n).
•  » » » 2 weeks ago, # ^ |   0 Okkk... got it. Thank you so much.
 » 3 weeks ago, # |   0 Hey, For problem C I was trying to write a dp solution in the contest but I was getting WA on test 2, eventually had to go without dp. Can anyone please help me in finding the error? I have wasted a lot of time finding a bug :( Please help, my submission: 267511316
•  » » 3 weeks ago, # ^ |   0 Replace lower_bound() with upper_bound()
•  » » » 3 weeks ago, # ^ |   0 That fails in the first test case itself :( I have possible tried everything.
•  » » » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # | ← Rev. 3 →   +7 An alternative way to calcute the DP in E goes like this. P. S. the length of the text might seem daunting but it is because I tried to explain the logic behind every step.Again, $dp(i, j)$ represents the number of subarrays for the first $2^i$ numbers if we can have at most $j$ bits. It is easy to notice that this formulation is equivalent to the number of subarrays formed by the numbers for which only the first $i$ bits can be non-zero. This might be useful for some for later intution. To make things a bit easier to write down, let's denote $g(x)$ as the number of subarrays contained in an array of length $x$, so $g(x) = \frac{x(x + 1)}{2}$.If $j \geq i$, then the answer is simply $g(2^i)$, because no number smaller than $2^i$ has more than $i$ bits.if $j=0$ then the answer is 1 because there is only one possible subarray (the one containing just a zero).Now for the general case, $1 \leq j < i$, we need to notice something. The smallest number with more then $j$ bits will be one that looks like $1...1$ in binary, where there are a total of $j + 1$ bits (equal to $2^{j+1} - 1$). In this case all the subarrays formed by these numbers will be included in the dp. The number of these subarrays is $g(2^{j + 1} - 1)$. It is also important to note that these numbers form a sequence of continous good numbers which don't neighbour the other good numbers because of $2^{j+1} - 1$.The number after $2^{j+1} - 1$ is $10..0$ or $2^{j + 1}$ where there are $j + 1$ zeros. We can notice that the number of subarrays formed by numbers where this lone bit is the highest one is just $dp(j + 1, j - 1)$, $j + 1$ because that is the number of zeros we have to work with and $j - 1$ because we need to account for the extra bit. In a similar fashion we include the numbers for which the $(j + 2)rd$ (0-indexed) bit is the highest one, the answer for which will be $dp(j + 2, j - 1)$. If we continue this pattern for every bit, we will have $dp(i, j) = g(2^{j + 1} - 1) + dp(j + 1, j - 1) + dp(j + 2, j - 1) + ... dp(i - 1, j - 1)$. The reason why we can sum up these states is because the sequence of numbers considered by each state are seperated by at least one bad number. E.g. $2^{j+1} - 1$ seperates the first sequence of numbers from the others. Similarly we can be sure that the numbers considered in the second term are seperated by the number $2^{j+2} - 1$ (the binary representation of this number is just $j + 1$ ones so this number is bad). For the third term the guaranteed bad number is $2^{j+3} - 1$, for the fourth its $2^{j+4} - 1$ and so on. This was also my intution for this dp. To somehow formulate the formula for dp such that all the terms are seperated by bad numbers. This dp yields a complexity of $O(log(n)^3)$ and it can be optimized to $O(log(n)^2)$ with prefix sums but it is not necessary to pass the TL.You can use this DP to solve the rest of the problem in the same way as the authors did but my approach is a bit simpler in my opinion (though I think they are fundementally the same).Step one: check if the smallest number with more than $k$ bits ($2^{k+1} - 1$) is greater than $n$, if that is true, then add add $g(n)$ to the answer and terminate.Otherwise we go to the highest bit of $n$. Let's say that is the $b$-th bit. We add the subbarays not containing the bit to the answer, the number of which is $dp(b, k)$. Then, we reduce $k$ by 1 and $n$ by $2^b$ since every other solution will include the $b$-th bit. Now we go back to step one and repeat until $n$ is zero or code is terminated in step one. We can be sure that the numbers included in the subbarays for each step are not neighbouring because of similar reasoning to the DP. The biggest number considered in the range (which is just a sequence of $1$-s in binary), seperates them. If there aren't more than $k$ bits the code terminates at step one, so we can be sure that everything is nice and seperated.Here is my code. code
•  » » 2 weeks ago, # ^ |   +5 Thank you very much for the detailed explanation. dp(i, j) = g(2^(k + 1) — 1) + ... should be dp(i, j) = g(2^(j + 1) — 1) + ...
•  » » » 2 weeks ago, # ^ |   0 Yes, thank you. I will correct it.
 » 3 weeks ago, # |   +3 In problem D, it is mentioned that, checking D mod gcd(d1,d2,…,dq)=0 is sufficient to test the existence of the solution for the equation c1⋅d1+c2⋅d2+⋯+cq⋅dq=D. Is it any proved theorem or intuition? Can any one explain this?
 » 2 weeks ago, # |   0 problem c) https://mirror.codeforces.com/contest/1982/submission/267544904 why is it failing on other tests
 » 2 weeks ago, # |   0 Please someone explain what the below lines do in code of solution E? if (s1 == e1 && s1 != 0){ s_cur = (s1 + s2); } if (s2 == e2 && s2 != 0){ e_cur = (e1 + e2); } 
 » 2 weeks ago, # |   0 Am i the only one who found F very easy for its position?
 » 2 weeks ago, # |   0 I have been accounted for cheating in question B. I am really not aware that using third party websites as code editor is a violation. I just came to know that once I have received mail regarding plagiarism. I assure that this will not repeated and I kindly request not to skip me in the upcoming contests. I hope my request will be considered.
»
2 weeks ago, # |
0

# define ll long long

using namespace std;

int main(){ int t; cin>>t; while(t--){ ll n,l,r; cin>>n>>l>>r; vectorv(n); for(ll i=0;i<n;i++){ cin>>v[i]; } reverse(v.begin(),v.end()); stackst; for(ll vl:v)st.push(vl);

ll sum=0,cnt=0;

while(!st.empty()){

sum+=st.top();

if(sum>r){

sum=st.top();

}

if(sum>=l&&sum<=r){
sum=0;
cnt++;
}

st.pop();

} cout<<cnt<<endl;

}

} help me to get the corner case

 » 2 weeks ago, # |   0 Can someone share the greedy solution of problem COr you can show the mistake of my solutionLink to submission
•  » » 2 weeks ago, # ^ |   0 267918536Here you go Hope it helps.
 » 2 weeks ago, # | ← Rev. 2 →   0 please help me to understand why equation in problem D looks like thatc[1] * d[1] + c[2] * d[2] + c[i] * d[i] = Dshouldnt it be:c[1] * d[1] + c[2] * d[2] + c[i] * d[i] = -Dbecause D is equal heights of mountains without snowy caps — heights of mountains with snowy caps and we want D to be 0, therefore, when we go through an n X m matrix considering every k X k submatrix we count how many there are mountains without snowy caps and we add that quantity multiplied by some c[i], after that we substract quantitiy of mountains with snowy caps multiplied by c[i] that means we want D + NOT_SNOWY * c[i] — SNOWY * c[i] = D + (NOT_SNOWY — SNOWY) * c[i] = D + d[i] * c[i] to be equal to 0hence D + d[1] * c[1] + d[2] * c[2] + d[2] * c[2] = 0 => d[1] * c[1] + d[2] * c[2] + d[i] * c[i] = -Dwhere am I making a mistake?
 » 2 weeks ago, # |   0 Is there any other way to solve this problem besides the method provided in the editorial? If you are not from a math background, guessing that method is pretty difficult. Are there any other possible solutions, like using dynamic programming?I realized that if we calculate the net difference of the types of mountains in each k*k matrix, then the question can be the same as finding the sum of h (total difference between the height of two types of mountains) using n(net difference between types of mountain in each k*k matrix) values, which can be added or subtracted to make the sum of h.
 » 2 weeks ago, # |   0 Any help with this?? https://mirror.codeforces.com/blog/entry/130850
 » 2 weeks ago, # |   0 For E problem - In the given test case 576460752303423268 59 (The last one)int mod = 1e9+7; The answer is just (C(n, 2)%mod + n%mod)%mod But I think my code is doing something wrong while calculating C(n, 2)%modAnd the final answer that I'm getting is 777901708. If anyone has solved it, can they tell me if there is some catch or a different method to calculate this?PS: I took help from stack overflow for getting the (nCr % p) value for big values of n.Thank You
 » 2 weeks ago, # |   0 Could I get some help please? The sample test case for small numbers seems to pass but not for big numbers ex: With input: 795569939321040850 56 it returns 332746568 instead of 741136395`Submission #: 267926843Thanks!
 » 2 weeks ago, # |   0 can anyone please figure it out, whats wrong with this code? I implemented exactly the way it's given in the editorial . still getting WA in test case 4(426th token) submission:https://mirror.codeforces.com/contest/1982/submission/267948051
 » 2 weeks ago, # | ← Rev. 3 →   0 .
 » 2 weeks ago, # |   0 Can someone please figure out why my code isn't accepting? Here is the submission linkhttps://mirror.codeforces.com/contest/1982/submission/268111102
 » 12 days ago, # |   0 Good round
 » 8 days ago, # |   0 Can someone tell me how to do problem E using technique meet in the middle?
 » 22 hours ago, # |   0 It is able to also do F using the formula that, if we treat $a_1, a_2, ..., a_n$ as array $\text{argmax}_{L} a_{1..L} = \text{sorted}(a)_{1..L} = X + Y$where $X$ is the largest index $i$ such that for all $j \leq i$, $\text{argmax}_{k} (v_j = v_k) - \text{#}[x : x \leq v_j] = 0$, and $Y$ is the "tail", which is, if $a[X+1]$ is directly following $a[X]$ in the array, $Y$ is the $\text{argmax}_T \ \ {a_{X+1}=a_{X+2}=...=a_{X+Y}}$The two parts of $X$ can be maintained in a lazy propagated walkable (binary searching) segment tree, and $Y$ can be also use another segment tree to find, or can build one without having lazy prop. Range queries can using BIT. I used two lazy prop (even though $Y$ don't need) so have to use fast IO to speed up sth, especially when outputing the 2e6 datas...https://mirror.codeforces.com/contest/1982/submission/270269570