Can you find a partition that is always valid?

Suppose you are given a set $$$S$$$. How do you judge whether $$$S$$$ is stable in $$$\mathcal O(\lvert S\rvert)$$$?

Are sets that are very large really necessary?

Note that: we always have a partition like $$$[a_1], [a_2], \dots, [a_n]$$$, since $$$(x, x, x)$$$ always forms a non-degenerate (equilateral) triangle.

We focus on the second partition scheme in which not all continuous subsegments have a length of $$$1$$$. One can also note that if a set $$$S$$$ is stable then for all $$$T \subsetneq S$$$ ($$$T \neq \varnothing$$$), $$$T$$$ is also stable.

• Short proof: If $$$\exists u, v, w \in T$$$ such that $$$(u, v, w)$$$ doesn't form a non-degenerate triangle, therefore $$$u, v, w \in S$$$ so it is concluded that $$$S$$$ is not stable. Contradiction!

If such a partition exists, we can always split long continuous subsegments into shorter parts, while the partition remains valid. Therefore, it's enough to check the case in which there is one subsegment of length $$$2$$$ and the rest of length $$$1$$$. So, we should output NO if and only if for all $$$1 \leq i < n$$$, $$$2\min(a_i, a_{i+1}) \leq \max(a_i, a_{i+1})$$$.

#include <bits/stdc++.h>
 
#define MAXN 1001
int a[MAXN];
void solve() {
	int n; std::cin >> n;
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	for (int i = 1; i < n; ++i) if (2 * std::min(a[i], a[i + 1]) > std::max(a[i], a[i + 1])) 
		{ std::cout << "YES\n"; return; }
	std::cout << "NO\n";
}
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int t; std::cin >> t; while (t--) solve(); return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What if for all $$$1 \leq i \leq n$$$, $$$l_i \ne r_i$$$ holds? How do you prove it?

Use prefix sums or similar to optimize your solution.

For each $$$1 \leq i \leq n$$$, for each $$$l_i \leq x \leq r_i$$$, we want to check if it is okay for impression $$$i$$$ being unique at the value of $$$x$$$. Note that: for each $$$j \neq i$$$, we can always switch $$$w_j$$$ to a value different from $$$x$$$ if $$$l_j \neq r_j$$$, since there are at least two options. Therefore, it is impossible if and only if there exists a $$$1 \leq j \leq n$$$ with $$$j \neq i$$$ such that $$$l_j = r_j = x$$$.

Let's record $$$a_i$$$ as the number of different $$$k$$$ satisfying $$$1 \leq k \leq n$$$ and $$$l_k = r_k = i$$$. If $$$l_i \neq r_i$$$, then we say impression $$$i$$$ cannot be made unique if and only if for all $$$l_i \leq k \leq r_i$$$, $$$a_k \geq 1$$$; otherwise ($$$l_i = r_i$$$), it cannot be unique if and only if $$$a_{l_i} \geq 2$$$.

This can all be checked quickly within a prefix sum, so the overall time complexity is $$$\mathcal O(\sum n)$$$.

#include <bits/stdc++.h>
 
