Is there any way to solve c by following 1) store all prefixes of string 2)store all suffixes of string 3)count 1 and 0 and store them in prefix array

Now when we get query l,r we create a temp string Such that temp= prefix till l-1 + string of zeroes till of length number of zeroes till r-l-1 +same with 1 + suffix [r+1]

Ans put them temp string to set ..

Will this work?

Hello everybody!

The competition was very interesting, but despite this, I will still get negative points.

Thanks for the competition: adedalic, awoo, BledDest, Neon and MikeMirzayanov

Any problems simillar to C?

Is there any way to solve C by constructing new string for each query? I am getting memory limit exceed

What is that simpler solution for problem F that most of the participants wrote?

Problem E can also be solved using the trick from 1156E - Special Segments of Permutation. Firstly, precalculate the "borders" in which $$$p_i$$$ is the minimum or the maximum element using monotonic stacks. Let's fix the maximum element of the segment. As in the problem mentioned above go to the closest end of the maximum border. If it is to the left of $$$p_i$$$ just calculate the number of good segments ($$$minpos(l, r) < maxpos(l, r)$$$) directly. Otherwise calculate the number of bad segments ($$$minpos(l, r) \geq maxpos(l, r)$$$) and subtract it from the total number of segments. You can see the details in my submission (with comments!): 216141125

Why in problem E in the author's solution in the line len += it->first - prv->first; (in the first while cycle) do we subtract from the it->first not from me->first? As I understand, in the case it->second == 0, we should firstly subtract from len the value it->first - me->first and then add the value it->first - prv->first.

More surprisingly, both versions get accepted: 216151073 and 216150501.

Can someone explain C in another way. I don’t really understand the editorial’s solution.

Why not add the editorial to "Contest Materials" ?

Upd: Added.

I am having a hard time understanding the problem C. While I can see that my approach isn't optimized at all, I would have expected either a TLE or an MLE but instead I got WA on test 2. My approach: for each m, sort the string [l,r], store it in an unordered set and later count the size of the set. I understand that if there is no change in the string after applying the op, adding the ti string (where ti==s) to the set means I have added the original string only and that is counted once as the set stores unique values. What am I understanding wrong here? My submission that got WA: 215938621

I tried double hashing for problem C im still getting sometimes 1 more than the answer.

216112844

For what it's worth, for problem E there is another (overly complicated, but perhaps more straightforward) solution.

Let $$$[l_i, r_i]$$$ be the range where $$$p_i$$$ is the maximum element, $$$a_i$$$ be the position of the closest element to the left of $$$p_i$$$ which is less than $$$p_i$$$, or $$$a_i = 0$$$ if it does not exist. Now, let's fix $$$i$$$ and look at the subarrays where $$$p_i$$$ is the maximum element, i.e. subarrays $$$p_l, \dots, p_r$$$ such that $$$l_i \le l \le i$$$ and $$$i \le r \le r_i$$$.

Here comes the main observation: the subarray $$$p_l, \dots, p_r$$$ is good ($$$minpos_{l,r} < i$$$) iff $$$\min(a_i, \dots, a_r) \ge l$$$. The proof should be trivial so I will omit it. Therefore, for fixed $$$r$$$ we have $$$\max(0, \min(a_i, \dots, a_r) - l_i + 1)$$$ good subarrays.

In order to get rid of the $$$\max(0, \dots)$$$ part let's find the rightmost index $$$r_i'$$$, such that $$$r_i' \le r_i$$$ and $$$\min(a_i, \dots, a_{r_i'}) \ge l_i$$$. Since the array $$$a$$$ can be calculated beforehand, this part can be done in $$$O(\log n)$$$ using a sparse table or some other data structure. Then, the number of good subarrays containing $$$p_i$$$ is

Subtracting the $$$(r_i' - i + 1) \cdot (l_i - 1)$$$ part is easy, let's focus on the sum. We have the following problem: given an array $$$a_1, \dots, a_n$$$ and $$$n$$$ queries of the form $$$(l, r)$$$, for each query find $$$\sum_{i=l}^r \min(a_l, \dots, a_i)$$$. There must be an easier way to solve it, but here is what I came up with. Let's answer these queries offline by iterating $$$l$$$ from right to left.

We need to support 2 kinds of operations on the array $$$b$$$ which is initially empty: 1) append an element to the left of $$$b$$$, 2) query $$$\sum_{i=1}^{r} \min(b_1, \dots, b_i)$$$. We can use a segment tree for that. Operation 1 can be done using range assignment: when we are appending $$$a_i$$$ all we need is to assign $$$a_i$$$ on the range $$$[i, q_i)$$$, where $$$q_i$$$ is the closest position of an element less than $$$a_i$$$ to the right of $$$a_i$$$ (or $$$n + 1$$$, if it does not exist). And operation 2 is simply a range sum query.

That's it, not the easiest implementation, but it felt very natural to come up with. The final complexity is $$$O(n \log n)$$$ and my submission is 215978080.

can someone please explain in c why cant we just sort the array on each iteration will that not be nlogn?

m for all iterations and then long for storing:

This gives WA on 2nd tc

C++

~~~~~

