1793A - Yet Another Promotion was authored and prepared by Ormlis

1793B - Fedya and Array was authored and prepared by TheEvilBird

1793C - Dora and Search was authored by fedoseev.timofey and prepared by vaaven

1793D - Moscow Gorillas was authored and prepared by Gornak40

1793E - Velepin and Marketing was authored and prepared by Tikhon228

1793F - Rebrending was authored by Tikhon228 and prepared by vaaven

## 1793A - Yet Another Promotion

Let $$$n = (m + 1) \cdot q + r$$$.

Note that you need to use a promotion if $$$a \cdot m \leq b \cdot (m + 1)$$$. In this case, we will buy potatoes $$$q$$$ times for the promotion. The remaining potatoes (or all if the promotion is unprofitable) can be bought at $$$\min(a, b)$$$ per kilogram.

Then the answer is:

Thus this solution works in $$$\mathcal{O}(1)$$$

**Code**

## 1793B - Fedya and Array

Note that the local minimums and maximums will alternate, and there will be the same number of them $$$k$$$. Let's call the $$$i$$$-th local maximum by $$$a_i$$$, the $$$i$$$-th local minimum by $$$b_i$$$. Without loss of generality, consider that $$$a_i$$$ goes before $$$b_i$$$. To get $$$b_i$$$ from $$$a_i$$$ we need to write out $$$a_i - b_i$$$ numbers, to get $$$a_{(i + 1) \bmod k}$$$ from $$$b_i$$$ we need to write out $$$a_{(i + 1) \bmod k} - b_i$$$ numbers.

Thus, $$$(a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k) =$$$

$$$= 2 \cdot (a_1 + a_2 + \ldots + a_k) - 2 \cdot (b_1 + b_2 + \ldots + b_k) = 2 \cdot (A - B) = n$$$

The array $$$[y, y + 1, y + 2, \ldots, x - 1, x, x - 1, x - 2, \ldots, y + 1]$$$ will satisfy the condition.

**Code**

## 1793C - Dora and Search

Suppose we want to check whether the entire array satisfies the claim. If this is the case, then we can output the entire array as an answer. Otherwise, one of the two extreme elements does not meet our requirements. From this we can conclude that all segments containing an element that does not meet our requirements will also be incorrect, because this extreme element will remain the minimum/maximum.

The algorithm follows from the fact above: let's look at the sub-section $$$[l; r]$$$, which is initially equal to $$$[1; n]$$$. If $$$a_l = \min(a_{l}, a_{l+1}, \ldots, a_{r})$$$ or $$$a_l = \max(a_l, a_{l +1}, \ldots, a_r)$$$, then we proceed to the segment $$$[l+1; r]$$$. A similar reasoning is also needed for $$$a_r$$$. Thus, either after some iterations we will get the required sub-section, or we will get $$$l == r$$$ and the answer will be $$$-1$$$.

Final asymptotics: $$$\mathcal{O}(n\log n)$$$ or $$$\mathcal{O}(n)$$$ depending on the implementation.

**Code**

## 1793D - Moscow Gorillas

Denote by $$$pos_x$$$ the index of the number $$$x$$$ in the permutation. Subsegments with $$$\operatorname{MEX}>1$$$ are as follows $$$1 \le l \le pos_1 \le r \le n$$$.

Denote by: $$$l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$$$, $$$r_x=\max{[pos_1, pos_2, \ldots, os_x]}$$$.

Subsegments with $$$\operatorname{MEX}>x$$$ are as follows $$$1 \le l \le l_x \le r_x \le r \le n$$$. Let's find all subsegments with $$$\operatorname{MEX}=x$$$.

If $$$pos_{x + 1} < l_x$$$, then the subsegments with $$$\operatorname{MEX}=x+1$$$ are as follows $$$pos_{x+1} < l \le l_x \le r_x \le r \le n$$$

If $$$l_x \le pos_{x + 1} \le r_x$$$, then there is no subsegment with $$$\operatorname{MEX}=x+1$$$

If $$$r_x <pos_{x+1}$$$, then the subsegments with $$$\operatorname{MEX}=x+1$$$ are as follows $$$1 \le l \le l_x \le r_x \le r < pos_{x+1}$$$

