Author: TheScrasse

Preparation: MyK_00L

**Hint 1**

Suppose that you can use $$$x$$$ operations of type $$$1$$$ and $$$y$$$ operations of type $$$2$$$. Try to reorder the operations in such a way that $$$a$$$ becomes the minimum possible.

**Hint 2**

You should use operations of type $$$2$$$ first, then moves of type $$$1$$$. How many operations do you need in the worst case? ($$$a = 10^9$$$, $$$b = 1$$$)

**Hint 3**

You need at most $$$30$$$ operations. Iterate over the number of operations of type $$$2$$$.

**Solution**

Notice how it is never better to increase $$$b$$$ after dividing ($$$\lfloor \frac{a}{b+1} \rfloor \le \lfloor \frac{a}{b} \rfloor$$$).

So we can try to increase $$$b$$$ to a certain value and then divide $$$a$$$ by $$$b$$$ until it is $$$0$$$. Being careful as not to do this with $$$b<2$$$, the number of times we divide is going to be $$$O(\log a)$$$. In particular, if you reach $$$b \geq 2$$$ (this requires at most $$$1$$$ move), you need at most $$$\lfloor \log_2(10^9) \rfloor = 29$$$ moves to finish.

Let $$$y$$$ be the number of moves of type $$$2$$$; we can try all values of $$$y$$$ ($$$0 \leq y \leq 30$$$) and, for each $$$y$$$, check how many moves of type $$$1$$$ are necessary.

Complexity: $$$O(\log^2 a)$$$.

If we notice that it is never convenient to increase $$$b$$$ over $$$6$$$, we can also achieve a solution with better complexity.

Official solution: 107232596

1485B - Replace and Keep Sorted

Author: TheScrasse

Preparation: Keewrem

**Hint 1**

You can make a $$$k$$$-similar array by assigning $$$a_i = x$$$ for some $$$l \leq i \leq r$$$ and $$$1 \leq x \leq k$$$.

**Hint 2**

How many $$$k$$$-similar arrays can you make if $$$x$$$ is already equal to some $$$a_i$$$ ($$$l \leq i \leq r$$$)?

**Hint 3**

How many $$$k$$$-similar arrays can you make if either $$$x < a_l$$$ or $$$x > a_r$$$?

**Hint 4**

How many $$$k$$$-similar arrays can you make if none of the previous conditions holds?

**Solution**

Let's consider each value $$$x$$$ from $$$1$$$ to $$$k$$$.

- If $$$x < a_l$$$, you can replace $$$a_l$$$ with $$$x$$$ (and you get $$$1$$$ $$$k$$$-similar array). There are $$$a_l-1$$$ such values of $$$x$$$.
- If $$$x > a_r$$$, you can replace $$$a_r$$$ with $$$x$$$ (and you get $$$1$$$ $$$k$$$-similar array). There are $$$k-a_r$$$ such values of $$$x$$$.
- If $$$a_l < x < a_r$$$, and $$$x \neq a_i$$$ for all $$$i$$$ in $$$[l, r]$$$, you can either replace the rightmost $$$b_i$$$ which is less than $$$x$$$, or the leftmost $$$b_i$$$ which is greater than $$$x$$$ (and you get $$$2$$$ $$$k$$$-similar arrays). There are $$$(a_r - a_l + 1) - (r - l + 1)$$$ such values of $$$x$$$.
- If $$$x = a_i$$$ for some $$$i$$$ in $$$[l, r]$$$, no $$$k$$$-similar arrays can be made.

The total count is $$$(a_l-1)+(k-a_r)+2((a_r - a_l + 1) - (r - l + 1))$$$, which simplifies to $$$k + (a_r - a_l + 1) - 2(r - l + 1)$$$.

Complexity: $$$O(n + q)$$$.

Official solution: 107232462

Authors: isaf27, TheScrasse

Preparation: Keewrem

**Hint 1**

Let $$$\lfloor \frac{a}{b} \rfloor = a~\mathrm{mod}~b = k$$$. Is there an upper bound for $$$k$$$?