#define MAXN 400001
int l[MAXN], r[MAXN], sum[MAXN], cnt[MAXN];
void solve() {
	int n; std::cin >> n;
	for (int i = 1; i <= 2 * n; ++i) sum[i] = cnt[i] = 0;
	for (int i = 1; i <= n; ++i) {
		std::cin >> l[i] >> r[i];
		if (l[i] == r[i]) sum[l[i]] = 1, ++cnt[l[i]];
	}
	for (int i = 2; i <= 2 * n; ++i) sum[i] += sum[i - 1];
	for (int i = 1; i <= n; ++i) 
		std::cout << ((l[i] == r[i] ? cnt[l[i]] <= 1 : sum[r[i]] - sum[l[i] - 1] < r[i] - l[i] + 1) ? "1" : "0");
	std::cout << '\n';
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int t; std::cin >> t; while (t--) solve(); return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Process many segments simultaneously. What kind of segments do we process at a time?

The length.

The point that must be noted is: that if we call the process of splitting a large segment into two smaller segments a round, then all segments are of the same length when the $$$i$$$-th round of the observation is conducted; and, the number of rounds does not exceed $$$\mathcal O(\log n)$$$. The $$$k$$$ restriction is equivalent to specifying that only a certain prefix of rounds is computed.

Here are some different approaches:

• (Most succinctly) Note that the distribution of segments after round 1 is centrally symmetric; Also, $$$x$$$ and $$$y$$$ being centrally symmetric implies that $$$x + y = n + 1$$$, so it is simple to calculate by simulating the number of segments and the length directly.
• If a segment $$$[l, r]$$$ is split into $$$[l, m - 1]$$$ and $$$[m + 1, r]$$$, its left endpoint sum changes from $$$l$$$ to $$$2l + \frac{r - l}{2} + 1$$$, and since $$$(r - l)$$$ is fixed, the sum of the left endpoints of all segments can be maintained similarly.
• The following recursive method also works: the answer to $$$n$$$ can be recovered by the answer to $$$\lfloor \frac{n}{2} \rfloor$$$. The time complexity is $$$\mathcal O(t\log n)$$$.

This is written by _TernaryTree_.

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
int T;
int n, k;
 
signed main() {
	cin >> T;
	while (T--) {
		cin >> n >> k;
		int mul = n + 1, sum = 0, cur = 1;
		while (n >= k) {
			if (n & 1) sum += cur;
			n >>= 1;
			cur <<= 1;
		}
		cout << mul * sum / 2 << endl;
	}
	return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What if $$$q = 0$$$?

How do you keep the array sorted?

The problem makes no difference when both $$$a$$$ and $$$b$$$ can be rearranged. Let the rearranged arrays of $$$a$$$ and $$$b$$$ be $$$c$$$ and $$$d$$$ respectively.

If $$$q = 0$$$, we can write $$$c$$$ as $$$\operatorname{SORTED}(a_1, a_2 \ldots, a_n)$$$ and $$$d$$$ as $$$\operatorname{SORTED}(b_1, b_2 \ldots, b_n)$$$. It can be proved that this reaches the maximum value: if not so, then

• There must be some pair $$$(i, j)$$$ such that $$$c_i < c_j, d_i > d_j$$$.
• Since $$$\min(c_i, d_i) \cdot \min(c_j, d_j) = c_i \cdot \min(c_j, d_j) \leq c_i \cdot \min(c_j, d_i) = \min(c_i, d_j) \cdot \min(c_j, d_i)$$$, we can swap $$$d_i$$$ and $$$d_j$$$, and the product does not decrease.

Consider the modification, which is a single element increment by $$$1$$$. Without loss of generality, let $$$c_x$$$ be increased by $$$1$$$ (and the processing method for $$$d$$$ is the same). If $$$c_x < c_{x+1}$$$, then after the modification $$$c_x \leq c_{x+1}$$$, which would be fine. Otherwise, we can modify the array $$$c$$$ in the form of a single round of "Insertion Sort": We continuously swap $$$c_x$$$ and $$$c_{x+1}$$$, $$$x \gets x + 1$$$, until $$$c_x < c_{x+1}$$$ (or $$$x = n$$$), and thus the array remains sorted after the increment.

In fact, the swap operation does nothing in the above process: in these cases, $$$c_x = c_{x+1}$$$ holds! So we can just set $$$x'$$$ as the maximum $$$k$$$ such that $$$c_k = c_x$$$, and then increase $$$c_{x'}$$$ by $$$1$$$, after which $$$c$$$ is still sorted. The $$$k$$$ can be found with a naive binary search, so the problem is solved in $$$\mathcal O(n\log n + q(\log p + \log n))$$$ per test case.

#include <bits/stdc++.h>
 
constexpr int MOD = 998244353;
int qpow(int a, int x = MOD - 2) {
	int res = 1;
	for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD;
	return res;
}
 
#define MAXN 200001
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
void solve() {
	int n, q, res = 1; std::cin >> n >> q;
	for (int i = 1; i <= n; ++i) std::cin >> a[i], c[i] = a[i];
	for (int i = 1; i <= n; ++i) std::cin >> b[i], d[i] = b[i];
	std::sort(c + 1, c + n + 1), std::sort(d + 1, d + n + 1);
	for (int i = 1; i <= n; ++i) res = 1ll * res * std::min(c[i], d[i]) % MOD;
	std::cout << res << " \n"[q == 0];
	for (int i = 1, op, x; i <= q; ++i) {
		std::cin >> op >> x;
		if (op == 1) {
			int p = std::upper_bound(c + 1, c + n + 1, a[x]) - c - 1;
			if (c[p] < d[p]) res = 1ll * res * qpow(c[p]) % MOD * (c[p] + 1) % MOD;
			++a[x], ++c[p];
		} else {
			int p = std::upper_bound(d + 1, d + n + 1, b[x]) - d - 1;
			if (d[p] < c[p]) res = 1ll * res * qpow(d[p]) % MOD * (d[p] + 1) % MOD;
			++b[x], ++d[p];
		}
		std::cout << res << " \n"[i == q];
	}
}
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int t; std::cin >> t; while (t--) solve(); return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Suppose somebody wins. In which round does he or she win?

A player can always undo what his opponent did in the previous turn.

Can you find the necessary and sufficient condition for $$$(p, q)$$$ to be a caterpillar that makes Aron win?

Denote Nora's first move as round $$$1$$$, Aron's first move as round $$$2$$$, and so on. Suppose a player does not have a winning strategy in the $$$k$$$-th round, but he or she has a winning strategy in the $$$(k + 2)$$$-th round — it can be shown impossible because the other player can always withdraw the last move of another player so that the status is the same as it was before the $$$k$$$-th round.

Therefore: if a player wins in the $$$k$$$-th round, we claim that $$$k \leq 2$$$.

Given $$$p, q$$$, let's determine who will eventually win the game.

1. If both $$$p$$$ and $$$q$$$ are leaves, the result is a tie.
2. If $$$p$$$ is a leaf while $$$q$$$ is not, Nora wins.
3. If $$$q$$$ is a leaf while $$$p$$$ is not, Aron wins.
4. If neither $$$p$$$ nor $$$q$$$ is a leaf:
   • Can $$$k = 1$$$? Nora wins if and only if $$$p$$$ is adjacent to a leaf.
   • Can $$$k = 2$$$? Aron wins if and only if $$$p$$$ is not adjacent to a leaf, and $$$f(p, q)$$$ is adjacent to a leaf.
   • Otherwise, the result is a tie.

The counting part can also be solved easily in $$$\mathcal O(n)$$$. Denote $$$c$$$ as the number of leaves. The initial answer would be $$$c \cdot (n - c)$$$, considering the third case. For the fourth case, we can enumerate $$$m = f(p, q)$$$, which is adjacent to at least one leaf. Given $$$m$$$, $$$q$$$ must be a non-leaf neighbor of $$$m$$$, and let the number of different $$$q$$$ be $$$k$$$. For each of the potential $$$p$$$, which is a non-leaf node whose neighbors are all non-leaf nodes too, it is computed exactly $$$k - 1$$$ times for all the $$$k$$$ candidates of $$$q$$$ (since $$$m$$$ must be on the simple path from $$$p$$$ to $$$q$$$), so the extra contributions are easy to calculate. (If you do not think that much, you can use some simple DP, which I will not elaborate here.)

#include <bits/stdc++.h>

#define MAXN 200001
std::vector<int> g[MAXN];
inline int deg(int u) { return g[u].size(); }

int d[MAXN];
void solve() {
	int n; std::cin >> n; long long ans = 0;
	for (int i = 1, u, v; i < n; ++i) {
		std::cin >> u >> v;
		g[u].push_back(v), g[v].push_back(u);
	}
	int c1 = 0, c2 = 0;
	for (int i = 1; i <= n; ++i) c1 += (deg(i) == 1);
	ans += 1ll * c1 * (n - c1);
	for (int i = 1; i <= n; ++i) if (deg(i) > 1) {
		for (int v : g[i]) d[i] += (deg(v) > 1);
		c2 += (d[i] == deg(i));
	}
	for (int m = 1; m <= n; ++m) if (deg(m) > 1 && d[m] != deg(m)) 
		ans += 1ll * c2 * (d[m] - 1);
	std::cout << ans << '\n';
	for (int i = 1; i <= n; ++i) 
		(std::vector<int>()).swap(g[i]), d[i] = 0;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int t; std::cin >> t; while (t--) solve(); return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What are we going to fill into the matrix? In other words, is there any relationship between the filed numbers?

Try to come up with a naive DP solution that works in large time complexity, such as $$$\mathcal O(nk^2)$$$.

For many different numbers between two consecutive rows, however, the transition is almost the same.

If $$$x' = \max(a, x + b)$$$ and $$$x'' = \max(c, x' + d)$$$, then $$$x'' = \max(\max(a + d, c), x + b + d)$$$.

Conclusion: For each row, an optimal solution exists, such that the newly filled-in numbers are the same.

• Proof: Consider fixing the rows $$$i - 1$$$ and $$$i + 1$$$, and observe all the newly filled-in numbers at row $$$i$$$. Then a new number $$$u$$$ brings a contribution of $$$c_{u, i-1} + c_{u, i+1}$$$, and it is clear that there exists a scheme that takes the maximum value such that all the $$$u$$$ filled in are equal. Adjusting for each row leads to the above conclusion.

Consider dp. Let $$$f_{i,j}$$$ denote the maximum contribution that can be achieved between the first $$$i$$$ rows (ignoring the initial contribution) when the empty elements in the $$$i$$$-th row are filled with $$$j$$$. Let $$$c_i$$$ be the number of $$$-1$$$ numbers in the $$$i$$$-th row, and $$$d_{i,j}$$$ denote the number of elements $$$j$$$ in the $$$i$$$-th row initially.

The transfer should be as follows:

In addition to being able to optimize the above transition to $$$\mathcal O(nk)$$$, the present problem in a matrix has a good property. Specifically, for the same $$$i$$$, there are only $$$\mathcal O(m)$$$ values of $$$j$$$ such that $$$d_{i,j} \neq 0$$$!

If $$$d_{i,j} = 0$$$ and $$$d_{i-1, j} = 0$$$, the original transfer can be viewed as

This can be seen as a global modification in the form of $$$x \gets \max(a, x + b)$$$. The tags are composable in $$$\mathcal O(1)$$$; Otherwise, we can brutely update the new $$$dp_j$$$ for $$$\mathcal O(m)$$$ positions.

Therefore, this problem is solved in $$$\mathcal O(nm)$$$. We decided to let every segment tree solution pass comfortably, so that we set small constraints and large TL.

Bonus Hint for implementation: always use $$$\max(a, dp_j + b)$$$ to get the real value.

#include <bits/stdc++.h>
 
namespace FastIO {
	char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
#undef getchar
}; using namespace FastIO;
 
using ll = long long;
void solve() {
	int n = read<int>(), m = read<int>(), k = read<int>(); ll cntP = 0, cntQ = 0;
	std::vector<int> vep(m), veq(m), cntp(k + 1), cntq(k + 1), vis(k + 1);
	std::vector<ll> dp(k + 1); ll a = 0, b = 0, v = 0, ext = 0; // max(a, x + b).
	cntp[0] = cntq[0] = m;
	auto get = [&](int x) -> int { return (~x) ? x : 0; };
	auto read_q = [&]() -> void {
		for (int i = 0; i < m; ++i) --cntq[get(veq[i])];
		for (int i = 0; i < m; ++i) ++cntq[get(veq[i] = read<int>())];
		cntQ = cntq[0];
	};
	auto roll = [&]() -> void { std::swap(vep, veq), std::swap(cntp, cntq), std::swap(cntP, cntQ); };
	auto chkmax = [&](ll &a, ll b) -> void { a = std::max(a, b); };
	read_q(), roll();
	for (int i = 2; i <= n; ++i) {
		read_q();
		ll max_dp = std::max(a, v + b);
		for (int k : vep) if (~k) chkmax(max_dp, std::max(a, dp[k] + b) + cntP * cntq[k]);
		for (int k : veq) if (~k) chkmax(max_dp, std::max(a, dp[k] + b) + cntP * cntq[k]);
		for (int k : vep) if ((~k) && vis[k] != i) {
			vis[k] = i, ext += 1ll * cntp[k] * cntq[k];
			dp[k] = std::max(a, dp[k] + b) + cntP * cntq[k] + cntQ * cntp[k] - b;
			chkmax(dp[k], max_dp + cntp[k] * cntQ - b - cntP * cntQ);
			chkmax(v, dp[k]);
		} for (int k : veq) if ((~k) && vis[k] != i) {
			vis[k] = i;
			dp[k] = std::max(a, dp[k] + b) + cntP * cntq[k] + cntQ * cntp[k] - b;
			chkmax(dp[k], max_dp + cntp[k] * cntQ - b - cntP * cntQ);
			chkmax(v, dp[k]);
		} a = std::max(max_dp, a + cntP * cntQ), b += cntP * cntQ;
		roll();
	} print<ll>(std::max(a, v + b) + ext, '\n');
}
 
int main() { int T = read<int>(); while (T--) solve(); return 0; }

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

(If we do not have to be deterministic) We do not need any hard string algorithm.

In what cases won't greed work? Why?

Is your brute forces actually faster (maybe you can explain it by harmonic series)?

note that: since $$$i + (n - i) = n$$$, then $$$\max(i, n - i) \geq \frac{n}{2}$$$. denote $$$X = s_1s_2\dots s_i$$$ and $$$Y = s_{i+1}s_{i+2}\dots s_n$$$, then $$$\max(\lvert X\rvert, \lvert Y\rvert) = \mathcal O(n)$$$.

If $$$X$$$ and $$$T$$$ have a common shortest period, the problem can be transformed into a pure number theory problem: If there are non-negative integers $$$p, q$$$ such that $$$px + qy = m$$$. By simply enumerating the coefficient of $$$\max(x, y)$$$, the total time complexity is actually $$$\mathcal O(\frac{m}{n}) \cdot \mathcal O(n) = \mathcal O(m)$$$, which is affordable.

In other cases, we can prove that if there is at least one possible partition, then there is exactly one partition. This can be proved inductively. If $$$X$$$ is not a prefix of $$$Y$$$ and $$$Y$$$ is not a prefix of $$$X$$$, greedy matching would work. Otherwise, WLOG let $$$Y = X + Y'$$$, we can try to split $$$t$$$ using $$$X$$$ and $$$Y'$$$, then try to recover the partition using $$$X$$$ and $$$Y$$$. This is like the process of doing Euclid algorithms on numbers, so if $$$X$$$ and $$$T$$$ don't share a common shortest period, there is at most one partition.

How do we judge it efficiently? WLOG let $$$\lvert X\rvert \leq \lvert Y\rvert$$$, we can write $$$Y = X^k + Y'$$$, in which $$$k$$$ is the maximum possible. We can always try to match with $$$X$$$, and if it fails withdraw the last $$$k$$$ matches of $$$X$$$ (if there is not that much, then no solution), and try to match with $$$Y$$$ (if it still fails, then no solution). Why would it work? If $$$Y'$$$ is a prefix of $$$X$$$ and for some $$$k'$$$, $$${Y'}^{k'} + X$$$ is a prefix of $$$X$$$, then it can be proven that the conditions lead to a common period, which makes a contradiction. To judge whether a prefix or suffix of $$$s$$$ matches a substring in $$$t$$$, it's more efficient to use Z Function. Well-implemented hashing methods can also pass comfortably.

The time complexity can be proven by harmonic series, therefore it is $$$\mathcal O(m\log n)$$$.

Thanks for orzdevinwang for pointing out it!

I will add that later, sorry for the inconvenience.

During testing, we found that jqdai0815's solution is actually more violent than we thought (We have also received something similar in contest).

He specially handled the case in which $$$X$$$ and $$$T$$$ share a common shortest period, and for the rest $$$i$$$, he just used two queues to optimize the BFS progress (actually changing it to std::priority_queue<int> or similar also works), and it passed just seeming to have a larger constant time complexity.

I'm curious if anybody can (hack it or) prove that it is correct. Thanks in advance!

#include <bits/stdc++.h>
 
void Zfunc(int* z, const std::string& S) {
	z[0] = 0;
	for (int i = 1, r = 0, n = (int)S.size(); i < n; ++i) if (r + z[r] - 1 < i) {
		z[i] = 0;
		while (i + z[i] < n && S[z[i]] == S[i + z[i]]) ++z[i];
		r = i;
	} else {
		z[i] = std::min({z[i - r], n - i, r + z[r] - i});
		while (i + z[i] < n && S[z[i]] == S[i + z[i]]) ++z[i];
		if (z[i] != z[i - r]) r = i;
	}
}
 
#define MAXN 10000005
int z[MAXN], r[MAXN];
char ans[MAXN];
void solve() {
	int n, m, k; std::cin >> n >> m, k = n + 1;
	std::string s, t; std::cin >> s >> t;
	Zfunc(z, s + "$" + t);
	std::reverse(s.begin(), s.end());
	std::reverse(t.begin(), t.end());
	Zfunc(r, s + "$" + t);
	auto match_pre = [&](int i, int j) -> bool { return z[n + j] >= i; };
	auto match_suf = [&](int i, int j) -> bool { return r[n + m - j - i + 2] >= i; };
	for (int i = 1; i <= n; ++i) if (z[i - 1] == n - i + 1) { k = i - 1; break; }
	bool period = (n % k == 0), ok = (m % k == 0);
	if (k <= n) for (int i = 0; i < m; ++i) if (t[i] != s[i % k]) ok = 0;
	for (int i = 1; i < n; ++i) {
		if (period && i % k == 0) {
			if (!ok) { putchar('0'); continue; }
			if (i > n / 2) { putchar(ans[n - i]); continue; }
			int x = i / k, y = n / k, z = m / k, flag = 0;
			for (int B = 0; !flag && B * y <= 2 * z; ++B) if ((z - (B * y)) % x == 0) 
				if ((z - (B * y)) / x + B >= 0) { flag = 1; break; }
			putchar(ans[i] = (flag ^ '0')); continue;
		}
		if (i <= n / 2) {
			int d = 0, pos = i + 1, flag = 1, now = 1, mth = 0;
			while (z[pos - 1] >= i) ++d, pos += i;
			// std::cout << d << ' ' << pos << '\n';
			while (now < m + 1) {
				if (match_pre(i, now)) ++mth, now += i; else {
					if (mth < d || !match_suf(n - i, now - d * i)) { flag = 0; break; }
					now = now - d * i + n - i, mth = 0;
				}
			} putchar(flag ^ '0');
		} else {
			int d = 0, pos = i + 1, flag = 1, now = 1, mth = 0;
			while (r[pos - 1] >= n - i && pos > n - i) ++d, pos -= n - i;
			while (now < m + 1) {
				if (match_suf(n - i, now)) ++mth, now += n - i; else {
					if (mth < d || !match_pre(i, now - d * (n - i))) { flag = 0; break; }
					now = now - d * (n - i) + i, mth = 0;
				}
			} putchar(flag ^ '0');
		}
	} puts("");
}
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int t; std::cin >> t; while (t--) solve(); return 0;
}