It remains only to intersect the sets of such subsegments for $$$p$$$ and $$$q$$$, which is done trivially.

**Code**

## 1793E - Velepin and Marketing

Let's sort people by their group size requirement. Suppose we have such a person $$$i$$$ that he is not satisfied, and we have a person $$$j > i$$$ who is satisfied. Then we can replace person $$$j$$$ in his group with $$$i$$$ and the answer for us will not be worse. It follows that for a particular $$$k$$$ the answer is some prefix of the people we can make satisfied.

Let us also prove that there exists some arrangement of groups that covers the same prefix, and that each group is a continuous segment. Let's take some correct partitioning into groups. Then each group will be a set of unconnected segments. Let's take the leftmost such segment. Note that we can swap it to the nearest segment of the same group to the right without breaking anything.

Thus we obtained that we can look for a solution in the form of partitioning each prefix into valid groups, which are segments. We will solve this problem using dynamic programming.

Let $$$dp[i]$$$ -- the maximum number of groups into which $$$i$$$th prefix can be partitioned, so that everyone is satisfied (and no elements beyond the prefix can be used). Dynamics base: $$$dp[0] = 0$$$ (empty prefix maximum can be divided into 0 groups). Transition: for $$$i$$$th person his group must have size at least $$$a[i]$$$, so the transition looks like this $$$dp[i] = \underset{0 \leqslant j \leqslant i - a[i]}{\max} dp[j] + 1$$$. But what if $$$a[i] > i$$$? Then we can't dial the $$$i$$$th prefix. Then we put $$$dp[i] = -\infty$$$. This dynamics can be calculated using prefix maximums. This part of the solution works for $$$\mathcal{O}(n)$$$.

Earlier we said that the answer would be some prefix of people who would be satisfied. If we can partition the prefix into some number of groups, then that answer can be the prefix for all $$$k \leqslant dp[i] + n - i$$$. (we partition our prefix into $$$dp$$$, and the rest of the people one by one into the group)

If we can't make the whole prefix satisfied ($$$dp[i] = -\infty$$$), then we need to add people from outside. Thus, the maximum number of groups we can split into if $$$i$$$th prefix is completely satisfied is $$$n - a[i] + 1$$$.

Note that if by some prefix we can score $$$k$$$, then we can also score $$$k - 1$$$ (combining two groups into one). Then we need to find the largest prefix that fits the given $$$k$$$ in the query. This can be done by an array of suffix maximums over $$$\mathcal{O}(q)$$$ total. The final asymptotic of the solution is $$$\mathcal{O}(n \log n + q)$$$.

**Code**

## 1793F - Rebrending

Let's go through all the elements from left to right. The main task will be to support the current version of $$$dp[i]$$$ -- the minimum difference of $$$a_i$$$ with the elements to the right of it that we managed to consider. Let us correctly calculate $$$dp$$$ for the first $$$r$$$ elements. Let's move on to $$$r + 1$$$. Let's show how to update the answer for all $$$j < i$$$, such that $$$a[j] > a[i]$$$. For $$$j < i$$$, such that $$$a[j] <a[i]$$$ is solved similarly.

Let's take the first element $$$a[j]$$$ to the left of $$$i$$$, such that $$$a[j] > a[i]$$$. Note that if there is $$$l<j < i$$$ such that $$$a[l] > a[j]> a[i]$$$, then we will not update $$$dp[l]$$$ for it, because $$$|a[l] - a[j]| < |a[l] - a[i]|$$$. Also, we will not update the answer for $$$l$$$ such that $$$|a[l] - a[j]| < |a[l] - a[i]|$$$, that is, if

Unable to parse markup [type=CF_MATHJAX]

. Therefore, further we will be interested only in the numbers from the segment $$$\left[a[i], a[i] + \frac{a[j] - a[i]}{2}\right]$$$.Let's note that we have reduced the length of the segment by $$$2$$$ times. That is, there will be no more such iterations than $$$\mathcal{O}(\log n)$$$. You can find the rightmost number belonging to a segment using the segment tree. The answer for the segment $$$l_i, r_i$$$ will be $$$\underset{l_i\leqslant j<r}{\min} dp[l]$$$ at the moment $$$r_i$$$. This can also be efficiently found using the segment tree. The final asymptotics of the solution is $$$\mathcal{O}(n\log^2 n + q\log n)$$$.