**Hint 2**

$$$k \leq \sqrt x$$$. For a fixed $$$k$$$, can you count the number of special pairs such that $$$a \leq x$$$ and $$$b \leq y$$$ in $$$O(1)$$$?

**Solution**

We can notice that, if $$$\lfloor \frac{a}{b} \rfloor = a~\mathrm{mod}~b = k$$$, then $$$a$$$ can be written as $$$kb+k$$$ ($$$b > k$$$). Since $$$b > k$$$, we have that $$$k^2 < kb+k = a \leq x$$$. Hence $$$k \leq \sqrt x$$$.

Now let's count special pairs for any fixed $$$k$$$ ($$$1 \leq k \leq \sqrt x$$$). For each $$$k$$$, you have to count the number of $$$b$$$ such that $$$b > k$$$, $$$1 \leq b \leq y$$$, $$$1 \leq kb+k \leq x$$$. The second condition is equivalent to $$$1 \leq b \leq x/k-1$$$.

Therefore, for any fixed $$$k > 0$$$, the number of special pairs ($$$a\leq x$$$; $$$b \leq y$$$) is $$$max(0, min(y,x/k-1) - k)$$$. The result is the sum of the number of special pairs for each $$$k$$$.

Complexity: $$$O(\sqrt x)$$$.

Official solution: 107232416

1485D - Multiples and Power Differences

Author: TheScrasse

Preparation: MyK_00L

**Hint 1**

Brute force doesn't work (even if you optimize it): there are relatively few solutions.

**Hint 2**

There may be very few possible values of $$$b_{i,j}$$$, if $$$b_{i-1,j}$$$ is fixed. The problem arises when you have to find a value for a cell with, e.g., $$$4$$$ fixed neighbors. Try to find a possible property of the neighbors of $$$(i, j)$$$, such that at least a solution for $$$b_{i,j}$$$ exists.

**Hint 3**

The least common multiple of all integers from $$$1$$$ to $$$16$$$ is less than $$$10^6$$$.

**Solution**

Build a matrix with a checkerboard pattern: let $$$b_{i, j} = 720720$$$ if $$$i + j$$$ is even, and $$$720720+a_{i, j}^4$$$ otherwise. The difference between two adjacent cells is obviously a fourth power of an integer. We choose $$$720720$$$ because it is $$$\operatorname{lcm}(1, 2, \dots, 16)$$$. This ensures that $$$b_{i, j}$$$ is a multiple of $$$a_{i, j}$$$, because it is either $$$720720$$$ itself or the sum of two multiples of $$$a_{i, j}$$$.

Complexity: $$$O(nm)$$$.

Official solution: 107232359

Author: TheScrasse

Preparation: TheScrasse

**Hint 1**

What happens if you can't swap coins?

**Hint 2**

Let $$$dp_i$$$ be the maximum score that you can reach after $$$dist(1, i)$$$ moves if there is a red coin on node $$$i$$$ after step $$$3$$$. However, after step $$$2$$$, the coin on node $$$i$$$ may be either red or blue. Try to find transitions for both cases.

**Hint 3**

If you consider only the first case, you solve the problem if there are no swaps. You can greedily check the optimal location for the blue coin: a node $$$j$$$ such that $$$dist(1,i) = dist(1,j)$$$ and $$$a_j$$$ is either minimum or maximum.

Instead, if the coin on node $$$i$$$ is blue after step $$$2$$$, the red coin is on node $$$j$$$ and you have to calculate $$$\max(dp_{parent_j} + |a_j - a_i|)$$$ for each $$$i$$$ with a fixed $$$dist(1, i)$$$. How?

**Solution**

Divide the nodes in groups based on the distance from the root. Then, for each $$$dist(1, i)$$$ in increasing order, calculate $$$dp_i$$$ — the maximum score that you can reach after $$$dist(1, i)$$$ moves if there is a red coin on node $$$i$$$ after step $$$3$$$. You can calculate $$$dp_i$$$ if you know $$$dp_j$$$ for each $$$j$$$ that belongs to the previous group. There are two cases:

if after step $$$2$$$ the coin on node $$$i$$$ is red, the previous position of the red coin is fixed, and the blue coin should reach either the minimum or the maximum $$$a_j$$$ among the $$$j$$$ that belong to the same group of $$$i$$$;

if after step $$$2$$$ the coin on node $$$i$$$ is blue, there is a red coin on node $$$j$$$ ($$$dist(1, i) = dist(1, j)$$$), so you have to maximize the score $$$dp_{parent_j} + |a_j - a_i|$$$.

This can be done efficiently by sorting the $$$a_i$$$ in the current group and calculating the answer separately for $$$a_j \leq a_i$$$ and $$$a_j > a_i$$$; for each $$$i$$$ in the group, the optimal node $$$j$$$ either doesn't change or it's the previous node.

Alternatively, you can notice that $$$dp_{parent_j} + |a_j - a_i| = \max(dp_{parent_j} + a_j - a_i, dp_{parent_j} + a_i - a_j)$$$, and you can maximize both $$$dp_{parent_j} + a_j - a_i$$$ and $$$dp_{parent_j} + a_i - a_j$$$ greedily (by choosing the maximum $$$dp_{parent_j} + a_j$$$ and $$$dp_{parent_j} - a_j$$$, respectively). In this solution, you don't need to sort the $$$a_i$$$.

The answer is $$$\max(dp_i)$$$.

Complexity: $$$O(n)$$$ or $$$O(n\log n)$$$.

Official solution: 107232216

Author: TheScrasse

Preparation: TheScrasse

**Hint 1**

Why isn't the answer $$$2^{n-1}$$$? What would you overcount?

**Hint 2**

Find a dp with time complexity $$$O(n^2\log n)$$$.

**Hint 3**

Let $$$dp_{i, j}$$$ be the number of hybrid prefixes of length $$$i$$$ and sum $$$j$$$. The transitions are $$$dp_{i, j} \rightarrow dp_{i+1, j+b_i}$$$ and $$$dp_{i,j} \rightarrow dp_{i+1,b_i}$$$. Can you optimize it to $$$O(n\log n)$$$?

**Solution**

For each $$$i$$$, you can choose either $$$a_i = b_i$$$ or $$$a_i = b_i - \sum_{k=1}^{i-1} a_k$$$. If $$$\sum_{k=1}^{i-1} a_k = 0$$$, the two options coincide and you have to avoid overcounting them.

This leads to an $$$O(n^2\log n)$$$ solution: let $$$dp_i$$$ be a map such that $$$dp_{i, j}$$$ corresponds to the number of ways to create a hybrid prefix $$$[1, i]$$$ with sum $$$j$$$. The transitions are $$$dp_{i, j} \rightarrow dp_{i+1, j+b_i}$$$ (if you choose $$$b_i = a_i$$$, and $$$j \neq 0$$$), $$$dp_{i,j} \rightarrow dp_{i+1,b_i}$$$ (if you choose $$$b_i = \sum_{k=1}^{i} a_k$$$).

Let's try to get rid of the first layer of the dp. It turns out that the operations required are

- move all $$$dp_j$$$ to $$$dp_{j+b_i}$$$
- calculate the sum of all $$$dp_j$$$ in some moment
- change the value of a $$$dp_j$$$

and they can be handled in $$$O(n\log n)$$$ with "Venice technique".

$$$dp$$$ is now a map such that $$$dp_j$$$ corresponds to the number of ways to create a hybrid prefix $$$[1, i]$$$ such that $$$\sum_{k=1}^{i} a_k - b_k = j$$$. Calculate the dp for all prefixes from left to right. if $$$b_i = a_i$$$, you don't need to change any value of the dp; if $$$b_i = \sum_{k=1}^{i} a_k$$$, you have to set $$$dp_{\sum_{k=1}^{i} -b_k}$$$ to the total number of hybrid arrays of length $$$i-1$$$.

Complexity: $$$O(n\log n)$$$.

Official solution: 107232144