Author: TheScrasse
Preparation: MyK_00L
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.
You should use operations of type 2 first, then moves of type 1. How many operations do you need in the worst case? (a=109, b=1)
You need at most 30 operations. Iterate over the number of operations of type 2.
Notice how it is never better to increase b after dividing (⌊ab+1⌋≤⌊ab⌋).
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(loga). In particular, if you reach b≥2 (this requires at most 1 move), you need at most ⌊log2(109)⌋=29 moves to finish.
Let y be the number of moves of type 2; we can try all values of y (0≤y≤30) and, for each y, check how many moves of type 1 are necessary.
Complexity: O(log2a).
If we notice that it is never convenient to increase b over 6, we can also achieve a solution with better complexity.
1485B - Replace and Keep Sorted
Author: TheScrasse
Preparation: Kaey
You can make a k-similar array by assigning ai=x for some l≤i≤r and 1≤x≤k.
How many k-similar arrays can you make if x is already equal to some ai (l≤i≤r)?
How many k-similar arrays can you make if either x<al or x>ar?
How many k-similar arrays can you make if none of the previous conditions holds?
Let's consider each value x from 1 to k.
- If x<al, you can replace al with x (and you get 1 k-similar array). There are al−1 such values of x.
- If x>ar, you can replace ar with x (and you get 1 k-similar array). There are k−ar such values of x.
- If al<x<ar, and x≠ai for all i in [l,r], you can either replace the rightmost bi which is less than x, or the leftmost bi which is greater than x (and you get 2 k-similar arrays). There are (ar−al+1)−(r−l+1) such values of x.
- If x=ai for some i in [l,r], no k-similar arrays can be made.
The total count is (al−1)+(k−ar)+2((ar−al+1)−(r−l+1)), which simplifies to k+(ar−al+1)−2(r−l+1).
Complexity: O(n+q).
Authors: isaf27, TheScrasse
Preparation: Kaey
Let ⌊ab⌋=a mod b=k. Is there an upper bound for k?
k≤√x. For a fixed k, can you count the number of special pairs such that a≤x and b≤y in O(1)?
We can notice that, if ⌊ab⌋=a mod b=k, then a can be written as kb+k (b>k). Since b>k, we have that k2<kb+k=a≤x. Hence k≤√x.
Now let's count special pairs for any fixed k (1≤k≤√x). For each k, you have to count the number of b such that b>k, 1≤b≤y, 1≤kb+k≤x. The second condition is equivalent to 1≤b≤x/k−1.
Therefore, for any fixed k>0, the number of special pairs (a≤x; b≤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(√x).
1485D - Multiples and Power Differences
Author: TheScrasse
Preparation: MyK_00L
Brute force doesn't work (even if you optimize it): there are relatively few solutions.
There may be very few possible values of bi,j, if bi−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 bi,j exists.
The least common multiple of all integers from 1 to 16 is less than 106.
Build a matrix with a checkerboard pattern: let bi,j=720720 if i+j is even, and 720720+a4i,j otherwise. The difference between two adjacent cells is obviously a fourth power of an integer. We choose 720720 because it is lcm(1,2,…,16). This ensures that bi,j is a multiple of ai,j, because it is either 720720 itself or the sum of two multiples of ai,j.
Complexity: O(nm).
Author: TheScrasse
Preparation: TheScrasse
What happens if you can't swap coins?
Let dpi 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.
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 aj 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 for each i with a fixed dist(1, i). How?
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\log n).
Author: TheScrasse
Preparation: TheScrasse
Why isn't the answer 2^{n-1}? What would you overcount?
Find a dp with time complexity O(n^2\log n).
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)?
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". It's not necessary to use a multiset (a map is enough) because you don't have to handle min / max queries.
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).