### Gheal's blog

By Gheal, history, 7 months ago, Author: Gheal

Hints
Solution
Code (C++)
Rate Problem

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

## C — Zero Sum Prefixes

Idea: Gheal, Solution: IgorI

Hints
Solution
Code(C++)
Rate problem

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

## F — Circular Xor Reversal

Idea: Gheal, Solution: IgorI

Hints
Solution
Code(C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me in the comments. Tutorial of Codeforces Round 833 (Div. 2) Comments (164)
 » Good Round! Thanks for the fast editorial!
•  » » bro how to achieve graph like you what are you doing
•  » » » They had probably done CP on other websites before starting on Cofedorces, or at least they had had experience with math and problem solving in programming, maybe also some algorithms.
•  » » » » Actually I believe it's an alt bro
 » 7 months ago, # | ← Rev. 2 →   My Solution for D:Check no solution:Note $cal(x)=max(i),2^i|x$,if $cal(d)>min(cal(a),cal(b))$,no solution.Otherwise,Let's construct the solution.First,let $d»=cal(d),a»=cal(d),b»=cal(d)$,calculate the $x$ for the new $a,b,d$.When outputting the answer, we only need to output $2^{cal(d)}x$.How to construct such $x$?The key point is make $x=(2^{key}-1)+2^{key}X$,($key=30-cal(d)$).This is actually a problem of solving congruence equations:$(2^{key}-1)+2^{key}X=0(mod\space d)$,use exgcd to get such $X$.
•  » » 7 months ago, # ^ | ← Rev. 2 →   Here is another solution for D:If $min(lsb(a),lsb(b))=lsb(d)$ so their $lsb$ can never be equal. Hence, they can't also be equal.Otherwise; let $ans = 0$ initially, we want to fill bits of $ans$ such that it will be multiple of d, and $ans$ will be *superset of $a|b$.Let's iterate over bits of $ans$ $0$ to $29$If $i$'th bit of $ans$ is $0$ then add $d * (2^{i-lsb(d)})$ to $ans$. Now that bit will be $1$ and it will contain $a|b$ anyway.Since $d$ has at most $30$ bits and our target is to fill first $30$ bits and there must be an intersection, our answer will require at most $30+30-1=59$ bits and this fits constraints!Here is my submission.(*Note : $X$ is superset of $Y$ if $Y$ is subset of $X$.)
•  » » » 7 months ago, # ^ | ← Rev. 2 →   tallbee23 "If i'th bit .... contain a|b anyway." Can you please explain this line? Like how did you come up with this approach?
•  » » » » If $i$'th bit of $ans$ is $0$, when we add $d*(2^{i-lsb(d)}$ to $ans$, actually we shifted $d$ to intersect $lsb(d)$ with that bit. Since $lsb(d)=2^{i}$ and $2^i$ & $ans = 0$ after shifting, if we gather them then $i$'th bit will be $1$. Since we filled first $30$ bits with $1$, it will be superset of $a|b$.Actually first $30$ bits except bits that is smaller than $lsb(d)$ are $1$. But since $lsb(d) \le lsb(a|b)$, it is meaningless. There is no bit such that $bit$ & $(a|b) = 1$ and $bit$ & $ans = 0$. I wrote above comment incorrectly you must to start from $lsb(d)$ instead of $0$ but when coding it, (1LL<
 » Problem D can also be solved using Chinese Remainder Theorem. First step is the same as stated in solution given above: proccess cases, when answer is -1, and then you can just find X, s.t. X = a|b (mod 2^30), and X = 0 (mod d'). Where d' comes from d = 2^i * d', where d' is odd. The answer is under 2^60, since 2^30*d < 2^30*2^30 = 2^60
•  » » I used the same approach as yours but getting wrong answer. if p=a|b and prod=(1l<<30)*d, i used x=p*(prod/(1l<<30))*inv(prod/(1l<<30))%(1l<<30)+d*(prod/d)*inv(prod/d)%dx%=prod181039686
•  » » 7 months ago, # ^ | ← Rev. 2 →   Can you explain the crt method in your code? I did like usual chinese remainder theorem and to take an account that x is congruent to 0 mod d. I took the remainder 0 as d and did normal chinese remainder theorem. It did not work. I saw that you are doing something in reverse fashion, but could not understand it. I appreciate your idea anyway! Thanks and eagerly waiting for your reply and my submission is at above comment.
•  » » » Basically, I used Garner's alrorithm for 2 co-prime numbers: d' and 2^30. You can read more about that here: https://cp-algorithms.com/algebra/chinese-remainder-theorem.html#garners-algorithm I don't really know what is wrong with your formula above, since it's quite messy, but maybe you can find your mistake by reading this article
•  » » » » oh, this is something new. Thanks for sharing this!
•  » » » » I finally got AC using your approach and normal congruence relation.We have two congruence equations as x=(a|b)mod(1l<<30) ---> 1x=0mod(d') ---> 2That means x=d'*k, replacing this in 1 givesd'*k=(a|b)mod(1l<<30)k=(a|b)(1/d')mod(1l<<30)Solve this we can find k and k*d is the answerHope it might help someone.Today i learned that if we have remainder 0 in chinese remainder theorem we can convert x into multiple of that modulus and solve it instead of doing normal chinese remainder theorem which might yield a wrong answer.181131228
•  » » » » » I think you are getting something wrong. There is only 1 chinese remainder theorem, but there is also an algorithm to construct the number from remainders modulo co-prime set of numbers. Chinese remainder theorem works for any remainders, as long as they are remainders modulo co-prime set of numbers. I don't understand what is normal chinese remainder theorem you are referring to.
•  » » » » » » 7 months ago, # ^ | ← Rev. 3 →   I also used chinese remainder theorem, By normal i mean without changing x(but for some reason it did not work). What worked is after changing x to k*d'Not worked: Using chinese remainder theorem: 181039686Worked: Using chinese remainder theorem but changing x to k*d' : 181131228I could not find the mistake i made and i clearly stated in my previous comments. But after changing the equations it worked, i don't know why.
•  » » » » » » » Take a look at Ticket 16436 from CF Stress for a counter example.
•  » » thx, got x * 2^30 + (a|b) = 0 (or d) mod d => x * 2^30 = (d — (a|b) % d) mod d => x * 2^30 = c => x = c * inv(2^30,d)
 » I think the problem b was difficult than usual.
•  » » agree
 » Huge gap between A and B.
•  » » next time we will give all problems to have *800 so there won't be any impediments for people to AK
 » Problem A is so dumb, just look at it, a lot of people did it under 1 minute, which is time to read the statement alone. Its enough just to go to test cases and see the STUPID pattern
•  » » 7 months ago, # ^ | ← Rev. 3 →   I agree. I do not understand why problemsetters include such problems. Such tasks punish participants who take the time to properly solve the problem (e.g. work out a few sample cases on their own, and figure out the $\lceil n/2\rceil$ relationship, rather than relying on sample cases to do it for you). Competitive programming should not be like this in my opinion.
•  » » Some would say pattern recognition is part of problem solving
 » I had the O(100*n) solution for B TLE: https://codeforces.com/contest/1748/submission/180630056 How come?
•  » » Same for C linear solution TLE: https://codeforces.com/contest/1748/submission/180643204
•  » » » python is so slow
•  » » » For C it's most likely this: https://codeforces.com/blog/entry/62393testcase 8 I think is an anti hash test that's designed to cause as many collisions as possible in your dictionary setup. This results in the dictionary taking O(n) per lookup causing TLE.For B I'm not entirely sure what's causing TLE but I don't think you need .strip for n and s. I also converted s from string to an int array initially so I wouldn't need to convert each character into int type excessively.
•  » » » » 181003922Getting TLE on Linear solution for Problem C: Test Case 7Have used unordered_map. If not to use hashing, then how to solve this one?
•  » » » » » https://codeforces.com/blog/entry/62393Looking at it test case 7 is also an anti hash test, specifically for c++ unordered map. you can still use hashing here but you you just need to define a custom hash function to reduce collisions.
•  » » » » » » Thank you for the reply. I have understood this now.
•  » » » I'm pretty sure it's because you're doing max(d.values()). That's an inefficient implementation because the max operation is O(n). Instead, try maintaining a variable for the max value in the dictionary and see if that passes.
•  » » You're checking if current digit's freq is greater than 10 or not, it could be possible that it is repeated only once, in this case you will check for all substrings (not just 100). You need a length check instead of individual digit's freq check.
•  » » » you think the solution is wrong? how did it pass all the 100 tests before the tle?
•  » » » » It isn't wrong. It's just inefficient. Replace the freq check with length check and it will produce the exact same output with less iterations.
•  » » » https://codeforces.com/contest/1748/submission/180679051 Can you say where am i suppose to doing error , it gives me WA in testcase 2
•  » » 7 months ago, # ^ | ← Rev. 3 →   you should try to define print = sys.stdout.write, it may decrease the time and instead of checking mx > 10, check if mx <= different values which is easily to find
•  » » I submitted your B with PyPy3, and it passed as usual, use PyPy if you're competing with Python
•  » » » So that's how it is, so funny
•  » » Python is not very fast. It can be accelerated. Go to my profile, I sent the problem with your complete solution (after the round). Only I used acceleration. It went in a time that is 10 times less than the maximum.
•  » » Unfortunately, yes this contest is not suitable for python users, I was skeptical of both B and C, even though my idea was same. B bcoz its 10^7 operations, C bcoz it uses dictionary
•  » » Python is extremely slow on looping. While 1e8~1e9 loop iterations are acceptable with C++, in python this number is about 1e6~1e7.
 » 7 months ago, # | ← Rev. 2 →   E is easy but I have no time :(use cartesian-tree and dp.
•  » » Looking at Um_nik's screencast, he only used 3 minutes (13:00 to 16:00) to read/think and 7 mins (16:00 to 23:00) to implement for E: https://www.youtube.com/watch?v=zdlrEs78gEQ&t=1004sMakes me feel bad that I gave up 30 minutes into the contest and solved nothing else because I kept coming up with hard to implement solutions and thought I wouldn't have time (even though I had over an hour left). There's always enough time, just gotta gitgud
 » is it possible to solve B in python 3 , I see no accepted solutions. would be greatly appreciated if someone can help me with it. thanks
•  » » Check the solutions under PyPy3
 » Wow so fast tutorials .Great Contest .Problems were great . Thank u :)
 » 7 months ago, # | ← Rev. 2 →   I dont know why I'm experiencing a TLE for this code on my last pretest for problem C T_T any idea?? for _ in range(int(input())): n = int(input()) arr = list(map(int, input().split())) s = 0 res = 0 flag = 0 d = {} maxi = 0 for i in arr: s += i if flag == 0 and s == 0 and i != 0: res += 1 if i == 0 and flag == 0: d[s] = 1 flag = 1 maxi = 1 elif i == 0 and flag: res += maxi s = 0 d = {} d = 1 maxi = 1 elif flag: if s in d: d[s] += 1 else: d[s] = 1 if d[s] > maxi: maxi = d[s] res += maxi print(res) 
•  » » python is so slow
•  » »
•  » » Just use the pypy3
•  » » 7 months ago, # ^ | ← Rev. 2 →   Actually, the hash seems to matter here too. Idk the exact reason, but my O(n) code got accepted when I only changed the hash (thanks @DrMrogon https://codeforces.com/contest/1748/submission/180659676).Before (TLE on test 8): https://codeforces.com/contest/1748/submission/180682651 After (Accepted): https://codeforces.com/contest/1748/submission/180683231
•  » » my python3 code alse TLE even on pypy3,no idea why from collections import * t=int(input()) for i in range(t): n=int(input()) arr=list(map(int,input().split())) cc0=[a for a in range(n) if not arr[a]] cc0.append(n) ans=0 s=0 for j in range(cc0): s+=arr[j] if not s: ans+=1 for j in range(1,len(cc0)): count=Counter() s=0 for k in range(cc0[j-1],cc0[j]): s+=arr[k] count[s]+=1 ans+=max(count.values()) print(ans) 
•  » » 7 months ago, # ^ | ← Rev. 2 →   well,i changed the number to str and count in dictionary and then accepted like this: t=int(input()) for i in range(t): n=int(input()) arr=list(map(int,input().split())) cc0=[a for a in range(n) if not arr[a]] cc0.append(n) ans=0 s=0 for j in range(cc0): s+=arr[j] if not s: ans+=1 for j in range(1,len(cc0)): # count=Counter() dic={} s=0 for k in range(cc0[j-1],cc0[j]): s+=arr[k] ss=str(s) dic[ss]=1 if ss not in dic else dic[ss]+1 ans+=max(dic.values()) print(ans) 
 » Really nice round. I had guessed that if $min(lsb(a), lsb(b)) < lsb(d)$, it might be impossible in problem D but can't prove it. Could someone provide a proof of why that is always true?
•  » » $lsb(kd) \ge lsb(d)$ for any natural number $k$, i think?but $min(lsb(a),lsb(b)) •  » » » I have proved it thanks to you. <3 •  » » » » please, can you share your proof? •  » » » » » 7 months ago, # ^ | ← Rev. 2 → Do the multiplication in binary, we multiply the decimal number$a$and$b$, you will notice that the first bit which is set in the binary representation of the product is at least$max(lsb(a), lsb(b))$.The$a$and$b$above are just for proof, don't confuse it with the$a$and$b$of problem.With this, we can conclude that if$min(lsb(a | x), lsb(b | x)) \ge lsb(d)$else it's impossible. •  » » » » » a|x and b|x should be of some form like k*d if they are divisible by d but if min(lsb(a), lsb(b))=lsb(d) => min(lsb(a), lsb(b))  » Am I the only one who stupidly used Euler's Theorem to find inverse modulo in D? •  » » lol i do this every single time i need inverse modulo))  » Can anyone explain me why am I getting TLE in Problem C here's my code https://codeforces.com/contest/1748/submission/180659944 •  » » Because of unordered_map.. change it to map only •  » » » After changing to map it got accepted but why ? I mean with unordered_map wasn't it O(n) and map O(nlogn) •  » » » » Unordered map can be forced to operate in O(n^2).Refer to this https://codeforces.com/blog/entry/62393 •  » » » » In worst case searching/insertion take o(n) time .. so ur complexity become o(n^2). •  » » 6 months ago, # ^ | ← Rev. 2 → I choose GNU C++20 11.2.0(64 bit, winlibs) when I submit your code, and it's ok.  » My solution for B: for each i such that 1<=i<=n we find for each possible number of distinct elements what is the range L,R where this occurs. Then for each range we check where is the first index j such that the subarray [i,j] is bad, and subract R-j+1 from all possible subarrays. Time complexity is O(100nlogn) because we can find the ranges and check for bad subarrays using binary search. You can check my code to understand more  » whats the expected rating for B?  » Thanks for the fast editorial. I quite liked problems A-C. However, on problem D I feel like there should have been a constraint that D is a prime that is not 2. Because most of the ideas from D still apply, but finding the modular inverse is much easier. Or it could have also been split into an easier and harder version, with the easier one having D as a prime. I feel that C-D gap was quite large. •  » » You can calculate composite inverses in$O(\log{m})$as well. https://codeforces.com/blog/entry/103374?#comment-917844 •  » » I got AC using Euler's theorem. but the complexity was O(t * sqrt(d)). It would not be good to split this problem into two versions. They would be almost the same. •  » » Why? We can simply use extended euclidean algorithm or a Euler's theorem right? •  » » » Yes, but that is much less known than modular inverse for prime modulo. And all other observations are more or less the same.  » can anyone please explain problem B... •  » » There are only 10 types of numbers, so the longest enumeration in a sequence is 100, and violence is sufficient •  » » we can only have 10 distinct characters [0..9], so at max each can be repeated 10 times, so max length of diverse string can't be more than 100.but the implemented solution is not straight forward.for each i in [0..n], we are finding maximum x, in (i..n], such that sub array [i,x] has all of its character's frequency<=10, because it can't be diverse as per hints and above logic. while finding we are also updating maximum frequency of all characters and number of distinct characters each time, and also checking if in current state has distinct>=max_freq if so then we can say sub array from [0..j] is diverse. this is run length counting, counting while running ^_^  » 1 second is too small for B, do better next time.  » I cant solve b during contest, but still I think that it was a nice problem •  » » Yeah I mean i am not able to solve B and C but this round teaches me some new concept .  » 7 months ago, # | ← Rev. 2 → Good and challenging round,tnx for the fast editorial. <3  » 7 months ago, # | ← Rev. 2 → I think my solution for D is somewhat simpler (at least for me) to understand:First, it is impossible if the (where$lsb$is the least significant bit)$lsb(a) \leq lsb(d)$or$lsb(b) \leq lsb(d)$because we are trying to find an$x$such that$a|x$and$b|x$are both multiples of$d$. When we multiply a number$h$by another$k$and look at the result in binary, the result is the sum of multiplying the first by each of the bits of the second, which would imply that$lsb(h*k) \geq lsb(h)$and$lsb(h*k) \geq lsb(k)$.After we figure this out and deal with that case, the rest is easy. First lets say$m_i$is the$i_{th}$bit of$m$. We want to find a multiple of$d$(lets call it$k$) where there is no bit$i$such that$x_i=1$and$k_i=0$. If we find this then all we need to do is apply a bitwise OR to$x$in order to make$x=k$. This is always possible through the following algorithm:Lets make$x=a|b$and$k=d$initally, then we iterate through the bits of both,If$x_i=k_i$then we can can ignore this bit.If$x_i=1$and$k_i=0$we can left shift$d$some number of times until the$lsb(d)$is at the$i_{th}$bit and then add this to$k$. This would not change any of the bits that we have already iterated over, would maintain that$k$is a multiple of$d$, and would make$k_i=1$.Now, there is no bit$i$where$x_i=1$and$k_i=0$, so we can just make$x = k$by making$x=x|k$Im pretty sure this is a naive solution compared to one using a single eqution but still I enjoyed coming up with it and think it is a little easier to understand. •  » » I was having a very hard time understanding it Now I get it after reading your comment...really thx <3 •  » » Could u plz say what's does curr+=e does in ur code? •  » » » e was$d$but right shifted until the$lsb(d)$was at the first bit. The way I iterated through the bits of$k$was by using a temporary variable for it and right shifting it continuously, only looking at it's first bit. So curr+=e is the same as adding$d$to$k$like I described in my solution.My implementation was quite messy though because I rushed it before the contest ended so I wouldn't really bother trying to understand it. •  » » » » Thanks a lot...Got it.... •  » » We want to find a multiple of d (lets call it k) where there is no bit i such that xi=1 and ki=0.Why do we want to do this? •  » » » Because then we can make$x=k$which would imply that$x$is a multiple of$d$. I am also assuming that$x=a|b$initally so this would then imply that$a|x$and$b|x$are both divisible by$d$. •  » » Your solution really deserve to be the editorial for this problem instead of the huge misleading equations of the official editorial, Thanks. rfhalb  » I did floor(ceil(n/2)) for problem A,(took n as double). Disappointed after seeing the simple (n+1)/2 solution as I failed to recognize pattern through testcase. •  » » Actually they are the same concept .ceil(n,k) is (n+k-1)/kif k==2 ceil(n,2) is (n+1)/2 That's all.floor is the normal dividing : floor(n/k) is n/k •  » » » Ayy Tx  » In problem F the number of operations can be improved from$\frac{3}{2} m^2 + O(m)$to$\frac{5}{4} m^2 + O(m)$.Similarly to$f(i, j)$in the editorial we can define$g(i, j, l)$as a sequence of operations that performs xor-assignments$a_i = a_i \oplus a_{j+l-1}$,$a_{i+1} = a_{i+1} \oplus a_{j+l-2}$, ...,$a_{i+l-1} = a_{i+l-1} \oplus a_{j}$, where indices are cyclic modulo$n$and cyclic segments$[i, i + l - 1]$and$[j, j + l - 1]$do not intersect. This sequence is the same as$f(i, j + l)$when$l \equiv j - i$and otherwise ends with 3 passes between$i + l - 1$and$j$to clean up the mess. Defining$h(i, j, l)$as a sequence of operations that reverse-swaps such two segments,$h(i, j, l) = g(i, j, l) \mathbin\Vert g(j, i, l) \mathbin\Vert g(i, j, l)$,$\frac{3}{2} m^2$solution is$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$.But we don't have to drag$a_{n-1}$through the whole array to get to$a_0$. Essentially instead of$swap(a_0, a_{n-1})$we can perform$swap(a_{n-1}, a_0)$, then we replace two long passes and one short with two short passes and one long. Instead of$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$we split both segments, reverse-swap one pair though the middle of the array and the other through the ends. For example, taking$x = \lfloor\frac{n}{2}\rfloor$,$y = \lceil\frac{x}{2}\rceil$:$h(n - y, 0, y) \mathbin\Vert h(y, n - x, x - y)$.  » Hint 2 for problme D: Combined with the first hint, we can say that a triplet (a,b,d) has no solutions if min(lsb(a),lsb(b)) •  » » 7 months ago, # ^ | ← Rev. 2 → Does this mean that if a and b are even and d is odd then it should have no solution It's incorrect. There is a solution.If$a$and$b$are even, then their LSB of both are greater than 1.If$d$is odd, then its LSB is 1.$min(1, 1) < 1$Isn't true. Hence, there is a solution.If you are confused with the fact that if$min(lsb(a), lsb(b)) < lsb(d)$, then there is no solution., read below.Let$dq$be any multiple of$d$. And$k = lsb(d)$. You can see that$lsb(dq) \geq lsb(d)$. It can be easily seen by adding d itself in its binary representation. You can see that any multiple of$d$will have its bits on after or from$lsb(d)$.Let$m = a|x$. According to the problem, we require$m$to be some multiple of$d$. Since$m$will be forced to have on all bits that are on in$a$or$x$, then$m$will have the$lsb(a)$bit on. But we have seen that any multiple of$d$will have its bits on from or after its lsb. Hence, if$lsb(a) < lsb(d)$, then there is no solution, it's impossible to have any multiple of$d$that can have the$lsb(a)$on, since it's less than$lsb(d)$. So if$lsb(a) < lsb(d)$or$lsb(b) < lsb(d)$, then there is no solution.  » I use unordered_map in C, and I get TLE. •  » » Use map instead. Remember not to use unordered_map in cf. •  » » » I also get TLE by using map.... •  » » » » 7 months ago, # ^ | ← Rev. 2 → but I Accepted it by using map: 180658394 •  » » » Thank you for your advice.  » 7 months ago, # | ← Rev. 2 → I keep getting a "wrong" judgement on my Kotlin code even though I followed the example solution to a tee. Any hints? import kotlin.math.max import kotlin.math.min fun main() { val t = readLine()!!.toInt() (1..t).forEach { readLine() val s = readLine()!! var result = 0L (0..s.length-1).forEach [email protected] { fro -> // count how often each digit 0..9 has occurred so far val numOccur = MutableList(10) { 0 } // only substrings of length <= 100 can be diverse, otherwise maxOccur >= 11 is forced val maxTo = min(fro+1 + 100, s.length) var diversity = 0 var maxOccur = 0 (fro+1..maxTo).forEach [email protected] { to -> val idx = s[to - 1] - '0' numOccur[idx] += 1 // no matter what chars we add, it can never be diverse anymore // note that this also makes the above length-100 condition obsolete if (numOccur[idx] > 10) [email protected] diversity += if (numOccur[idx] == 1) 1 else 0 maxOccur = max(maxOccur, numOccur[idx]) result += if (diversity >= maxOccur) 1 else 0 } } println(result) } }  •  » » Apparently I need to replace [email protected] with [email protected]  » I'm not sure I'm right or not, but const number can't exist in$O()$(except$1$).The number of operations are$n\times10^2$but you can't say that the time complexity is$O(n\times10^2)$,maybe.And of course it is easy to understand, but I suggest to fix it due to rigour.If I'm wrong please figure out thx. •  » » I think$O(N \cdot 10^2)$is more concise than saying "$O(N \cdot a^2)$, where$a=10$is the alphabet size", even though it's not as rigorous.Nice observation though! •  » » 7 months ago, # ^ | ← Rev. 2 → me when worst case$n$is worst case$10^5$so my$O(n^3)$solution becomes$O((10^5)^3)$which is a constant so it is equal to$O(1)$so it enters any conceivable TL  » Is anyone able to provide a detailed youtube explanation in english for solution C? Struggling to get my head around it.. •  » » 7 months ago, # ^ | ← Rev. 3 → Is anyone able to let me know if my explanation is correct here? // Original Author: Gheal // Solution by: Gheal / CodeForces // Comments by: Nicholas #include #include using namespace std; typedef long long ll; // NOTE: // This is my attempt of trying to understand the code, if anyone find any // flaw in this please let me know, am keen to understand how this works. // Defining the max boundaries of the array as per the problem statement const ll MAXN=2e5+5; ll a[MAXN]; // Map to store the frequency of the sum of the subarrays as we iterate over // them map freq; void tc(){ ll n; cin>>n; // max frequency - most common sum found in the array // current sum - current sum of the array // answer - total number of subarrays which sum up to 0 ll maxfr=0,current_sum=0,ans=0; // found wildcard - basically when you find 0 bool found_wildcard=0; // Removing all contents of the frequency map freq.clear(); for(ll i=0;i>a[i]; // If the current element is 0 if(a[i]==0){ // If the previous element is 0 // OR // If we have found a 0 at all in this test case if(found_wildcard) { ans+=maxfr; } else { // If we have not found a 0, this is the first time // we will add the number of times that 0 occured (either by // itself or as a sum of all the numbers) ans+=freq; } // Mark that we have found a wildcard found_wildcard=1; maxfr=0; freq.clear(); } // Whether or not we find a wildcard - add to the current sum this value current_sum+=a[i]; // Max frequency is retrieving the higher of the two values - // the current max // OR // the frequency of the current sum maxfr=max(maxfr,++freq[current_sum]); } // NOTE: Needs clarification // If we found a wildcard - we will add all the times that we // found 0 as the total sum of the arrays if(found_wildcard) { ans+=maxfr; } // Otherwise - we will just add the number of time that 0 occurred else ans+=freq; cout<>t; while(t--) tc(); return 0; }   » 7 months ago, # | ← Rev. 3 → https://codeforces.com/contest/1748/submission/180639586#wa on #516th ... any help? •  » » Take a look at Ticket 16437 from CF Stress for a counter example. •  » » » already got it, but thanks!  » I finally became Master after this round. Thank you for the interesting problems.  » I feel like there's an error in editorial of problem C. It should be added$[s_{i_1}, s_{i_1 + 1}, \cdots, s_{i_2 - 1}]$in between$[s_1, s_2, \cdots, s_{i_1 - 1}]$and$[s_{i_2}, s_{i_2 + 1}, \cdots, s_{i_3 - 1}]$. Of course, it does not really matter, the pattern is obvious, I was just pointing it out. •  » » You're right, thanks for noticing. It's fixed now.  » I have a stupid and complicated solution for B https://codeforces.com/contest/1748/submission/180642025 time complexity O(n logn)  » I think the sample of D is a big hint. During the competition, I tried to convert the output of the last example into binary and found that the last 30 digits are all 1s, so I could find the solution. I think if the sample set the last 30 digits to be a|b, I must not be able to solve it.  » Editorial posted 3 weeks ago..  » how to solve d with exgcd（Extended Euclidean algorithm）?  » Have someone else solved C by dp? •  » » tried but wa if you know pls teach me •  » » » 7 months ago, # ^ | ← Rev. 2 → Consider$O(n^2)$dp:$dp(i)$-- maximum number of consecutive subsegments with zero sum you can get from the$i$-th prefix.$dp(i) = max_{j = 1...i} check(j, i) * dp(j - 1) + 1$where function$check(l, r)$is a boolean function which returns$1$if you could obtain subsegment$(l, r)$having zero sum. It is possible if and only if it contains$0$or if it has zero sum. You can consider these two cases and optimize dp: find previous zero left to position$i$and get something like prefix minimum, and for second case you can store in map optimum dp for every prefix sum value.  » 7 months ago, # | ← Rev. 4 → so my question is:the only difference is that in #1 I go from n-1 to 0 and #2 I go from 0 to n-1 •  » » i would be glad if anyone could help me! •  » » » you are doing something wrong on the way you access indexes. May be printing indexes would help •  » » have not gone through the code completely, but since we have to look at the prefix sums it makes sense that only one of them is ccorrect •  » » I guess I got it. The problem is that we need to count the most frequent sum on suffix, not on prefix. Thanks y'all!  » can someone explain greedy approach of c ? It sounds unintutive to me.  » This's a great round... and my first round in CF :)  » Balanced Substrings is too hard for a B  » can someone explain how is the score at index where a[i]==0 is independent from score at a[j] == 0 where j  » can someone explain the dp solution for qC?  » Can anyone explain why in problem "C — Zero Sum Prefixes" is c++ std::map (my test) more preferable than std::unordered_map (my time limit test)? Always thought that std::unordered_map should give constant time on all required operations but std::map — logarithmic. sorry for the newbie question. •  » » This blog explains the issues with std::unordered_map very well: https://codeforces.com/blog/entry/62393  » I participated from an alt but wanted to offer my feedback on the problems.A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually workedB — also alrightC — not very interesting, this problem does not need to existD — weird definition of an integer, this problem does not need to existE — annoying, this problem does not need to existF — incredibly annoying, I don't like this problem at all, i won't even try to solve itAm o problema mai calitativa:Dandu se un sir de operanzi cifre si operator ^ * | & ~ XOR + — / ** ! oplus, gasiti valoarea maxima a expresiei facand maximum k interschimbari.Marinush  » Can somebody help me with problem C? My submission is here : https://codeforces.com/contest/1748/submission/180749200 . I don't know why i get WA and tried to figure out a testcase to get me WA. I have tried many times but failed. Please help ):(.  » i did not understand the editorial for first problem,can anyone explain please???  » B problem is really hard as usual. I was surprised to see that B problem was 1400 rated..!!  » I participated from an alt but wanted to offer my feedback on the problems. A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked B — also alright C — not very interesting, this problem does not need to exist D — weird definition of an integer, this problem does not need to exist E — annoying, this problem does not need to exist F — incredibly annoying, I don't like this problem at all, i won't even try to solve it I have another solution for F: Bagi bulaneala pe vectori  » Good. A *3000 in Div.2.  » At Codeforces Round #833 (Div. 2)There is a case of cheating in the problem B A solution is available during the contest on YouTube https://youtu.be/0x9kKxfqLr8Matching solutions:- https://codeforces.com/contest/1748/submission/180650292https://codeforces.com/contest/1748/submission/180650184https://codeforces.com/contest/1748/submission/180649269https://codeforces.com/contest/1748/submission/180646072https://codeforces.com/contest/1748/submission/180646346https://codeforces.com/contest/1748/submission/180646263https://codeforces.com/contest/1748/submission/180646094https://codeforces.com/contest/1748/submission/180645940  » 7 months ago, # | ← Rev. 2 → Can someone tell why I'm getting Wrong Answer for Problem C, testcase 2, #410, please. Thanks https://codeforces.com/contest/1748/submission/181030747 •  » » Take a look at Ticket 16438 from CF Stress for a counter example. •  » » » Thanks a lot, didnt know about this website.  » For problem D, how can we say for sure that$x$will be of the form:$p11..11(30 - k \ times)00..00(k \ times)$ » In problem D: How can we prove that$x_{(2)}=p 1 1 1 … 1 0 0 … 0$is divisible by both a and b? Please, help!  » The data structure, described in the editorial for problem E, is called Cartesian tree. One can build it in O(N).  » How come in Problem B, not using ~~~~~ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ~~~~~ gives AC 181109995 but using this in code gives WA 181109865  » Guys I can't seem to find what's wrong with my code for problem C https://pastecode.io/s/6qmq0jkc please take a look •  » » Maybe you should iterate in subarray, not all element in the whole array. •  » » » No i got it, i forgot to check the case where there are no 0's in v or the case where prefix sum can be zero even before we encounter our 1st 0 in v[i].https://pastecode.io/s/yic81p8g  » Problem C Test 7 will block solutions using unordered_map, shit.  » 7 months ago, # | ← Rev. 3 → I came up with a different solution to problem E but it is not working (even on the first test case). I can't figure out what is wrong with my approach. I have described the idea below.Observationa[i] >= a[i + 1] implies b[i] >= b[i + 1]a[i] < a[i + 1] implies b[i] < b[i + 1]dp state: dp[i][j] = number of arrays with b[i] = j // base case for j: 1 ... m dp[j] = 1; // transition for i: 2 ... n for j: 1 ... m if(a[i - 1] >= a[i]) // then b[i - 1] must be greater than j as per observation for k: j ... m dp[i][j] += dp[i - 1][k] else for k: 1 ... j - 1 // then b[i - 1] must be lesser than j as per observation dp[i][j] += dp[i - 1][k] Below is a link to my submission with actual code (which optimizes the above pseudocode using a prefix sum array.181409754 •  » » Take a look at Ticket 16439 from CF Stress for a counter example.  » In problem D, there's this step in the explanation$p+1 ≡ (2^{−1})^{30−k} \mod d' ⇔ p+1 ≡ (\frac{d'+1}{2}) ^ {30−k} \mod d'$I don't understand where it comes from, like what property is being used or why this is done, can anybody help me please?  » 5 months ago, # | ← Rev. 2 → Still confused about C, consider a test case: 1 10 1 0 1 -1 1 0 1 1 -1 0 considering that i partition into subsegments then i will get answer as 5 here, but if i make replacements in subsegment for example: [0,1,-1,1]=[0,1,0,1]=-1(replace it with 0 in array)1 -1 1 -1 1 0 1 1 -1 0now [0,1,1,-1]=[0,1,2,1]=-1(replace with 0)1 -1 1 -1 1 -1 1 1 -1 0replace last with 0 with -prefix sum till ith index[1,-1,1,-1,1,-1,1,1,-1,-1]=[1,0,1,0,1,0,1,2,1,0]so after doing these operation according to subsegment i get answer 5 but if i change element to do dry run to see structure of array i get 4 zeros, is there anything wrong i did? or can you propose me some solution having 5 zeros? thanks in advance  » Why is my same code getting accepted in GNU G++17 7.3.0 and not in GNU G++20 11.2.0 (64 bit, winlibs) ? What's the difference between these two languages? GNU G++17 7.3.0 — 186674226 GNU G++20 11.2.0 (64 bit, winlibs) — 186674279  » For problem B, can anyone help me understand why this 188673953 is AC, but this 188673213 is WA?The AC one is simply starting from ans=0 and doing ans++ for each diverse substring. The WA one is the opposite. It starts with ans=(n*(n+1))/2 and doing ans--` for each non-diverse substring. •  » » 5 months ago, # ^ | ← Rev. 2 → Take a look at Ticket 16693 from CF Stress for a counter example.By the way, it's trivial to prove that your WA algorithm is incorrect. In your AC submission, you are iterating over all diverse substrings. In your WA submission, you iterate over all non-diverse substrings. So if I combine both of your solutions, I would be able to iterate over all$O(n^2)$substrings in$O(n)$time. A contradiction. The catch here is that the diverse substrings are scarce, and closer to$O(n)$, while their complement is abundant, of order$O(n^2)\$. That's why the subtraction strategy would result in TLE if implemented properly, or would undercount the non diverse substrings of length greater than 100 if implemented poorly.
•  » » » Thanks so much!
 » Awesome contest but most of us were late :)
 » In C can it happen that maximum frequency prefix of the subarray is such that for nullifying that prefix our ai exeeds the limit of 1e9 ?
•  » » My bad it can be any arbitary number.... i thought that just like initial ai new replaced ones should also lie b/w -1e9 and 1e9
 » D is such a nice problem man but there is something that I found very unintuitive about it and that is — why you filled all the digits before p and after k to be one. I mean the best thing I could arrive at after solving this problem for hours was that rather than filling up all of them with ones as you did I would fill it with a^b and I reched nowhere.