PROBLEM LINK:
Author: Zubair Hasan
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium
PREREQUISITES:
dp bitmask, long common subsequence (LCS) or longest increasing subsequence (LIS)
PROBLEM:
You are given an array a consisting of either 10, 20, 50, 100, 200, 500, 2000. In a single operation, you can pick some element of the array and insert at any position (including at the beginning or at the end). Find out the minimum number of operations required so that all the numbers with the same value are consecutive in the array.
SOLUTION
First, let us remap the numbers 10, 20, 50, 100, 200, 500, 2000 to 1, 2, 3, 4, 5, 6, 7. So, the array now array consists of 1, 2, 3 \dots .. 7.
A bit slow solution
Let us fix the order of numbers at the end. There can be 7! (all permutations of 7 numbers) possible numbers. For a fixed permutation, you can find the minimum number of operations required. For that, we first change the array element a_i with value p_i to be i. Now, you have to find the longest increasing (non-decreasing to be precise) subsequence in this array. All the elements that don’t belong to this LIS should be moved. Hence, the minimum number of operations required for obtaining this order of numbers will be n \, - LIS of the updated array. Finding LIS of the array can be done \mathcal{O}(n \log n) (binary search or dp with BIT) or \mathcal{O}(n * 7) (dp with BIT with the optimization that there are exactly 7 different numbers in the array) time.
Overall, this algorithm will take \mathcal{O}(7! * n * 7) which won’t fit in time for n = 10^5 and 5 test cases.
Better solution
We want to remove the 7! part from the time complexity. It will be great if we can make it 2^7 or something similar. That way, our solution can fit in time.
Let us think the problem in a different way. Instead of minimizing the number of operations, we would like to maximize the length of the longest increasing subsequence of the final array with the given array.
Now, we try to create the final array by going from left to right and try to maximize the length of LCS (longest common subsequence). Note that the final array should have same numbered element consecutive in it. So, we keep track of which position of the array we are, what was the last value that we put in the array and the set of values (a bitmask) to keep tracking of which of the values \{1, 2, \dots, 7\} have been used. Now, while making transitions, at this position we can decide to keep this element same as the previously put element or can decide to add a new element that is not present in the bitmask.
Note that in the previous dp state, we don’t care about the number of times a number appears in the original array. Note that if we want to maximize the LCS, then we can always create the final array such that it contains exactly the same number of occurrences of elements as that of the original array without changing the LCS. You can visualize this as follows. Suppose a number has less number of occurrences in the final array than the original array. Then, there will be an element which has a higher number of occurrences, then you can potentially replace this element with the less frequency element and get a higher LCS. Similarly, you can make an argument in case the final array element has a higher frequency than the original array.
void relax(int &a, int b):
if (a < b):
a = b;
// Renumber the elements in the array a such that it consists of numbers in the range [0..6]
int dp[MaxN][1 << 7][8];
memset(dp, -1, sizeof(dp));
// At the beginning, we haven't put any number, which we think
// of putting a number 8 (indexed by 7) at the beginning of the array.
dp[0][0][7] = 0;
for (int p = 0; p < n; ++p):
for (int mask = 0; mask < 1 << 7; ++mask):
for (int who = 0; who <= 7; ++who): //who denotes element placed at position p-1
if (dp[p][mask][who] >= 0): // if the states is reachable
relax(dp[p + 1][mask][who], dp[p][mask][who]);
int nxt = a[p];
if (nxt == who):
relax(dp[p + 1][mask][who], dp[p][mask][who] + 1);
if (~mask & (1 << nxt)): // if nxt is not part of mask.
relax(dp[p + 1][mask | (1 << nxt)][nxt], dp[p][mask][who] + 1);
int ans = 0;
for (int mask = 0; mask < 1 << 7; ++mask):
for (int who = 0; who < 7; ++who):
relax(ans, dp[n][mask][who]);
printf("%d\n", n - ans);
There are total \mathcal{O}(n * 2^7 * 8) states in the dp. Per state of the dp, the transition time is \mathcal{O}(1). So, the overall time complexity of the algorithm is \mathcal{O}(n * 2^7 * 8) per test case, which comes out to 5 * 10^8 for 5 test cases, which will pass in the 7 seconds time limit.