There is also a solution for $$$\mathcal{O}(n\sqrt{n} + q\log q)$$$ that passes all the tests.

**Code**

is this contest rated?

[deleted]

You want:Rated:Unrated:Edit: the ratings have been updated!!if copy F: rated else unrated

Though I solved F, I think it shoud be unrated. But now it is rated.

Did anyone solved F using Mo's algo (specific sqrt decomposition) ?

I made some failed attempts using sets with a TC of $$$\mathcal{O}(n\sqrt{n}\log{n})$$$

Yes, check out my submission.

Super fast set for integers and super fast IO were used to pass TL, overall complexity is $$$O(C\cdot (N+Q)\sqrt{N})$$$, where $$$C$$$ is some small constant of fast set.

Wow, that's kinda amazing. Do you have a template / resource for this super fast set and super fast IO, that you can share with me ?

It's actually hard for me to wrap my head around it...

Both templates are in the code or wdym by that. IO was taken from someone's submission here, fast set was written by me based on 64-nary tree.

Practice on infoarena and this won't feel that amazing.

What is infoarena dude ?

Could you describe your solution, please?

It's something like this: link

in your MO you are not using optimizations,maybe it would have been easier to pass TL if you used tricks that are making NO even faster?

What optimizations you are talking about?

the sorting of the blocks, (you have it commented), also you may have used the best comparator that i really do not remember and will include a link when i find it

It is not an usual MO where you can move left and right pointers as you want, so the comparator you're talking about won't work here.

Could someone help identify the mistake in my code for problem D?

193336874

Problem C : Dora and Search Video Editorial Link : https://youtu.be/l5GgWZmsZ98 Happy Coding

Problem E is a cleverly-designed dp problem with easy implementation and requirement for thinking ability. However, it's ruined by a duplicate problem F, otherwise more contestants could solve it.

