This was one of the most unbalanced rounds ive been in but div2D was pretty cool i guess

My solution for Div2D/1B.

 0, 0 + 1, 0 + 1 + 2... (0... x-3) + x-2, (0... x-4) + x-1

Now, Let's do a binary search to find k.

length of segment [j, k] = k - j + 1 = query(1, k) - query(1, k-1) + 1.

j = k - query(1, k) + query(1, k -1)

you can repeat this for [i, j-1] to figure out i.

code

I also tried to explain my thought process, hope it helps. :D

speedforces and implementionforces

For problem D div 2, I don't know what went wrong with my submission at 135395991 (it received a Query Limit Exceeded), since I had the same approach and even took some time to reduce 2 binary searches down to 1. I then changed my binary search implementation (135421249), and got Accepted, but I still don't know why my old implementation of binary search used much more queries though.

I hope somebody could tackle my code and find out what's wrong with my old implementation. And I still feel pretty bad for having been so close to D, I could've been promoted to pupil. But overall, nice problem and great contest!

Video Editorial of A

For Div1D, we can just do dfs and use map to store answer.

I seem to get a runtime error for Div1C, which I can't reproduce locally for the same test case- anyone have ideas on what could be wrong?

https://mirror.codeforces.com/contest/1588/submission/135533102

UPDATE: I was able to edit the logic for modifying the map to get A/C but unable to see what the issue was. New submission- 135560689

I see... you guys have developed a new LaTeX formula usage.

It's normal for beginners to not use $$$\log$$$ instead of $$$log$$$. But when I see lonely =s and <s are excluded from the great union form by the $$ delimiters, my eyes blurred, poor little symbols.

Things all changed when you wrote binomial coefficients as $$$\Large (_2^{k - j + 1})$$$, a very impressive and revolutionary act. Now I can write Stirling numbers so easily: $$$\large [_2^{k - j + 1}]$$$ and $$$\large \{_2^{k - j + 1}\}$$$, forget about \brace and \brack, great job guys!

Bonus! I used Dinic to solve problem C!

For 1584D - Guess the Permutation there is easier solution. Instead of using [x, n] ranges, let's take a look at ranges [1, x].

• Notice, that starting from k number of inversions never change, because all numbers after k is greater than k, so they can't produce any inversions. So, using binary search over x we know k after around 30 queries.
• Then, notice that new value at position k is actually j, because this is how we reverse things. And before it there is exactly (k — j) numbers which are greater than j. So, if we ask [1, k — 1] we get number (k — j) and it's easy to derive j from it. This require single additional query (if you don't cache results).
• Notice that for [1, j — 1] works same approach: at position (j — 1) stands i. And before it there is exactly (j — 1 — i) numbers which are greater than i. So if we ask [1, j — 2] we get number (j — 1 — i) and it's easy to derive i from it. This require two additional queries in case when range [j, k] is not short.

So, it require around 33 queries in total. No binomial coefficients involved, no quadratic equations envolved.

Different algorithm for 2D:

• First do the query [1,n] and find the total inversion $$$TS$$$.

• Lets try to find the position of $$$j$$$.

• Lets do query in the form [1,x]. Suppose we get $$$S$$$.

• How to know $$$x<j$$$ or not?

• If $$$S==TS$$$ it definitely is not.

• If $$$S==0$$$ it definitely is.

• Otherwise lets try to find a integer solution to the equation $$$\frac{p*(p-1)}{2}=S$$$ for $$$p>1$$$

• If we can't find a solution then definitely $$$x>=j$$$. If we can find a solution , it is likely that $$$x<j$$$ but we can't be sure because there may also be a solution to $$$\frac{p*(p-1)}{2}+\frac{q*(q-1)}{2}=S$$$ where $$$p>1$$$ and $$$q>0$$$. So lets do the query [1,x-p+1] and get the sum $$$QS$$$.

• If $$$QS==0$$$ then $$$x<j$$$. And we can find $$$i=x-p+1$$$. Once we find the value of $$$i$$$, we can later use it to check whether $$$x<j$$$ or not by checking whether $$$x-p+1==i$$$ or not.

