i learnt a lot from this contest. Thanks a lot for such a educational one.

I could just solve 2 questions but the the problems were really educational. Thanks for the preparation.

Maybe you shoule've set n,k <= 2500 or sth for problem E, because this way many were able to make the n^2k pass while others (myself included) didn't even try it even with the idea in mind

yaya, nice to see the nk^1.5 solution, was wondering about that from seeing all the fast submissions

I had a different solution for E that runs in $$$O(n^2 \sqrt{k})$$$ and is adapted from the slow dp:

Let $$$m$$$ be the number of balls and let $$$pos_i$$$ be the position of the $$$i$$$th ball. Then, we can calculate $$$dp[i][k][j]$$$, the number of ways to put the first $$$i$$$ balls in the first $$$j$$$ bins, the cost is $$$k$$$. I order like $$$i, k, j$$$ for cache purposes. This is just a standard dp, where the transitions are $$$dp[i][k][j] = dp[i][k][j-1] + dp[i][k-|pos_i-j|][j-1]$$$.

We can observe the following fact: the position of the $$$i$$$th ball is limited to the range of $$$[pos_{i-\sqrt{k}-1}, pos_{i+\sqrt{k}+1}]$$$, where negative indices are filled with 0 and indices above $$$m$$$ are filled with $$$n$$$. This is true because if the ith ball went beyond this range, at least $$$\sqrt{k}+1$$$ balls would have to move at least $$$\sqrt{k}+1$$$ distance.

This optimization is important because the distance between balls is roughly $$$n/m$$$, so the size of the average range among the balls is $$$\sqrt{k} \cdot n/m$$$. Over all of the balls, and over all costs, the total number of positions we will look at in our dp will be $$$O(m \cdot n \cdot (\sqrt{k}\cdot n/m)) = O(n^2 \sqrt{k})$$$.

For the implementation, we can store a table $$$range[i][k] = [pos_{i-\sqrt{k}-1}, pos_{i+\sqrt{k}+1}]$$$, which is the range of $$$j$$$ that $$$dp[i][k][j]$$$ is calculated for. The dp values before this range are 0, and the dp values afterward are just the dp value of right endpoint of the range. This allows us to avoid traversing all $$$j$$$ from 1 to $$$n$$$ for every $$$i, k$$$, and only traverses the ranges that we care about.

Submission: https://codeforces.net/contest/1845/submission/211638320

can C be done using digit DP?

Why I am getting WA on D? Can someone Help me? Tried 2 different approaches.

Approach 1 : https://codeforces.net/contest/1845/submission/211638397

Approach 2 : https://codeforces.net/contest/1845/submission/211644844

Why is the explanation for B so sub quality? No definition for bounding box, "since d(X,B)+d(X,C) is constant and equal to d(A,B) if X is in the bounding box. " Randomly stating facts

sad

Here's another solution for C. The idea is to count the #of unique valid passwords of length m in the password database. Then if the #of unique valid passwords is less than the total #of valid passwords, there is guaranteed to be at least one password that we can use for our answer. You can count the #of unique valid passwords of length m in the database using dp.

211486674

Does anyone know of a good resource that explains how to use FFT to solve problems like 1845F - Swimmers in the Pool from scratch, i.e., without assuming I already know what a FFT is and how it applies to problems like this?

Some key observations in problem D:

1. The value of K is one of the prefix values of the array (As it is clearly mentioned that, to get benefited player must achieve achieve a minimum of score 'K')
2. We can go over all prefixes of the array and for each prefix value we again can compute the maximum score (N^2 solution)

From now on we try to reduce the complexity from N^2 to N

1. The suffix of array having all positive elements will always contribute positive to the answer , for example, A = [-1, -1, 2, 2] then the suffix [2,2] (last two elements) will always be added to the answer no matter what prefix we choose (As there are no negative elements after them to reduce its value back to k)
2. Lets call this suffix as confirmPos. Now the array can be divided into continuous subsegments based upon the signs of elements.
3. Lets focus on two subsegments A, B. Such that Array = [....., A, B, confirmPos]. Now its clear that all elements in B are negative and all elements in A are positive let, pos = sum(A) & neg = sum(B)
4. There are two cases

• pos + neg < 0, this will contribute negative to the answer, so for the next iterations, neg = neg + pos; pos = 0.
• pos + neg > 0, which essentially means their total contribution to the answer is always positive no matter what prefix we choose (As we are going backwards in array, we know there is nothing negative to reduce this value further more). Thus we can consider them as confirm positive thus, for next iteration, confirmPos += pos + neg; pos = 0; neg = 0;

These observations derive the fact that for index i

maximum answer by keeping k as pref[i-1] = pref[i-1] + max(0, pos + neg) + confirmPos

