I liked the problems and the contest overall. The beautiful illustrations were the cherry on top !!!

E2,I cannot understand why multiplication is O(lognk^3).For each fixed sum S,we need to recalculate the matrix.why is not O(lognk^4)?

C is also solvable with Digit DP!

ans of E is

https://codeforces.net/contest/1808/submission/199905893

Problem C I tried to solve with simple maths but idk why getting Wrong Ans in TC7 (158 case).Is there any corner case?

I have added my approach :

Approach:

First im checking whether l and r of same length (cnt1 and cnt2)

a) in case they are nothing for ex say 12 and 113 then answer is simple 10^cnt1 -1 (99 in this case)

b) in case they are of same length then we traverse from right to left( in v1 ,v2 vectors we store digits of l and r from right to left) Till we get their first point of difference

b1) if there is no diff ie l and r are same we print l

b2) suppose there is difference at index i. So we keep a track of maxi,mini of digits till i-1 and these digits will surely be in ans. Suppose at index i, l has digit a and r has digit b . then the value at index i can move from [a,b]

So I made a for loop from a to b: In case I =a ,we have to make sure than maxi doesnt increment else diff may be inc. So suppose we keep

276___ say 6 is a If we get any digit less than maxi till index i, All the next digits can be madi Suppose l = 276134 So in this case we will store the val 276777 And compute min diff

Else if digit is greater than or equal to maxi we will move with same digits (I=2 and a=6) Suppose l= 276814 So corresponding no will be 276888. Now compute maxi-mini and check.

If I= b ,same reverse logic for I=a,

Else if i b/w a and b , keep all the digits from point of difference as i

So for I>=a and I<=b find min diff and print

Can someone please explain D in simpler way?

D: For every index $$$i$$$, let's see all such indexes $$$j$$$, that there is exists such subarray of $$$a$$$ $$$[l; r]$$$ of size $$$k$$$, that $$$i$$$ — $$$l$$$ = $$$r$$$ — $$$j$$$; for index $$$i$$$ let's call all such positions $$$j$$$ good.

We can see, that for all odd $$$i$$$ good positions are odd too, for all even $$$i$$$ good positions are even.

For every index $$$i$$$ we have to count $$$z$$$ = number of non-equal to $$$a_i$$$ elements on good positions, to do this we can count $$$x$$$ = number of good positions and $$$y$$$ = number of equal to $$$a_i$$$ elements on good positions, $$$z$$$ = $$$x$$$ — $$$y$$$.

Let's build two Merge Sort Trees, one for elements on odd indexes and one for elements on even indexes.

The number of good positions is just some simple math, the number of equal to $$$a_i$$$ elements on good positions is just one Merge Sort Tree query (if $$$i$$$ is odd, query to first MST, otherwise to the second).

Answer is (sum of all $$$z$$$ for all $$$i$$$) / $$$2$$$.

Time complexity: $$$O(n$$$ * $$$log$$$ ^ $$$2)$$$.

My solution: 199667931

Is the total time complexity of E2's solution O($$$k^4logn$$$)?(for each sum from 0 to k-1 there's a O($$$k^3logn$$$))

For problem A, there's a solution using sparse table if you couldn't get the observation like me. 199925584

can somebody explain solution of B in simple terms?

Problem D has O(n logn) solution: https://codeforces.net/contest/1808/submission/199685296

In a same way as in the post we can transform orignal problem into counting pairs of equal elements, with some restrictions on distances between them.

Idea is to group all numbers by (array value, parity of its index), and for each group have an array of indexes. In each such array we have indexes of equal numbers, and for each element we need to only count a number of elements in some segment (coming from the distance restrictions).

Deleted.

Can somebody explain problem C tutorial's the first paragraph? For example, input values are $$$l=2340$$$ and $$$r=2360$$$. Common prefix: $$$23$$$, so $$$a=4$$$ and $$$b=6$$$. Condition $$$b-a >= 2$$$ is true, so tutorial advices to put $$$4+1=5$$$ as next digit of answer. But correct answer is $$$2344$$$.

Thanks in advance.

In fact,the Problem E3 have one solution that costs O(k*log(n)).K can be much larger,for example,10^6 is ok. We can even develop a solution that costs O(log(n)) based on my thinking possibly.

Simple O(n) solution for D: https://codeforces.net/contest/1808/submission/200108231

For problem D, I'm not completely sure about the first half of the 3rd paragraph in its solution. In particular, I get what the setup for array a looks like. However I'm not sure why the condition that a_i*a_j = 1, j-i<k, and (j-i)mod2 is enough. For example if the array a looks something like this: 101000101 and k = 5, then i can match the first and third indices as they satisfy those conditions. However they wouldn't correspond to each other in any substring of length 5.

solution for problem-C using digit dp- https://codeforces.net/contest/1808/submission/200349073

Since no one has mentioned it before, it is possible (and is very pleasant) to solve E3 in logn + logk using roots of unity

The tutorial of problem C really sucks!!!

I have a cool digit dp solution of C

When I solve E, the first thing I come up with is PIE, well the computation is not much and easily passed in O(K) runtime :v

Problem D : Brute force solution (count dissimilar pair for all subarray) is accepted using pragmas !! Taking only 1.1 second to be executed :) Note: Worst TP — (n^2)/8

Problem D cannot be solved with matrix but polynomial multiplication.277253973

awful explanation for C