first time i got to solve D in contest and i was just 10 seconds away from submitting it :(

same here ;(

Also was super close to submitting D. Bricked B hard :(

Can somebody explain to me this statement from the solution for problem F:

That is, there will be no more such iterations than O(logn)? Also, I think it should have been`|a[l]-a[j]|`

instead of`|a[l]isa[j]|`

and`[a[i],a[i]+(a[j]−a[i])/2]`

instead of`[a[i],a[i]+(a[j]−a[l])/2]`

.Every time comes a new $$$i$$$ , we try to update all the $$$dp_j$$$ that $$$j<i$$$ and $$$a_j>a_i$$$ ($$$<$$$ the same).

We first find the nearest such $$$j$$$ and update it. As we know, elements greater than $$$a_j$$$ are ignored, so the range we consider now is $$$[a_i,a_j]$$$ . Also, the elements greater than the center of the range are ignored. So the next $$$a_j$$$ we find is in $$$\left[a_i,a_i+\frac{a_j-a_i}{2}\right]$$$(the left half of the old range).

We find the nearest such $$$j$$$ again. This can be done as a maximum query on a weight segment tree. Now we have a new $$$j$$$ , and then repeat the process above. Note that each time we find a new $$$j$$$, the length of the range is halved. So the whole process will stop in $$$O(log\ v)$$$ . Here $$$v$$$ is the range of array $$$a$$$ , and we know $$$v=n$$$ .

And your correction is right. vaaven please check that.

Only got a micro positive delta but luckily became expert from specialist narrowly :)

congratz)

Can sqrt-decomposition solve the problem F? I got a TLE and don't know how to optimize

Yes, and it runs really fast.

Can't I just put 'n' to place 'q' in problem a tutorial?

Can anyone Please explain Problem B . It is really Confusing.

Read my code here. U might understand. https://codeforces.com/contest/1793/submission/193333638

start answer array from maximum_sum and keep subtracting 1 until you got minimum_sum,

as now you have both maximum and minimum sum

now keep adding 1 until you get maximum_sum-1

because you have to make it circular so absolute difference between last element and 1st element have to be 1

I'll try to specify the 2nd paragraph of E.

From para#1 we know that in the sorted array, it is always possible that all the satisfied people form a prefix of this array. But in this prefix, maybe a group is separated into a set of unconnected segments. Now we'll prove that all these segments from the same group can be connected.

Let's pick two segments from one of the groups, calling the left segment $$$A$$$ , and the right one $$$B$$$ . We now try to keep moving $$$A$$$ to the right until $$$A$$$ connects with $$$B$$$ . While $$$A$$$ moving right, it squeezes other elements to the left. From para#1 we know if you throw an element to the left, it won't be worse. So don't worry about these squeezed elements. As for $$$A$$$ , it will stop as soon as it meets $$$B$$$ . We know people in $$$B$$$ are all satisfied, because all the people in the whole prefix are satisfied. We also know the whole array is sorted, so the elements in $$$A$$$ will not be greater than $$$B$$$ . And, we only move segments and not change the length, so the group size always stays the same. So people in $$$B$$$ stay satisfied, people in $$$A$$$ with lower requirement (than $$$B$$$) also stay satisfied. Nothing is wrong.

Now we can connect together any two segments from the same group by moving the left one to the right. The remaining task is only to repeat this operation.

Therefore, we have proved that, each group in this prefix can be a continuous segment.

Thank you very much, I finally understand what editorial is trying to say .....

Actually the above explanation is not completely correct and also misleading as we can not always squeeze elements to the left. There is something missing in it due to which it gives false impressions. As it took me quite a lot of time to understand it,i would try my best to explain my argument here : first we sort the requirement vector a : a1,a2,a3,...,an in a non-decreasing order of ai's i.e. now for all 1<=i,j<=n , i<j implies ai<=aj.

Proof of para 1 : Suppose we assign some book numbers to all ai's(that is what we have to do in the problem) and call this array b i.e. bi=x means that we assigned the book number x to the ith index (reader). Now consider a case where for some i<j the ith index(or the reader) is not satisfied but the jth one is satisfied. Suppose we assigned book number x to i and y to j(i.e bi=x and bj=y), then from the condition of satisfaction we get : number of x's(in the array b) is strictly less than ai and number of y's(in b) is not less than aj. Let's denote the number of x's in b by u and number of y's in b by v(i know that there are a lot of variables and notations introduced, but please bare with me.) then we have : u=aj. Now due to these two indices the contribution in ans is 1: why ?,it's obvious as ai is not satisfied but aj is. Now swap the book numbers assigned to i and j i.e make bi=y and bj=x, now we have that the index i is satisfied because bi=y, and number of y's in b = v>=aj>=ai and index j is no longer satisfied as bj=x, and number of x's in b = u<ai<=aj. Hence the pair (i,j) still contributes 1 to the answer(which is the number of indices that are satisfied) and hence the answer does not get worse. Hence we can always have a prefix of indices that are satisfied.

Proof of para 2 : Now again consider an assignment of book numbers to all indices. Assume the the prefix(m) is satisfied for this assignment. Now consider a case where in this prefix, a group is separated into set of unconnected segments. Consider two separated segments of the same group. For the sake of simplicity consider both these segments to be of length 1 because if we can only prove that we can bring together two indices belonging to the same group, we are done, as for larger segments we can bring indices together one by one to make into a single continuous segment. Now coming back to the proof : consider the following scenario :

array a : ai , aj , akarray b : x. , y , xwhere i<j<k<=m(i.e all 3 indices lie in the satisfied prefix) and bi=x , bj=y , bk=x , i.e indices i and k belong to the same group but are separated into unconnected segments.Also following the variable names from the previous proof, denote number of x's in b by u and number of y's in b by v. Now since all the three indices are satisfied, we have : u>=ai , v>=aj , u>=ak . We can write the 1st and 3rd conditions together as u>=ak and ai<=aj<=ak. Hence we have u>=ak , v>=aj , ai<=aj<=ak ----- * Now let's analyse what happens when we swap the values of b for indices i and j(in order to bring the two x's together : we want to bring all the separated segments belonging to a same group together into a continuous segment) :