• Otherwise $$$x>=j$$$ and we continue with binary search.

• According to my intuition there are not so many cases we would encounter where we can find integer solutions to both the equations $$$\frac{p*(p-1)}{2}=S$$$ and $$$\frac{p*(p-1)}{2}+\frac{q*(q-1)}{2}=S$$$ for $$$p>1$$$ and $$$q>0$$$. Thus we won't be doing double queries that much, at least until finding the value of $$$i$$$, after which we won't be needing double queries any more. And we have 40 queries which means 7-8 extra queries.

**I have not proven the correctness the algorithm yet and there may exist hack cases

div. 2 E $$$c_i^l = a_i^l - a_{i - 1}^l + \ldots + (-1)^{i-1} \cdot a_1^l = a_{l+i-1} - a_{l+i-2} + \ldots + (-1)^{i-1} \cdot a_{l} = c_{l+i-1} + (-1)^{i-1} \cdot c_{l - 1}$$$

Doesn't $$$c_i^l$$$ mean $$$c_{l+i-1}$$$ ?

What is "efinegraph" in Strange LCS ?

Problem C can be done in O(N) without sorting. Code

Explanation : Just count the frequency of each number then for each number it's enough to check this condition :

extra[x] + cnta[x] >= cntb[x]. (extra[x] here defines frequency of x-1 left over in the array a.)

1589E - Game with Stones can be solved using "Venice Technique" or whatever you call it. 135753412

imo it would be better to make elimination rounds with full tests and not pretests, because it isn't just matter of rating, many people can be eliminated because of terrible pretests like in this round.

Just wondering for Eligible Segments. You have a constraint that $$$R$$$ being changed by $$$10^{-2}$$$ will not affect the answer. How did you write the validator to check that hacks do not violate this constraint?

Hey guys, in problem Div2-E/Div1-C, I'm getting MLE on test 37 here and I'm not able to see why. Can someone help me?

Code: https://mirror.codeforces.com/contest/1588/submission/135797278

no one's wondering where the tutorial of 1588F - Jumping Through the Array goes?

or someone just gives a short explanation

Could you please publish some STDs to make the solution easier to understand?

I have another idea for 1589E - Game with Stones 136087401. Find all l for r(r -> count(l)). s[i] = k * x[i] + b. After taking i-th rock apply k_new = -k, b_new = k * b + s[i], and lets encode every s[i] as x[i], so after taking j-th rock, k * x[i] + b — gives addition for every rock in [i, j], and then delete every x, s.t. k * x[i] + b < 0. Because k = +-1, we can find such x, kx + b = 0, and then xs that we must delete will be x + dir, x + 2 * dir, x + 3 * dir, etc. For every rock we must add count of xs that kx + b = 0

Div 1D can be solved in $$$O(|\Sigma|^2 2^n)$$$.

In editorial of 2E, shouldn't it be $$$C^l_i<0$$$ if and only if $$$C_{l+i−1}<(−1)^iC_{l−1}$$$ instead of $$$C^l_i<0$$$ if and only if $$$C_{l+i−1}<(−1)^{i-1}C_{l−1}$$$

can anyone tell whats wrong in my approach for problem C. Two Arrays .... I am first matching all the already matched elements of array b with array a and deleting them simultaneously from both arrays. Then I am matching the remaining elements of array a with remaining elements of array b by adding 1 to them...If some element is not matched I am printing "NO". Else after end of loop I am printing "yes".

For Div2E. the problem reduces to finding the nearest position on suffix which is strictly less than some $$$x$$$. Can some one please explain in a bit more detail as to how to do it?

Sorry for necroposting, but why isn't the following solution valid in F:

Take the LCS of first two strings. this is O(sigma^2) (because each string can have up to 2 * sigma characters). Then, take the LCS with the third string (because LCS is associative). this is still O(sigma^2). So on and so forth and we get the final LCS in O(sigma^2 * n), much faster than what is written in the editorial.