sorry for poor english, I tried my best to explain what I understood from the problem :)

Submission Link

Can anyone help me to remove the RE in 3rd Question

Hi can anyone explain why binary search on k does not work for D? I kept thinking of counterexamples but I cannot seem to find any.

Can anyone explain binary search solution to C?

I think the questions in this game are very good

Why the time limit of problem E is 5s?

211713164 My solution is $$$O(n^2k)$$$,it only executed 1029ms

Here is another idea for D: consider the following question: what the rating change will be (if we can simplify it) after applying a list of rating changes a[1], a[2], ... , a[n]. Observe that:

• if a[i] is 0, delete it.
• if a[i] and a[i+1] are both positive or both negative, merge them to a single item.
• if a[i] is positive and a[i+1] is negative, merge them too.
• if a[i] is negative and a[i+1] is positive, the change depends on k, so we keep both a[i] and a[i+1] unchanged.

After applying transformation above on initial rating changes list, the size of result list will be at most 2. So we can enumerate every index i, to check:

• define rating is R[i] after rating changes from beginning to a[i];
• set k = R[i];
• with fixed initial rating and fixed k, apply following rating changes (a[i+1], a[i+2], ... , a[n]) to get final rating.
• update overall result.

To get simplified rating change list for each index i, we can calculate backwards from index n to index 1.

Some of the results will be invalid, since for some R[i], the rating on previous steps may reach k (=R[i]) and then drop below k (=R[i]), so use R[i] as initial rating with k=R[i] is actually wrong. But in such cases the result got from the step that "reach k" will always be better, so we can just ignore such (wrong) cases.

Can someone please tell me why my solution is so slow, although it is accepted? I used $$$dp[i][j][k]$$$ =number of ways to store first $$$i$$$ balls in first $$$j$$$ boxes such that minimal cost for it is $$$k$$$. Transition looks like:
$$$dp[i][j][k]=dp[i][j-1][k]+dp[i-1][j-1][k-|pos[i]-j|]$$$ , there $$$pos[i]$$$ is position of $$$i$$$th ball on the beginning. Solution would be sum of $$$dp[m][n][i]$$$ for each $$$i$$$ of same parity as $$$k$$$,where $$$m$$$ is the number of balls. Also I used that for $$$i$$$th ball set of possible positions $$$j$$$ on which we can move it belongs to interval $$$[pos[i-\sqrt{k} -1],pos[i+\sqrt{k}+1]]$$$.
In this comment https://codeforces.net/blog/entry/117791?#comment-1042133 was explained why time complexity should be $$$O(n^2\sqrt{k})$$$. Most of solutions have runtime up to $$$1000ms$$$, but mine is more than $$$3700ms$$$, so I would be grateful if someone can tell me why is it so? This is my submission: https://codeforces.net/contest/1845/submission/211839395

$$$\textbf{Upd}$$$ I got it, only need to change from long long to int

I want to add something about problem F.

I didn't really understand what the P.S. in the tutorial for this problem means, maybe it is exactly what I want to say, then I am sorry.

I just wanted to say that I think that Möbius transform is too hard of a concept for situations as described in the problem. Here we have a situation where we have some array $$$a_i$$$ consisting of sums of answers over all divisors of $$$i$$$, and we would like to get the actual answer array $$$b_i$$$. So we know $$$a$$$ and we know that $$$a_i = \sum_{j \vert i} b_j$$$. In situations like this indeed one could use Möbius but it is not actually needed.

Let's imagine that instead we actually have the array $$$b$$$, and we would like to calculate the array $$$a$$$. How would we do it? Well, for every number just go through all the divisors and sum up the corresponding $$$b$$$ values. As going through dividends is easier, we would probably do that instead. And if we want to recalculate it in-place, we need to go in the decreasing order of $$$i$$$ to not add things many times. The code would look something like this:

for (int i = n; i > 0; i--) {
    for (int j = 2 * i; j <= n; j += i) {
        b[j] += b[i];
    }
}

If you found my explanation not so clear, I just want you to realize that this is a very natural and obvious way to do the job we want. If you were asked to do this, you would come up with exactly the same solution. Just add the value to all dividends but be careful with the order (the same way as with the knapsack problem).

Now we have an algorithm that transforms the array $$$b$$$ into the array $$$a$$$. "And what? We want the opposite!" you will say. Exactly! We want to do exactly the opposite. Just imagine in your head that you have the array $$$b$$$ and run this algorithm. Step-by-step. And now comes the key idea: just imagine that you have a weird time machine that allows you to reverse time. If you reverse time, the algorithm will run in the opposite direction and it will go back from the array $$$a$$$ to array $$$b$$$. This is exactly what we want! Now it remains to understand how to code an algorithm that reverses the time. It is easy. We should just undo all the actions in the reversed order. If we have a cycle, we should reverse it. If we add something, just subtract! Here is the solution:

for (int i = 1; i <= n) {
    for (int j = 2 * i; j <= n; j += i) {
        b[j] -= b[i];
    }
}

You may notice that I did not reverse the inner cycle. I didn't do it because the actions that are performed inside this cycle are independent of each other: we just subtract $$$b[i]$$$ from all its dividends. You can actually think about this as just one single action that we reversed. I did it because it is just a bit more complicated to go through dividends in descending order, and it is actually not needed here. And now we indeed have an algorithm that transforms the array $$$a$$$ into the array $$$b$$$! And no math is needed! We just used a very generic idea. The beauty of it is that we don't even need to understand what the algorithm we are trying to reverse does. It is a very manual low-level job: reverse and inverse all the actions.

Yes, indeed you can analyze it and understand that it does exactly the same thing as the Möbius transform, but well... Yes... But I claim that this is more understandable, easier to reproduce, less magical, and you don't need to calculate the $$$\mu$$$ function.

Some more notes: this idea of reversing time can be used in many settings. The most common one is DSU with rollbacks. You just remember all the things that changed and undo the actions. But here we actually performed all these actions, and after that reverse them. In our situation, we only imagine that these actions were performed. So in the DSU with rollbacks we can do any actions we want, for example, we do something like updating parents of some vertices: $$$p_u = v$$$, and remembering what was the old parent of $$$u$$$ (well, in this case, it was $$$u$$$, so we don't need to remember it, but whatever). And later we can just go back and replace $$$p_u$$$ with the old value. Our situation is different: we don't know what was the old value, and we want to find it. For it to be possible, the actions that we perform should be inversible. So, for example, in our case, we add one number to another number. It is an inversible action: we can just subtract back to undo it. But if the action is, for example, assignment or taking the maximum of two values, it is not inversible, and we would not be able to do our trick if we had such actions. This idea is similar to the fact that prefix sums allow us to find sums and bitwise xors of segments but not minimums and bitwise ors.

You may argue that DSU with rollbacks only somewhat uses the same concept. It is not exactly the same. And I would agree. But there are other situations where we can use exactly the same idea. FFT, Walsh-Hadamard transform, sum over subsets (SoS-dp), sum over supersets, etc. If you look closely, for all of them, if we already know the convolution one way, the inverse can be obtained without knowing anything about the math behind these algorithms by simply reversing the time. And actually, the thing that we wanted to calculate can be called a sum over divisors. All these are some transformations that can be used for convolutions. FFT can be used for $$$+$$$-convolution, Walsh-Hadamard for xor-convolution, sum over subsets for or-convolution, etc.

And at the end of this long comment, I will leave you with two simple exercises: - if all of these transformations before could be used to get a convolution, what kind of a convolution does our transformation give? - use the method we discussed to get an inversed sum over dividends. What convolution does it give?

EASY DP SOLUTION FOR C

Hi, can anyone explain more about this balance in solution for E? I don't get why are only good solutions with balance equal to 0?

In F tutorial, what's the "easy system of equation" mentioned in the second paragraph?

Can anyone tell me why my solution gives WA for problem D. 211601552

Thanks You

Can someone help me in this interactive problem, couldn't figure out why I'm getting a TLE. https://codeforces.net/gym/101021/problem/1

My submisision: 212177668

Can someone elabortae more on the greedy approach for problem C. Specifically, I don't understand how it allways leads to the correct answer.

The way I originally solved should not pass since it is $$$O(N^2K)$$$, but it passes anyways :). Simply do what the editorial says naively, but either take the string $$$s$$$ or the complement of the string $$$s$$$, whatever is faster. (So define balance as either # of ones or # of zeroes depending on which is smaller). And this halves the runtime more or less, enough to get it to pass.

The solution to problem D is the Maximum subarray problem using Kadane's algorithm

Can somebody explain the editorial of B in better detail? I am having trouble understanding it.

Can someone explain me the transitions in problem E

Can someone explain to me in more detail why in problem C, the running time is O(m + nD) in the editorial? I understand the reduction from O(m + nD) to O(nD). "O(m) comes from the outer loop over digits that you can't really get rid of" this part I am not sure of.

I think C was a great problem, i kinda fell in the DP way to do it and didn't think the simple greedy. Probably a new way for me to look at subsequences.

In the C question the given solution is not considering the case when any element in the given range is not present in the string. Please correct me if I am wrong... For example 88225553535123456 2 50 56 In this test case 0 is not present in the array even then when we are iterating for 0 in the string starting from 5th index(0 based indexing) its obvious that we won't get 0 and our pointer will go out of the bound and it will give "YES" as the output.

Please check it...