If possible do link codes with solution .

I solved F by reducing it to a geometry problem. But I only fixed my TLE 5 minutes after the contest ended :rage:

First, for each index, we want to know the largest range on which it's the minimum element, and the largest range on which it's the maximum element. We can precompute all these ranges in linear time with a monotonic stack idea, for example. Let's say the range where $$$a_i$$$ the minimum element is $$$[l_1(i), r_1(i)]$$$ and the range where it's the maximum element is $$$[l_2(i), r_2(i)]$$$. If there's a tie for the minimum (maximum) element in a range, we always pick the first occurrence to be the minimum (maximum).

Now, for each index $$$i$$$, let's consider the set of intervals $$$[l, r]$$$ on which $$$a_i$$$ is the minimum element. We simply require it to be a subinterval containing index $$$i$$$. So the only constraints are $$$l_1(i) \le l \le i$$$ and $$$i \le r \le r_1(i)$$$. If we visualize this in the plane where one axis is $$$l$$$ and the other is $$$r$$$, we simply are describing a rectangle. Similarly, we have a rectangle for the maximum case.

Let's say that a rectangle is red if it came from the minimum case, and blue if it came from the maximum case. First, notice that no two rectangles of the same color intersect, because a range has a unique minimum and maximum by our tie-breaking rule. Our task is to calculate how many lattice points are the intersection of a red and blue rectangle, and both of them have the same "group number", namely the popcount of their corresponding $$$a_i$$$ values.

Let's just offset rectangles according to their group number so that rectangles of different group numbers definitely don't intersect, and rectangles of the same group are offset by the same amount.

The only thing we need to compute is the area of intersection of red rectangles and blue rectangles. It's sufficient to find the area of the union of rectangles, by inclusion-exclusion. We can find the area of the union of these rectangles in $$$O(n \log n)$$$ time with a sweepline and segment tree. Reference for rectangle union problem: https://cses.fi/problemset/task/1741

Can anyone please explain E in more detail ? I am not able to understand the solution presented in the editorial.