array a : ai , aj , akarray b : y , x , xnow since the index k is unchanged, it is still satisfied. index i is still satisfied by the same argument as in proof 1 : number of y's in b = v>=aj>=ai (from *) and index j(the most confusing one) is also still satisfied(all this was possible because of the presence of the index k<j having bk=x) because : number of x's in b = u>=ak>=aj(from *). Hence we can perform the swap without breaking anything. Hence we can always bring together two different indices(that are not initially together) belonging to the same group by making swaps from left to right as shown above and hence we are done!

I'm sorry but I have to say your text is hard to read... Anyway, I know what you are talking about. That's exactly the same as what I tried to say. Maybe my words such as "move the segment" and "squeeze" caused some misunderstandings. I'll clarify my idea.

"Moving a segment" only moves the arrangement of groups, not the elements themselves. For example, $$$\Big[(1,2),[3,4],(5,6)\Big]\rightarrow\Big[[1],(2,3),[4],(5,6)\Big]$$$ . In fact, this step swaps the arrangement of groups between the two indexes $$$1$$$ and $$$3$$$ . That is the same as your proof.

Anyway, thanks for your discussion.

F can be solved using sqrt decomposition in $$$O((n+q)\sqrt n)$$$ with a small constant.

Notice that a pair $$$l,r$$$ can contribute to the answer only if $$$r-l\leq \sqrt n$$$ or $$$|a_r-a_l|\leq \sqrt n$$$, and there are only $$$O(n\sqrt n)$$$ of them. So we can find the answers offline, sorted by increasing $$$r$$$, and each time we add an element to the right, we update the answers in the segtree, but this will be $$$O((n\sqrt n+q)\log n)$$$, which is too slow.

But we have a trick here, notice that we have $$$O(n\sqrt n)$$$ updates and only $$$O(q)$$$ queries in the segtree, we can trade query time complexity for update time complexity using sqrt decomposition. Therefore the total time complexity is $$$O((n+q)\sqrt n)$$$.

Here is the submission 193306318 (it is really short).

What do you mean by "can contribute to the answer"? What if the statement is false? How is the answer calculated? update: You have already precalculated answers for each block of size sqrt(n).

actually it seems that number of segments that might contribute to the answer are only O(n) instead of O(n * root(n)). I am not able to prove it but it does seems like the case.

In problem B, there isn't any restriction to the (x — y) difference. But when I try to hack solutions using the case x, y = {1e9, -1e9}, the validator says "Invalid Case". Why?

You may say; "It is impossible / incredibly hard to find a solution to that case". That's what I thought when I was trying to solve this problem. Yes, there is a restriction on the sum of 'n', but that doesn't mean (x — y) is also restricted.

Looking forward to your opinions about that.

It is a implicit restriction, due to the limit on N this case has no valid solution. I agree that this is misleading... maybe they didn't make it clear to avoid giving a hint

Well, x — y means one of your n's will be equal to x-y. That means the original restriction on the sum of n's indirectly restricts the value of x and y

It doesn't. Because there isn't anything like "It is guaranteed that the answer exists" in the statement. Or "It is guaranteed that answer exists with n <= 2e5".

I meant it comes from the sketch of the optimal solution, I dont see the problem, is part of being a competitor to check the implicit constraints too and I think it's brilliant how they did it here, it made me doubt a lot

The problem statement says:

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$It was proven in the editorial that in any valid solution, $$$n = 2 \cdot (x - y)$$$.

Here, the "gurantee" means that an input is valid only if the sum of $$$n$$$ in the answer will not exceed $$$2 \cdot 10^5$$$. Any input that doesn't satisfy this will be deemed invalid, even if it satisfies the $$$-10^9 \le x, y \le 10^9$$$ requirement.

This can be understood incorrectly, because the word "gurantee" is very ambiguous here. You should read more about it here.

i think its fine the way they did it, and to some extent reduced the guessing on the problem, if they instead say sum of x-y doesnt exceed 1e5, solution would be obvious

Can anyone tell me why wrong answer is coming for Test 6 in problem D?

Link to Submission

5

2 3 1 4 5

2 3 1 4 5

Why can't the explanations be more elaborate? Aren't they supposed to induce more interest? I always feel these tutorials require a lot of cognitive effort, does anybody feel the same?

