PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Preparation: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
There are N items in a shop, numbered 1 to N. Item i has a type, denoted B_i, which is either 0 or 1.
You will buy all N items exactly once, in some order.
- When buying an item of type 0, you will receive an additional copy of it if you’ve previously bought any item with lower index.
- When buying an item of type 1, you will receive an additional copy of it if you’ve previously bought any item with higher index.
For each prefix, find the minimum total number of items you can obtain.
EXPLANATION:
Let’s solve the problem for a fixed array first - we can think about extending the solution to all prefixes later.
Each purchase gives either one item or two.
Ideally, we want to minimize the number of times we obtain two objects.
That means,
- For each i with B_i = 0, we’d prefer if no item bought before buying item i is smaller than it.
- For each i with B_i = 1, we’d prefer if no item bought before buying item i is larger than it.
This means, we’d like items with B_i = 0 to be prefix minimums in the buying order P, and items with B_i = 1 to be prefix maximums.
Suppose we want the type 0 prefix minimums to be
and the type 1 prefix maximums to be
Observe that if y_1 \lt x_1, there’s in fact no way to satisfy all these elements simultaneously (i.e, there’s no way to make all the x_i prefix minimums and all the y_i prefix maximums), because:
- If y_1 is placed before x_1, then x_1 can’t be a prefix minimum - there’s something smaller than it before it in the order.
- If y_1 is placed after x_1, then y_1 can’t be a prefix maximum instead, since x_1 is larger than it and before it.
So, if we want to satisfy all those indices simultaneously, we must have y_1 \gt x_1.
But then that simply combines both chains of inequalities, giving us
Further, it’s easy to see that if we choose any subset of x_i and y_i that satisfy this chain, it’s easy to make them all prefix minimums/maximums as they want: place all the x_i in descending order first, then all the y_i in ascending order, and then do whatever you want with the remaining elements afterwards.
Our task is thus reduced to finding the largest valid subset of x_i's and y_i's we can choose.
Every x_i must be before every y_i - that is, every chosen 0 type item must be before every 1 type item.
Observe that this is exactly what a non-decreasing subsequence in B looks like - several zeros followed by several ones!
In other words, what we’re really looking for is exactly the longest non-decreasing subsequence in B.
Since B is a boolean array, the longest non-decreasing subsequence can be computed greedily.
- Start with \text{lis} = 0 and \text{zeros} = 0.
- For each i = 1, 2, 3, \ldots
- If B_i = 1, extend the subsequence by including this 1: \text{lis} \gets \text{lis} + 1.
- If B_i = 0, increase the number of zeros: \text{zeros} \gets \text{zeros} + 1.
Then, consider if taking all existing zeros is better than the current increasing subsequence:
\text{lis} \gets \max(\text{lis}, \text{zeros}).
The final value of \text{lis} is the length of the longest non-decreasing subsequence.
If we have N items, \text{lis} of them can give us one item while the remaining will give us two.
So, the total number of items we receive is
Note that the method outlined above in fact computes the longest non-decreasing subsequence length for every prefix of B, not just the full string.
This gives us the answers to every prefix without doing any extra work: if \text{lis}_i is the length of the longest non-decreasing subsequence obtained till the i-th element in the above algorithm, the answer for the i-th prefix is simply 2i - \text{lis}_i.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Preparer's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> b(n);
for (auto &x : b) cin >> x;
vector <int> dp(2, 0);
int len = 0;
for (auto x : b){
len++;
if (x == 0){
dp[0] = dp[0] + 1;
} else {
dp[1] = max(dp[0], dp[1]) + 1;
}
cout << (2 * len - max(dp[0], dp[1])) << " ";
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
b = list(map(int, input().split()))
lis, zeros, tot = 0, 0, 0
ans = []
for x in b:
tot += 2
if x == 1: lis += 1
else:
zeros += 1
lis = max(lis, zeros)
ans.append(tot - lis)
print(*ans)