### 74TrAkToR's blog

By 74TrAkToR, history, 10 months ago,

Thanks for the participation!

• +21

 » 10 months ago, # | ← Rev. 2 →   +22 D can also be solved by using GCD convolution.
•  » » 10 months ago, # ^ |   0 That's true
•  » » 10 months ago, # ^ |   0 Can you please elaborate moreI read this article, and checked your solution, but I am confused, especially about this part: for(i=0;i<=n;i++) { b[i]=b[i]*b[i]; } gcd_convolution_inv(b); Aren't we supposed to get the 'dp' array (the same one as in the official solution) after the first convolution? Why square it? Why inverse?
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 I guess $b_i$ correspond to the number of occurrences of i.So if that's true, normal convolution process on $C=A \times B$ is like doing transform on $A,B$ and let $C_i=A_i \times B_i$, then doing inverse transform on $C$.So if you want to calculate the number of pairs $(i, j)$ such that $\gcd(a_i,a_j)=k$, so this equals to doing an gcd convolution on the cnt array, that is the array b.So as what I said above, doing a gcd convolution on b is what the code do.
•  » » 9 months ago, # ^ |   0 It's a wonderful solution and it's better than the Editorial!
 » 10 months ago, # |   0 i think i was tooo close to solve c. damn it , i will see it next time
•  » » 10 months ago, # ^ |   0 me too, bro, i've saw a similar problem in jscpc last year, but i forgot the progress
 » 10 months ago, # | ← Rev. 2 →   +2 It says tutorial is not available, so I'll write about what I solved myself.A: Digit sum can be found in $O(\log x)$. $y$ is at most $x + 2k$. Time complexity $O(k \log x)$.B: If there are $a$ digit with $1$ in the $k$ smallest digits, you can shift them all to the $k$ rightmost position to make a multiple of $2^{k-a}$. Try for all $k$, utilizing prefix sum to not make time complexity $O(n^2)$. Time complexity $O(n)$D: If there is an integer $x$ that $a_i$ and $a_j$ are both divisible by, then they are not good pairs, only if $x$ is present in $a$. However if $2$ and $3$ is present but $6$ is not, then you need to subtract duplicates in multiples of $6$. Therefore, you must use Inclusion-Exclusion, but exclusively on elements of $a$ and their multiples. Because $a_i$ is bounded by $n$, time complexity is $O(n \log n)$ due to the harmonic lemma.EDIT: Tutorial is up. You might better link it to the contest as well
•  » » 10 months ago, # ^ |   0 and their multiples damn, how did i not see that D:
•  » » » 10 months ago, # ^ |   0 Don't worry, I was bashing my head for 15 minutes on why my solution based on the mobius function doesn't work, then realized there are values outside $a$, fixed that, and bashed my head for another 15 minutes on why the solution is spitting $42$ on the last TC of examples
•  » » » » 10 months ago, # ^ |   0 Same. Realized after the contest that I was considering every gcd's. Should have considered the numbers present in the array only.
•  » » » » 10 months ago, # ^ |   0 I don't understand how you can generalize the mobius function for non-primes. Can you give explanation?
•  » » » » » 10 months ago, # ^ | ← Rev. 3 →   0 Read the discussion under this thread. If that discussion was not enough and you need some in-depth stuff, that type of transformation is often called the 'divisor möbius transform' (or simply the dirichlet inverse). If we use the divisor möbius transform on $\mathbf{1}$, the vector containing $1,0,0,0,0,\cdots$, you'll get the möbius function. If you use it on some other vector, we will result in some other 'function', which can then be used in our Inclusion-Exclusion.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Hi could you tell how to do that in O(n) for problem B. I got the idea like we need to move the ones from the last to zeros just before, but unable to implement it.I have seen one implementation (below) in which we only need to consider the movements of zeros, but not sure what are takeaways from this. void solve(){ int n; cin>>n; string s; cin>>s; int start = n-1, end = n-1; ll ans = 0; for(; end >= 0; end--){ while(start >= 0 && s[start] != '0') start--; if(start < 0) { cout<<"-1 "; continue; } ans += end-start; start--; cout<
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 you can store the positions of all the zeroes or maybe just iterate through the string to find the next zero and store that index ,say i, next time you need to find the index of a zero , start from i
•  » » » 7 months ago, # ^ |   0 void solve() { ll n; cin >> n; string s; cin >> s; ll zero = 0; ll ans = 0; reverse(s.begin(), s.end()); ll cnt = 0; for (int i = 0; i < n; i++) { if (s[i] == '0') { ans += (i — zero); cout << ans << " "; cnt++; zero++; } else if (s[i] == '1') continue; } while (cnt++ < n) cout << -1 << " "; cout << endl; } Easy solution to problem B...
•  » » » » 5 months ago, # ^ |   0 Sorry, I accidentally clicked the wrong one.I'm new to this site and I'm not very familiar with it.
•  » » » 7 months ago, # ^ |   0 What is your logic behind code? Thanks
•  » » 3 weeks ago, # ^ |   0 Your text to link here... I'd like to know why my code always times out, obviously I've restricted it to be able to output -1 directly as soon as the second pointer reaches n. Why on earth is this causing a timeout! Can you help me to solve the error of my answer?
•  » » » 3 weeks ago, # ^ |   0 Are you discussing question B?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Your linked solution will build a new bitset sized 200005 at most $t=10^4$ times, leading to $2\cdot 10^9$ bits allocated (of course, they are constantly freed, but they contribute to runtime).
 » 10 months ago, # |   0 fast editorial
 » 10 months ago, # |   0 thanks for fast editorial ! pE too hard and interesting !!
 » 10 months ago, # |   -7 what a hard div 2!