#pragma GCC optimize(2)
#include <bits/stdc++.h>

const unsigned B = 131, C = 96;

#define MAXN 10000001
unsigned p[MAXN], pre[MAXN], suf[MAXN], hsht[MAXN];
inline unsigned qry_s(int l, int r) {
	return pre[r] - pre[l - 1] * p[r - l + 1];
}
inline unsigned qry_t(int l, int r) {
	return hsht[r] - hsht[l - 1] * p[r - l + 1];
}

char ans[MAXN];

unsigned pred[25]; int len[25];
void solve() {
	int n, m; std::string s, t;
	std::cin >> n >> m >> s >> t;
	s = " " + s, t = " " + t;
	pre[0] = suf[n + 1] = hsht[0] = 0;
	for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] * B + s[i] - C;
	for (int i = n; i; --i) suf[i] = suf[i + 1] + (s[i] - C) * p[n - i];
	for (int i = 1; i <= m; ++i) hsht[i] = hsht[i - 1] * B + t[i] - C;
	int k = n + 1;
	for (int i = 2; i <= n; ++i) if (suf[i] == pre[n - i + 1]) { k = i - 1; break; }
	bool period = (n % k == 0), ok = (m % k == 0);
	if (k <= n) for (int i = 1; i <= m; ++i) if (t[i] != s[(i - 1) % k + 1]) ok = 0;
	for (int i = 1; i < n; ++i) {
		if (period && i % k == 0) {
			if (!ok) { putchar('0'); continue; }
			if (i > n / 2) { putchar(ans[n - i]); continue; }
			int x = i / k, y = n / k, z = m / k, flag = 0;
			for (int B = 0; !flag && B * y <= 2 * z; ++B) if ((z - (B * y)) % x == 0)
				if ((z - (B * y)) / x + B >= 0) { flag = 1; break; }
			putchar(ans[i] = (flag ^ '0')); continue;
		}
		if (i <= n / 2) {
			int now = 1, cur = i + 1, flag = 1, mth = 0, k = 0, d = 0;
			pred[0] = pre[i], len[0] = i;
			while (len[d] <= m / 2) {
				pred[d + 1] = pred[d] * p[len[d]] + pred[d];
				len[d + 1] = len[d] * 2, ++d;
			}
			for (int j = d; ~j; --j) if (cur + len[j] <= n + 1 && qry_s(cur, cur + len[j] - 1) == pred[j])
				k |= (1 << j), cur += len[j];
			while (now <= m) {
				if (now + i <= m + 1 && qry_t(now, now + i - 1) == pre[i]) {
					for (int j = d; ~j; --j) if (now + len[j] <= m + 1 && qry_t(now, now + len[j] - 1) == pred[j])
						mth += (1 << j), now += len[j];
				} else {
					if (mth < k || qry_t(now - k * i, now - k * i + n - i - 1) != suf[i + 1]) { flag = 0; break; }
					now = now - k * i + n - i, mth = 0;
					if (now > m + 1) { flag = 0; break; }
				}
			} putchar(flag ^ '0');
		} else {
			int now = 1, cur = 1, flag = 1, mth = 0, k = 0, d = 0;
			pred[0] = suf[i + 1], len[0] = n - i;
			while (len[d] <= m / 2) {
				pred[d + 1] = pred[d] * p[len[d]] + pred[d];
				len[d + 1] = len[d] * 2, ++d;
			}
			for (int j = d; ~j; --j) if (cur + len[j] <= i + 1 && qry_s(cur, cur + len[j] - 1) == pred[j])
				k |= (1 << j), cur += len[j];
			while (now <= m) {
				if (now + n - i <= m + 1 && qry_t(now, now + n - i - 1) == suf[i + 1]) {
					for (int j = d; ~j; --j) if (now + len[j] <= m + 1 && qry_t(now, now + len[j] - 1) == pred[j])
						mth += (1 << j), now += len[j];
				} else {
					if (mth < k || qry_t(now - k * (n - i), now - k * (n - i) + i - 1) != pre[i]) { flag = 0; break; }
					now = now - k * (n - i) + i, mth = 0;
					if (now > m + 1) { flag = 0; break; }
				}
			} putchar(flag ^ '0');
		}
	} puts("");
}

