1619E based on a similar idea (although easier) to Problem D of this contest. Got the idea for D through this previously solved problem.

is this contest rated?

You want:

Rated:

Unrated:

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})$$$

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

193336874

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 :(

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].

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

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

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

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.

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).

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.

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

Link to Submission

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)$$$

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

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<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> 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);
    }

Can anyone tell me why WA on tc 9. https://mirror.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 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).

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:

1. $$$[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.
2. $$$[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

A more intuitive version of the halving condition in F is just:

Consider the set of points that are "updatable" by the first condition, this is monotonically increasing (when we consider all a[j] > a[i]). Update the rightmost two points that satisfy the condition. Now:

let d = a[j] — a[j-1] (in the monotonic point set)

If d is "small", then we know our search range is [a[i], a[i] + d]

If d is "large", then we know that a[j-1] is small anyways. Since there's no points in between j-1 and j by definition, it's also a candidate for shrinking the valid updating range by

So our new update range is always [a[i], min(a[i] + d, a[j-1])]. If you draw a picture, the worst case is at the halfway point, so it shrinks in log(n) steps.

The visual intuition for the problem still makes sense in the editorial too, but this is even clearer IMO, and it motivates the solution a lot more I feel.