int main() { long t,m,n; string s; cin>>t;

while(t>0){
    cin>>n>>m;
    cin>>s;
    long l,r;
    unordered_set<string> tempstore;
    for(int i=0;i<m;i++){
        cin>>l>>r;
        l--;
        r--;
        string temp=s;
        if (l<=r) sort(temp.begin()+l,temp.begin()+r);
        tempstore.insert(temp);
    }
    cout<<tempstore.size()<<endl;
    t--;
}
return 0;

}

~~~~~~

Python

t=int(input())

while t>0:
    n,m=map(int,input().split())
    strs=set()
    s=input()
    
    for i in range(m):
        l,r=map(int,input().split())
        l-=1
        r-=1
        temp=s[:l]+''.join(sorted(s[l:r+1]))+s[r+1:]
        strs.add(temp)
    print(len(strs))
    t-=1

understood why got tle on python , but got a wa on cpp soln?

tle reason: for the tle part the thing is while sorting the time complexity is nlogn but when we insert in to set it is about logn so the difference of n matters in this case that causes tle (as we know n>logn)

Problem E was a very interesting problem. My initial idea was to use a lazy segtree for an NlogN solution, but it turns out that the O(N) solution is much cleaner and simpler.

https://codeforces.me/contest/1849/submission/216349588

I've tried C with string hashing, my idea was basically for every query we first subtract the hashed part (l, r) from the full string hash, and then we add the "sorted" hash of (l, r) by counting the number of 1s and 0s in (l, r) using prefix sum. I am able to do it in O(1) as I am precomputing powers of "p" from 1 to n, prefix sum and prefix_hash of the string.

Although I think my logic seems sound, my solution fails on test case 4: link I am not able to recognize my mistake, any help would be appreciated.

My implementation is based on this source: https://cp-algorithms.com/string/string-hashing.html

Why do I think D is easier than C?

Cab anyone help me to understand editorial of problem E? I tried but, I failed to understand it.

has anybody done D with DP? If yes could you please explain and share the approach?

There is another solution in F, a bit hard to code but easy to understand. Let's write binary search on the answer, now we need to check if answer is <= X. Then go from left to right, maintaining a binary trie. Then, on each level of the trie, check the following: if ith bit is set in X, then all of the numbers with which the XOR would have that bit have to be in a different component. Otherwise we can ignore the bigger component. Since we can unite components in $$$O(sz)$$$, and the sum of all sizes is $$$O(NlogMAX)$$$, one check works in $$$O(NlogMAX)$$$. Since the DFS constant is really hig, use DSU.

Working code: https://codeforces.me/contest/1849/submission/216600784

Can someone help with finding issue in my code?: 216602874 For each l[i], r[i], I substract hash of section from hash of the string and add hash of sorted section which is calculated using the formula of geometric series sum. I add ultimate hash to the set and output size of the set as an answer

For problem E, I have a cool idea, but unfortunately my poor ability can't make it happen. Is there anyone willing to take a look and tell me if this is impossible?

My idea is: for each index $$$i$$$, we can use a monotonic stack to solve $$$Lmin_i,Rmin_i$$$, meaning that when the interval left endpoint is in $$$[Lmin_i,i]$$$, the right endpoint is in $$$[i,Rmin_i]$$$, the minimum value of this interval is $$$a[i]$$$. The maximum value is similar, and can be described by $$$Lmax,Rmax$$$.

Then we try to construct a rectangle $$$A$$$ on a two-dimensional plane. Its lower left coordinate is $$$(Lmin, i)$$$, and its upper right coordinate is $$$(i, Rmin)$$$.

That is to say, this rectangle spans $$$[Lmin_i,i]$$$ on the x-axis, and spans $$$[i,Rmin_i]$$$ on the y-axis. The area of this rectangle is the number of intervals that satisfy the minimum value is a[i].

If we add another rectangle $$$B$$$ in the same way with $$$Lmax_j, Rmax_j$$$. Then the intersection part of rectangles $$$A$$$ and $$$B$$$ is: the number of intervals that satisfy the minimum value is a[i] and the maximum value is a[j].

If we require $$$i<j$$$ at this time. Then the sum of all such rectangle pairs intersecting like this is the answer to this question.

So what I think is that index $$$i$$$ goes from left to right, first query the total area of all $$$Lmin,Rmin$$$ rectangles within the range of $$$Lmax_i, Rmax_i$$$ rectangle, add it to the answer, and then add a $$$Lmin_i,Rmin_i$$$ rectangle.

The key to the problem is this task of dynamically adding rectangles and solving total area.

My idea may be naive, please don't laugh at me hard XD

Can i use string hash to solve the problem C?

C and D should be swapped in my opinion

https://codeforces.me/contest/1849/submission/239744150 For problem E, Does anyone know what is this judgement means? I believe my code is correct and it passed 35 testcases.

IN PROBLEM D, WHY CAN'T I FIRST BFS ALL THE 2 ONES AND THEN ALL ONES AND COUNT REST UNVISITED INDICES? PLS GIVE A TEST CASE FAILING THIS?

Problem B monsters solution video editorial link: https://youtu.be/C1v2IkfKaEM?si=vfMBsIDWsvGQCO51