Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### vaaven's blog

By vaaven, 10 months ago, translation,

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.

$q \cdot \min(a \cdot m, b \cdot (m + 1)) + r \cdot \min(a, b)$

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
• +130

 » 10 months ago, # |   +3 is this contest rated?
 » 10 months ago, # | ← Rev. 3 →   0
•  » » 9 months ago, # ^ |   0 [deleted]
 » 10 months ago, # | ← Rev. 2 →   0 You want:Rated: Unrated:
•  » » 10 months ago, # ^ | ← Rev. 3 →   +2 Edit: the ratings have been updated!!
•  » » 10 months ago, # ^ |   +72 if copy F: rated else unrated
•  » » 9 months ago, # ^ |   0 Though I solved F, I think it shoud be unrated. But now it is rated.
 » 10 months ago, # |   +9 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})$
•  » » 10 months ago, # ^ |   +29 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.
•  » » » 10 months ago, # ^ |   0 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...
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » » 10 months ago, # ^ |   +27 Practice on infoarena and this won't feel that amazing.
•  » » » » » 9 months ago, # ^ |   +8 What is infoarena dude ?
•  » » » 10 months ago, # ^ |   +5 Could you describe your solution, please?
•  » » » » 9 months ago, # ^ |   +5 It's something like this: link
•  » » » 9 months ago, # ^ |   0 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?
•  » » » » 9 months ago, # ^ |   +15 What optimizations you are talking about?
•  » » » » » 9 months ago, # ^ |   0 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
•  » » » » » » 9 months ago, # ^ |   0 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.
 » 10 months ago, # |   0 Could someone help identify the mistake in my code for problem D?193336874
 » 10 months ago, # |   0 Problem C : Dora and Search Video Editorial Link : https://youtu.be/l5GgWZmsZ98 Happy Coding
 » 10 months ago, # |   +8 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.
 » 10 months ago, # |   0 first time i got to solve D in contest and i was just 10 seconds away from submitting it :(
•  » » 10 months ago, # ^ |   +1 same here ;(
•  » » 10 months ago, # ^ |   +4 Also was super close to submitting D. Bricked B hard :(
 » 10 months ago, # |   +4 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].
•  » » 9 months ago, # ^ |   +8 Every time comes a new $i$ , we try to update all the $dp_j$ that $ja_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.
 » 10 months ago, # |   +1 Only got a micro positive delta but luckily became expert from specialist narrowly :)
•  » » 9 months ago, # ^ |   0 congratz)
 » 10 months ago, # |   0 Can sqrt-decomposition solve the problem F? I got a TLE and don't know how to optimize
•  » » 10 months ago, # ^ |   +3 Yes, and it runs really fast.
 » 10 months ago, # |   0 Can't I just put 'n' to place 'q' in problem a tutorial?
 » 10 months ago, # |   0 Can anyone Please explain Problem B . It is really Confusing.
•  » » 10 months ago, # ^ |   0 Read my code here. U might understand. https://codeforces.com/contest/1793/submission/193333638
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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
 » 10 months ago, # | ← Rev. 2 →   +7 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.
•  » » 9 months ago, # ^ |   +4 Thank you very much, I finally understand what editorial is trying to say .....
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 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=aj>=ai and index j is no longer satisfied as bj=x, and number of x's in b = 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 , ak array 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=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!
•  » » » 9 months ago, # ^ |   +5 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.
 » 10 months ago, # |   +52 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).
•  » » 9 months ago, # ^ | ← Rev. 4 →   0 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).
•  » » 9 months ago, # ^ |   0 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.
 » 9 months ago, # |   0 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.
•  » » 9 months ago, # ^ |   0 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
•  » » 9 months ago, # ^ |   +3 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
•  » » » 9 months ago, # ^ |   0 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".
•  » » » » 9 months ago, # ^ |   0 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
•  » » 9 months ago, # ^ |   +8 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.
•  » » 9 months ago, # ^ |   +5 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
 » 9 months ago, # |   0 Can anyone tell me why wrong answer is coming for Test 6 in problem D?Link to Submission
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 52 3 1 4 52 3 1 4 5
 » 9 months ago, # |   +11 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?
 » 9 months ago, # |   0 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?
 » 9 months ago, # | ← Rev. 2 →   0 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$.194176722Final Complexity: $O(N \sqrt N \log N + Q \log N)$
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 9 months ago, # ^ |   0 You are right. I updated the post.
 » 9 months ago, # |   0 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?
•  » » 9 months ago, # ^ |   0 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.
 » 9 months ago, # |   0 vaaven What is the $O(n\sqrt{n}+q\log q)$ solution? Please tell us.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +5 Code#include "bits/stdc++.h" #define rep(i, n) for(int i = 0; i < (n); ++i) #define repr(i, n) for(int i = (n - 1); i >= 0; --i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define ar array using namespace std; typedef long long ll; using vi = vector; using vvi = vector; using vl = vector; using pi = pair; const int INFi = 2e9; const ll INF = 2e18; const int maxN = 6e5; const int K = 350; void solve() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vi a(n); rep(i, n) cin >> a[i]; vi pos(n); rep(i, n) { a[i]--; pos[a[i]] = i; } vvi qs(n); vi l(q), r(q); vi ans(q, -1); rep(i, q) { cin >> l[i] >> r[i]; l[i]--; r[i]--; qs[r[i]].push_back(i); } vi dp(K, -1); vi dp2(n, INFi); int len = 1; while(len * K - (K - 1) <= n) len++; for(int i = 0; i < n; ++i) { for(int j = max(a[i] - K + 1, 0); j < min(n, a[i] + K); ++j) { if (pos[j] < i) dp[abs(j - a[i])] = max(dp[abs(j - a[i])], pos[j]); } for(int j = i - 1; j >= max(i - len, 0); --j) { dp2[j] = min(dp2[j], min(dp2[j + 1], abs(a[i] - a[j]))); } sort(all(qs[i]), [&] (const int &x, const int &y) { return l[x] < l[y]; }); int j = 0; rep(t, K) { while(j < qs[i].size() && l[qs[i][j]] <= dp[t]) { ans[qs[i][j++]] = t; } } while (j < qs[i].size()) { ans[qs[i][j]] = dp2[l[qs[i][j]]]; j++; } } rep(i, q) { cout << ans[i] << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; rep(_, t) { solve(); } return 0; } We 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)$.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +5 Yeah, we know about $\mathcal{O}(n\sqrt{n} + q)$ solution, but we are too lazy to сode a counting sort ¯ \ _ (ツ) _ / ¯
 » 9 months ago, # |   0 Hi, can you please tell me the test I'm missing for problem A: wrong answer 1202nd numbers differ — expected: '666666667', found: '1000000000'
•  » » 9 months ago, # ^ |   0 Nvm, I found the issue.
 » 8 months ago, # |   0 It took me a really long time to understand the E editorial. Anyone else on the same boat?
 » 7 months ago, # | ← Rev. 3 →   0 C: Dora & Search Why would this O(n(logn)) fail on given constraints?Code static void solve(int tc) { int n = io.nextInt(); int[] a = io.nextIntArray(n); PriorityQueue max = new PriorityQueue<>(Collections.reverseOrder()); PriorityQueue min = new PriorityQueue<>(); for(int i:a){ max.add(i); min.add(i); } int p1 = 0, p2 = n-1; while(p1<=p2){ if(a[p1]==min.peek() || a[p1]==max.peek()){ //not this min.remove(a[p1]); max.remove(a[p1++]); }else if(a[p2]==min.peek() || a[p2]==max.peek()){ //not this min.remove(a[p2]); max.remove(a[p2--]); }else{ //found io.println((p1+1)+" "+(p2+1)); return; } } io.println(-1); } 
 » 6 months ago, # |   0 Can anyone tell me why WA on tc 9. https://codeforces.com/contest/1793/submission/209140213
 » 4 months ago, # |   0 I got the idea of D but couldn't trivially find the intersections (while I practiced).
 » 3 months ago, # | ← Rev. 2 →   0 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 smallest valid 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: $[n - x \geq k]$ in this case, all groups except the first will have only one guy from the suffix, and the first group has all the remaining people from the suffix. All the people from the prefix should obviously be put in the first group as it has the most number of people. We can check in $O(1)$ if all people will be satisfied as we only need to check if the last guy of the prefix is satisfied. $[n - x < k]$ in this case, there will be $k - n + x$ empty groups left after each guy from the suffix is assigned a unique group. 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