void init(const int v = 10000000) {
	p[0] = 1; for (int i = 1; i <= v; ++i) p[i] = p[i - 1] * B;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	init(); int t; std::cin >> t; while (t--) solve(); return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What if $$$w = 2$$$? Is it optimal to increase $$$\sum\limits_{i=0}^n [a_i \neq a_{i+1}]$$$ (suppose $$$a_0 = a_{n+1} = 2$$$)?

If $$$w \geq 3$$$, what's the answer to the first question?

If $$$a_i = a_{i+1}$$$, after the operation we can obtain $$$a_{i-1} = a_i$$$ or $$$a_{i+1} = a_{i+2}$$$ (and possibly, both).

Try to think of the whole process reversedly. If $$$w \geq 3$$$, $$$1 \leq a_i \leq w - 1$$$, can you solve the problem?

How many extra operations are required for each $$$1 \leq i \leq n$$$ if $$$a_i = w$$$, in the above scheme you use for $$$a_i \leq w - 1$$$?

Read the Hints.

• $$$w = 2$$$

After any operation, $$$k = \sum\limits_{i=0}^n [a_i \neq a_{i+1}]$$$ won't decrease (suppose $$$a_0 = a_{n+1} = 2$$$). For a fixed $$$k$$$, the maximal $$$\sum a_i = 2n - \frac{1}{2}k$$$ and can be reached by each time turning a $$$[2, 1, 1]$$$ into $$$[2, 2, 1]$$$ (or symmetrically, $$$[1, 1, 2] \rightarrow [1, 2, 2]$$$.

• $$$w \geq 3$$$
  • No initial operations can be conducted, or $$$\min(a_i) = w$$$

This case is trivial.

• $$$w \geq 3$$$
  • Some initial operations can be conducted

We claim that the answer to the first question is $$$nw - 1$$$. For the second question, let's study some rather easier cases below.

• $$$w \geq 3$$$
  • Some initial operations can be conducted
    • $$$a_i \neq w$$$

We pretend that the final sequence is $$$[w, w, \dots, w, (w-1), w, w, \dots, w]$$$, then since $$$(a_i, a_{i+1})$$$ must be different after the operation, the last operation can only occur on $$$[w, (w-1)]$$$ (or $$$[(w-1), w]$$$). And since initially $$$a_i \neq w$$$, each position must have been operated on at least once.

This gives us states such as $$$[w, \dots, w, x, x, w, \dots, w]$$$, $$$[w, \dots, w, y, y, x, w, \dots, w]$$$, etc. To the leftmost positions, we get $$$a_1 = a_2$$$ (essentially based on Hint 3). Also, we get ...... $$$a_{n-1} = a_n$$$? This is if and only if the initial $$$[w, (w - 1)]$$$ is neither at the beginning nor at the end. If the initial $$$[w, (w - 1)]$$$ is at the beginning, we only need $$$a_{n-1} = a_n$$$ to achieve the goal, and symmetrically the same. Less is more. Obviously, we only need to satisfy either $$$a_1 = a_2$$$ or $$$a_{n-1} = a_n$$$, and then use $$$n - 1$$$ more operations to reach the target situation.

How do we get to $$$a_1 = a_2$$$ (symmetrically the same)? Based on Hint 3, we find the smallest $$$x$$$ that satisfies $$$a_x = a_{x+1}$$$, and then follow the example above, again using $$$x - 1$$$ operations to conduct the equality sign to $$$a_1 = a_2$$$.

• $$$w \geq 3$$$
  • Some initial operations can be conducted
    • $$$a_1 \neq w, a_n \neq w$$$

Basically, the idea remains to reach $$$a_1 = a_2$$$ in the same way first (symmetrically the same), and then to extend to all positions. However, at this point, in the second stage, some problems may arise as follows:

• $$$[\dots \underline{a_k}\ a_{k+1}\ w\ a_{k+3} \dots]$$$
• $$$[\dots \underline{\color{red}{a_{k+1}}\ a_{k+1}}\ w\ a_{k+3} \dots]$$$
• $$$[\dots \color{red}s\ \underline{\color{red}w\ w}\ a_{k+3} \dots]$$$
• $$$[\dots \color{red}{\underline{s\ s}}\ t\ a_{k+3} \dots]$$$
• $$$[\dots \color{red}w\ \underline{\color{red}t\ t}\ a_{k+3} \dots]$$$
• $$$[\dots \color{red}{w\ w}\ \underline{\color{red}{a_{k+3}}\ a_{k+3}} \dots]$$$

In which $$$s, t, w$$$ are three distinct integers in the range $$$[1, w]$$$ (This also explains why we need to specially deal with the $$$w = 2$$$ case). Since we cannot fix $$$a_{k+2} = w$$$ at the beginning (refer to the "Why is it optimal?" spoiler above), we have to first change $$$a_{k+2}$$$ into something not equal to $$$w$$$, and that cost at least $$$2$$$ extra operations, which is shown here.

Do we always need $$$2$$$ extra operations? One may note that if $$$a_i = a_{i+1} = w$$$, in which the two elements are both in the way of expansion, we can only use $$$1$$$ operation to vanish their existence. Formally, if there is a maximum continuous subsegment of $$$w$$$ in the way of expansion, let its length be $$$L$$$, then we will spend $$$\lceil \frac{L}{2} \rceil + [L = 1]$$$ extra operations.

• $$$w \geq 3$$$
  • Some initial operations can be conducted
    • No additional constraints

It may come to you that if $$$a_1 = w$$$, we can ignore $$$a_1$$$; if $$$a_1 = a_2 = w$$$, we can ignore $$$a_2$$$. Symmetrically the same. And so on... Then we boil the problem down to the case above.

It is correct unless in some rare cases when we ignore all the prefixes and suffixes, there will be no remaining $$$a_i = a_{i+1}$$$; or if we pick any pair $$$a_i = a_{i+1}$$$ as the starting pair in the remaining array, it is not optimal compared to picking an $$$a_k = a_{k+1} = w (a_{k+2} \neq w)$$$ (symmetrically the same). So, we have to special handle the deleted prefix and suffix, once it has a length greater than $$$2$$$.

In summary, the problem can be solved in $$$\mathcal O(n)$$$.

#include <bits/stdc++.h>

#define MAXN 200005
int a[MAXN];

void solve() {
	int N, w; scanf("%d%d", &N, &w);
	for (int i = 1; i <= N; ++i) scanf("%d", a + i);
	if (N == 1) return (void)printf("%d 0\n", a[1]);
	if (*std::min_element(a + 1, a + N + 1) == w)
		return (void)printf("%lld 0\n", 1ll * w * N);
	if (w == 2) {
		int ans = N * 2, pans = 0;
		for (int i = 1, j = 1; i <= N; i = ++j) if (a[i] == 1) {
			--ans; while (j < N && a[j + 1] == 1) ++j; pans += j - i;
		}
		return (void)printf("%d %d\n", ans, pans);
	}
	bool flag = true;
	for (int i = 1; i < N; ++i) if (a[i] == a[i + 1]) flag = false;
	if (flag) return (void)printf("%lld 0\n", std::accumulate(a + 1, a + N + 1, 0ll));
	printf("%lld ", 1ll * w * N - 1);
	if (std::accumulate(a + 1, a + N + 1, 0ll) == 1ll * w * N - 1) return (void)puts("0");
	int ans = 0x3f3f3f3f, l = (a[1] == w ? 2 : 1), r = (a[N] == w ? N - 1 : N);
	if ((a[1] == w && a[2] == w) || (a[N] == w && a[N - 1] == w)) {
		int Lw = 0, Rw = N + 1;
		while (a[Lw + 1] == w) ++Lw; while (a[Rw - 1] == w) --Rw;
		int pans = Rw - Lw;
		for (int i = Lw + 1, j = i; i < Rw; i = ++j) if (a[i] == w) {
			while (j + 1 < Rw && a[j + 1] == w) ++j;
			pans += (i == j ? 2 : ((j - i) >> 1) + 1);
		}
		ans = pans, l = Lw + 1, r = Rw - 1;
	}
	for (int d = 0; d < 2; std::reverse(a + l, a + r + 1), ++d) 
		for (int i = l - 1, pre = 0, len = 0; i + 2 <= r; ) {
			if (a[i + 1] == a[i + 2]) 
				ans = std::min(r - (i + 1) + r - l - 1 + pre - ((len == 1) && i + 2 < r && a[i + 3] != w ? 1 : 0), ans);
			++i; if (a[i] == w) ++len, pre += (len == 1 ? 2 : len == 2 ? -1 : (len & 1)); else len = 0;
	}
	printf("%d\n", ans);
}

int main() { int T; scanf("%d", &T); while (T--) solve(); return 0; }

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

What is the minimized LIS?

How do you prove that it is an achievable lower bound?

Go for a brute DP first.

We claim that the minimized LIS is $$$\sum a_i$$$. Let $$$p$$$ be $$$\sum a_i$$$.

Since it is required that $$$\operatorname{LIS}(b) = p$$$ while $$$\sum b_i = p$$$, we point out that it is equivalent to each of the prefix sums of the sequence being between $$$[0, p]$$$.

• Sufficiency: $$$\forall X \in [0, p], Y \in [0, p]$$$, $$$X - Y \leq p$$$. Also, we can pick $$$X = p, Y = 0$$$, so it can only be $$$= p$$$.
• Necessity: disproof. If a prefix sum is $$$< 0$$$, then choose the whole array except for this prefix; if a prefix sum is $$$> p$$$, then choose this prefix. Both derive a contradiction of the LIS being greater than $$$p$$$.

Consider dp. Let $$$f_{i,j}$$$ denote, after considering the first $$$i$$$ numbers, the minimum extra sequence length (i.e. the actual length minus $$$i$$$), when the current prefix sum is $$$j$$$. The initial states are $$$f_{0,j} = [j \neq 0]$$$. The transfer is simple too:

It is possible to optimize the transfer to $$$\mathcal O(np)$$$, since for each $$$j$$$, the contribution from at most one $$$k$$$ is special ($$$+0$$$). We can calculate the prefix and suffix $$$\min$$$ for $$$f_{i-1}$$$ and it will be fast to get the dp array in the new row. Then, let's focus on optimizing it to $$$\mathcal O(n)$$$.

We call the set of $$$0 \leq k \leq p$$$ satisfying $$$0 \leq k + a_i \leq p$$$ as the legal interval of $$$i$$$ (denoted as $$$L_i$$$).

It is concluded that the range of $$$f_{i, 0\dots p}$$$ is at most $$$1$$$, and this can be proven by considering the transfer to each of the $$$j$$$ with the $$$k \in L_i$$$ which has the least $$$f_{i-1, k}$$$. Let $$$v_i = \min_{0 \leq j \leq p}(f_{i, j})$$$. We also have: for those $$$j$$$ with $$$f_{i,j} = v_i$$$, they form a consecutive segment in the integer field. Let the segment be covering $$$[l_i, r_i]$$$.

Inductive proof. The essence of the transfer is that it shifts all the DP values $$$= v_{i-1}$$$ by $$$a_i$$$ unit length, and all the other numbers will be updated to $$$v_{i-1} + 1$$$. Then truncates the $$$j \in ((-\inf, 0) \cup (p, +\inf))$$$ part. The consecutive segment remains consecutive. Specially, if $$$[l_{i-1}, r_{i-1}] \cap L_i = \varnothing$$$, then $$$\min_{k \in L_i}(f_{i-1, k}) = v_{i-1} + 1$$$, hence we need to set $$$v_i = v_{i-1} + 1$$$, and $$$l_i, r_i$$$ as the range of $$$j = k + a_i$$$ in which $$$k \in L_i$$$. Otherwise, $$$v_i = v_{i-1}$$$, and $$$l_i, r_i$$$ can be calculated by shifting $$$l_{i-1}, r_{i-1}$$$ by $$$a_i$$$ unit length.

In fact, we only need to maintain three variables $$$l, r, v$$$ to represent the current consecutive segment and the current value field. Therefore, this problem can be easily solved in $$$\mathcal O(n)$$$.

#include <bits/stdc++.h>
 
namespace FastIO {
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
 
#define MAXN 3000001
int a[MAXN];
void solve() {
	int N = read<int>(); long long p = 0, l = 0, r = 0, v = 0;
	for (int i = 1; i <= N; ++i) p += (a[i] = read<int>());
	for (int i = 1; i <= N; ++i) if (a[i] >= 0) {
		l += a[i], r = std::min(r + a[i], p);
		if (l > r) ++v, l = a[i], r = p;
	} else {
		a[i] = -a[i];
		r -= a[i], l = std::max(l - a[i], 0ll);
		if (l > r) ++v, l = 0, r = p - a[i];
	}
	print<int>(v + N + (int)(r != p), '\n');
}
int main() { int T = read<int>(); while (T--) solve(); return 0; }

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve: