How many described diagonals are there in total? How many cells do they contain?

In total we have $$$2 n - 1$$$ diagonals. There is only one diagonal that contains $$$n$$$ cells, two containing $$$n - 1$$$ cells, ..., and two containing only one cell each (namely passing through $$$(1, n)$$$ and $$$(n, 1)$$$).

Obviously, in this case, it is worth filling the largest diagonal with chips, then two that are smaller in size, and so on. The asymptotics turns out to be $$$O(n)$$$.

272176453

For each number of petals, we can bruteforce the answer for $$$x, x + 1$$$

First, we can aggregate number of flowers with $$$x$$$ petals into $$$c_{x}$$$ (for example, sort the array and then create array of pairs $$$(x, c_{x})$$$, where $$$c_{x}$$$ is the length of segment with elements equal to $$$x$$$).

Note that $$$\sum_{x} c_{x} = n$$$. Also note that for every $$$x$$$ we won't need more than $$$\left\lfloor\frac{m}{x}\right\rfloor$$$ flowers (otherwise total number of petals will exceed $$$m$$$).

Then we iterate through all $$$x$$$. Suppose that we want to assemble a bouquet with $$$x, x + 1$$$ petals. We can bruteforce the amount of flowers with $$$x$$$ petals in $$$O(c_{x})$$$. If we have $$$0 \le k_1 \le min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$$$ flowers with $$$x$$$ petals, we already have $$$k_1 * x$$$ petals. There are still $$$m - k_1 * x$$$ coins which we can spend for flowers with $$$x + 1$$$ petals. There are at most $$$k_2 = min(c_{x + 1}, \left\lfloor\frac{m - k_1 * x}{x + 1}\right\rfloor)$$$ flowers with $$$x + 1$$$ petal we can buy. So we need to find maximum over all such $$$k_1 * x + k_2 * (x + 1)$$$.

Total complexity is $$$O(\sum_{x} c_{x}) = O(n)$$$ for finding the maximum and $$$O(n \log n)$$$ for sorting.

272263831

Maybe there is a way to change bruteforce into checking optimal values for counts of $$$x, x + 1$$$? Maybe there are only few types of optimal bouquets for $$$x, x + 1$$$?

We already have a list of $$$c_x$$$. We can use hash map to be able to check for any $$$c_x$$$ by $$$x$$$.

We again will try to assemble the bouquet only with flowers with $$$x, x + 1$$$ petals. We set $$$k1 = min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$$$. Then we have $$$coins = m - k1 * x$$$. Let's set $$$k2 = min(c_{x + 1}, \left\lfloor\frac{coins}{x + 1}\right\rfloor)$$$. Then we have $$$coins = m - (k1 * x + k2 * (x + 1))$$$. Let's substitute flower with $$$x$$$ petals with flower with $$$x + 1$$$ petals as many times as we can. This can be done $$$r = min(k1, c_{x + 1} - k2, coins)$$$ times, as each operation will require us 1 coin, 1 flower in the bouquet with $$$x$$$ petals and one 1 flower with $$$x + 1$$$ petals not in the bouquet. In total we can get $$$(k1 - r) * x + (k2 + r) * (x + 1)$$$ petals.

This assembling is optimal. Here is why. Suppose that we have $$$0 \le b1 \le c_{x}$$$ flowers with $$$x$$$ petals and $$$0 \le b2 \le c_{x + 1}$$$ flowers with $$$x + 1$$$ petals and greater total value of $$$b1 * x + b2 * (x + 1)$$$. We already know that $$$b1 \le k1$$$ by choosing of $$$k1$$$. If $$$k1 - r < b1$$$, then we can ''undo'' our operation $$$r + b1 - k1$$$ times, sum is still not greater than $$$m$$$, and we know that now there can't be more than $$$k2 + r + b1 - k1$$$ flowers with $$$x + 1$$$ petals, as otherwise we didn't chose optimal $$$k2$$$. If $$$k2 + r < b2$$$, then $$$r \ne c_{x + 1} - k2$$$, if $$$r = k1$$$ then it is just the case when we have only flowers with $$$x + 1$$$ petals which will be considered in case $$$x + 1, x + 2$$$, if $$$r = coins$$$ then $$$m = (k1 - r) * x + (k2 + r) * (x + 1)$$$ and we already found the maximum. So $$$b2 \le k2 + r$$$ and $$$b1 \le k1 - r$$$ and $$$b1 * x + b2 * (x + 1)$$$ is not better than optimal.

Total time complexity is $$$O(n)$$$.

272263882

How many times we need to apply the operation to index $$$i$$$, so that $$$a[i - 1] \leq a[i]$$$? Let's call it $$$op[i]$$$
It's easy to calculate these values in no time.
Can we just accumulate them?

We almost can. But, let's take $$$[4, 2, 4]$$$ as an example. op[2] = 1, but we don't want to do anything with a[3].
So, sometimes $$$a[i - 1] \le a[i]$$$ and we may not want touch a[i] at all, even if something was applied before it.
So, should we consider making $$$op[i] < 0$$$ for some $$$i$$$?

Let's set $$$op[i]$$$ to the number of operation we need to apply to index $$$i$$$ so that $$$a[i - 1] \leq a[i]$$$.
But, if $$$a[i - 1] \ll a[i]$$$, let's set it to the negative number of times that we can apply the operation to $$$a[i - 1]$$$ so that $$$a[i - 1] \leq a[i]$$$ still holds.
Now let's just calculate the prefix sum $$$\texttt{prefix_op}$$$, don't forget to do $$$\max(0, \texttt{prefix_op}[i])$$$. The sum of values in $$$\texttt{prefix_op}$$$ is the answer.

Let's try to go to the logarithmic space to get rid of too big numbers.
$$$\log(x * x) = 2\log(x)$$$
So, if we replace each value with its logarithm, the operation of squaring becomes multiplying by 2.
But this is not good enough, since we may need to do the operation thousands of times, $$$2^{1000}$$$ is too big, it doesn't fit into any floating point.
So, let's just repeat our trick and go to the log-log space
$$$\log(2 * y) = \log(y) + \log(2)$$$
Now we see that the operation turns into just adding $$$\log(2)$$$. We can afford doing that thousands and millions of times.
Let's deine $$$b[i] = \log{\log{a[i]}}$$$
So now, we can just go with a for-loop and do $$$\displaystyle{\left\lceil\frac{b[i] - b[i - 1]}{\log(2)}\right\rceil}$$$ opeartions with $$$i$$$-th element, updating $$$b[i]$$$ accordingly.
Since initially $$$b[i] \leq \log(10^6) \leq 20 \log(2)$$$, we can maintain the invariant that $$$b[i] \leq (20 + i)\log(2)$$$ since after applying an operation to $$$b[i]$$$ we can't exceed $$$b[i - 1]$$$ by more than $$$\log(2)$$$. It means that the final numbers in the log-log space won't exceed $$$(n + 20)\log(2)$$$. We can maintain $$$O(n)$$$ arithmetics using double without any problems.

272174772

272174825

If letter is chosen as an ending to some case, each occurrence of this letter may in the text can be considered an ending?

The length of the word is something too complex. How can you simplify the restriction?

The final letter must be an ending of some case and among any $$$k$$$ consecutive letters there must be at least one ending.

Now you don't need the text because you can store bitmasks instead of substrings of length $$$k$$$. To calculate the bitmasks you can use prefix sums for each of the characters (it will take $$$O(cn)$$$ overall).

Now you need to find a bitmask with a minimal number of ones which intersects all the stored bitmasks.

Identify "bad" bitmask instead of "good" ones.

(Read the hints.) $$$b$$$ is bad if there exists stored $$$a$$$ such that $$$a \text{&} b = 0$$$ which is equivalent to $$$b$$$ being a submask of $$$\text{~}a$$$. All such b can be found using simple dp on bitmasks. The rest $$$b$$$ are good.

Time complexity: $$$O(c n + c 2^c)$$$

272218277

Consider cases of odd and even $$$n$$$. Which one is simpler?

Even. In this case you can solve the problem for the opposite desks independently. From now on $$$n$$$ is odd.

If you reorder desks/knights in a way that you swap neighbors (i.e. $$$2$$$ with $$$3$$$, $$$4$$$ with $$$5$$$, ..., $$$2 n$$$ with $$$1$$$) instead of opposite knights, it'll probably become easier to think about this problem. We will use this notation from now on.

You're allowed to run in $$$O(n^2)$$$. Wouldn't it have sense to fix some entity and solve in linear time for fixed entity?

Fix the minimal (maximal) desk and the knights who are sitting at it (if the original knights were swapped or not). You'll need to find the minimal maximum on a desk for $$$4 n$$$ such cases.

DP.

(Read the hints.) Let the fixed desk have index $$$k$$$. Let $$$dp_{i, b}$$$ (where $$$i$$$ is the index of the desk and $$$b$$$ is $$$0$$$ / $$$1$$$ which indicates whether the knight $$$2 i$$$ was swapped) be the minimal maximum that can be achieved on a segment from $$$k$$$ to $$$i$$$ (satisfying bit $$$b$$$ and the fact that the desk $$$k$$$ is actually minimal). Then you can easily make transitions $$$dp_{i, 0}, dp_{i, 1} \to dp_{i + 1, 0}, dp_{i + 1, 1}$$$. In the end you'll just need to check $$$dp_{k - 1, b'}$$$ where $$$b'$$$ indicates whether the knight $$$2 * k - 1$$$ was swapped in our choice.

(All the indices for the desks are taken modulo $$$n$$$ and all the indices for the knights are taken modulo $$$2 n$$$.)

Time complexity: $$$O(n^2)$$$, but the constant is large and $$$O(n^2\log n)$$$ solutions with binary search are unlikely to pass.

272207462

Read the first two hints to E1.

There are $$$4 n$$$ possible desks in total. One of them will be the minimal desk and another one will be the maximal. What is the common-used technique for such problems?

Sort them and then use two pointers.

The data structure you need is very famous.

(Read the hints.) Assign a boolean matrix $$$2 \times 2$$$ to each of the desks. Rows correspond to the first knight at the desk (two rows for each of the events "the knight was swapped" / "the knight was not swapped"), columns correspond to the second one. The value in the intersection is true if under current restrictions (minimum and maximum) both events can happen, i.e. the result on the desk is between minimum and maximum.

What is a (boolean) multiplication of matrices from $$$d_l$$$ to $$$d_r$$$?

To determine whether it's possible to swap the knights under current restrictions you can just multiply all the matrices and check if there are ones on the main diagonal. Now using two pointers and a segment tree on these matrices you can solve the problem (basically, when you leave some option for a desk in the sorted array of options, you change one of the values of this matrix from $$$1$$$ to $$$0$$$, and vice versa).

272212685