Let me give it a try.

Sort all the given N number in the decreasing order. Maintain a disjoint set union with N components initially. Start traversing array in the decreasing order and for current element with index i, add edges [i, i+1] if A[i+1] >= A[i] in the dsu similar add edge for [i-1, i] if A[i-1] >= A[i]. After each step maintain the count of possible subarrays with size K which will be summation_of(component_size-K+1). This count will keep on increasing as you are traversing array.

Now any two values can be act as X & Y such that X <= Y if count_of_subarrays_at_Y — count_of_subarrays_atX >= Q. This can be easily calculated by sorting the count and two pointers.

I have not validated this approach.

Hmm... I gave up on B =)

The idea is we can form a bipartite graph with points. Then choose a partition in it.

My idea comes from the proof given in here tutorial to choose greedily the largest partition.

Let's fix the order of points. After that, we can iterate over them and add points greedily.

Checking if we can add a point to the current set is relatively straightforward. Let's find all such integer a and b such that a * a + b * b == d1 and do the same thing for d2. After that, we just need to iterate over all these pairs and mark some points as unfeasible when we add a new point to the set.

The more interesting question is how to find a "good" order. I did the following: let's sort the points by (x + y) % mod for several small values of mod. It's sufficient to pass all tests but one. If sorting by the sum modulo something works pretty well, why not sort them by the difference? Indeed, sorting them by (x - y) % mod for a few small values of mod is sufficient to pass all the tests. In my case, "several small values" means 2, 3, 4, 5, 6, 7 for the sum and until we're done for the difference.

I solved it by generating a few interesting cases (with many ways to represent d as a sum of squares of two integers) and making random changes to my code until it passes them. I still have no idea why this solution works.

You can take a look at my incredibly beautiful code for implementation details: https://pastebin.com/v6YDFrPG.

You can solve it recursively

only remainder by 4 matters for each D, there are lots of cases though

for example, when D1%4=3 and D2%4=3 you can pick all points

when D1%4=0 and D2%4=0 you can solve recursively 4 subproblems with same x%2 and same y%2, using D1=D1/4,D2=D2/4, then merge everything

Other cases are similar, sometimes you take only odd rows, sometimes only odd columns, sometimes with x%2=y%2

My solution is quite simple. Start with the set of all points. If , remove points with . If , remove points with . If , there is no need to do anything. If , set D₁:  = D₁ / 4 and check ⌊ x / 2⌋ and ⌊ y / 2⌋ instead of x and y. Do the same for D₂. Code.

If you are finding D difficult, you can try out this question on HackerEarth first. (Problem F of June Easy Challenge 2018).

It's an easier version of D, because there's only one distance rather than 2. :)

Coincidentally, it was asked just two days before the AtCoder Grand Contest.

You can see everyone's submissions here. Click on Details link in the rightmost column to see the code.

Painting a level green is like painting that level blue and then red. So you can iterate over the number of levels you're going to paint blue (let's call this I). The number of levels you'll have to paint red will be uniquely determined (let's call this j). Then you add choose(n,i) * choose(n,j) to answer.

If you fix the number of red, then you just calculate the number of blue one. So all other just calculate binomial coefficents in O(1). It can be done by storing factorial and reverse factorials.

I want to add link to my submission, but I can't find the link to submission on atcoder site.

P.S. I found the link Code

I spent a lot of time on that and passed all but two tests :(

I got TL on a single test, optimised my solution for a lot of time and in the end I found out that on test 300 5000 10000 I can only get about 50000 points. :(

Sorry, we completely agree with your idea in general. The main part here is to get anything better than O(n²), and we want to allow them if possible.

However, this time we are quite afraid of O(n² / 64) with very small constant factor.

Was it easy for you? For me it looks like an impossible problem even with the log factor, while E is quite solvable.

My solution passed without any problems.

You can check the formula here.

After checking it, you'll find this (negative rating change) reasonable.

In short, your rating is a weighted average of your performances (over all rated contests). And it weights more for recent contests or high performance contests.

So when you get a new rated contest, it decreases the weight of all other contests. And (in your case), ARC098 and ARC097 have significantly higher performance, which leads to your rating decreasing.

Consider a point. In every row there can be at most four points on that row adjacent to the considered one (two on distance d₁ and two on distance d₂), therefore total number of adjacent points cannot exceed 8·n. And we can find them all in linear time using two pointers.

It is modular multiplicative inverse of n! with respect to modulus 998244353.

Because number of ways to choose k items out of n is n! / (k! (n — k)!)