PROBLEM LINK:
Author: Alex Danilyuk
Tester: Riley Borgard
Editorialist: Jatin Yadav
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Greedy, DP
PROBLEM:
Given an array of size N. It has to be partitioned into blocks with odd sum. For each size 1 \le m \le N, find the minimum number of blocks needed if each block must have a size \leq m
EXPLANATION:
Let P_i be the prefix sum for the prefix of length i. For the sum of a block [L, R] to be odd, P_R and P_{L-1} must have different parities. Also, we need R - (L - 1) to be \le m. So, we can think of using the block [L, R] as jumping from L-1 to R. We start at 0 and we have to reach N, making jumps of size \le m such that each jump changes prefix parity. Let’s color the indices with odd prefix red and those with even prefix blue.
Subtasks 1 and 2
Define dp[x] to be the minimum number of jumps we need to make starting from x to reach N. We can do a simple O(N^2) dp for every m, where we iterate on the index that we jump to, from x. Total complexity would be O(N^3), which passes subtask 1. This can be optimized to O(N^2 \log N) by using two segment trees one for each parity, containing minimum dp value in range. This is enough to pass subtask 2.
Subtask 3
Greedily, we would want to make as big jumps as possible. So, let’s define b_x to be the largest index y \in [x + 1, x + m] having color opposite to that of x. If no such b_x exists, then we clearly can’t reach N from x. In the rest of the editorial, I’ll assume b_x exists for any x in focus.
Unfortunately, always jumping to b_x doesn’t work. A simple example is 11100 with m= 3. If you make the biggest possible jump from 0, you’ll jump to index 3 directly and then there’s only zeroes remaining, so we’re stuck. Let’s try to fix this.
Let’s define c_x to be the largest index z \in [x + 1, b_x - 1] such that z has color opposite to that of x, and at least one index w \in [z + 1, b_x - 1] has color same as x. This ensures that we can jump from x \rightarrow z \rightarrow w and then probably to outside x + m. If there doesn’t exist such a vertex z, define c_x = b_x.
Lemma 1: There exists an optimal solution in which from any x, we either jump to b_x or c_x
Proof
WLOG, assume x is colored red. Let the remaining sequences of indices be x \rightarrow y_1 \rightarrow y_2 \ldots y_k = N
If k = 1, then b_x = N and we are done. If k = 2, we can replace y_1 by b_x.
Else, let y_j be the largest in this sequence \leq x + m. If y_j is colored blue, we could have gone x\rightarrow b_x \rightarrow y_{j+1} without increasing the number of jumps. Else, if y_{j} > c_x, we could have gone x \rightarrow c_x \rightarrow y_j. Else, c_x < b_x, as there is a red node y_j \in [y_{j-1}+1, b_x - 1]. Let w be a red colored node between c_x and b_x. We could have gone x \rightarrow c_x \rightarrow w \rightarrow y_{j+1}. Both of these new sequences are not worse than the original sequence, as j \geq 2
Using this, we can solve the problem in O(N) for a given m, as now there are only two transitions x \rightarrow b_x and x \rightarrow c_x for any x. Also, after a basic linear precomputation, b_x and c_x can be found for any x in O(1). Hence, the total complexity is O(N^2), which passes subtask 3.
Subtask 4
Lemma 2: If there exists an optimal solution, it must have \le 3\lceil \frac{n}{m} \rceil blocks
Proof
Consider any three consecutive blocks in the optimal solution. The sum of their sizes must be > m, as otherwise we could have merged them to obtain a better solution.
For m \leq K(to be chosen later), let’s do an O(N) computation as in the last subtask. For m > K, the answer is O(\frac{N}{K}), and we can keep on binary searching on the smallest m that gives a smaller answer than the current. The complexity would be O(NK + \frac{N^2}{K} \log N). Choosing K = \sqrt{N \log N} gives an O(N \sqrt{N \log N}) solution.
Subtask 5
Lemma 3: If N is reachable from b_x, it is optimal to jump to b_x
Proof
Let the optimal solution be x \rightarrow (y_0=c_x) \rightarrow y_1 \rightarrow y_2 \ldots y_k = N. Consider an alternate path x \rightarrow (z_0=b_x) \rightarrow z_1 \rightarrow z_2 \ldots z_t = N.
If t = k, we are done. Else, t > k and there exists some 1 \leq i \leq k for which y_i > z_i. Consider the smallest such i. Then, z_{i-1} \geq y_{i-1}, hence we could have jumped from z_{i-1} \rightarrow y_i and x \rightarrow b_x \rightarrow z_1 \rightarrow z_2 \ldots z_{i-1} \rightarrow y_i \ldots y_k = N is a valid optimal sequence of jumps. Thus, it is optimal to jump to b_x whenever N is reachable from b_x.
So, if we could answer reachability queries in O(R), then we can solve the problem for a given m in O(R N / m), as, upto a constant factor, we ask as many reachability queries as the jumps in the optimal solution, which we already proved to be O(N / m)
Lemma 4: N is reachable from x if and only if it is reachable from c_x
Proof
If N is reachable from c_x, clearly it is also reachable from x. If N is reachable from x, we would have a solution in which the second index was either b_x or c_x. If it was c_x, we are done. Else, we know there exists an index w \in [c_x + 1, b_x - 1], such that we can jump c_x \rightarrow w \rightarrow b_x, and hence we can also reach N from c_x.
So, to check whether N is reachable from x, we could keep jumping to c_x until we finally reach N. This takes time O(N / m) to check reachability. So, for a given m, we can solve the problem in O(\min( N, (\frac{N}{m})^2 )). Summing this over all m gives O(N \sqrt{N}).
Subtask 6
First, find the smallest m for which answer is not -1 using binary search. This takes O(N \log N) time. For all greater m, N is reachable from 0.
We will maintain a reachability array. As we now increase m, N might become reachable from some new indices.
Lemma 5: In any maximal contiguous segment with all indices having the same color, the set of indices from which N is reachable, is a non-empty suffix.
Proof
Let the maximal segment in focus be [L, R] and WLOG assume it to be red. If N is reachable for some i < R in this segment, it must also be reachable from i + 1, as any index that we jump to from i can also be jumped to from i + 1. To prove that it’ll be non-empty, consider the path from 0 to N. If R = N, we are done. Else, consider smallest index i > R in the path. If it is blue, we can jump to i from R. Else, there must be a blue maximal segment between R and i and we can jump from R to some index in this blue segment and then to i.
Let’s consider a maximal monochromatic segment that isn’t fully reachable yet. As we increase m by 1, the length of the suffix from which N is reachable will increase. This is because if k was the leftmost index in the segment from which N was reachable, then now we can also jump from k-1 to the same index that we earlier jumped to, from k.
Let’s maintain a set of suffixes that are not fully reachable yet. When we increase m, lets iterate on these suffixes right to left and keep trying to increase the suffix size until we have covered the whole segment or we reach a node from which N is unreachable. If the suffix size increases by l, the total number of operations for this suffix is l + 1, and l \geq 1. So, the total number of operations is \leq 2 \times number of newly reachable indices, whose sum over all m is \le 2N. For iterating/deleting over the set of suffixes, we need O(\log N) time per operation, hence overall complexity of maintaining reachability is O(N \log N).
Now, when finding the optimal answer for m, we need to ask O(N/m) reachability queries. Summing over all m gives O(N \log N).
Setter's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = (int)1e6 + 7;
char s[N];
int a[N];
int n;
int m;
int b[N];
int c[N];
int nxt[N][2];
bool good[N];
vector<int> notFull;
int solve(int k) {
vector<int> nw;
while(!notFull.empty()) {
int p = notFull.back();
if (c[p - 1] == b[p - 1]) {
break;
}
notFull.pop_back();
while(c[p] < b[p + 1] && c[p] - c[p - 1] < k) {
good[c[p]] = 1;
c[p]++;
}
if (c[p] < b[p + 1]) nw.push_back(p);
}
while(!nw.empty()) {
notFull.push_back(nw.back());
nw.pop_back();
}
if (!good[n]) return -1;
int p = n;
for (int t = 1;; t++) {
int q = max(0, p - k);
q = nxt[q][a[p] ^ 1];
if (!good[q]) {
q = nxt[q][a[q] ^ 1];
q = nxt[q][a[q] ^ 1];
}
assert(good[q]);
p = q;
if (p == 0) return t;
}
}
void read() {
/*
n = 1000000;
for (int i = 0; i < n; i++)
s[i] = '0' + (int)(i > n / 2);
*/
scanf("%d", &n);
scanf("%s", s);
}
void solve() {
read();
a[0] = 0;
for (int i = 0; i < n; i++)
a[i + 1] = a[i] ^ (int)(s[i] == '1');
a[n + 1] = a[n] ^ 1;
m = 0;
b[m++] = 0;
for (int i = 1; i <= n + 1; i++)
if (a[i] ^ a[i - 1])
b[m++] = i;
m--;
c[0] = 1;
for (int i = 1; i < m; i++)
c[i] = b[i];
notFull.clear();
for (int i = m - 1; i > 0; i--)
notFull.push_back(i);
for (int i = 0; i <= n; i++)
good[i] = 0;
good[0] = 1;
nxt[n][0] = nxt[n][1] = n + 1;
nxt[n][a[n]] = n;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 2; j++)
nxt[i][j] = nxt[i + 1][j];
nxt[i][a[i]] = i;
}
for (int k = 1; k <= n; k++) {
printf("%d ", solve(k));
}
printf("\n");
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t;
scanf("%d", &t);
// t = 1;
while(t--) solve();
return 0;
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
struct window {
deque<pii> Q;
void clear() {
Q.clear();
}
void add(int i, int x) {
while(!Q.empty() && Q.back().second >= x) Q.pop_back();
Q.push_back({i, x});
}
void del(int i) {
if(!Q.empty() && Q.front().first == i) Q.pop_front();
}
int getmin() const {
return Q.empty() ? INT_MAX : Q.front().second;
}
};
void solve() {
int n;
string s;
cin >> n >> s;
s = "0" + s;
rep(i, 1, n + 1) {
if(s[i] == '1') s[i] = '0' ^ '1' ^ s[i - 1];
else s[i] = s[i - 1];
}
vector<vi> nxt(2, vi(n + 2, n + 2));
vi le(n + 1);
for(int i = n; i >= 0; i--) {
nxt[0][i] = nxt[0][i + 1];
nxt[1][i] = nxt[1][i + 1];
nxt[s[i] == '1'][i] = i;
}
rep(i, 1, n + 1) {
if(s[i] == s[i - 1]) le[i] = le[i - 1];
else le[i] = i;
}
vi ans(n + 1, -2);
vector<bool> reach(n + 1, false);
window D0, D1;
auto get = [&](int m) {
D0.clear();
D1.clear();
D0.add(0, 0);
reach[0] = true;
ans[m] = INT_MAX;
rep(i, 1, n + 1) {
ans[m] = (s[i] == '1' ? D0 : D1).getmin();
if(ans[m] != INT_MAX) {
ans[m]++;
reach[i] = true;
}else {
reach[i] = false;
}
(s[i] == '0' ? D0 : D1).add(i, ans[m]);
D0.del(i - m);
D1.del(i - m);
}
if(ans[m] == INT_MAX) ans[m] = n + 1;
return ans[m];
};
int L = 1, R = n + 1;
while(L < R) {
int M = (L + R) / 2;
if(get(M) == n + 1) {
L = M + 1;
}else {
R = M;
}
}
fill(ans.begin() + 1, ans.begin() + L, n + 1);
if(L != n + 1) get(L);
vi len(n + 1, 0), Q;
rep(i, 0, n + 1) {
if(i > 0 && le[i] == i) Q.push_back(i);
if(reach[i]) len[le[i]] = i - le[i] + 1;
}
rep(m, L, n + 1) {
{
int j = 0;
rep(i, 0, sz(Q)) {
int idx = Q[i];
int k = le[idx - 1] + len[le[idx - 1]] - 1 + m;
len[idx] = k - idx + 1;
if(idx + len[idx] >= nxt[s[idx] == '0'][idx]) {
len[idx] = nxt[s[idx] == '0'][idx] - idx;
j++;
}else {
Q[i - j] = idx;
}
}
Q.erase(Q.end() - j, Q.end());
}
int i = n;
ans[m] = 0;
while(i > 0) {
ans[m]++;
int j = nxt[s[i] == '0'][max(0, i - m)];
if(le[j] + len[le[j]] <= j) {
j = nxt[s[i] == '0'][nxt[s[i] == '1'][j]];
}
i = j;
}
}
rep(m, 1, n + 1) {
cout << (ans[m] == n + 1 ? -1 : ans[m]) << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#endif
const int INF = 1 << 30;
struct dsu{
int n;
vector<int> par;
dsu(int n) : n(n), par(n){
iota(par.begin(), par.end(), 0);
}
int root(int x){
vector<int> ALL;
while(x != par[x]){
ALL.push_back(x);
x = par[x];
}
for(int y : ALL) par[y] = x;
return x;
}
void merge(int x, int y){
par[root(x)] = root(y);
}
};
vector<int> nlogn(int n, string s){
vector<int> prefix(n + 1);
vector<vector<int>> lst(n + 1, vector<int>(2)); //[i][j] -> last ball <= i of color j
for(int i = 1; i <= n; i++){
lst[i] = lst[i - 1];
lst[i][prefix[i] = prefix[i - 1] ^ (s[i - 1] - '0')] = i;
}
vector<int> ans(n, INF);
vector<int> dp(n + 2);
function<int(int)> get = [&](int m){
fill(all(dp), INF);
dp[n] = 0;
for(int x = n; x >= 0; x--){
int c = prefix[x];
int pos = min(x + m, n);
int y = lst[pos][c ^ 1];
if(y <= x) continue;
dp[x] = min(dp[x], dp[y] + 1);
if(y == pos){
y = lst[lst[y][c]][c ^ 1];
if(y > x) dp[x] = min(dp[x], dp[y] + 1);
}
}
return dp[0];
};
int lo = 1, hi = n + 1;
while(lo < hi){
int mid = (lo + hi) >> 1;
if(get(mid) < INF) hi = mid;
else lo = mid + 1;
}
int m = lo;
get(m);
vector<int> reachable(n + 1);
dsu D(n + 1);
reachable[0] = true;
for(int i = n; i > 0; i--){
if(reachable[i] = (dp[i] < INF)){
D.merge(i, i - 1);
}
}
while(m <= n){
int x = 0, len = 0;
// O(n / m)
while(x < n){
int c = prefix[x];
int pos = min(x + m, n);
int y = lst[pos][c ^ 1];
if(y <= x) break;
len++;
if(y == pos){
if(reachable[y]){
x = y;
continue;
}
else{
y = lst[lst[y][c]][c ^ 1];
if(y <= x) break;
x = y;
}
} else x = y;
}
assert(x == n); // reached
ans[m - 1] = len;
m++;
// update reachability
x = D.root(n);
while(x > 0){
int c = prefix[x];
int pos = min(x + m, n);
int y = lst[pos][c ^ 1];
if(y > x) reachable[x] |= reachable[y];
y = lst[lst[y][c]][c ^ 1];
if(y > x) reachable[x] |= reachable[y];
if(reachable[x]){
D.merge(x, x - 1);
x = D.root(x - 1);
} else{
x = D.root(lst[x][c ^ 1]); // opposite color
}
}
}
for(int i = 0; i < n; i++) if(ans[i] == INF) ans[i] = -1;
return ans;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int t; cin >> t;
while(t--){
int n; cin >> n;
string s; cin >> s;
for(int v : nlogn(n, s)) cout << v << " ";
cout << "\n";
}
}