•  » » 10 months ago, # ^ |   0 I couldn't solve 2nd today, but I don't claim it to be hard or soft.
 » 10 months ago, # |   +1 I didn't solve C . But I cant realise the solution . someone help me to understand !
•  » » 10 months ago, # ^ |   0 I missed it too. I don't understand how in the solution, they say that the minimum will either occur at position 1 or position m. What if we have: (1, 1) (1, 2) (m-1, m) (m,m). Then the minimum will be any value between 2 and m-1, and the maximum will be either 1 or m, both possessing value 2.(Assuming m > 3 for simplicity of the example). I also don't quite see how that is necessary for their algorithm to work? The whole line sweep thing doesn't seem to require that fact either, right? It just requires the minimum to be outside of all the current open segments?
•  » » » 10 months ago, # ^ |   0 i don't get it too.. Can someone please explain the solution of C?
•  » » » » 10 months ago, # ^ | ← Rev. 3 →   +8 Oh shoot, I think I get it now. Maybe this restating/re-explanation will help others: For a given solution, there are multiple valid configurations of segments that achieve the same minimum/maximum delta. But for any optimal configuration, you can always tweak it so that the minimum is at position 1 or m. Imagine for a second that we are given a sample optimal configuration, with a minimum value at some index y, and a maximum at some index z, where y < z. But the minimum doesn't occur at index 1, which is to say y != 1. Then, since the value at y is less than the value at 1, we must have some segments included in our problem that include 1 as a starting index, but have an ending index of less than y. Since these segments can not add to our maximum, since y < z, we can remove them from our configuration and we still have an optimal configuration. Thus if your minimum index is less than your maximum index, we can transform your optimal configuration to possess a minimum at 1. The same logic is true if we have a minimum index greater than our maximum index, only in this case, we can create an optimal configuration with a minimum value at m. Now, given that it is always possible to get an optimal configuration with either 1 as the minimum or m as the minimum, we can sweep through and try either as the minimum. We can also always have a minimal configuration where the value at 1 or m is zero, because if there's a segment that covers the maximum index and the minimum index, removing it has no affect, and if it just covers the minimum index and other indices that aren't maximum, it must be removed in order for us to have an optimal configuration with that minimum index. Now, the line sweep is a way of finding the peak position when we have a minimum of 0 at 1 or at m, so we have two sweeps for that. Hope this helps and isn't too much word salad! If I'm missing anything, would be happy to hear from someone more knowledgable on this stuff. This was my first programming competition and this stuff seems quite interesting!
•  » » » » » 10 months ago, # ^ |   +1 since the value at y is smaller than the value at 1(if I am not wrong). Good explanation bud.
•  » » » » » » 10 months ago, # ^ |   0 Good catch, thanks! Sorry about that
•  » » » » » 9 months ago, # ^ |   0 excellent explaination！thanks！
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   0
•  » » » » » 9 months ago, # ^ |   0 thnx a lot..
•  » » 10 months ago, # ^ |   0 I tried to put comments in the code explaining the problem maybe you can get it from here — https://mirror.codeforces.com/contest/1884/submission/229341013
 » 10 months ago, # | ← Rev. 2 →   0 What's wrong in this solution for problem D — 229186378 ? Any help is appreciated.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I did the same ... cant figure out where it goes wrong ... did you find the error? UPD: nvm found the bug