I can't find what's wrong with my code for problem F, which uses the same approach as in the editorial. My submission — 194098249. Can anyone please point out the mistake?

Different idea for problem F (that is hopefully easier to find).

Consider a 1d array $$$dp$$$ of size $$$N$$$. Through various iterations, our array $$$dp$$$ keeps changing.

In the first iteration, $$$dp[i]$$$ is the minimum absolute difference between $$$a[i]$$$ and some other element in indices in the range $$$N - 1 \dots i$$$. In the second iteration, $$$dp[i]$$$ is the minimum absolute difference between $$$a[i]$$$ and some other element in indices in the range $$$N - 2 \dots i$$$. More generally, at the $$$x$$$th iteration, $$$dp[i]$$$ is the minimum absolute difference between $$$a[i]$$$ and some other element in indices in the range $$$N - x \dots i$$$.

It is not hard to see that for a query $$$(l, r)$$$, all we need to do is find $$$\text{min}_{l \le x \le r} dp[x]$$$ on the $$$N - l$$$th iteration of $$$dp$$$. Since we can process the queries offline, we can process the queries in decreasing order of $$$l$$$--or in increasing order of "iteration."

So now the question becomes how to actually construct $$$dp$$$. At the beginning, at the $$$0$$$th iteration, $$$dp$$$ is simply an array where all elements are infinity (or some extremely large number). So we just need to figure out how to update and go from the i — 1th iteration to the ith iteration. What changes? Not much.

