PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums
PROBLEM:
You’re given an array A containing the elements 1 and 2.
Consider the following process:
- Start with p = 1.
- While p \le N, replace p with p + A_p.
This counts as one step.
f(A) is the number of steps taken by this process.
You can swap adjacent elements of A.
Find the minimum number of swaps needed to maximize the value of f(A).
EXPLANATION:
Since we can perform adjacent swaps, we can pretty much freely rearrange the elements of A.
So, let’s first understand what sort of arrangement will maximize f(A).
Each time we visit the value 2, we skip the next index (unless it’s the last index, i.e. N.)
The value 1 doesn’t cause any skips at all.
So, maximizing the number of steps is equivalent to minimizing the number of skips, i.e. minimizing the number of twos we visit.
Suppose there are c_1 ones and c_2 twos.
Each 2 we visit allows us to skip one other element.
Since we want to skip twos but don’t want to skip ones, it’s ideal to always skip a 2 if possible.
Thus, we need to visit at least half the occurrences (rounded up), i.e. \displaystyle\text{ceil}\left(\frac{c_2}{2}\right) occurrences of 2.
This tells us that the maximum possible value of f(A) equals c_1 + \text{ceil}\left(\frac{c_2}{2}\right).
This upper bound is also achievable, for example via the configuration
[1, 1, \ldots, 1, 1, 2, 2, \ldots, 2, 2]
that places all ones before all twos.
Now we need to understand which configurations reach this value.
First, let’s consider the case of odd c_2.
Here, note that to reach a value of c_1 + \text{ceil}\left(\frac{c_2}{2}\right), we’re forced to have A_N = 2.
This is because if we don’t, the last 2 will cause us to skip over a 1, which is undesirable because the optimal score requires every 1 to be used.
So, let’s move the last 2 to the end of the array using swaps.
We now have an even number of twos remaining, and our goal is to skip exactly half of them.
This is only possible if:
- The first and second occurrences of 2 are adjacent (so that visiting the first occurrence skips the second occurrence).
- The third and fourth occurrences of 2 are adjacent (so that visiting the third occurrence skips the fourth occurrence).
\vdots - In general, the (2i-1)-th and (2i)-th occurrence of 2 must be adjacent to each other for each i, so that visiting the (2i-1)-th occurrence skips the (2i)-th occurrence.
There is no other configuration, because we must visit the first occurrence of 2 (ones don’t let us skip anything), then after skipping the second occurrence we must visit the third occurrence, and so on.
Let the positions of the twos in A be x_1, x_2, x_3, \ldots, x_{c_2} from left to right.
Observe that the number of swaps needed to make the i-th and (i+1)-th twos adjacent to each other equals (x_{i+1} - x_i - 1), since that’s the amount of “empty space” between them and any adjacent swap can only reduce this space by 1.
Thus, the overall number of swaps needed to obtain our required configuration equals
where the last term of (N - x_{c_2}) comes from moving the last occurrence of 2 to position N.
Next, consider the case of even c_2.
Just as in the odd case, we can pair up the (2i-1)-th and (2i)-th occurrences of 2 so ensure that we skip half the twos. This results in a cost of
However, is this always optimal?
As it turns out, not necessarily!
Note that in the even case, we aren’t forced to have A_N = 2, which is what really forced things in the odd c_2 case.
So, let’s analyze what happens if we don’t pair everything up nicely.
Suppose we don’t pair up all the twos.
Let x_{2i-1} be the index of the first occurrence of 2 such that we don’t pair the (2i-1)-th and (2i) -th occurrences.
What changes?
To begin with, because these two are not paired, there will be a 1 after this occurrence of 2 that we end up skipping (because we’ll definitely visit this occurrence, given that everything else is paired up.)
However, there are an odd number of twos remaining to the right - so we just end up back in the odd case, which we know to be forcing!
This means:
- The last occurrence of 2 is forced to be at index N.
- All remaining twos other than that one must be paired up.
This means we instead have the pairs (x_{2i}, x_{2i+1}), (x_{2i+2}, x_{2i+3}), \ldots
along with moving the two at x_{c_2} to index N.
The cost of this is thus
The final answer is then obtained by taking the minimum of this across all choices of i.
Don’t forget to also include the initial case where all twos are indeed paired up; which might be optimal.
Note that directly computing the sum upon fixing i will result in an algorithm that’s \mathcal{O}(N^2).
To optimize it, you can build prefix sums over the x_{2j} - x_{2j-1} values and suffix sums over the x_{2j+1} - x_{2j} values, which will give a linear time solution.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector a(n, 0);
for (int &x : a) cin >> x;
vector<int> twos;
for (int i = 0; i < n; ++i) if (a[i] == 2) {
twos.push_back(i);
}
int ans = 0, k = size(twos);
for (int i = 1; i < k; i += 2) {
ans += twos[i] - twos[i-1] - 1;
}
if (k & 1) {
ans += n-1 - twos.back();
}
else if (k > 0) {
vector suf(k, 0);
suf[k-1] = n-1 - twos[k-1];
for (int i = k-3; i >= 0; i -= 2) {
suf[i] = suf[i+2] + twos[i+1] - twos[i] - 1;
}
int pref = 0;
for (int i = 0; i < k; i += 2) {
ans = min(ans, pref + suf[i+1]);
pref += twos[i+1] - twos[i] - 1;
}
}
cout << ans << '\n';
}
}