•  » » 9 months ago, # ^ |   0 Take a look at Ticket 17110 from CF Stress for a counter example.
 » 10 months ago, # |   0 I would have become CM today. Screw sets bro.Submission for D using sets: (TLE >2000ms) https://mirror.codeforces.com/contest/1884/submission/229175001Submission for D with array: (AC ~700ms) https://mirror.codeforces.com/contest/1884/submission/229192264:(
•  » » 10 months ago, # ^ |   0 why use trees tho
•  » » » 10 months ago, # ^ |   0 Convenience, habit, underthinking, etc. Should have seen that coming though.
•  » » » » 10 months ago, # ^ |   0 I feel you brother. You'll goin to be CM in today's next contest no worries.
 » 10 months ago, # |   +2 In problem C, I cant understand why From this, it follows that the minimum will either occur at position 1 or at position mcan't the minimum occur somewhere in between
•  » » 10 months ago, # ^ |   0 we are only selecting segments that contain x
•  » » » 10 months ago, # ^ |   0 Consider this test :2 31 13 3Doesn't the minimum occur in 2-2?
•  » » » » 10 months ago, # ^ |   0 I think i get it now, the minimum may occur at any other place but if it occurs in a segment [l,r] along with max position x we can calculate if it can be ignored by either choosing to ignore segments starting from 1 or segments ending at m, if it cannot be ignored our answer does not worsen.
•  » » » » 9 months ago, # ^ |   0
•  » » 10 months ago, # ^ |   0 sort the relevant segments by the left point and by the right point, you'll see.
 » 10 months ago, # |   0 What is the reason behind the name of the second problem?
 » 10 months ago, # |   0 even though i couldnt solve any but problem A was beautiful
 » 10 months ago, # |   0 Can anyone pls help me identify my mistake in Div2D link? Any help would be appreciated.
•  » » 9 months ago, # ^ |   0 Take a look at Ticket 17112 from CF Stress for a counter example.
 » 10 months ago, # | ← Rev. 2 →   0 "Now let's understand which gcd values are not suitable. If there is a number x in the array (i.e., cntx>0 ), then all g multiples of x are not suitable"Can someone please elaborate the meaning of the above statement in the editorial for problem D? 'not suitable' for what?
•  » » 10 months ago, # ^ |   0 dp_g denotes the number of (i, j) for which gcd(a[i], a[j]) = gg is not suitable, indicating that g % a[i] == 0 exists in the array, and dp_g cannot accumulate to the answer
 » 10 months ago, # |   0 Can Someone Explain the Solution for Problem C. Most Importantly the Part From this, it follows that the minimum will either occur at position 1 or at position m