Lots of stuff that is within $$$\sqrt{N}$$$ of index may change. We can apply these changes manually. What about stuff that is farther than $$$\sqrt{N}$$$ of index $$$i$$$? Only $$$O(\sqrt{N})$$$ of them change. The thing is that $$$dp[x]$$$ gets really small when $$$|x - i| > \sqrt{N}$$$. In fact, when $$$|x - i| > \sqrt{N}$$$, $$$dp[x] < \sqrt{N}$$$. So basically, most of the dp values are quite small (and probably won't change). The only $$$dp$$$ values that may be affected are ones where $$$a[x]$$$ is really close to $$$a[l]$$$ (in fact, within $$$\sqrt{N}$$$ of $$$a[l]$$$).

So now we know how to update $$$dp$$$ $$$O(\sqrt{N})$$$ times each iteration.

Now, the rest is just answering queries, which we can do once we slap on a segment tree to $$$dp$$$.

194176722

Final Complexity: $$$O(N \sqrt N \log N + Q \log N)$$$

I'm sorry, but you modified $$$dp$$$ $$$O(\sqrt{N})$$$ times on each iteration, and on each modfication you need to update it in the segment tree. As a result, the complexity should be $$$O((N\sqrt{N}+Q)\log N$$$ instead of what you mentioned.

You are right. I updated the post.

How to solve task B if x-y=1, for example, x=3 and y=2?

If follow the proposed solution, the answer is: n=2*(3-2)=2; numbers: 2 3. But this is incorrect, because the list length must be n>=3. Is there a solution for this case?

I see my assumption n>=3 is not correct in view of a circular list. The list (2, 3) implies that 2 is minimum among its left neighbor 3 and right neighbor also 3. And 3 is maximum among its neighbors 2 and 2.

So the answer (2, 3) seems OK for the max=3 and min=2 case.

vaaven What is the $$$O(n\sqrt{n}+q\log q)$$$ solution? Please tell us.

CodeWe can split our quieries in two groups. $$$r - l > \sqrt{n}$$$ and $$$r - l \leqslant \sqrt{n}$$$. Let's solve the task for each queries in order of increasing $$$r_i$$$. For second group of queries it's really easy to solve this task, because after moving $$$r$$$ to $$$r + 1$$$ we need to recalculate nearest element only for $$$\sqrt{n}$$$ elements. For first group we can do similar dp but not for elements but for answers. This will work in $$$\mathcal{O}(n \sqrt n + q\sqrt{n})$$$. To reach $$$\mathcal{O}(n \sqrt n + q \log q)$$$ we need to sort queries for each $$$r$$$ in order of decrease $$$l$$$ and understand that answer deacrese. That's why we can use smart pointer and our solution will work in $$$\mathcal{O}(n \sqrt n + q \log q)$$$.

This sorting task can be done in linear time. First sort the queries in deceasing $$$l$$$. This can be done with counting sort. After this, put each query to its $$$r_i$$$ bucket. Because this doesn't change the relative position for queries whose $$$r_i$$$ are the same, so we finished the sorting in linear time.

Complexity is $$$O(n\sqrt{n}+q)$$$ now.

ps: Thank you for this solution. I learnt a lot.

Yeah, we know about $$$\mathcal{O}(n\sqrt{n} + q)$$$ solution, but we are too lazy to сode a counting sort ¯ \ _ (ツ) _ / ¯

Hi, can you please tell me the test I'm missing for problem A: wrong answer 1202nd numbers differ — expected: '666666667', found: '1000000000'

Nvm, I found the issue.

It took me a really long time to understand the E editorial. Anyone else on the same boat?

C: Dora & Search Why would this O(n(logn)) fail on given constraints?

Code

Can anyone tell me why WA on tc 9. https://codeforces.com/contest/1793/submission/209140213

I got the idea of D but couldn't trivially find the intersections (while I practiced).

Alternate $$$O(n\log{n} + q)$$$ solution for problem E using binary search (can be optimized to $$$O(n + q)$$$) :

Let satisfiability of person $$$i$$$ be $$$S(i)$$$. Also, sort all the people in increasing order of $$$S(i)$$$.

The first observation is the same as the editorial, For any $$$k$$$(number of groups to partition the people into), there exists atleast one optimal partition in which only some prefix of people are satisfied.

Now let's consider trying to partition the given set of people into the maximum number of valid groups.

We can observe that an optimal assignment strategy is to do the following repeatedly:

Starting from the first unassigned person till that moment, create the

smallestvalid group which consists of a subsegment in the sorted array. (ie. keep adding people into this set only till it remains invalid, stop once it becomes valid).At the end we will be left with some suffix of unassigned people, and it's optimal to assign these people to the last group that we made (this way the maximal prefix of this suffix becomes satisfied as the last group is the largest).

Why is this optimal?Firstly, observe that each created group's (through the assignment strategy) size is equal to the last element in it (as adding any less/more would be a contradiction to the fact that we create the smallest possible valid group).

Secondly, the proof for groups being continuous segments is mentioned in the editorial.

Lastly, we can easily show that there exists atleast one optimal solution in which making only the smallest groups is optimal using contradiction and exchange arguments (consider what happens when we add extra elements to a group)

Now consider binary searching on maximal size $$$x$$$ of prefix of satisfied people we can get for $$$k$$$ groups. It's optimal to use the unsatisfied suffix to occupy as many groups as possible, so that the prefix has to occupy the minimum number of groups. Therefore each person in the suffix should be alone in his group.

Now there are two cases:

Now we can see that some (say $$$a$$$) of the created "groups" from the optimal strategy lie completely within the prefix of size $$$x$$$, and atmost one (last) group may lie partially within this prefix.

Now, if $$$a < k - n + x$$$ then it's obviously impossible for us to satisfy everyone in this prefix as that would be a contradiction to the fact that our assignment strategy was optimal.

Otherwise, if $$$a \geq k - n + x$$$ then the optimal thing for us to do is to put the first $$$k - n + x - 1$$$ groups into seperate groups, and put all the remaining people in the prefix into the last group. This is optimal because each group's size is equal to the last element in it, and we want to put the people from the last group (which lied partially within the prefix $$$x$$$) into a group with the maximum number of people (as rest of the groups lie completely within the prefix and will be satisfied anyways).

Thus we can check for a particular $$$x$$$ (size of prefix) and $$$k$$$(number of groups), if it's possible to make such partition in $$$O(1)$$$ time. For a fixed $$$k$$$, $$$f(x, k)$$$ is obviously boolean monotonic, so we can binary search.

How to optimise this to $$$O(n + q)$$$ you say? Just observe that as $$$k$$$ increases, $$$x$$$ decreases, so we don't even need binary search. Also, we can sort by satisfiability in $$$O(n)$$$ using counting sort, as $$$1 \leq a_i \leq n$$$.

$$$O(n + q)$$$ Implementation: link