Problem D was more an English comprehension test for me :(

For anyone looking for video editorial, I have made for problems A to D.

Link to the video

What's the expected time complexity for C? I've used seive to find the primes less than 10^6 and then checked how many pairs are possible when the sequence starts from the ith term, but it's taking too long. From my understanding time complexity of seive is O(log(log(n))) that of my remaining script is O(nlog(n)). Can anyone point where I am going wrong?

My Submission

In D, how do we know that the way topvals are inserted in the solution above doesn't exceed logN, is it similar to the reason why find of the dsu doesn't exceel logN ?

In E, am I right that the model solution has the intended complexity of O(n log n * 32 * 32), which is more than what seems reasonable?

It seems that you've done some constant optimization because the number of states which make sense is a bit smaller than 2^5, I have no idea how Java users are supposed to pass this task...

I don't quite like the style of the editorial

But I do appreciate the attempt to include solutions with more readable code than usual. I'll give you that

in problem B: can someone tell me why this code fails 137283903, and this code passes 137284479 ?

Can anyone help me find the time complexity of my solution for problem C?

Submission: 137291865

I am just wondering how this got AC

I solved problem E other dp. Notice, that abc exist if and only if exist 'b' between first 'a' and last 'c'. It is beneficial for us to do this: replace the first few 'a', the last few 'c' and all the 'b' between the first remaining 'a' and the last remaining 'c'. Note also that we can assume that we are deleting the symbol, and not replacing it. Because We can replace 'a' and 'b' with 'c', and 'c' with 'a'.

Let's first reduce the task to an array task. Let's create 3 arrays a, b, c, where a[i] = 1 if s[i] = 'a', b[i] = 1 if s[i] = 'b', c[i] = 1 if c[i] = 1. Then what does our answer look like? Answer is $$$\min_{i <= j} (a_0 + ... + a_i) + (b_{i + 1} + ... + b_{j - 1}) + (c_j + ... + c_{n - 1})$$$ Here you can come up with dp, which will consider the answer as O(n), but let's come up with a quick solution right away.

Let's $$$dp[v][i][j]$$$ — answer for node v segment tree if we begin in array i and finish in array j on subsegment. Then, in order to solve the problem, it remains only to learn how to combine 2 vertices. If we recalculate through v1 and v2 $$$dp[v][i][j] = min_{k1 <= k2} \, \, ( dp[v1][i][k1] + dp[v2][k2][j] )$$$ Explicitly recalculation works in $$$O(\Sigma ^4)$$$, but this is optimized to $$$O(\Sigma ^3)$$$, where $$$\Sigma$$$ is the size of the alphabet. Then the whole solution will work for $$$O((n + q \log n) \Sigma ^3)$$$

It would be nice if the editorial for problem A did not just tell what we need to "notice" to solve it, but also provided some kind of a proof. Because for me the proof is not that obvious, even though I know how to prove it now.

I have a time limit in this submission: 137334481

However, when I checked if some elements are infinity, the solution passed: 137334234

I don't really understand why it did, do these if statements really optimize the solution to that extent, and most importantly why?

My solution to F only uses Divide and Conquer. I think it's quite simple, actually.

Suppose we are calculating the answer for segment $$$[l,r]$$$ that passes through $$$mid$$$ and $$$mid+1$$$. For each $$$l\in [l,mid]$$$, find the following: (with two-pointers)

• the maximum $$$r\in [mid+1,r]$$$ such that the maximum in $$$[l,r]$$$ is in $$$[l,mid]$$$, $$$j$$$;
• the maximum $$$r\in [mid+1,r]$$$ such that the minimum in $$$[l,r]$$$ is in $$$[l,mid]$$$, $$$k$$$.

WLOG $$$j<k$$$. Then,

• If $$$r\le j$$$, the number of bits in the maximum and minimum of $$$[l,r]$$$ only depends on $$$l$$$. This is easy to deal with.
• If $$$r\ge k+1$$$, the number of bits in the maximum and minimum of $$$[l,r]$$$ only depends on $$$r$$$. This is easy to deal with, with suffix sums on $$$r$$$.
• Otherwise, what we are calcuting is like, "how many numbers in $$$b_{[l..r]}$$$ are $$$k$$$"? This can be solved offline with a sweep-line like method. We add $$$(l,k,-1),(r+1,k,-1)$$$ to the set of queries and process it when we scan from $$$mid+1$$$ to $$$r$$$, maintinging a bucket array.

Complexity is $$$O(n\log n)$$$ and independent of $$$a_i$$$.

Can anyone help me understand why my submission for B is getting WA on test 3. My approach is exactly same as in editorial. can't seem to find the edge case. help will be truly appreciated.137250167

Even after reading D for so long I was not able to understand the testcase 2. Now after reading the editorial one thing is clear — that I don't understand the question itself. Any help in understanding the question or testcase 2 is appreciated. Thank you.

Can anyone tell me why am i wrong in this code ? https://mirror.codeforces.com/contest/1609/submission/137238591 Thanks you.

I have alternative perhaps slightly complicated solution for F. However most of the complexity comes from the stringent memory limit. We first iterate over what is maximum element. To find what subranges $$$u$$$ is maximum for, we just need to find closest left element that is larger($$$l-1$$$) and closest right element that is larger($$$r+1$$$). Now we need to find total subarrays such $$$bits(\min(a[l\ldots r])) = bits(a[u])$$$, where $$$bits$$$ is number of set bits.

Let us let the left ending of subarray be $$$l \le l' \le u$$$. Let us now find 2 other arrays as precomputation.

rhtmin[i] : This tells us the index of closest element to the right of $$$a[i]$$$ that is smaller if it exists and $$$n$$$ otherwise

rhtcnt[i] : This tells us for how many $$$i \le x \le n-1$$$ is such that $$$bits(a[i]) = bits(\min(a[i\ldots x]))$$$

Let us now find the number of $$$r'$$$ such that $$$l \le l' \le u \le r' \le r$$$ such that the the number of bits is the same as in $$$a[u]$$$. We can keep a rolling minimum while iterating $$$l'$$$ from $$$u$$$ to $$$l$$$. Lets use rhtmin on the minimum element to find till what value of $$$r'$$$ will the minimum be on the left side of the array. Using this we can check if should add these subarrays or not.

Now we need to use the next trick. We want to find when will the minimum become an element with $$$b$$$ bits. If we do that we can use rhtcnt to compute the answer. The minimum from $$$i$$$ will change at rhtmin[i]. Therefore when an element is found with $$$b$$$ bits is the same for $$$i$$$ and rhtmin[i] except when $$$b = bits(i)$$$. So if we iterate from $$$n-1$$$ to $$$0$$$ and copy the positions we find bit $$$b$$$ it will be fast enough. However as the memory limit does not allow us to make array of size $$$64n$$$ we need to do some memory optimisation.

Instead we store when the next element with $$$8k \le b \le 8k + 7$$$ bits appears for each $$$k$$$, and then for an element with $$$8k + i$$$ bits we also store where the next element with $$$8k + j$$$ bits appears. This has optimised memory usage to $$$16n$$$ instead. Now to find the next element with $$$b$$$ bits, we first find an element whose bits $$$b'$$$ satisfies $$$\lfloor b'/8\rfloor = \lfloor b/8\rfloor$$$, and then we find an element with exactly $$$b$$$ bits from the element with $$$b'$$$ bits. This finds the answer in $$$O(1)$$$ still.

Ok now we have found when the number of bits in the minimum becomes $$$b = bits(a[u])$$$. Using rhtcnt we get the answer for number of subarrays $$$l \le l' \le u \le r' \le n$$$ such that $$$bits(\min(a[l'\ldots r]) = b$$$.

To remove the extraneous arrays, we will first have to find the minimum closest to the edge of $$$r$$$. This can be done effortlessly with binary lifting on $$$i \to rhtmin[i]$$$. This used $$$20n$$$ memory which is too much for us. We optimise this by using quaternary lifting which will only use $$$10n$$$ memory at the cost of an extra $$$3/2$$$ factor in runtime.

Ok now we have the closest element to the edge($$$r_m$$$). This will remain constant until the minimum on the left side becomes less than $$$r_m$$$, in which case the minimum of all subarrays is a trivial case and is constant. Let us break $$$r_m$$$ into two cases. If it has $$$b$$$ bits we can easily subtract its rhtcnt to remove extraneous $$$r'$$$. We just add the answer for $$$r_m \le r' \le r$$$ back.

If its not, we need to find where is the next time the minimum has $$$b$$$ bits, which will be outside the array and we can simple subtract its rhtcnt to remove extraneous values. All we need to do is the earlier trick again to find the next element with $$$b$$$ bits from $$$r_m$$$ and subtract its rhtcnt to get the answer.

We can do the exact same iteration for $$$u \le r' \le r$$$.

If we do it for the smaller of the 2, we will do not more than $$$O(n\log{n})$$$ iterations. If you think of the maximum of an array splitting it into two like some sort of divide and conquer it is clear that this is the case.

And using that we can get the solution in $$$O(n\log{n})$$$.

Solution

I think the memory limit for problem F is too small so that In my solution can't use prefixsum but just can use persistence segment tree. Such as https://mirror.codeforces.com/contest/1609/submission/137397827 and https://mirror.codeforces.com/contest/1609/submission/137397769

"A little later"

В решении задачи E подпоследовательность ab = ba ? почему мы не рассматриваем cba ? почему это будет оптимальным ответом ?

why "Tutorial is not available" for problem H?

Edit : mistake from my part, sorry

I have a question in problem E. The code you added to the tutorial doesn't define the following base cases: if we are at the node that contains one character and let's say it's "a" we define seg[ver].dp[1] = 0 but we don't define the case if we replaced the character with "b" or "c". Therefore, instead of defining seg[ver].dp[2] = seg[ver].dp[4] = 1, we are defining seg[ver].dp[2] = seg[ver].dp[4] = inf. How does the solution works even with this? Note: both cases will get accepted so why it doesn't make a difference?