•  » » 10 months ago, # ^ |   +2 Imagine the selected segments. The maximum is reached somewhere, let's say at X.Now, there are two types of segments: Containing X: they are guaranteed to increase maximum (value at X) by 1, but may (or may not) also increase minimum by 1. So they are either good or neutral. Let's simply include them Not containing X: they are guaranteed not to change maximum (value at X), but may increase minimum. So they are either bad or neutral. Let's simply NOT include them So, we include all segments containing X (and only them). Now let's say X=6 (and all segments contain X). You can't have minimum at, say 3, because that would require that vs[2] > vs[3], so there is some segment, that contains 2, but not 3 — but that is impossible because all segments contain X (so segment containing 2 and X would also contain everything in-between including 3).Then we "brute force" all possible X's fast with Events:https://mirror.codeforces.com/blog/entry/121618?#comment-1080014
 » 10 months ago, # |   0 I am new to Competitive Programming. Is there any guideline for me? Any path I can follow?
 » 10 months ago, # |   0 There is a bit flaw in problem E's tutorial, in the second paragraph there should be b_{pos} not $b_pos$
 » 10 months ago, # | ← Rev. 3 →   +10 Here is another way to solve D.Let us call $f_x$ mean that is there $a_i$ is its factor.We can get the values in $\Theta(n\ln{n})$.And than we can get the answer: \begin{aligned} & \sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{\gcd(a_i,a_j)} \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(a_i,a_j)=d] \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(\frac{a_i}{d},\frac{a_j}{d})=1][d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n \varepsilon(\gcd(\frac{a_i}{d},\frac{a_j}{d}))[d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [d|a_i][d|a_j]\sum\limits_{t|\frac{a_i}{d}\bigwedge t|\frac{a_j}{d}} \mu(t)\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)\sum\limits_{i=1}^n\sum\limits_{j=1}^n [dt|a_i][dt|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)(\sum\limits_{i=1}^n[dt|a_i])^2\\ \end{aligned}The last $\sum$ we can solve it in $\Theta(n\ln{n})$.So we can solve the problem in $\Theta(n\ln{n})$.
 » 10 months ago, # |   0 Can anyone please show me why my code for B goes wrong
