Author: | Daniel Posdarascu |
Solution 1:
Sort elements in because the order does not matter.
O(N^2) solution:
= the minimum cost in order to solve the first elements in and the element on position is (the initial value) dpB[i][j] = the minimum cost in order to solve the first elements in and the element on position is (it was replaced)
For we have two cases:
The previous element has also kept his initial value. This can be applied only if A[i - 1] < A[i].
The previous element was replaced with something from , so any B[j] < A[i].
Therefore, dpA[i] = min(dpA[i - 1] (if it's the case), dpB[i][j]) for all with B[j] < A[i]. This can easily be done with partial min.
For dpB[i][j] we have two cases:
The previous element kept its initial value. This can be applied only if A[i - 1] < B[j].
The previous element was also replaced by another element in . The key observation is that if position in was replaced by element in , then position i - 1 will be replaced by element j - 1 in (or there is no reason to take any other element from B).
Therefore, dpB[i][j] = min(dpA[i - 1] + 1 (if it's the case), dp[i - 1][j - 1] + 1).
O(N \cdot \log N) optimization:
We will iterate only through the first dimension (iterate only ) and we will update all the values of dpB[i][j] using a data structure. We can see that we only need minimum on prefix, update with minimum on suffix and update on elements. This can be done using lazy update on a segment tree for example.
Solution 2:
We want to replace as few elements of as possible, which is the same as not touching as many elements of as possible. Let's mentally fix the elements of we won't touch, can we achieve that? Obviously, the untouched elements should be increasing left-to-right, but also we should have enough elements in to fill in the gaps. The good news is since the untouched elements are increasing, the elements of we can use to fill in the gaps are different for each gap, so we can check if we can fill in each gap independently.
That leads to a polynomial solution: we don't need to choose all the elements we won't touch, we can choose them one-by-one left-to-right, each time checking that we have enough elements in to fill in the gap. Do DP[v] — maximum number of untouched elements if the last one is on position v. To make a transition, iterate over the next untouched element u, check that A_{v} < A_{u} and that we have at least (u - v - 1) elements in between A_{v} and A_{u}. The obvious implementation is O(N^{2} M), we need to do better than that. (For convenience, add elements A_{0} = -\infty and A_{N+1} = \infty, so that we can always take them)
Can we do the transition faster? Well, yes, we only need to check if the number of elements in is enough, we can do that with a couple of lower\_bounds if we sort in advance. Moreover, we can right away define p_{v} — position of first element in which is greater than A_{v}, then the transition is possible if and only if A_{v} < A_{u} and u - v - 1 \le p_{u} - p_{v}. Unless u = v + 1, which we can check separately, the second condition implies the first, so we only need to check the second one. We can rewrite it as p_{v} - v - 1 \le p_{u} - u, which is good, because the left side depends only on and the right side depends only on . Therefore, to calculate DP[u], we only need to take maximum over DP[v] for v with p_{v} - v less than some value.
It can be done with Segment Tree, but there is a way that requires only std::set. Smaller values of p_{v} - v are better — higher chances to be less than some value. Therefore, if there are two states and with p_{v} - v \le p_{u} - u and DP[v] \ge DP[u], we don't need , we can just forget about it. So, if we only store the values which are useful, a higher value of p_{v} - v will mean a higher value of . Let's store the pairs (p_{v} - v, DP[v]) in std::set, they will be sorted by the first parameter, which also means sorted by the second. When we insert the new value, erase all the old ones that are worse. To calculate the new DP value you only need one lower\_bound. Since we can insert each element at most once, we can erase it at most once, thus the amortized complexity is O(N \log N).
Accounting for the sorting of and lower\_bounds needed to calculate p_{v}, total complexity is O((N+M)(\log N + \log M)).