•  » » 9 months ago, # ^ |   0 Take a look at Ticket 17111 from CF Stress for a counter example.
 » 10 months ago, # |   0 Why this code gives wrong answer for problem D — 229186378
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Anyone? Why am I undercounting the number of non intersting pairs by above approach of op?For a number x in a(consider distinct as I've precalculated their frequency)cnew = #of multiples of x visited for the first time cprev=#of multiples of x which were already visited by some y
•  » » » 10 months ago, # ^ |   0 Same approach bud! That's giving me wrong answer on test 5.
•  » » 10 months ago, # ^ |   +3 hey check this test case1152 2 2 2 2 2 2 2 2 2 2 3 5 10 15ans=35our output=36Here we are not excluding the (10,15) pair as when iterating at 5 both 10 and 15 are already visited
 » 10 months ago, # |   0 Any small hint for D? I am stuck over 10 hours on it.I had some idea, but it ended up working 30 seconds on random data and up to 80 seconds on test #15 (2, 3, 4, 5 ... 1000000) — much better than naive O(N^3), but nearly not fast enough.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Think of the harmonic lemma, i.e. $\sum_{i=1}^n{n/i} = O(n \ln n)$. Find out how that relates to the bound on the values of $a_i$.
•  » » » 10 months ago, # ^ |   0 I already do.To be a bit more specific. I start by computing "base blockers": for example in case array contains both 4 and 12, we don't have to check any pair against 12, because if the pair is divisible by 12, it is also divisible by 4.Pseudocode here: for (int g in sorted-grouped(vs)) if (!excluded[g]) { base.push_pack(g) for (int i = 1; i*g <= n; i++) { if (counts[i*g] == 0) continue; excluded[g * i] = true; blocking[g].push(g*i) blockers[g*i].push(g); } } This works in sum(n/i) = N log NThen I for the most part do a stupid thing: for all possible "conflicts" ("baseBlocks" in code below) mark all conflicting elements one by one and keep track of the remaining number of unconflicting ones for (int g in sorted-grouped(vs)) unblockedCount = n; for (int baseBlock : blockers[g]) for (int toExclude : blocking[baseBlock]) if (blockedCount[toExclude] == 0) unblocked -= count[toExclude] blockedCount[toExclude]++; ans += counts[g] * unblockedCount ans /= 2 I cut(ed) out some optimizations which allow this thing to run somewhat fast (80s) instead of absolutely slow.
•  » » » » 10 months ago, # ^ |   0 For some value of $a_k$, the number of conflicts is $C \choose 2$, where $C$ is the number of occurrences of multiples of $a_k$. Apply the Inclusion-Exclusion theorem to this for prevent some conflicts being counted multiple times.
•  » » » » » 10 months ago, # ^ |   0 I thought about Inclusion-Exclusion, but couldn't come up with anything with it, because the formula grows rapidly depending on the number of sets. Just for 4, it is big: StackOverflowHere there seems to be up to ~8 sets (because 2*3*5*7*11*13*17*19 = 9699690 > 1000000, so "divisible by ~9+ 'various' numbers" sets are all empty), which is a lot.I guess, I'll think more in this direction. Thanks!
•  » » » » » 10 months ago, # ^ |   0 Implemented Inclusion-Exclusion: lon combinations = 0; function backtrack = [&](int l, lon p, int m, bool ne) { if (p > n) return; if (ne) { int c = divisibleBy[p]; lon combinationsChange = m * c * (lon)(c - 1); combinations += combinationsChange; } if (l >= base.size()) return; backtrack(l + 1, p, m, false); backtrack(l + 1, lcm(p, base[l]), -m, true); }; backtrack(0, 1, 1, true); cout << (combinations / 2) << endl; 'ne' (from NEw, but that is keyword) — whether we yet have to account for current combination'm' — swaps sign depending on the number of elements in the subset, to account for inclusion/exclusion'p' — LCM of the chosen subsetit works, but now I get Time Limit on test #9 ... Locally takes 110-200 seconds just for 50 000 elements. There are just too many possible subsets with LCM<=n. I hoped that there won't be too many because LCM might grow rapidly, close to multiplication, but overall I am not too surprised. Looks like this approach is exponential.
•  » » » » » » 10 months ago, # ^ | ← Rev. 5 →   0 That is kind of a "naive" inclusion-exclusion implementation, sometimes it works,but most of the time it really doesn't.The key to inclusion-exclusion (especially in number theory) is to "record the contribution" of that set. For example using the set operation, let's say that we want to find $|A \cup B \cup C|$. That is $|A|+|B|+|C|-|A \cap B|-|B \cap C|-|A \cap C|+|A \cap B \cap C|$. However we do not need to explicitly know this, we only need to record the contribution of $A$, $B$, $C$, etc. When counting the set $S$, find each subset $T \subset S$, and set $cont(T) \leftarrow cont(T)-cont(S)$. Initially This way, $A$, $B$, $C$ contribute by $1$, $A \cap B$, $B \cup C$, $A \cap C$ contribute by $1-2=-1$, and $A \cap B \cap C$ contributes by $1-3+3=1$. Things are automagically done. This can be generalized to superset operations as well (then can be naturally translated to zeta/mobius transform and then Subset/Superset/AND/OR/GCD/LCM convolution), but that's not a topic for this task anyways.Now apply this to number theory. In number theory, subsets/supersets are simply multiple/divisor relations. We know "multiples of $2k$" are subsets of "multiples of $2$", "multiples of $3k$" are subsets of "multiples of $3$", etc. So, start by setting the $cont(S)$ of everything as $1$. For each multiple of any value in $a$, do what I just described above. Then, we have the answer $z$ for non-good pairs. The answer for good pairs is simply ${n \choose 2} - z$. Time complexity is $O(n \ln n)$ due to the harmonic lemma.
•  » » » » » » » 10 months ago, # ^ |   0 Good news: After implementing my 3rd idea, I finally solved the task, largely with Inclusion-Exclusion, although differently. I used relation for 2 sets/properties, but "conditional": f( (a | b | c)&sub ) = f( (a | b)&sub ) + f(c&sub) - f( (a | b) & c&sub ) By f( (a | b | c)&sub ) I mean: "count of pairs, which satisfy property "sub" and satisfy at least one of properties "a", "b", "c". Properties are all of type "pair divisible by X".Then: the first part: f( (a | b)&sub ) is a main loop accumulator the second part: f(c&sub) is direct formula using precomputed array the third part: f( (a | b) & c&sub ) ... well ... this is a recursive call Finally, the recursive function has a "fast-track": in case "sub" property (numbers divisible by "sub") narrows down initial set to <= 40 numbers, it uses alternative N^2 * log N algorithm.The entire time complexity is O(god knows how much of N), but took 889ms on CodeForces. I kinda intuitively understand why this approach had a chance, but my previous two approaches also seemed to have a chance.You can glance at my code and see that I probably overcomplicated it.
•  » » » » » » » 10 months ago, # ^ |   0 Bad news: I still don't understand what you mean. After re-reading your comment several times, my impression is that you mean this kind of code: vector cont(n+1, 1); for (int base = 2; base <= n; base++) for (int k = 2; base*k <= n; k++) cont[base*k] -= cont[base]; Do I understand correctly? If so, what's the logic behind it? Seems absolutely random. There's gotta be something simple I don't see: too many people solved the task:)
•  » » » » » » » » 10 months ago, # ^ |   0 Yes, that's what I meant. It's kind of an "intuitive" thing. "If you counted $a$ then you don't want to count $2a$ or else you'll double count things", "If you counted $a$ and $b$ separately you need to subtract the count of $\text{lcm}(a,b)$ because they are counted twice" All these things have meanings compressed in this $cont$ array. What may be also interesting is, that $cont$ array where bases are all integers greater than $1$, is basically the Möbius function. Yes, we are reinventing many wheels here! The explanation there could give you some deeper insights into this. Or if you want how the code works, you can read 229166896. mu is the $cont$ array in my code.
•  » » » » » » » » » 10 months ago, # ^ |   0 I managed to gain some intuition for the 'cont' array: cont[i] is how many times we have "yet to account" for pairs where both numbers are divisible by 'i'.And I managed to (finally) solve the problem accordingly: https://mirror.codeforces.com/contest/1884/submission/229543303I have yet to: Think through how this specific case relates to the general case you described in the previous comment Analyse your code: looks like we still have some differences in how we account for specific divisors You solved this during the contest. How come you are blue instead of red?
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 "How come you are blue instead of red?" mostly due to unbalanced skillset. I absolutely suck at DP/brute force for example. I just managed to solve the task because I am probably overskilled at NT compared to other skills
•  » » » » » » » » » 10 months ago, # ^ |   0 DP is hard, because there are just so many possibilities what dynamics to compute. And I think this task is a perfect example of that: the solution (which is largely DP) ends up being short, but it's far from trivial to come up with the right DP here. cont array where bases are all integers greater than 1, is basically the Möbius function I was able to prove it based on this definition of the Mobius function. I actually came up with two independent proofs for it and very related Inclusion-Exclusion "sign change" (depending on how many sets intersection are being accounted for). Although I don't get an intuition for neither — are they supposed to be not entirely obvious? Thought through the general case from your previous comment And analyzed the details of how your solution works (fundamentally — the same as my last one). And also understood how the official solution works and coded it (my 5th, 3rd passing solution:) It's different — it computes good pairs directly I'm probably done with this task. Thanks a lot for your help! :)Now trying to come back to one of the tasks in my "solve later" list, which also seems to have some even more elaborate Inclusion-Exclusion.
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 chromate00 Bro, how/where did you learn number theory? Is there any source/book recommendation?
•  » » » » » » » » » 10 months ago, # ^ |   0 Mostly in material regarding MO problems. For CP this should be generally good enough though.
 » 10 months ago, # |   0 Can anyone explain E in detail? I cannot understand the editorial.
 » 10 months ago, # |   0 what is sweep algorithm mentioned in C?
•  » » 10 months ago, # ^ |   +4 It means that for each segment [l, r] we generate two "events": { l, "start" } { r, "end" } Then we sort them by location and process them (events, not original segments) left to right: "start" event: increase current segment count, also check if new best score is achieved "end" event: decrease current segment count Take a look at my solution, it should be quite readable
•  » » » 10 months ago, # ^ |   +1 okay got, it thanksI solved this by compressing the ranges https://mirror.codeforces.com/contest/1884/submission/229383481
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   +1 Interesting. At its core, it is similar to events: freq[mpp[l]]++; is like "start" freq[mpp[r]+1]--; is like "end" but I think events are more intuitive and end up being less code
 » 10 months ago, # | ← Rev. 2 →   0 I don't know why I get wa for D use inclusion-exclusion, who can help me
•  » » 9 months ago, # ^ |   0 Take a look at Ticket 17117 from CF Stress for a counter example.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 thinks for you,I have known why I get wa.
•  » » » 9 months ago, # ^ |   0 I get AC finally! grateful to your help!
 » 10 months ago, # |   0 Can anyone explain what is sweep line algorithm?
•  » » 10 months ago, # ^ |   0
 » 10 months ago, # |   0 Can anyone explain me how would we implement the logic of B problem as explained in editorial , like its easy to maintain cnt_1 and sum_1 but how would we find cnt_1 number of zeroes after every index ? I tried storing the indisces in a vector and then find the sum of first cnt_1 for every index but that gave me a TLE. Someone pls explain
•  » » 10 months ago, # ^ |   0 You compute prefix/suffix sum. Something like this: vector prefix1(n+1); for (int i = 0; i < n; i++) prefix1[i+1] = prefix1[i] + (s[i] == '1'); // ... later prefix1[b] - prefix[a] // number of 1s between 'a' and 'b' (not inclusive 'b') vector suffix0(n+1); for (int i = n-1; i >= 0; i--) suffix0[i] = suffix0[i+1] + (s[i] == '0'); // ... later suffix0[a] - suffix0[b] // number of 0s between 'a' and 'b' (not inclusive 'b') You don't need to compute prefix/suffix sum in this case (I didn't — note that I moved the opposite direction though — right to left), but it might be easier to solve with them sometimes
 » 10 months ago, # |   0 I believe I have a solution for E that differs slightly from the editorial. We also consider the inverted array $B$. Let $f(l, r)$ be the cost to reduce $B[l, r]$ to all zeros. If we could compute the prefix/suffix values $f(1, i)$ and $f(i, N)$, we could compute the $i$'th answer as $f(i, N) + f(1, i-1)$. Note this doesn't necessarily work because we might have to consider wrapping around the end of the array--consider an array like 2 0 1, for instance. However, the prefixes/suffixes can be computed independently if $B_1 = 0$, and since $B$ always contains a $0$, we can rotate $B$ such that $B_1 = 0$.Thus the problem reduces to finding the values of $f(1, i)$ ($f(i, N)$ can be computed in the same manner by reversing $B$). We process them in increasing order of $i$. The number of operations is just $\sum_{j=1}^i \max(0, B_j - B_{j-1})$. The cost can be maintained using a monotonic stack.
 » 10 months ago, # |   0 got stuck on A for half the comp because i missed k <= 10 and tried finding ways to optimize the solution... I need to be more careful.
 » 10 months ago, # | ← Rev. 2 →   0 can anyone please debug my code for the problem C(counting rythm). It is giving wrong solution on test case 3..I can't figure out that hidden test case. Below is the code -> int n,m; cin>>n>>m; `set index; map end; map> start; for(int i=0; i>l>>r; index.insert(l); index.insert(r); start[l].first++; end[r]++; if(r==m) start[l].second++; } ll cnt1 = 0, cnt2 = 0, res1 = 0, res2 = 0; for(auto &idx : index){ if(idx != 1){ cnt1 += start[idx].first; if(end[idx]){ res1 = max(res1,cnt1); cnt1 -= end[idx]; // if(cnt1<0) cnt1 = 0; } } if(idx != m){ cnt2 += start[idx].first-start[idx].second; if(end[idx]){ res2 = max(res2,cnt2); cnt2 -= end[idx]; // if(cnt2<0) cnt2 = 0; } } } cout<
 » 9 months ago, # |   0 In question E , why the answer should add a value (s+n-i+1)^2+(bi-bli) rather than (s+n-1-l)^2+(bi-bli)?
 » 9 months ago, # |   0 How to solve B using Binary Search?
 » 9 months ago, # |   0 Can anyone give a counter test case for this solution of Problem C: Medium Design link
 » 9 months ago, # |   0 Nice editorial
 » 8 months ago, # | ← Rev. 3 →   0 Can anyone help me know why my code of div2 D is giving me wrong answer in test 5? Thanks in advance.
 » 7 months ago, # | ← Rev. 4 →   -10 10 dislike? why bro why. I just told you how to solve this problem. Is it my mistake? Or to support Palestine on my profile