• Amazing round:
• Good round:
• Average round:
• Bad round:
• Horrible round:

If one team got a score of $$$x$$$ in the first half, what is the maximum score the other team could get?

We can consider the first half and the second half separately. The dream might come true if and only if the scores in both halves are possible. In the second half, the RiOI team scored $$$(c - a)$$$ goals, while the KDOI team scored $$$(d - b)$$$ goals.

Suppose the RiOI team scored $$$x$$$ goals in some half. Denoting the score of the KDOI team as $$$y$$$, one can see that the maximal value of $$$y$$$ is $$$2\cdot x + 2$$$, under the goal order $$$\tt{\color{red}K\color{red}K\color{black}RK\color{red}K\color{black}R...RK\color{red}K\color{black}RK\color{red}K}$$$. When $$$y \geq x$$$, all scores in the range $$$[x, 2\cdot x+2]$$$ can be achieved by deleting several $$$\tt K$$$-s colored red.

Therefore, the scores $$$x: y$$$ in a single half are possible, if and only if $$$\max(x, y) \leq 2\cdot \min(x, y) + 2$$$.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int T, a, b, c, d;

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d%d%d%d", &a, &b, &c, &d), c -= a, d -= b;
		if (a > b) swap(a, b); if (c > d) swap(c, d);
		puts((a + 1 << 1) >= b && (c + 1 << 1) >= d ? "YES" : "NO");
	}
}

import sys
input=sys.stdin.readline
 
t=int(input())
for _ in range(t):
    a,b,c,d=map(int,input().split())
    if(max(a,b)>2*min(a,b)+2):
        print("NO")
    elif(max(c-a,d-b)>2*min(c-a,d-b)+2):
        print("NO")
    else:
        print("YES")

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

When shall we output $$$\tt{NO}$$$?

We can put larger numbers on indices with $$$s_i = \tt{0}$$$, and smaller numbers on indices with $$$s_i = \tt{1}$$$.

Note that if there is an interval $$$p_l, \ldots, p_r$$$ such that $$$r - l + 1 \geq k$$$, and $$$s_l = s_{l+1} = \ldots = s_r = \tt{1}$$$, then it's impossible to satisfy all the requirements, since by iterating $$$i$$$ over $$$l$$$ to $$$r$$$, there must be some $$$i$$$ such that $$$p_i = \max(p_l, \ldots, p_r)$$$.

Otherwise, denote $$$c$$$ as the number of occurrences of $$$\tt{1}$$$ in the string $$$s$$$. We can always construct the permutation by filling the indices $$$i$$$ of $$$s_i = \tt{1}$$$ with $$$1$$$ to $$$c$$$ respectively, and indices of $$$s_i = \tt{0}$$$ with $$$(c + 1)$$$ to $$$n$$$ respectively. It works because for every interval $$$[l, r]$$$ such that $$$r - l + 1 \geq k$$$, there is at least one index $$$l \leq i \leq r$$$ such that $$$s_i = \tt{0}$$$, and it will be greater than all the indices of $$$s_i = \tt{1}$$$.

Time complexity: $$$\mathcal O(n)$$$ per test case.

#include <bits/stdc++.h>
 
void solve() {
	int n, k; std::cin >> n >> k;
	std::string s; std::cin >> s, s = " " + s;
	for (int i = 1, j = 1; i <= n; i = ++j) if (s[i] == '1') {
		while (j < n && s[j + 1] == '1') j++;
		if (j - i + 1 >= k) return (void)puts("NO");
	}
	puts("YES");
	int c1 = 0, c2 = std::count_if(s.begin(), s.end(), [&](char ch) -> bool { return ch == '1'; });
	for (int i = 1; i <= n; ++i) 
		std::cout << (s[i] == '1' ? ++c1 : ++c2) << " \n"[i == n];
}
 
int main() { int t; std::cin >> t; while (t--) solve(); return 0; }

import sys
input=lambda:sys.stdin.readline().rstrip()
for _ in range(int(input())):
  n,k=map(int,input().split())
  s=input()
  if "1"*k in s: # YES YOU WILL NOT BELIEVE THAT THIS IS O(N)
    print("No")
  else:
    print("Yes")
    a=sorted(range(0,n),key=lambda i:s[i],reverse=True)
    ans=[0]*n
    for i in range(n):
      ans[a[i]]=i+1
    print(*ans)

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

DP is needed for this problem.

If you force some index to be in the subsequence, there is only one optimal transition.

Let's go for DP. Denote $$$dp(i)$$$ as the length of the longest neat subsequence of prefix $$$[a_1, a_2, \ldots, a_i]$$$. It's obvious that $$$dp(0) \leq dp(1) \leq \ldots \leq dp(n)$$$.

Suppose we have calculated $$$dp(0), \ldots, dp(i-1)$$$. Let's try to calculate $$$dp(i)$$$:

1. If $$$a_i$$$ is not selected in the neat subsequence, we simply use $$$dp(i-1)$$$ to update $$$dp(i)$$$;
2. If $$$a_i$$$ is selected in the neat subsequence, the subsequence must end with $$$a_i$$$ elements equal to $$$a_i$$$. Since the $$$dp$$$ array is monotone, we should greedily find the $$$a_i$$$-th largest index $$$x$$$ in $$$[a_1, \ldots, a_i]$$$ where $$$a_x = a_i$$$, and use $$$dp(x-1) + a_i$$$ to update $$$dp(i)$$$.

The resulting $$$dp(i)$$$ is $$$\max(dp(i-1), dp(x-1) + a_i)$$$. Finding $$$x$$$ can be done efficiently by storing the occurrences of each different value.

Time complexity: $$$\mathcal O(n)$$$ per test case.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

int T, n, a[MAXN], dp[MAXN]; deque<int> q[MAXN];

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) q[i].clear();
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) {
			dp[i] = dp[i - 1], q[a[i]].emplace_back(i);
			if (q[a[i]].size() > a[i]) q[a[i]].pop_front();
			if (q[a[i]].size() == a[i]) dp[i] = max(dp[i], dp[q[a[i]].front() - 1] + a[i]);
		}
		printf("%d\n", dp[n]);
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

You may not know the given Manhattan distance is between you and which anchor point. Can you make some moves so that you can determine it?

The absolute value in $$$\lvert x_i-c \rvert + \lvert y_i-d \rvert$$$ is somehow annoying, because you don't know whether it's $$$(x_i - c)$$$ or $$$(c - x_i)$$$. Find a way to fix the sign of $$$(x_i - c)$$$ and $$$(y_i - d)$$$.

Read the hints.

Denote $$$V$$$ as $$$10^9$$$. Let's first use four operations $$$(\texttt{L}, V)$$$, $$$(\texttt{L}, V)$$$, $$$(\texttt{U}, V)$$$, and $$$(\texttt{U}, V)$$$. Since initially $$$-V \leq X, Y \leq V$$$, after the four operations, it's guaranteed that $$$X', Y' \leq -V$$$.

Thus, one can note that the current value received from the jury is exactly $$$\min\limits_{1 \leq i \leq n}(\lvert x_i - X'\rvert + \lvert y_i - Y'\rvert) = \min\limits_{1 \leq i \leq n}(X' - x_i + y_i - Y')$$$, which equals $$$\min\limits_{1 \leq i \leq n}(x_i - y_i) - X + Y + 4V$$$. This gives us the value of $$$X + Y$$$.

Similarly, if we move to the top-right corner (or the bottom-left one), we can know the value of $$$X - Y$$$. It would take $$$4$$$ extra steps of moving down or moving right (instead of $$$4 + 4$$$). By knowing $$$X + Y$$$ and $$$X - Y$$$, $$$X$$$ and $$$Y$$$ can be solved out.

Hence, we use only $$$8$$$ operations for each test case, which is sufficient to pass.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
    ll mn1 = LLONG_MAX, mx2 = -LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        ll x, y; cin >> x >> y;
        mn1 = min(mn1, y - x);
        mx2 = max(mx2, x + y);
    }
    ll res;
    cout << "? R 1000000000" << endl;
    cin >> res;
    cout << "? R 1000000000" << endl;
    cin >> res;
    cout << "? D 1000000000" << endl;
    cin >> res;
    cout << "? D 1000000000" << endl;
    cin >> res;
    ll res1 = mn1 - res + 4000000000ll;
    cout << "? U 1000000000" << endl;
    cin >> res;
    cout << "? U 1000000000" << endl;
    cin >> res;
    cout << "? U 1000000000" << endl;
    cin >> res;
    cout << "? U 1000000000" << endl;
    cin >> res;
    ll res2 = mx2 + res - 4000000000ll;
    cout << "! " << (res2 - res1) / 2 << ' ' << (res2 + res1) / 2 << endl;
	return;
}

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

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

Consider the value of nodes on a cycle.

Consider the parity of the cycle's length.

The following are equivalent statements:

• "There is a cycle containing nodes $$$u, v$$$";
• "Nodes $$$u, v$$$ are in the same two-edge-connected component".

Two two-edge-connected components don't affect each other.

Read the hints.

First, focus on a simple cycle only. Denote its length as $$$l$$$. We can choose two arbitrary nodes $$$u$$$ and $$$v$$$ on the cycle, obtaining two different simple paths. The two paths have equal values for all pairs of $$$(u, v)$$$. This implies that, for each set of size $$$l-2$$$ containing only nodes on the cycle, the bitwise XOR of the weight of the nodes in the set should equal $$$0$$$.

Thus, all nodes on the cycle have equal weight, since when sets $$$S_0 \cup {v}$$$ and $$$S_0 \cup {u}$$$ have equal bitwise XOR of node weights, this leads to nodes $$$u$$$ and $$$v$$$ having equal weights. Additionally, if $$$l$$$ is odd, one can verify that the weight of nodes on the cycle must be equal to $$$0$$$ (otherwise, it can be an arbitrary integer in $$$[0, V)$$$).

By decomposing the graph into two-edge-connected components, one can easily determine whether two nodes share a cycle —— by checking whether they belong to the same component. The answer is independent in each component, so we can simply multiply them together.

How to calculate the answer for a two-edge-connected component? First of all, the weight of all nodes must be equal. Then, if there exists an odd cycle (which can be detected with 2-coloring), it should equal $$$0$$$. There are only three different possible answers: $$$0$$$, $$$1$$$, and $$$V$$$.

Thus, one can calculate the answer to the original problem efficiently.

Time Complexity: $$$\mathcal O(n + m)$$$ per test case.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int mod = 998244353;

vector<int> g[MAXN], dcc[MAXN];

int dfn[MAXN], low[MAXN], id;

int s[MAXN], tp, p[MAXN], cnt;

void tarjan(int u, int f = 0) {
	dfn[u] = low[u] = ++id, s[++tp] = u;
	for (int v : g[u]) {
		if (!dfn[v]) tarjan(v, u), low[u] = min(low[u], low[v]);
		else if (v != f) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		cnt++;
		for (int x = 0; x != u; ) {
			x = s[tp--], p[x] = cnt;
			dcc[cnt].emplace_back(x);
		}
	}
}

int col[MAXN];

bool check(int u, int f = 0) {
	if (~col[u]) return col[u] == f; col[u] = f;
	for (int v : g[u]) if (p[u] == p[v] && !check(v, f ^ 1)) return 0;
	return 1;
}

int T, n, m, V, a[MAXN], ans;

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d%d%d", &n, &m, &V), id = cnt = 0, ans = 1;
		for (int i = 1; i <= n; i++) dfn[i] = low[i] = p[i] = 0, col[i] = -1;
		for (int i = 1; i <= n; i++) g[i].clear(), dcc[i].clear();
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1, u, v; i <= m; i++) {
			scanf("%d%d", &u, &v);
			g[u].emplace_back(v), g[v].emplace_back(u);
		}
		for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
		for (int i = 1; i <= cnt; i++) {
			int x = -1;
			for (int u : dcc[i]) {
				if (a[u] < 0) continue;
				if (x < 0) x = a[u];
				else if (x != a[u]) { ans = 0; break; }
			}
			if (!ans) break;
			bool f = check(dcc[i][0]);
			if (f) { if (x < 0) ans = (ll)ans * V % mod; }
			else if (x > 0) ans = 0;
			if (!ans) break;
		}
		printf("%d\n", ans);
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

Try to input $$$10^5$$$ copies of $$$1$$$ in the first query. What can you get then?

After the first query, you can get $$$W\in [L, R]$$$. And $$$2\cdot L\ge R$$$ always holds. Now, can you construct the second query?

In the first query, we will input $$$10^5$$$ copies of $$$1$$$. And the result will be equal to $$$r_1 = \left\lceil\frac{10^5}{W}\right\rceil$$$. By solving the equation $$$\left\lceil\frac{10^5}{x}\right\rceil = r_1$$$, we can get

For example, if:

• $$$r_1 = 1$$$, then $$$W=100\,000$$$;
• $$$r_1 = 2$$$, then $$$W\in [50\,000, 99\,999]$$$;
• $$$r_1 = 3$$$, then $$$W\in [33\,334, 49\,999]$$$;
• ...

For each interval $$$[L, R]$$$ above, $$$2\cdot L \gt R$$$ always holds, which is because $$$\lfloor \frac{n}{2L} \rfloor = \lfloor \frac{\lfloor \frac{n}{L} \rfloor}{2} \rfloor \neq \lfloor \frac{n}{L} \rfloor$$$.

Thus, we can input the following article in the second query:

For each of the underlined group $$$(L, x)$$$:

• If $$$L + x \le W$$$, the two words in this group will be displayed in the same line;
• Otherwise, they will be displayed in different lines.

Note that $$$L + x + L \gt 2\cdot L \gt R \ge W$$$, so for each $$$1\le x \le W - L$$$, the group $$$(L, x)$$$ takes a single line, and for each $$$W - L \lt x \le R - L$$$, the group $$$(L, x)$$$ always take two lines. So the result of the query is $$$r_2 = (W - L) + 2\cdot (R - W)$$$. Hence, we get $$$W = 2\cdot R - L - r_2$$$. And we need to use $$$n = 2\cdot (R - L)\le 10^5$$$ words in this query.

Thus, we solved the problem in at most $$$2$$$ queries, which fits the constraints of the Easy Version.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
//const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;

inline void get(int l, int r) {
	int len = r-l+1;
	cout << "? " << len * 2 << ' ';
	for(int i = 1;i <= len;i++) {
		cout << l << ' ' << i << ' ';
	}
	cout << endl;
	int x;
	cin >> x;
	cout << "! " << len * 2 - x + l << endl;
}

inline void solve_test() {
	int n=1e5;
	cout << "? ";
	cout << n << ' ';
	for(int i = 1;i <= n;i++) cout << "1 ";
	cout << endl;
	int x;
	cin >> x;
	if(x == 1) {
		cout << "! " << n << endl;
		return;
	}
	int l = -1, r = -1;
	for(int i = 1;i <= n;i++) {
		if((n + i - 1) / i == x && l == -1) l = i;
		if((n + i - 1) / i == x) r = i;
	}
	get(l,r);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tt = 1;
    cin >> tt;
    while(tt--) {
		++tc;
        solve_test();
    }
}

Can you do something better than $$$10^5~1~1~\ldots~1$$$ in the first query, so that the interval length will be reduced for the second query?

Change the first query to $$$N$$$ copies of $$$B$$$, where $$$N$$$ and $$$B$$$ are both undetermined constants.

Brute force to find the optimal value of $$$N$$$ and $$$B$$$.

We want to cut down the total length of articles. So here comes a new strategy for the first query: $$$N$$$ copies of $$$B$$$, where $$$N$$$ and $$$B$$$ are both undetermined constants.

Now, the result for the first query is $$$r_1 = \displaystyle\left\lceil \frac{N}{\left \lfloor\frac{W}{B}\right\rfloor} \right\rceil$$$.

If $$$W\in [1, B - 1]$$$, the editor will be unable to display the article, and unfortunately our original strategy for the second query will not work in this case. But we can still use the strategy in the first query! Now we can query $$$B^2$$$ copies of $$$1$$$, and it's easy to show that the results for each $$$W=1,2,\ldots,B - 1$$$ will be distinct.

Otherwise, $$$W\in [B, 10^5]$$$, similar to the easy version, we will get an interval $$$[L, R]$$$, where $$$2\cdot L\ge R$$$ always holds. Then, we can use the same strategy as the second query in the easy version and get a solution with $$$2\cdot(R - L)$$$ queries. To calculate $$$L$$$ and $$$R$$$, you can simply use binary search, or do some math work to get

There is also a fact that the rightmost interval will be cut off by the upper bound of $$$10^5$$$.

We can use brute force to find suitable values for $$$N$$$ and $$$B$$$. In the main correct solution, we choose $$$N = 11\,343$$$ and $$$B = 116$$$, and the maximal interval length is $$$6\,263$$$. Thus, the total length of articles won't exceed $$$11\,343 + \max(2\cdot 6\,263, 116^2) = 24\,799\le 25\,000$$$.

By some further optimization we can reduce $$$116^2$$$ a little to $$$\le 12\, 526$$$, so the total length of articles can be reduced to $$$23\,869$$$, but that's not needed.

#include <bits/stdc++.h>
using namespace std;

const int MAXW = 100'000;
const int MAXSUM = 25'000;
const int B = 116;
const int K = 11343;

int t;

inline int ask(vector<int> v) {
  cout << "? " << v.size();
  for (int i : v) {
    cout << ' ' << i;
  }
  cout << endl;
  int x;
  cin >> x;
  if (x == -1) {
    exit(0);
  }
  return x;
}
inline void answer(int x) { cout << "! " << x << endl; }

int main() {
  cin >> t;
  while (t--) {
    vector<int> v_qry1(K, B);
    int res_qry1 = ask(v_qry1);
    if (res_qry1 == 0) {
      // W < B
      vector<int> v_qry2(B * B, 1);
      int res_qry2 = ask(v_qry2);
      int w = (B * B - 1) / (res_qry2 - 1);
      answer(w);
    } else {
      // W >= B
      int min_w = ((K - 1) / res_qry1 + 1) * B,
          max_w = ((K - 1) / (res_qry1 - 1) + 1) * B - 1;
      max_w = min(max_w, MAXW);
      for (int w = B; w <= MAXW; w++) {
        int h = (K - 1) / (w / B) + 1;
        if (h == res_qry1) {
          assert(min_w <= w);
          assert(w <= max_w);
        } else {
          assert(w < min_w || w > max_w);
        }
      }

      if (min_w == max_w) {
        answer(min_w);
      } else {
        vector<int> v_qry2;
        for (int i = min_w + 2; i <= max_w; i++) {
          v_qry2.push_back(min_w + 1);
          v_qry2.push_back(i - min_w - 1);
        }
        if (v_qry2.empty()) {
          v_qry2.push_back(min_w + 1);
        }
        int res_qry2 = ask(v_qry2);

        if (res_qry2 == 0) {
          answer(min_w);
        } else {
          answer(min_w + 1 + ((int)v_qry2.size() - res_qry2));
        }
      }
    }
  }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

Replace $$$\tt 0$$$ with $$$1$$$ and $$$\tt 1$$$ with $$$-1$$$. Try to find a sufficient and necessary condition of $$$s$$$ almost-palindrome.

Denote the $$$\pm 1$$$-s you get in Hint 1 as array $$$a$$$, and $$$b_i = \sum_{j=1}^n a_j$$$. ($$$s$$$ is almost-palindrome) $$$\Longleftrightarrow$$$ ($$$\min b_i + \max b_i = b_n$$$),

You will need to solve the following subproblem:

You are on an infinite 2D plane, initially at $$$(0, 0)$$$. You can only move up/right by $$$1$$$ unit in one step. Also, you cannot touch the line $$$y=x + l$$$ or $$$y = x+ r$$$ during your move. Count the number of ways to travel to $$$(n, m)$$$.

We can solve the subproblem by a technique called "reflection inclusion-exclusion" in $$$\mathcal{O}\left(\frac{n}{|l - r|}\right)$$$ time complexity. You can view more details in problem E1 part of this blog: https://mirror.codeforces.com/blog/entry/129027

Or here is a detailed explanation in Chinese: https://www.cnblogs.com/Hanghang007/p/18159154

Try to compress sums by processing all $$$\max b_i - \min b_i = k$$$ together.

Read the hints first.

Recall the answer for the subproblem in Hint 3 as $$$f(n, m, l, r)$$$, we have

Suppose $$$\min b_i = l$$$ and $$$\max b_i = r$$$, the number of $$$b$$$-s is the number of ways to travel from $$$(0, 0)$$$ to $$$(n, m)$$$, "exactly" touching $$$y=x+l$$$ and $$$y=x+r$$$, that is,

Now we can compress the sums by processing all $$$\max b_i - \min b_i = k$$$ together. Let's enumerate on $$$k$$$, and note that the upper index of binomials is always $$$\frac{n-(l+r)}{2}+\frac{n+(l+r)}{2}=n$$$, and the lower index moves contiguously with the same $$$k$$$.

Thus, we have solved the problem in $$$\mathcal{O}(n\log n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int MAXN = 1e6 + 10;
const int mod = 998244353;
 
inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); }
 
int inv[MAXN], a[MAXN], s[MAXN];
 
inline 
void init(int n) {
	inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
}
 
int n;
 
inline 
int ask(int l, int r) {
	l = max(l, 0), r = min(r, n);
	return l ? sub(s[r], s[l - 1]) : s[r];
}
 
inline 
int calc(int k, int t) {
	int sum = 0;
	for (int p = 0; (n + k >> 1) - p * (k + 2 - t) >= 0; p++) {
		cadd(sum, ask((n - k >> 1) - p * (k + 2 - t), (n + k >> 1) - t - p * (k + 2 - t)));
	}
	for (int p = 0; (n - k >> 1) - 1 - p * (k + 2 - t) >= 0; p++) {
		csub(sum, (ll)(k + 1 - t) * a[(n - k >> 1) - 1 - p * (k + 2 - t)] % mod);
	}
	for (int p = 1; (n - k >> 1) + p * (k + 2 - t) <= n; p++) {
		cadd(sum, ask((n - k >> 1) + p * (k + 2 - t), (n + k >> 1) - t + p * (k + 2 - t)));
	}
	for (int p = 0; (n + k >> 1) + 1 - t + p * (k + 2 - t) <= n; p++) {
		csub(sum, (ll)(k + 1 - t) * a[(n + k >> 1) + 1 - t + p * (k + 2 - t)] % mod);
	}
	return sum;
}
 
int T, ans;
 
int main() {
	for (scanf("%d", &T), init(1e6 + 1); T--; ) {
		scanf("%d", &n), *a = *s = 1, ans = 0;
		for (int i = 1, x = 1; i <= n; i++) {
			a[i] = (ll)a[i - 1] * inv[i] % mod * (n - i + 1) % mod;
			s[i] = add(s[i - 1], a[i]);
		}
		for (int i = 1, x = 0, y = 0; i <= n; i++) {
			if (n + i & 1) continue;
			cadd(ans, x), cadd(ans, x = calc(i, 0));
			y = calc(i, 1), csub(ans, add(y, y));
		}
		printf("%d\n", ans);
	}
}

List out the coefficients of all $$${n\choose m}$$$.

Try linear sieve.

Read the hints and E1 editorial first. We'll try to speed up in a different way.

Let's consider $$$f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l,r\right)$$$ first. Let $$$k=r-l$$$. For each $$$k=1,2,\ldots,n$$$, we have

$$$\displaystyle\sum_{-k\le l\le 0}f\left(\frac{n-(l+r)}{2},\frac{n+(l+r)}{2},l,r\right)$$$

$$$=\displaystyle\sum_{-k\le l\le 0}\sum_{z\in\mathbb Z} {n\choose (n-(2z+1)\cdot k) / 2-l}-{n\choose (n-(2z-1)\cdot k) / 2}$$$

$$$=\displaystyle\sum_{-k+1\le l\le 0}\sum_{z\in\mathbb Z} {\color{red}{n\choose (n-(2z+1)\cdot k) / 2-l}}-{\color{blue}{n\choose (n-(2z-1)\cdot k) / 2}}$$$

$$$={\color{red}2^{\color{red}n}}-\displaystyle k\cdot { \sum_{z\in\mathbb Z}\color{blue}{n\choose (n-(2z-1)\cdot k) / 2}}$$$

We will consider the coefficient of $$${n\choose m}$$$ in the blue part. Note that $$$(n-(2z-1)\cdot k) / 2 = m\Longleftrightarrow k=(n-2m)/(2z-1)$$$. Define $$$g(n)=\sum_{d\mid n,2\nmid(n/d)} d$$$, then the coefficient of $$${n\choose m}$$$ is $$$g(|n-2m|)$$$.

The other 3 parts are similar.

Summing all, we got the final answer is

And we can use linear sieve to precalculate $$$g(n)$$$. Thus, the whole problem is solved in $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int MAXN = 2e7 + 10;
const int mod = 998244353;
 
inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += mod); }
 
inline 
int qpow(int b, int p) {
	int res = 1;
	for (; p; b = (ll)b * b % mod, p >>= 1) if (p & 1) res = (ll)res * b % mod;
	return res;
}
 
int f[MAXN], g[MAXN], p[MAXN], tot;
 
int fac[MAXN], ifac[MAXN];
 
inline 
void init(int n) {
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!f[i]) p[++tot] = i, f[i] = g[i] = i + (i > 2);
		for (int j = 1; j <= tot; j++) {
			if (i * p[j] > n) break;
			if (i % p[j] == 0) {
				g[i * p[j]] = g[i] * p[j] + (j > 1);
				f[i * p[j]] = f[i] / g[i] * g[i * p[j]];
				break;
			}
			f[i * p[j]] = f[i] * (p[j] + (j > 1));
			g[i * p[j]] = p[j] + (j > 1);
		}
	}
	*fac = 1;
	for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i; i--) ifac[i - 1] = (ll)ifac[i] * i % mod;
}
 
int T, n, ans;
 
int main() {
	for (scanf("%d", &T), init(2e7 + 1); T--; ) {
		scanf("%d", &n), ans = 0;
		for (int i = 0; i <= n; i++) {
			ans = (ans + (ll)ifac[i] * ifac[n - i] % mod * sub(f[abs(n - i * 2 - 1)], f[abs(n - i * 2)])) % mod;
		}
		ans = (ll)ans * fac[n] % mod;
		cadd(ans, ans), (n & 1 ? cadd : csub)(ans, qpow(2, n));
		printf("%d\n", ans);
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

How to compare two $$$f$$$ values? Since this function grows extremely fast, try to compare $$$\ln f$$$, $$$\ln \ln f$$$ and so on.

You only need to compare lexicographical order.

How to quickly compare lexicographical order? Try using hashing.

Use a data structure to maintain the hash value for each point.

Consider performing a topological sort on the tree from the bottom up. Then, when a node needs to be inserted into another tree, its ranking is already determined. A segment tree can be used instead of a balanced tree.

First, define the concept of a $$$\textbf{power tower}$$$. $$$X$$$ is a power tower if and only if one of the following holds:

• $$$X = x$$$.
• $$$X = x^{X_1X_2\cdots X_m}$$$, where $$$m$$$ is a constant independent of $$$x$$$, and $$$X_1, X_2, \cdots, X_m$$$ are all power towers.

Clearly, for power towers $$$X$$$ and $$$Y$$$, $$$X^Y$$$ is also a power tower. Therefore, in this problem, any $$$f_u(x)$$$ is a power tower.

First, consider how to compare two power towers $$$X$$$ and $$$Y$$$. The steps are as follows:

• If $$$X = x$$$ or $$$Y = x$$$, directly return their magnitudes.
• Otherwise, let $$$X = x^{X_1X_2\cdots X_p}$$$, $$$Y = x^{Y_1Y_2\cdots Y_q}$$$, where the quantities in the exponents are power towers.
  • Sort $$$X_1, X_2, \cdots, X_p$$$ and $$$Y_1, Y_2, \cdots, Y_q$$$ in descending order.
  • Compare their lexicographical order. If the lexicographical orders are equal, return that $$$X$$$ and $$$Y$$$ are equal; otherwise, return that the power tower with the larger lexicographical order is greater than the one with the smaller lexicographical order.

This gives a solution that can determine the relative sizes of two power towers in polynomial complexity. However, this is far from sufficient.

To optimize the complexity, when comparing $$$X$$$ and $$$Y$$$, we at least need to know the sorted order of $$$X_1, X_2, \cdots, X_p$$$ and $$$Y_1, Y_2, \cdots, Y_q$$$. This is equivalent to knowing the size relationships among them.

A key property of the tree can be easily observed: Let $$$fa_u$$$ be the father of $$$u$$$ in the tree. Then, it must hold that $$$f_u(x) \prec f_{fa_u}(x)$$$. Consider performing a topological sort on the original tree and using a heap to maintain the current queue. Each time, the smallest node is taken out to update the others. For any node $$$u$$$ in the queue, the corresponding power tower $$$X = f_u(x)$$$ already has known rankings for $$$X_1, X_2, \cdots, X_p$$$. A persistent segment tree can then be used to maintain prefix-sum hashes. When comparing two power towers, binary search can be performed on the segment tree to quickly find the first position where their exponent power towers differ, achieving a fast comparison in $$$\mathcal{O}(\log n)$$$ time per operation.

Time complexity: $$$\mathcal{O}(n\log^2 n)$$$ per test case.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef unsigned long long ull;
 
const int MAXN = 4e5 + 10;
 
ull A = mt19937_64(time(0))();
 
inline ull shift(ull x) {
	return x ^= A, x ^= x << 13, x ^= x >> 7, x ^= x << 11, x ^= A;
}
 
struct node {
	int l, r, num; ull val;
} t[MAXN * 20]; int cnt, rt[MAXN];
 
void add(int &p, int pre, int l, int r, int k, ull x) {
	t[p = ++cnt] = t[pre], t[p].val += x, t[p].num++;
	if (l == r) return ; int mid = l + r >> 1;
	if (k <= mid) add(t[p].l, t[pre].l, l, mid, k, x);
	else add(t[p].r, t[pre].r, mid + 1, r, k, x);
}
 
bool find(int p, int pre, int l, int r) {
	if (l == r) return t[p].num > t[pre].num; int mid = l + r >> 1;
	if (t[t[p].r].val == t[t[pre].r].val) return find(t[p].l, t[pre].l, l, mid);
	else return find(t[p].r, t[pre].r, mid + 1, r);
}
 
int n, l[MAXN], r[MAXN], fa[MAXN], d[MAXN];
 
int rk[MAXN], tot, lst; ull h[MAXN];
 
struct cmp {
	bool operator () (int x, int y) {
		return h[x] == h[y] ? x > y : find(rt[x], rt[y], 1, n);
	}
}; priority_queue<int, vector<int>, cmp> q;
 
 
inline 
void upd(int u) {
	h[u] = h[l[u]] + shift(h[r[u]]);
	add(rt[u], rt[l[u]], 1, n, rk[r[u]], shift(h[r[u]]));
}
 
int T;
 
int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d", &n), cnt = lst = tot = 0;
		for (int i = 1; i <= n; i++) rt[i] = 0; 
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &l[i], &r[i]);
			d[i] = (l[i] && r[i] ? 2 : 0), fa[l[i]] = fa[r[i]] = i;
		}
		for (int i = 1; i <= n; i++) if (!d[i]) h[i] = 1, q.emplace(i);
		for (int u; !q.empty(); ) {
			printf("%d ", u = q.top()), q.pop();
			if (h[u] != h[lst]) tot++; lst = u, rk[u] = tot;
			if (!--d[fa[u]]) upd(fa[u]), q.push(fa[u]);
		}
		puts("");
	}
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

Greedy from small to large.

We can delete the numbers from small to large. Thus, previously removed numbers will not affect future choices (if $$$x \lt y$$$, then $$$x$$$ cannot be a multiple of $$$y$$$). So an integer $$$x$$$ ($$$l\le x\le r$$$) can be removed if and only if $$$k\cdot x\le r$$$, that is, $$$x\le \left\lfloor\frac{r}{k}\right\rfloor$$$. The answer is $$$\max\left(\left\lfloor\frac{r}{k}\right\rfloor-l+1,0\right)$$$.

Time complexity: $$$\mathcal{O}(1)$$$ per test case.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
const int _N = 1e5 + 5;
 
int T;
 
void solve() {
	int l, r, k; cin >> l >> r >> k;
	cout << max(r / k - l + 1, 0) << endl;
	return;
}
 
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}
}

for _ in range(int(input())):
    l, r, k = map(int, input().split())
    print(max(r // k - l + 1, 0))

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

($$$\texttt{01}$$$ or $$$\texttt{10}$$$ exists) $$$\Longleftrightarrow$$$ (both $$$\texttt{0}$$$ and $$$\texttt{1}$$$ exist).

Each time we do an operation, if $$$s$$$ consists only of $$$\texttt{0}$$$ or $$$\texttt{1}$$$, we surely cannot find any valid indices. Otherwise, we can always perform the operation successfully. In the $$$i$$$-th operation, if $$$t_i=\texttt{0}$$$, we actually decrease the number of $$$\texttt{1}$$$-s by $$$1$$$, and vice versa. Thus, we only need to maintain the number of $$$\texttt{0}$$$-s and $$$\texttt{1}$$$-s in $$$s$$$. If any of them falls to $$$0$$$ before the last operation, the answer is NO, otherwise, the answer is YES.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()

using namespace std;
using ll = long long;

const int _N = 1e5 + 5;

void solve() {
	int n; cin >> n;
	string s, t; cin >> s >> t;
	int cnt0 = count(all(s), '0'), cnt1 = n - cnt0;
	for (int i = 0; i < n - 1; i++) {
		if (cnt0 == 0 || cnt1 == 0) {
			cout << "NO" << '\n';
			return;
		}
		if (t[i] == '1') cnt0--;
		else cnt1--;
	}
	cout << "YES" << '\n';
}

int main() {
	int T; cin >> T;
	while (T--) {
		solve();
	}
}

for _ in range(int(input())):
    n = int(input())
    s = input()
    one = s.count("1")
    zero = s.count("0")
    ans = "YES"
    for ti in input():
        if one == 0 or zero == 0:
            ans = "NO"
            break
        one -= 1
        zero -= 1
        if ti == "1":
            one += 1
        else:
            zero += 1
    print(ans)

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

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	vector<int> pre(n + 1);
	int curf = 0;
	for (int i = 1; i <= n; i++) {
		if (curf < a[i]) curf++;
		else if (curf > a[i]) curf--;
		pre[i] = max(pre[i - 1], curf);
	}
	auto check = [&](int k) {
		int curg = k;
		for (int i = n; i >= 1; i--) {
			if (pre[i - 1] >= curg) return true;
			if (a[i] < curg) curg++;
			else curg--;
		}
		return false;
	};
	int L = 0, R = n + 1;
	while (L < R) {
		int mid = (L + R + 1) >> 1;
		if (check(mid)) L = mid;
		else R = mid - 1;
	}
	cout << L << '\n';
	return;
}

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

for _ in range(int(input())):
    n = int(input())
    
    def f(a, x):
        return a + (a < x) - (a > x)
    
    dp = [0, -n, -n]
    for x in map(int, input().split()):
        dp[2] = max(f(dp[1], x), f(dp[2], x))
        dp[1] = max(dp[1], dp[0])
        dp[0] = f(dp[0], x)

    print(max(dp[1], dp[2]))

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

Try to make the graph into a forest first.

($$$deg_i\le 1$$$ for every $$$i$$$) $$$\Longrightarrow$$$ (The graph is a forest).

Let $$$d_i$$$ be the degree of vertex $$$i$$$.

First, we keep doing the following until it is impossible:

• Choose a vertex $$$u$$$ with $$$d_u\ge 2$$$, then find any two vertices $$$v,w$$$ adjacent to $$$u$$$. Perform the operation on $$$(u,v,w)$$$.

Since each operation decreases the number of edges by at least $$$1$$$, at most $$$m$$$ operations will be performed. After these operations, $$$d_i\le 1$$$ holds for every $$$i$$$. Thus, the resulting graph consists only of components with size $$$\le 2$$$.

If there are no edges, the graph is already cool, and we don't need to do any more operations.

Otherwise, let's pick an arbitrary edge $$$(u,v)$$$ as the base of the final tree, and then merge everything else to it.

For a component with size $$$=1$$$ (i.e. it is a single vertex $$$w$$$), perform the operation on $$$(u, v, w)$$$, and set $$$(u, v) \gets (u, w)$$$.

For a component with size $$$=2$$$ (i.e. it is an edge connecting $$$a$$$ and $$$b$$$), perform the operation on $$$(u, a, b)$$$.

It is clear that the graph is transformed into a tree now.

The total number of operations won't exceed $$$n+m\le 2\cdot \max(n,m)$$$.

In the author's solution, we used some data structures to maintain the edges, thus, the time complexity is $$$\mathcal{O}(n+m\log m)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...) (void)0
#endif

using i64 = int64_t;
constexpr bool test = false;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  for (int ti = 0; ti < t; ti += 1) {
    int n, m;
    cin >> n >> m;
    vector<set<int>> adj(n + 1);
    for (int i = 0, u, v; i < m; i += 1) {
      cin >> u >> v;
      adj[u].insert(v);
      adj[v].insert(u);
    }
    vector<tuple<int, int, int>> ans;
    for (int i = 1; i <= n; i += 1) {
      while (adj[i].size() >= 2) {
        int u = *adj[i].begin();
        adj[i].erase(adj[i].begin());
        int v = *adj[i].begin();
        adj[i].erase(adj[i].begin());
        adj[u].erase(i);
        adj[v].erase(i);
        ans.emplace_back(i, u, v);
        if (adj[u].contains(v)) {
          adj[u].erase(v);
          adj[v].erase(u);
        } else {
          adj[u].insert(v);
          adj[v].insert(u);
        }
      }
    }
    vector<int> s;
    vector<pair<int, int>> p;
    for (int i = 1; i <= n; i += 1) {
      if (adj[i].size() == 0) {
        s.push_back(i);
      } else if (*adj[i].begin() > i) {
        p.emplace_back(i, *adj[i].begin());
      }
    }
    if (not p.empty()) {
      auto [x, y] = p.back();
      p.pop_back();
      for (int u : s) {
        ans.emplace_back(x, y, u);
        tie(x, y) = pair(x, u);
      }
      for (auto [u, v] : p) {
        ans.emplace_back(y, u, v);
      }
    }
    println("{}", ans.size());
    for (auto [x, y, z] : ans) println("{} {} {}", x, y, z);
  }
}

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

$$$2$$$ is powerful.

Consider primes.

How did you prove that $$$2$$$ can generate every integer except odd primes? Can you generalize it?

In this problem, we do not take the integer $$$1$$$ into consideration.

Claim 1. $$$2$$$ can generate every integer except odd primes.

Proof. For a certain non-prime $$$x$$$, let $$$\operatorname{mind}(x)$$$ be the minimum divisor of $$$x$$$. Then $$$x-\operatorname{mind}(x)$$$ must be an even number, which is $$$\ge 2$$$. So $$$x-\operatorname{mind}(x)$$$ can be generated by $$$2$$$, and $$$x$$$ can be generated by $$$x-\operatorname{mind}(x)$$$. Thus, $$$2$$$ is a generator of $$$x$$$.

Claim 2. Primes can only be generated by themselves.

According to the above two claims, we can first check if there exist primes in the array $$$a$$$. If not, then $$$2$$$ is a common generator. Otherwise, let the prime be $$$p$$$, the only possible generator should be $$$p$$$ itself. So we only need to check whether $$$p$$$ is a generator of the rest integers.

For an even integer $$$x$$$, it is easy to see that, $$$p$$$ is a generator of $$$x$$$ if and only if $$$x\ge 2\cdot p$$$.

Claim 3. For a prime $$$p$$$ and an odd integer $$$x$$$, $$$p$$$ is a generator of $$$x$$$ if and only if $$$x - \operatorname{mind}(x)\ge 2\cdot p$$$.

Proof. First, $$$x-\operatorname{mind}(x)$$$ is the largest integer other than $$$x$$$ itself that can generate $$$x$$$. Moreover, only even numbers $$$\ge 2\cdot p$$$ can be generated by $$$p$$$ ($$$x-\operatorname{mind}(x)$$$ is even). That ends the proof.

Thus, we have found a good way to check if a certain number can be generated from $$$p$$$. We can use the linear sieve to pre-calculate all the $$$\operatorname{mind}(i)$$$-s.

Time complexity: $$$\mathcal{O}(\sum n+V)$$$, where $$$V=\max a_i$$$.

Some other solutions with worse time complexity can also pass, such as $$$\mathcal{O}(V\log V)$$$ and $$$\mathcal{O}(t\sqrt{V})$$$.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 4e5 + 5;

int vis[_N], pr[_N], cnt = 0;

void init(int n) {
	vis[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			pr[++cnt] = i;
		}
		for (int j = 1; j <= cnt && i * pr[j] <= n; j++) {
			vis[i * pr[j]] = pr[j];
			if (i % pr[j] == 0) continue;
		}
	}
}

int T;

void solve() {
	int n; cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	int p = 0;
	for (int i = 1; i <= n; i++) {
		if (!vis[a[i]]) p = a[i];
	}
	if (!p) {
		cout << 2 << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] == p) continue;
		if (vis[a[i]] == 0) {
			cout << -1 << '\n';
			return;
		}
		if (a[i] & 1) {
			if (a[i] - vis[a[i]] < 2 * p) {
				cout << -1 << '\n';
				return;
			}
		} else {
			if (a[i] < 2 * p) {
				cout << -1 << '\n';
				return;
			}
		}
	}
	cout << p << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	init(400000);
	cin >> T;
	while (T--) {
		solve();
	}
}

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

If there are both consecutive $$$\texttt{R}$$$-s and $$$\texttt{B}$$$-s, does the condition hold for all $$$(i,j)$$$? Why?

Suppose that there are only consecutive $$$\texttt{R}$$$-s, check the parity of the number of $$$\texttt{R}$$$-s in each consecutive segment of $$$\texttt{R}$$$-s.

If for each consecutive segment of $$$\texttt{R}$$$-s, the parity of the number of $$$\texttt{R}$$$-s is odd, does the condition hold for all $$$(i,j)$$$? Why?

If for at least two of the consecutive segments of $$$\texttt{R}$$$-s, the parity of the number of $$$\texttt{R}$$$-s is even, does the condition hold for all $$$(i,j)$$$? Why?

Is this the necessary and sufficient condition? Why?

Don't forget some trivial cases like $$$\texttt{RRR...RB}$$$ and $$$\texttt{RRR...R}$$$.

For each $$$k \gt n$$$ or $$$k\leq0$$$, let $$$c_k$$$ be $$$c_{k\bmod n}$$$.

Lemma 1: If there are both consecutive $$$\texttt{R}$$$-s and $$$\texttt{B}$$$-s, the answer is NO.

Proof 1: Suppose that $$$c_{i-1}=c_i=\texttt{R}$$$ and $$$c_{j-1}=c_j=\texttt{B}$$$, it's obvious that there doesn't exist a palindrome route between $$$i$$$ and $$$j$$$.

Imagine there are two persons on vertex $$$i$$$ and $$$j$$$. They want to meet each other (they are on the same vertex or adjacent vertex) and can only travel through an edge of the same color.

Lemma 2: Suppose that there are only consecutive $$$\texttt{R}$$$-s, if for each consecutive segment of $$$\texttt{R}$$$-s, the parity of the number of $$$\texttt{R}$$$-s is odd, the answer is NO.

Proof 2: Suppose that $$$c_i=c_j=\texttt{B}$$$, $$$i\not\equiv j\pmod n$$$ and $$$c_{i+1}=c_{i+2}=\dots=c_{j-1}=\texttt{R}$$$. The two persons on $$$i$$$ and $$$j$$$ have to "cross" $$$\texttt{B}$$$ simultaneously. As for each consecutive segment of $$$\texttt{R}$$$-s, the parity of the number of $$$\texttt{R}$$$-s is odd, they can only get to the same side of their current consecutive segment of $$$\texttt{R}$$$-s. After "crossing" $$$\texttt{B}$$$, they will still be on different consecutive segments of $$$\texttt{R}$$$-s separated by exactly one $$$\texttt{B}$$$ and can only get to the same side. Thus, they will never meet.

Lemma 3: Suppose that there are only consecutive $$$\texttt{R}$$$-s, if, for at least two of the consecutive segments of $$$\texttt{R}$$$-s, the parity of the number of $$$\texttt{R}$$$-s is even, the answer is NO.

Proof 3: Suppose that $$$c_i=c_j=\texttt{B}$$$, $$$i\not\equiv j \pmod n$$$ and vertex $$$i$$$ and $$$j$$$ are both in a consecutive segment of $$$\texttt{R}$$$-s with even number of $$$\texttt{R}$$$-s. Let the starting point of two persons be $$$i$$$ and $$$j-1$$$ and they won't be able to "cross" and $$$\texttt{B}$$$. Thus, they will never meet.

The only case left is that there is exactly one consecutive segment of $$$\texttt{R}$$$-s with an even number of $$$\texttt{R}$$$-s.

Lemma 4: Suppose that there are only consecutive $$$\texttt{R}$$$-s, if, for exactly one of the consecutive segments of $$$\texttt{R}$$$-s, the parity of the number of $$$\texttt{R}$$$-s is even, the answer is YES.

Proof 4: Let the starting point of the two persons be $$$i,j$$$. Consider the following cases:

Case 1: If vertex $$$i$$$ and $$$j$$$ are in the same consecutive segment of $$$\texttt{R}$$$-s, the two persons can meet each other by traveling through the $$$\texttt{R}$$$-s between them.

Case 2: If vertex $$$i$$$ and $$$j$$$ are in the different consecutive segment of $$$\texttt{R}$$$-s and there are odd numbers of $$$\texttt{R}$$$-s in both segments, the two person may cross $$$\texttt{B}$$$-s in the way talked about in Proof 2. However, when one of them reaches a consecutive segment with an even number of $$$\texttt{R}$$$-s, the only thing they can do is let the one in an even segment cross the whole segment and "cross" the next $$$\texttt{B}$$$ in the front, while letting the other one traveling back and forth and "cross" the $$$\texttt{B}$$$ he just "crossed". Thus, unlike the situation in Proof 2, we successfully changed the side they can both get to and thus they will be able to meet each other as they are traveling toward each other and there are only odd segments between them.

Case 3: If vertex $$$i$$$ and $$$j$$$ are in the different consecutive segment of $$$\texttt{R}$$$-s and there are an odd number of $$$\texttt{R}$$$-s in exactly one of the segments, we can let both of them be in one side of there segments and change the situation to the one we've discussed about in Case 2 (when one of them reached a consecutive segment with even number of $$$\texttt{R}$$$-s).

As a result, the answer is YES if:

• At least $$$n-1$$$ of $$$c_1,c_2,\dots,c_n$$$ are the same (Hint 6), or
• Suppose that there are only consecutive $$$\texttt{R}$$$-s, there's exactly one of the consecutive segments of $$$\texttt{R}$$$-s such that the parity of the number of $$$\texttt{R}$$$-s is even.

And we can judge them in $$$\mathcal{O}(n)$$$ time complexity.

#include <bits/stdc++.h>
using namespace std;
void solve(){
	int n; cin>>n;
	string s; cin>>s;
	int visr=0,visb=0,ok=0; 
	for(int i=0;i<n;i++){
		if(s[i]==s[(i+1)%n]){
			if(s[i]=='R') visr=1;
			else visb=1;
			ok++;
		}
	}
	if(visr&visb){
		cout<<"NO\n";
		return ;
	}
	if(ok==n){
		cout<<"YES\n";
		return ;
	}
	if(visb) for(int i=0;i<n;i++) s[i]='R'+'B'-s[i];
	int st=0;
	for(int i=0;i<n;i++) if(s[i]=='B') st=(i+1)%n;
	vector<int> vc;
	int ntot=0,cnt=0;
	for(int i=0,j=st;i<n;i++,j=(j+1)%n){
		if(s[j]=='B') vc.push_back(ntot),cnt+=(ntot&1)^1,ntot=0;
		else ntot++;
	}
	if(vc.size()==1||cnt==1){
		cout<<"YES\n";
		return ;
	}
	cout<<"NO\n";
	return ;
}
signed main(){
	int t; cin>>t;
	while(t--) solve();
	return 0;
}

Count the number of strings of length $$$n$$$ satisfying the condition.

Solve the problem for $$$c_i\in\{\texttt{A},\texttt{B},\dots,\texttt{Z}\}$$$, and solve the counting version.

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

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = double;

const int _N = 4105;
const ld inf = 1e15;

int T;

struct fenwick {
	ll c[_N]; int N;
	int lowbit(int x) { return x & (-x); }
	void init(int n) {
		N = n;
		for (int i = 1; i <= N; i++) c[i] = -1e18;
	}
	void update(int x, ll v) {
		// assert(x != 0);
		while (x < N) {
			c[x] = max(c[x], v);
			x += lowbit(x);
		}
	}
	ll getmx(int x) {
		// assert(x != 0);
		ll res = -1e18;
		while (x > 0) {
			res = max(res, c[x]);
			x -= lowbit(x);
		}
		return res;
	}
} pre[4105], suf[4105];

void solve() {
	int n, o, m, k; cin >> n >> o >> m;
	k = 0;
	vector<ll> a(n + 3), c(n + 3), d(n + 3), L(n + 3), R(n + 3), L2(n + 3), R2(n + 3);
	for (int i = 1; i <= n; i++) cin >> c[i];
	for (int i = 1; i <= o; i++) {
		char op; int x; cin >> op >> x;
		if (op == 'L') L[x]++;
		else R[x]++;
	}
	vector<int> tL(n + 3), tR(n + 3);
	for (int i = 1; i <= n; i++) tR[i] = tR[i - 1] + R[i];
	for (int i = n; i >= 1; i--) tL[i] = tL[i + 1] + L[i];
	int q = 0, curL = 0, curR = 0;
	for (int i = 1; i <= n; i++) {
		a[i] = tL[i] + tR[i];
		if (a[i] <= m + k) {
		    if (a[i] == a[i - 1] && L[i] == 0 && R[i] == 0) {
		        if (q == 0) q++;
		        d[q] += c[i];
		        continue;
		    }
			q++;
			L2[q] += L[i];
			R2[q] += R[i] + curR;
			L2[q - 1] += curL;
			d[q] += c[i];
			curL = curR = 0;
		} else {
			curL += L[i];
			curR += R[i];
		}
	}
	L2[0] = 0; L2[q] += curL;
	for (int i = 1; i <= q; i++) L2[i] += L2[i - 1], R2[i] += R2[i - 1];
    m += k;
    vector<ll> dp(2 * m + 2, -1e18);
	for (int i = 0; i <= 2 * m; i++) {
		pre[i].init(2 * m + 2);
		suf[i].init(2 * m + 2);
	}
	vector<ll> ans(m + 1);
	for (int i = 1; i <= q; i++) {
        dp.resize(2 * m + 2, -1e18);
		dp[L2[i - 1]] = d[i];
		for (int s = 0; s <= m; s++) {
			ll res1 = pre[s - L2[i - 1] + m].getmx(R2[i] - L2[i - 1] + m + 1);
			ll res2 = suf[s - R2[i] + m].getmx(m + 1 - R2[i] + L2[i - 1]);
			dp[s] = max({ dp[s], res1 + d[i], res2 + d[i] });
			if (L2[q] + R2[i] - s >= 0 && L2[q] + R2[i] - s <= m) ans[L2[q] + R2[i] - s] = max(ans[L2[q] + R2[i] - s], dp[s]);
		}
		for (int s = 0; s <= m; s++) {
			if (dp[s] <= -1e12) continue;
			pre[s - L2[i - 1] + m].update(R2[i] - L2[i - 1] + m + 1, dp[s]);
			suf[s - R2[i] + m].update(m + 1 - R2[i] + L2[i - 1], dp[s]);
		}
	}
	for (int i = 1; i <= m; i++) {
		ans[i] = max(ans[i - 1], ans[i]);
		cout << ans[i] << " \n"[i == m];
	}
	return;
}

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7, N = 5005;

void solve() {
    int n, m, V;
    cin >> n >> m >> V;
    vector <int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    vector <int> pre(n + 1);
    for (int i = 0; i < m; ++i) {
        char x; int v; cin >> x >> v, --v;
        if (x == 'L') {
            pre[0]++, pre[v + 1]--;
        } else {
            pre[v]++;
        }
    }
    for (int i = 0; i < n; ++i) {
        pre[i + 1] += pre[i];
    }
    vector <pair <ll, int>> vec;
    for (int i = 0, j = 0; i < n; i = j) {
        ll tot = 0;
        while (j < n && pre[i] == pre[j]) {
            tot += c[j], j++;
        }
        if (pre[i] <= V) {
            vec.emplace_back(tot, pre[i]);
        }
    }

    vector bit(V + 5, vector <ll>(V + 5, -1ll << 60));
    auto upd = [&](int x, int y, ll v) {
        for (int i = x + 1; i < V + 5; i += i & (-i)) {
            for (int j = y + 1; j < V + 5; j += j & (-j)) {
                bit[i][j] = max(bit[i][j], v);
            }
        }
    };
    auto query = [&](int x, int y) {
        ll ans = -1ll << 60;
        for (int i = x + 1; i > 0; i -= i & (-i)) {
            for (int j = y + 1; j > 0; j -= j & (-j)) {
                ans = max(ans, bit[i][j]);
            }
        }
        return ans;
    };

    upd(0, 0, 0);
    vector <ll> tmp(V + 1);
    for (auto [val, diff] : vec) {
        for (int i = 0; i + diff <= V; ++i) {
            tmp[i] = query(i, i + diff);
        }
        for (int i = 0; i + diff <= V; ++i) {
            upd(i, i + diff, tmp[i] + val);
        }
    }

    for (int i = 1; i <= V; ++i) {
        cout << query(i, i) << " \n"[i == V];
    }
}

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

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

Solve the problem in $$$\mathcal{O}(V^2)$$$.

It's hard to calculate the expected number. Try to change it to the probability.

Consider a $$$\mathcal{O}(3^n)$$$ dp first.

Use inclusion and exclusion.

Write out the transformation. Try to optimize it.

Let $$$dp_S$$$ be the probability such that exactly the points in $$$S$$$ have the message.

The answer is $$$\sum dp_S\cdot tr_S$$$, where $$$tr_S$$$ is the expected number of days before at least one vertex out of $$$S$$$ to have the message (counting from the day that exactly the points in $$$S$$$ have the message).

For transformation, enumerate $$$S,T$$$ such that $$$S\cap T=\varnothing$$$. Transfer $$$dp_S$$$ to $$$dp_{S\cup T}$$$. It's easy to precalculate the coefficient, and the time complexity differs from $$$\mathcal{O}(3^n)$$$, $$$\mathcal{O}(n\cdot 3^n)$$$ to $$$\mathcal{O}(n^2\cdot 3^n)$$$, according to the implementation.

The transformation is hard to optimize. Enumerate $$$T$$$ and calculate the probability such that vertices in $$$S$$$ is only connected with vertices in $$$T$$$, which means that the real status $$$R$$$ satisfies $$$S\subseteq R\subseteq (S\cup T)$$$. Use inclusion and exclusion to calculate the real probability.

List out the coefficient:

(Note that $$$w_e$$$ denotes the probability of the appearance of the edge $$$e$$$)

We can express it as $$$\mathrm{Const}\cdot f_{S\cup T}\cdot g_S\cdot h_T$$$. Use a subset convolution to optimize it. The total time complexity is $$$\mathcal{O}(2^n\cdot n^2)$$$.

It's easy to see that all $$$dp_S\neq0$$$ satisfies $$$1\in S$$$, so the time complexity can be $$$\mathcal{O}(2^{n-1}\cdot n^2)$$$ if well implemented.

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=(1<<21),mod=998244353;
const int Lim=8e18;
inline void add(signed &i,int j){
	i+=j;
	if(i>=mod) i-=mod;
}
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return ans;
}
int dp[N],f[N],g[N],h[N];
int s1[N],s2[N];
signed pre[22][N/2],t[22][N/2],pdp[N][22];
int p[N],q[N],totp,totq;
signed main(){
	int n,m; cin>>n>>m;
	int totprod=1;
	for(int i=0;i<(1<<n);i++) s1[i]=s2[i]=1;
	for(int i=1;i<=m;i++){
		int u,v,p,q; cin>>u>>v>>p>>q;
		int w=p*qp(q,mod-2)%mod;
		(s1[(1<<(u-1))+(1<<(v-1))]*=(mod+1-w))%=mod;
		(s2[(1<<(u-1))+(1<<(v-1))]*=qp(mod+1-w,mod-2))%=mod;
		(totprod*=(mod+1-w))%=mod;
	}
	for(int j=1;j<=n;j++) for(int i=0;i<(1<<n);i++) if((i>>(j-1))&1) (s1[i]*=s1[i^(1<<(j-1))])%=mod,(s2[i]*=s2[i^(1<<(j-1))])%=mod;
	for(int i=0;i<(1<<n);i++) f[i]=s2[i],g[i]=totprod*s2[((1<<n)-1)^i]%mod*qp(mod+1-totprod*s2[i]%mod*s2[((1<<n)-1)^i]%mod,mod-2)%mod,h[i]=s1[i];
	for(int i=1;i<(1<<n);i++) pre[__builtin_popcount(i)][i>>1]=h[i];
	dp[1]=1;
	for(int j=1;j<=n;j++){
		if(!((1>>(j-1))&1)) add(pdp[1|(1<<(j-1))][j],mod-(dp[1]*g[1]%mod*f[1]%mod));
	}
	t[0][0]=dp[1]*g[1]%mod;
	for(int k=1;k<=n;k++) for(int j=1;j<n;j++) for(int i=0;i<(1<<(n-1));i++) if((i>>(j-1))&1) add(pre[k][i],pre[k][i^(1<<(j-1))]);
	for(int j=1;j<n;j++) for(int i=0;i<(1<<(n-1));i++) if((i>>(j-1))&1) add(t[0][i],t[0][i^(1<<(j-1))]);
	for(int k=1;k<n;k++){
		totp=totq=0;
		for(int i=0;i<(1<<(n-1));i++) if(__builtin_popcount(i)<=k) p[++totp]=i; else q[++totq]=i;
		for(int l=1,i=p[l];l<=totp;l++,i=p[l]) for(int j=0;j<k;j++) add(t[k][i],1ll*t[j][i]*pre[k-j][i]%mod);
		for(int i=0;i<(1<<(n-1));i++) t[k][i]%=mod;
		for(int j=1;j<n;j++) for(int l=1,i=p[l];l<=totp;l++,i=p[l]) if((i>>(j-1))&1) add(t[k][i],mod-t[k][i^(1<<(j-1))]);
		for(int i=0;i<(1<<(n-1));i++){
			if(__builtin_popcount(i)==k){
				add(pdp[(i<<1)|1][0],t[k][i]*f[(i<<1)|1]%mod);
				int pre=0;
				for(int j=1;j<=n;j++){
					(pre+=pdp[(i<<1)|1][j-1])%=mod;
					if(!((((i<<1)|1)>>(j-1))&1)) add(pdp[(i<<1)|1|(1<<(j-1))][j],mod-pre);
				}
				(pre+=pdp[(i<<1)|1][n])%=mod;
				dp[(i<<1)|1]=pre;
				for(int j=1;j<=n;j++){
					if(!((((i<<1)|1)>>(j-1))&1)) add(pdp[(i<<1)|1|(1<<(j-1))][j],mod-(dp[(i<<1)|1]*g[(i<<1)|1]%mod*f[(i<<1)|1]%mod));
				}
				t[k][i]=pre*g[(i<<1)|1]%mod;
			}
			else t[k][i]=0;
		}
		for(int j=1;j<n;j++) for(int l=1,i=q[l];l<=totq;l++,i=q[l]) if((i>>(j-1))&1) add(t[k][i],t[k][i^(1<<(j-1))]);
	}
	int ans=0;
	for(int i=1;i<(1<<n)-1;i+=2) (ans+=dp[i]*qp(mod+1-totprod*s2[i]%mod*s2[((1<<n)-1)^i]%mod,mod-2)%mod)%=mod;
	cout<<ans;
	return 0;
}

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

The intended solution has nothing to do with dynamic programming.

This is the key observation of the problem. Suppose we have an array $$$b$$$ and a function $$$f(x)=\sum (b_i-x)^2$$$, then the minimum value of $$$f(x)$$$ is the variance of $$$b$$$.

Using the observation mentioned in Hint 2, we can reduce the problem to minimizing $$$\sum(a_i-x)^2$$$ for a given $$$x$$$. There are only $$$\mathcal{O}(n\cdot m)$$$ possible $$$x$$$-s.

The rest of the problem is somehow easy. Try flows, or just find a greedy algorithm!

If you are trying flows: the quadratic function is always convex.

Key Observation. Suppose we have an array $$$b$$$ and a function $$$f(x)=\sum (b_i-x)^2$$$, then the minimum value of $$$f(x)$$$ is the variance of $$$b$$$.

Proof. This is a quadratic function of $$$x$$$, and the its symmetry axis is $$$x=\frac{1}{n}\sum b_i$$$. So the minimum value is $$$f\left(\frac{1}{n}\sum b_i\right)$$$. That is exactly the definition of variance.

Thus, we can enumerate all possible $$$x$$$-s, and find the minimum $$$\sum (a_i-x)^2$$$ after the operations, then take the minimum across them. That will give the correct answer to the original problem. Note that there are only $$$\mathcal{O}(n\cdot m)$$$ possible $$$x$$$-s.

More formally, let $$$k_{x,c}$$$ be the minimum value of $$$\sum (a_i-x)^2$$$ after exactly $$$c$$$ operations. Then $$$\mathrm{ans}_i=\displaystyle\min_{\text{any possible }x} k_{x,i}$$$.

So we only need to solve the following (reduced) problem:

• Given a (maybe non-integer) number $$$x$$$. For each $$$1\le i\le m$$$, find the minimum value of $$$\sum (a_i-x)^2$$$ after exactly $$$i$$$ operations.

To solve this, we can use the MCMF model:

• Set a source node $$$s$$$ and a target node $$$t$$$.
• For each $$$1\le i\le n$$$, add an edge from $$$s$$$ to $$$i$$$ with cost $$$0$$$.
• For each $$$1\le i\le n$$$, add an edge from $$$i$$$ to $$$t$$$ with cost $$$0$$$.
• For each $$$1\le i \lt n$$$, add an edge from $$$i$$$ to $$$i+1$$$ with cost being a function $$$\mathrm{cost}(f)=(a_i+f-x)^2-(a_i-x)^2$$$, where $$$f$$$ is the flow on this edge.
• Note that the $$$\mathrm{cost}$$$ function is convex, so this model is correct, as you can split an edge into some edges with cost of $$$\mathrm{cost}(1)$$$, $$$\mathrm{cost}(2)-\mathrm{cost}(1)$$$, $$$\mathrm{cost}(3)-\mathrm{cost}(2)$$$, and so on.

Take a look at the model again. We don't need to run MCMF. We can see that it is just a process of regret greedy. So you only need to find the LIS (Largest Interval Sum :) ) for each operation.

Thus, we solved the reduced problem in $$$\mathcal{O(n\cdot m)}$$$.

Overall time complexity: $$$\mathcal{O}((n\cdot m)^2)$$$ per test case.

Reminder: don't forget to use __int128 if you didn't handle the numbers carefully!

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	ll n, m, k; cin >> n >> m >> k;
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	vector<ll> kans(m + 1, LLONG_MAX);
	vector<__int128> f(n + 1), g(n + 1), v(n + 1);
	vector<int> vis(n + 1), L(n + 1), L2(n + 1);
	ll sum = 0;
	for (int i = 1; i <= n; i++) sum += a[i];
	__int128 pans = 0;
	for (int i = 1; i <= n; i++) pans += n * a[i] * a[i];
	auto work = [&](ll s) {
		__int128 ans = pans;
		ans += s * s - 2ll * sum * s;
		f.assign(n + 1, LLONG_MAX);
		g.assign(n + 1, LLONG_MAX);
		for (int i = 1; i <= n; i++) {
			v[i] = n * (2 * a[i] * k + k * k) - 2ll * s * k;
			vis[i] = 0;
		}
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				L[j] = L2[j] = j;
				if (f[j - 1] < 0) f[j] = f[j - 1] + v[j], L[j] = L[j - 1];
				else f[j] = v[j];
				if (!vis[j]) {
					g[j] = LLONG_MAX;
					continue;
				}
				if (g[j - 1] < 0) g[j] = g[j - 1] + 2ll * n * k * k - v[j], L2[j] = L2[j - 1];
				else g[j] = 2ll * n * k * k - v[j];
			}
			__int128 min_sum = LLONG_MAX;
			int l = 1, r = n, type = 0;
			for (int j = 1; j <= n; j++) {
				if (f[j] < min_sum) {
					min_sum = f[j], r = j, l = L[j];
				}
			}
			for (int j = 1; j <= n; j++) {
				if (g[j] < min_sum) {
					min_sum = g[j], r = j, l = L2[j];
					type = 1;
				}
			}
			ans += min_sum;
			if (type == 0) {
				for (int j = l; j <= r; j++) vis[j]++, v[j] += 2 * n * k * k;
			} else {
				for (int j = l; j <= r; j++) vis[j]--, v[j] -= 2 * n * k * k;
			}
			kans[i] = min((__int128)kans[i], ans);
		}
	};
	
	for (ll x = sum; x <= sum + n * m * k; x += k) {
		work(x);
	}
	for (int i = 1; i <= m; i++) cout << kans[i] << " \n"[i == m];
	return;
}

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

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

In Year 2023, 74 had coordinated $$$10$$$ rounds in total. Here's something about them:

• Good Bye 2023. This round. I don't want to say anything more. Votes of the announcement: $$$-3405$$$. (up to 2023/12/31)

• Codeforces Round 908 (Div. 1, Div. 2). No fatal problems occurred in the round, but it feels like Div1A=B=C=D for me :( And actually the performance people who solved problems range from CM to GM, so I would say that this round is of low discrimination. Votes of the announcement: $$$+175$$$.

• Codeforces Round 907 (Div. 2). Also, no fatal problems occurred in the round, but problem F is way too simple. Difficulty disorder usually happens in 74 rounds. Votes of the announcement: $$$+232$$$.

• CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!). Good contest imo, I enjoyed E very much. Qualities of the problems are above average. Votes of the announcement: $$$+394$$$.

• Codeforces Round 880 (Div. 1; Div. 2). I didn't participate in this round, and a *2500 occurred for position Div1B/Div2D. Yet another difficulty disorder. Votes of the announcement: $$$-1467$$$.

• Codeforces Round #873 (Div. 1 & 2). I didn't participate in this round, and it seems a good round. I saw problem Div1B/Div2D before the contest (guess why) and found it really cool. Votes of the announcement: $$$+439$$$.

• CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!). Great round! I enjoyed the problemset very much. Kudos to the authors! Votes of the announcement: $$$+687$$$.

• Nebius Welcome Round (Div. 1 + Div. 2, rated, t-shirts!). Good round. And a fact is that this round is coordinated by both 74 and KAN. Votes of the announcement: $$$+720$$$.

• TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!). A just-so-so round. Problem E<C imo. According to feecle6418, this round also has a known problem, but fortunately it caused little influence. Votes of the announcement: $$$+209$$$.

• Codeforces Round #846 (Div. 2). The NP-hard round. I'm really curious that why none of the authors and testers, and of course, the coordinator, did not find the error in the intended solution. Votes of the announcement: $$$-628$$$.

Out of these $$$10$$$ rounds, $$$4$$$ rounds are generally considered as good rounds, $$$3$$$ rounds have negative votes in announcement, $$$2$$$ rounds have serious problem disorder, and the average votes of these rounds is $$$-264.4$$$. In 2023, there are $$$6$$$ rounds getting negative votes in all (I didn't count educational rounds.), and 74 rounds take up half of them. Some authors said that 74 is the kind of coordinator who goes his own way. All in all, 74 should do improve his ability before coordinating rounds any more.

Indeed at most $$$\bf 4$$$ operations will be used.

If $$$r-l+1$$$ is even, and you do the operation on $$$[l,r]$$$ twice, then the subarray $$$a[l;r]$$$ will all become $$$0$$$.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	if (n & 1) {
		cout << "4" << '\n';
		cout << "1 " << n - 1 << '\n';
		cout << "1 " << n - 1 << '\n';
		cout << n - 1 << ' ' << n << '\n';
		cout << n - 1 << ' ' << n << '\n';
	} else {
		cout << "2" << '\n';
		cout << "1 " << n << '\n';
		cout << "1 " << n << '\n';
	}
	return;
}

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

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

What will happen if there are no major cities?

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n, k, s, t; cin >> n >> k >> s >> t;
	vector<int> x(n + 1), y(n + 1);
	for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	ll ans = llabs(x[s] - x[t]) + llabs(y[s] - y[t]);
	ll mins = LLONG_MAX / 2, mint = LLONG_MAX / 2;
	for (int i = 1; i <= k; i++) {
		mins = min(mins, llabs(x[s] - x[i]) + llabs(y[s] - y[i]));
		mint = min(mint, llabs(x[t] - x[i]) + llabs(y[t] - y[i]));
	}
	ans = min(ans, mins + mint);
	cout << ans << '\n';
	return;
}

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

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

What is the upper bound of $$$s$$$ according to $$$n$$$ and $$$m$$$? Can you construct such a matrix that reaches the upper bound?

If not, can you construct a matrix which maximizes $$$\sum_{i=1}^m v_i$$$? This is of some help to get the solution.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n, m;
	cin >> n >> m;
	if (m == 1) cout << 0 << '\n';
	else if (n > m - 1) cout << m << '\n';
	else cout << n + 1 << '\n';
	for (int i = 0; i < min(m - 1, n); i++) {
		for (int j = 0; j < m; j++) {
			cout << (j + i) % m << ' ';
		}
		cout << '\n';
	}
	if (n > m - 1) {
		for (int i = m - 1; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << j << ' ';
			}
			cout << '\n';
		}
	}
	return;
}

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

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

You can calculate the number of candies of each person after the swap easily. Denote the number as $$$s$$$.

Since a person gives candies to and receives candies from exactly one person, assume he gives away $$$2^x$$$ candies and receives $$$2^y$$$ candies, then we have $$$a_i - 2^x + 2^y = s$$$. If $$$a_i \ne s$$$, at most how many pairs $$$(x,y)$$$ can satisfy this equation?

Do the two restrictions in the statement,

Note that one cannot give more candies than currently he has (he might receive candies from someone else before) and he cannot give candies to himself, either.

really make any difference to the answer?

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll sum = 0;
	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if (sum % n) return cout << "No" << '\n', void();
	sum /= n;
	vector<int> bit(31, 0);
	auto lowbit = [](int x) {
	    return x & (-x);
	};
	for (int i = 0; i < n; i++) {
		if (a[i] == sum) continue;
		int d = abs(a[i] - sum);
		int p = lowbit(d);
		int e = d + p;
		if (__builtin_popcount(e) == 1) {
		    if (a[i] > sum) bit[__lg(e)]++, bit[__lg(p)]--;
		    else bit[__lg(e)]--, bit[__lg(p)]++;
		} else {
		    cout << "No" << '\n';
		    return;
		}
	}
	for (int i = 0; i < 31; i++) {
		if (bit[i]) {
			cout << "No" << '\n';
			return;
		}
	}
	cout << "Yes" << '\n';
	return;
}

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

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

For whom may not give or receive candies?

When $$$|a_i-s|$$$ is a power of $$$2$$$, how many ways can the person gives/receives candies at most?

Try to determine some people's way to give/receive candies first, then others.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int _N = 1e5 + 5;

int T;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll sum = 0;
	for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
	if (sum % n) return cout << "No" << '\n', void();
	sum /= n;
	vector<int> bit(31, 0), pow1(31, 0), pow2(31, 0);
	for (int i = 0; i < n; i++) {
		int flag = 0;
		if (a[i] == sum) continue;
		for (int j = 0; j < 31; j++) {
			if (a[i] + (1 << j) == sum) {
				pow1[j]++;
				flag = 1;
				continue;
			}
			if (a[i] - (1 << j) == sum) {
				pow2[j]++;
				flag = 1;
				continue;
			}
		}
		if (flag) continue;
		flag = 0;
		for (int j = 0; j < 31; j++) {
			for (int k = 0; k < 31; k++) {
			    if (a[i] + (1 << j) - (1 << k) == sum) {
			        flag = 1;
			        bit[j]++;
			        bit[k]--;
			    }
			}
		}
		if (!flag) {
			cout << "No" << '\n';
			return;
		}
	}
	for (int i = 30; i >= 0; i--) {
		bit[i] += (pow1[i] - pow2[i]);
		if (i == 0) break;
		if (bit[i] < 0) {
			pow1[i - 1] -= -bit[i];
			bit[i - 1] -= -bit[i];
			if (pow1[i - 1] < 0) {
				cout << "No" << '\n';
				return;
			}
		} else {
			pow2[i - 1] -= bit[i];
			bit[i - 1] += bit[i];
			if (pow2[i - 1] < 0) {
				cout << "No" << '\n';
				return;
			}
		}
	}
	if (bit[0] == 0) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	return;
}

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

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

For any simple path length $$$t$$$, what's the sum of the maximum value of cities in all assignments? For the cities out of the path, their value doesn't matter.

Consider an easy dp to calculate the number of paths with different lengths.

How many different subtrees are there in this tree?

What's the maximum length of the paths?

Try to optimize the dp with the conclusion you get in Hint 3 and Hint 4.

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
#pragma GCC optimize("Ofast")

ll tot[505],n,m,dp[125][125],dp2[125],g[125][125],g2[125],f[125],pw[100005][125];
const ll mod=998244353;

inline ll dep( ll root) {
	if (root>n)return 0;
	return dep(root*2)+1;
}

inline ll dep2( ll root) {
	if (root>n)return 0;
	return dep2(root*2+1)+1;
}

inline bool full( ll root) {
	return dep(root)==dep2(root);
}

void dfs( ll root) {
	if (root*2>n) {
		g2[0]=dp2[0]=1;
		return;
	}
	if (root*2==n) {
		g2[0]=2,g2[1]=1;
		dp2[0]=1,dp2[1]=1;
		return;
	}
	ll d=0;
	if (full(root*2)) {

		d=dep(root*2);
		dfs(root*2+1);
	} else {
		d=dep(root*2+1);
		dfs(root*2);
	}
	ll mx=2*d+4;
	for (ll i=0; i<=mx; i++) {
		g2[i]+=g[d][i];
		for (ll j=0; j<=min(d+2,i); j++) {
			g2[i+2]+=dp2[j]*dp[d][i-j]%mod;
		}
	}
	for (ll i=mx; i>0; i--)dp2[i]=(dp2[i-1]+dp[d][i-1])%mod;
	dp2[0]=1;
	for (ll i=0; i<=mx; i++)g2[i]+=dp2[i],g2[i]%=mod;
}

inline ll qkp(ll a,ll k) {
	ll ans=1;
	while (k) {
		if (k&1)ans*=a,ans%=mod;
		a*=a,a%=mod;
		k>>=1;
	}
	return ans;
}

int main() {
	ll t;
	scanf("%lld",&t);
	for (ll i=1; i<=60; i++) {
			dp[i][0]=1;
			for (ll j=1; j<=i-1; j++) {
				dp[i][j]=2*dp[i-1][j-1]%mod;
			}
			for (ll j=0; j<=2*i-2; j++) {
				g[i][j]+=g[i-1][j]*2;
				g[i][j]+=dp[i][j];
				g[i][j]%=mod;
				for (ll k=0; k<=j; k++) {
					g[i][j+2]+=dp[i-1][k]*dp[i-1][j-k]%mod;
					g[i][j+2]%=mod;
				}
			}
		}
	while (t--) {
		scanf("%lld%lld",&n,&m);
		
		// log n^3
		dfs(1);
		ll d=dep(1),ans=0;
		for (ll j=0; j<=m; j++) {
			pw[j][0]=1;
			for (ll i=1; i<=2*d; i++) {
				pw[j][i]=pw[j][i-1]*j%mod;
			}
		}

		for (ll i=0; i<=2*d-2; i++) {
			for (ll j=1; j<=m; j++) {
				f[i]+=(pw[j][i+2]+mod-pw[j-1][i+1]*j%mod)%mod;
				f[i]%=mod;
			}
			if (n>=i+1)
				ans+=f[i]*g2[i]%mod*qkp(m,n-i-1)%mod;
			ans%=mod;
		}
		printf("%lld\n",ans);
		for (ll i=1;i<=60;i++){
			for (ll j=0;j<=2*i-2;j++){
				f[j]=g2[j]=dp2[j]=0;
			}
		}
	}

	return 0;
}

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int cnt=0;
int reg[100005][131],reg2[100005][131];
unordered_map<int,int> mp;
void dfs(int now){
	if(mp[now]) return ;
	mp[now]=++cnt;
	if(now==0) return ;
	reg[cnt][0]++,reg2[cnt][0]++;
	if(now==1) return ;
	int i=0;
	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
	i-=2;
	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
	if(lft<=(1LL<<i)) lnum+=lft;
	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
	dfs(lnum),dfs(rnum);
	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
	for(int i=0;i<=130;i++){
		for(int j=0;j<=130;j++){
			if(i+j+2>=130) break;
			(reg2[mn][i+j+2]+=(reg[ml][i]*reg[mr][j]))%=mod; 
		}
	}
	for(int i=0;i<=129;i++) (reg[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i+1]+=reg[ml][i]+reg[mr][i])%=mod,(reg2[mn][i]+=reg2[ml][i]+reg2[mr][i])%=mod;
}
int pw[100005][150],tot[205];
signed main(){
	init();
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		dfs(n);
		int nn=mp[n];
		int ans=0;
		tot[0]=(m-1)%mod;
		for(int i=2;i<=135;i++){
			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
		    (tot[i-1]*=qp(i,mod-2))%=mod;
		}
		for(int i=0;i<=min(130ll,n-1);i++){
			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
			(ans+=tmp*reg2[nn][i]%mod*qp(m%mod,n-(i+1)))%=mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int cnt=0;
int reg[100005][131],dep[100005],depc[100005],rett[131],invi[131];
unordered_map<int,int> mp;
void dfs(int now){
	if(mp[now]) return ;
	mp[now]=++cnt;
	if(now==0) return ;
	dep[cnt]=1,depc[cnt]=1,reg[cnt][0]++;
	if(now==1) return ;
	int i=0;
	for(i=1;i<=62;i++) if((1LL<<i)-1>=now) break;
	i-=2;
	int lnum=(1LL<<i)-1,rnum=(1LL<<i)-1,lft=now-(1LL<<(i+1))+1;
	if(lft<=(1LL<<i)) lnum+=lft;
	else lnum+=(1LL<<i),rnum+=(lft-(1LL<<i));
	dfs(lnum),dfs(rnum);
	int ml=mp[lnum],mr=mp[rnum],mn=mp[now];
	if(dep[ml]>dep[mr]){
		dep[mn]=dep[ml]+1; depc[mn]=depc[ml];
		for(int i=0;i<=129;i++) reg[mn][i]=reg[ml][i];
	}
	else{
		dep[mn]=dep[ml]+1; depc[mn]=(depc[ml]+depc[mr])%mod;
		for(int i=0;i<=129;i++) reg[mn][i]=(reg[ml][i]+reg[mr][i])%mod;
		(reg[mn][dep[mn]*2-2]+=depc[ml]*depc[mr])%=mod;
	}
}
int pw[100005][150],tot[205],pw2[135];
signed main(){
	pw2[0]=1;
	for(int i=1;i<=130;i++) pw2[i]=pw2[i-1]*2%mod,invi[i]=qp(i,mod-2);
	init();
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		int lg=0,lft;
		for(int i=0;i<=130;i++) rett[i]=0;
		for(lg=61;lg>=0;lg--){
			if(n>=(1LL<<(lg+1))-1){
				lft=n-((1LL<<(lg+1))-1);
				lft%=mod;
				break;
			}
		}
		for(int i=0;i<=lg;i++){
			for(int j=0;j<=lg;j++){
				int tt=max(i,j);
				(rett[i+j]+=(pw2[lg-tt+1]-1)*pw2[max(0ll,i-1)+max(0ll,j-1)]%mod)%=mod;
			}
		}
		for(int i=1;i<=lg+1;i++){
			for(int j=0;j<i;j++){
				(rett[i+j]+=lft*pw2[max(0ll,j-1)]%mod)%=mod;
			}
		}
		dfs(n);
		int nn=mp[n];
		if(n!=(1ll<<(lg+1))-1) for(int i=0;i<=130;i++) (rett[i]+=reg[nn][i])%=mod;
		int ans=0;
		tot[0]=(m-1)%mod;
		for(int i=2;i<=130;i++){
			tot[i-1]=(qp((m-1)%mod+1,i)+mod-1)%mod;
			for(int l=2;l<=i;l++) (tot[i-1]+=mod-C(i,l)*tot[i-l]%mod)%=mod;
		    (tot[i-1]*=invi[i])%=mod;
		}
		for(int i=0;i<=min(130ll,n-1);i++){
			int tmp=(qp(m%mod,i+2)+mod-tot[i+1])%mod;
			(ans+=tmp*rett[i]%mod*qp(m%mod,n-(i+1)))%=mod;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,_##i##__end=(n);i<_##i##__end;++i)
#define rep1(i,n) for(int i=1,_##i##__end=(n);i<=_##i##__end;++i)
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
const ll mod1=998244353;
int t;
ll n;
int m;
ll qkpw(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod1;
		a=a*a%mod1;
		b>>=1;
	}
	return ret;
}
ll val_full[114];
ll val_link[114];
pair<ll,ll> realget(ll P,unsigned long long c)
{
	if((c&(c+1))==0)
	return mp(val_link[bit_width(c)-1],val_full[bit_width(c)-1]);
	if(c==2)
	return mp((P*P+P)%mod1,(P*P+P+P)%mod1);
	if(c&(bit_floor(c)>>1))
	{
		pair<ll,ll> A=realget(P,bit_floor(c)-1),B=realget(P,c-bit_floor(c));
		return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
	}
	pair<ll,ll> A=realget(P,c-(bit_floor(c)>>1)),B=realget(P,(bit_floor(c)>>1)-1);
	return mp((A.fi+B.fi+1)*P%mod1,(A.se+B.se+(1+A.fi)*(1+B.fi)%mod1*P)%mod1);
}
ll get_value(ll P,ll c)
{
	val_full[0]=P;val_link[0]=P;
	rep1(i,64)
	{
		val_full[i]=(val_full[i-1]*2+(1+val_link[i-1])*(1+val_link[i-1])%mod1*P)%mod1;
		val_link[i]=((val_link[i-1]*2+1)*P)%mod1;
	}
	return realget(P,c).second;
}
void Q()
{
	cin>>n>>m;
	ll cur=((n%mod1)*(n%mod1+1)/2%mod1)*qkpw(m,n+1)%mod1;
	ll INV_M=qkpw(m,mod1-2);
	rep(i,m) cur=(cur-qkpw(m,n)*get_value(i*INV_M%mod1,n)%mod1+mod1)%mod1;
	cout<<cur<<endl;
}
int main()
{
	cin>>t;while(t--)Q();
}

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

In fact, vertices with degree $$$1$$$ are useless, let's first ignore them. It's easy to see that when $$$\sum_{i=1}^nd_i=2n$$$, we can simply hang them under the vertices which haven't reached their degree limit.

In most cases, we can simply put two vertices on the cycle.

Sort $$$d_i$$$ from the largest to the smallest. Can we construct a flower-like psuedotree when $$$d_1=2$$$? Can we construct a flower-like psuedotree when $$$d_1\neq 2$$$ and $$$d_2=2$$$?

Can you find an easy way to construct the flower-like psuedotree when the number of $$$d_i \gt 1$$$ is even?

Try to extend the solution when the number of $$$d_i \gt 1$$$ is even to the odd case. Note some corner cases.

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
struct node{
	int d,pos;
}a[1000005];
bool cmp(node x,node y){
	return x.d>y.d;
}
void pe(int x,int y){
	cout<<a[x].pos<<" "<<a[y].pos<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n,tot=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].d,a[i].pos=i,tot+=a[i].d;
		if(tot!=2*n){
			cout<<"No\n"; continue;
		}
		if(n==1){
			cout<<"No\n"; continue;
		}
		sort(a+1,a+n+1,cmp);
		if(a[1].d==2){
			cout<<"Yes\n";
			for(int i=1;i<=n;i++) pe(i,i%n+1);
			continue;
		}
		if(a[2].d==2){
			cout<<"No\n"; continue;
		}
		int cntb=0;
		for(int i=3;i<=n;i++) cntb+=(a[i].d>1);
		int num[n+1]; for(int i=1;i<=n;i++) num[i]=a[i].d;
		if(!(cntb&1)){
			cout<<"Yes\n";
			pe(1,2),pe(1,2);
			num[1]-=2,num[2]-=2;
			for(int i=3;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
		if(a[1].d==3){
			if(a[3].d==2){
				cout<<"No\n"; continue;
			}
			if(cntb==1){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,1);
				pe(1,4),pe(2,5),pe(3,6);
				continue;
			}
			if(a[5].d==2&&cntb==3){
				cout<<"No\n"; continue;
			}
			if(cntb==3){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,4),pe(4,5),pe(5,1);
				pe(1,6),pe(2,7),pe(3,8),pe(4,9),pe(5,10);
				continue;
			}
			cout<<"Yes\n";
			pe(1,2),pe(1,2),pe(1,3),pe(2,4),pe(3,5),pe(3,6),pe(4,7);
			num[1]-=3,num[2]-=3,num[3]-=3,num[4]-=2,num[5]--,num[6]--,num[7]--;
			for(int i=8;i<=cntb+2;i++) pe(i-2,i),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
		else{
			if(a[3].d==2&&cntb==1){
				cout<<"No\n"; continue;
			}
			if(cntb==1){
				cout<<"Yes\n";
				pe(1,2),pe(2,3),pe(3,1);
				num[1]-=2,num[2]-=2,num[3]-=2;
				int it=1;
				for(int i=4;i<=n;i++){
					while(!num[it]) it++;
					num[it]--,pe(i,it);
				}
				continue;
			}
			cout<<"Yes\n";
			pe(1,2),pe(1,2),pe(1,3),pe(1,4),pe(2,5);
			num[1]-=4,num[2]-=3,num[3]-=1,num[4]-=1,num[5]-=1;
			for(int i=6;i<=cntb+2;i++) pe(i,i-2),num[i]--,num[i-2]--;
			int it=1;
			for(int i=cntb+3;i<=n;i++){
				while(!num[it]) it++;
				num[it]--,pe(i,it);
			}
			continue;
		}
	}
	return 0;
}

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

Consider this problem on the prefix sum array.

Try to make some observations about the prefix sum array. Consider dp.

Go for a slow solution first, for example, $$$\mathcal{O}(n^6)$$$ or $$$\mathcal{O}(n^4)$$$.

The last step is to optimize your dp to $$$\mathcal{O}(n^3)$$$. :)

$$$\mathcal{O}(n^6)$$$ can pass $$$n\le 100$$$ easily so we have to raise the limit for $$$\sum n$$$ to $$$1~000$$$.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <random>
#include <ctime>
#include <string_view>
#include <queue>
#include <cassert>

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define ld long double

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

bool contains(ll x, ll l, ll r) {
    return (x >= l) && (x <= r);
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << 1 << "\n";
        return;
    }
    vector<ll> pr(n + 1);
    for (int i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i + 1];
    vector<vector<vector<int>>> dp_leftmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_leftmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_rightmin(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<vector<vector<int>>> dp_rightmax(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    vector<pair<ll, int>> b(n + 1);
    for (int i = 0; i <= n; i++) b[i] = mp(pr[i], i);
    sort(all(b));
    vector<vector<int>> next_left(n + 1, vector<int>(n + 1, -1));
    vector<vector<int>> next_right(n + 1, vector<int>(n + 1, -1));
    for (int i = 0; i <= n; i++) {
        int prev = -1;
        for (int j = 0; j <= n; j++) {
            next_left[i][j] = prev;
            if (pr[j] == pr[i]) prev = j;
        }
        prev = n + 1;
        for (int j = n; j >= 0; j--) {
            next_right[i][j] = prev;
            if (pr[j] == pr[i]) prev = j;
        }
    }
    for (int len = 0; len <= n; len++) {
        for (int i = 0; i <= n && i + len <= n; i++) {
            int j = i + len;
            for (int k = 0; k <= n; k++) {
                if (contains(pr[i], pr[i], pr[k]) && contains(pr[j], pr[i], pr[k])) dp_leftmin[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[k], pr[i]) && contains(pr[j], pr[k], pr[i])) dp_leftmax[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[j], pr[k]) && contains(pr[j], pr[j], pr[k])) dp_rightmin[i][j][k] = min(len, 1);
                if (contains(pr[i], pr[k], pr[j]) && contains(pr[j], pr[k], pr[j])) dp_rightmax[i][j][k] = min(len, 1);
            }
            if (len <= 1) continue;
            for (int x = i; x <= j; x++) {
                if (next_left[i][x] >= i) {
                    int y = next_left[i][x];
                    if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][y][x] + dp_leftmax[x][j][i] + 1);
                    if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][y][x] + dp_leftmin[x][j][i] + 1);
                }
                if (next_left[j][x] >= i) {
                    int y = next_left[j][x];
                    if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[x][j][x] + dp_rightmin[i][y][x] + 1);
                    if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[x][j][x] + dp_rightmax[i][y][x] + 1);
                }
                if (next_right[i][x] <= j) {
                    int y = next_right[i][x];
                    if (pr[x] >= pr[i]) dp_leftmin[i][j][x] = max(dp_leftmin[i][j][x], dp_leftmin[i][x][x] + dp_leftmin[y][j][x] + 1);
                    if (pr[x] <= pr[i]) dp_leftmax[i][j][x] = max(dp_leftmax[i][j][x], dp_leftmax[i][x][x] + dp_leftmax[y][j][x] + 1);
                }
                if (next_right[j][x] <= j) {
                    int y = next_right[j][x];
                    if (pr[x] >= pr[j]) dp_rightmin[i][j][x] = max(dp_rightmin[i][j][x], dp_rightmin[y][j][x] + dp_rightmax[i][x][j] + 1);
                    if (pr[x] <= pr[j]) dp_rightmax[i][j][x] = max(dp_rightmax[i][j][x], dp_rightmax[y][j][x] + dp_rightmin[i][x][j] + 1);
                }
            }
            int mx_left = -INF;
            int mx_right = -INF;
            for (int k = 0; k <= n; k++) {
                int p = k;
                while (p <= n && b[p].fi == b[k].fi) {
                    mx_left = max(mx_left, dp_leftmin[i][j][b[p].se]);
                    mx_right = max(mx_right, dp_rightmin[i][j][b[p].se]);
                    p++;
                }
                for (int l = k; l < p; l++) {
                    dp_leftmin[i][j][b[l].se] = mx_left;
                    dp_rightmin[i][j][b[l].se] = mx_right;
                }
                k = p - 1;
            }
            mx_left = -INF;
            mx_right = -INF;
            for (int k = n; k >= 0; k--) {
                int p = k;
                while (p >= 0 && b[p].fi == b[k].fi) {
                    mx_left = max(mx_left, dp_leftmax[i][j][b[p].se]);
                    mx_right = max(mx_right, dp_rightmax[i][j][b[p].se]);
                    p--;
                }
                for (int l = k; l > p; l--) {
                    dp_leftmax[i][j][b[l].se] = mx_left;
                    dp_rightmax[i][j][b[l].se] = mx_right;
                }
                k = p + 1;
            }
        }
    }
    int ans = -INF;
    ans = max(ans, dp_leftmin[0][n][n]);
    ans = max(ans, dp_leftmax[0][n][n]);
    for (int x = 0; x <= n; x++) {
        for (int y = x + 1; y <= n; y++) {
            ans = max(ans, dp_rightmin[0][x][y] + dp_leftmax[y][n][x] + 1);
            ans = max(ans, dp_rightmax[0][x][y] + dp_leftmin[y][n][x] + 1);
        }
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #else 
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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

Greedy.

This problem is somehow related to geometry.

What structure will the intervals you choose each time form?

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using point = pair<ll, ll>;

const int _N = 5e5 + 5;

int n;
ll a[_N], pre[_N], suf[_N], ans;
struct interval{
	int l, r; 
	ll d, dneed;
	int type, pos; // type0 - l, type1 - r
};
struct cmp{
	bool operator () (const interval &a, const interval &b) {
		return a.dneed - a.d > b.dneed - b.d;
	}
};

ll ceildiv(ll a, ll b) {
	// return a/b;
	if (a * b > 0) return a / b;
	else return a / b - !!(a % b);
}

namespace sg_left{ // [l, r] -> hull of point l-1 to r-1
	vector<int> hull[_N << 2];
	point pt[_N];
	void get_hull(int p, int l, int r) {
		int head = 0, tail = -1;
		for (int i = l; i <= r; i++) {
			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) <= (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
				tail--;
				hull[p].pop_back();
			}
			tail++;
			hull[p].emplace_back(i);
		}
	}
	void build(int p, int l, int r) {
		get_hull(p, l - 1, r - 1);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p * 2, l, mid);
		build(p * 2 + 1, mid + 1, r);
	}
	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
		if (l >= L && r <= R) { // do ternary search
			int tl = 1, tr = hull[p].size();
			while (tl < tr) {
				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
				if ((o.second - p1.second) * (o.first - p2.first) >= (o.second - p2.second) * (o.first - p1.first)) {
					tl = m1 + 1;
				} else tr = m2 - 1;
			}
			return {ceildiv((o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] + 1};
		}
		int mid = (l + r) >> 1;
		pair<int, int> res = {-1, -1};
		if (L <= mid) {
			res = query(p * 2, l, mid, L, R, o);
		} 
		if (R > mid) {
			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
			if (res == make_pair(-1, -1)) return res2;
			else {
				if (res2.first <= res.first) {
					return res2;
				} else return res;
			}
		}
		return res;
	}
	void test() {
		auto res = query(1, 1, n, 1, n, pt[n]);
		cout << res.first << ' ' << res.second << '\n';
	}
};
namespace sg_right{ // [l, r] -> hull of point l+1 to r+1
	vector<int> hull[_N << 2];
	point pt[_N];
	void get_hull(int p, int l, int r) {
		int head = 0, tail = -1;
		for (int i = l; i <= r; i++) {
			while (head < tail && (pt[hull[p][tail]].second - pt[hull[p][tail - 1]].second) * (pt[i].first - pt[hull[p][tail]].first) < (pt[i].second - pt[hull[p][tail]].second) * (pt[hull[p][tail]].first - pt[hull[p][tail - 1]].first)) {
				tail--;
				hull[p].pop_back();
			}
			tail++;
			hull[p].emplace_back(i);
		}
	}
	void build(int p, int l, int r) {
		get_hull(p, l + 1, r + 1);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p * 2, l, mid);
		build(p * 2 + 1, mid + 1, r);
	}
	pair<int, int> query(int p, int l, int r, int L, int R, point o) {
		if (l >= L && r <= R) { // do ternary search
			int tl = 1, tr = hull[p].size();
			while (tl < tr) {
				int m1 = (tl + tr) / 2, m2 = (tl + tr) / 2 + 1;
				auto p1 = pt[hull[p][m1 - 1]], p2 = pt[hull[p][m2 - 1]];
				if ((o.second - p1.second) * (o.first - p2.first) <= (o.second - p2.second) * (o.first - p1.first)) {
					tl = m1 + 1;
				} else tr = m2 - 1;
			}
			return {ceildiv(-(o.second - pt[hull[p][tl - 1]].second), (o.first - pt[hull[p][tl - 1]].first)), hull[p][tl - 1] - 1};
		}
		int mid = (l + r) >> 1;
		pair<int, int> res = {-1, -1};
		if (L <= mid) {
			res = query(p * 2, l, mid, L, R, o);
		} 
		if (R > mid) {
			auto res2 = query(p * 2 + 1, mid + 1, r, L, R, o);
			if (res == make_pair(-1, -1)) return res2;
			else {
				if (res.first <= res2.first) {
					return res;
				} else return res2;
			}
		}
		return res;
	}
	void test() {
		auto res = query(1, 1, n, 1, n, pt[1]);
		cout << res.first << ' ' << res.second << '\n';
	}
};


int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	if (n == 1) {
		cout << max(a[1] + 1, 0ll) << '\n';
		return 0;
	}
	sg_left::pt[0] = {0, 0}; sg_right::pt[n + 1] = {n + 1, 0};
	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + a[i];
		sg_left::pt[i] = {i, pre[i]};
	}
	for (int i = n; i >= 1; i--) {
		suf[i] = suf[i + 1] + a[i];
		sg_right::pt[i] = {i, suf[i]};
	}
	sg_left::build(1, 1, n);
	sg_right::build(1, 1, n);
	ll ans = 0;
	priority_queue<interval, vector<interval>, cmp> q;
	pair<int, int> resL = sg_left::query(1, 1, n, 1, n, sg_left::pt[n]);
	pair<int, int> resR = sg_right::query(1, 1, n, 1, n, sg_right::pt[1]);
	if (resL.second == 1) q.push({1, n, 0, resR.first + 1, 1, resR.second});
	else if (resR.second == n) q.push({1, n, 0, resL.first + 1, 0, resL.second});
	else if (resL.first <= resR.first) q.push({1, n, 0, resL.first + 1, 0, resL.second});
	else q.push({1, n, 0, resR.first + 1, 1, resR.second});
	while (!q.empty()) {
		auto x = q.top(); q.pop();
		if (x.d < x.dneed) {
			ans += x.dneed - x.d;
			x.d = x.dneed;
		}
		//split
		if (x.type == 1) x.pos++;
		int l = x.l, r = x.r;
		resL = sg_left::query(1, 1, n, l, x.pos - 1, sg_left::pt[x.pos - 1]);
		resR = sg_right::query(1, 1, n, l, x.pos - 1, sg_right::pt[l]);
		if (l == x.pos - 1) {
			ans += max(0ll, a[l] - x.d + 1);
		} else {
			if (resL.second == l) q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
			else if (resR.second == r) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
			else if (resL.first <= resR.first) q.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
			else q.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
		}
		resL = sg_left::query(1, 1, n, x.pos, r, sg_left::pt[r]);
		resR = sg_right::query(1, 1, n, x.pos, r, sg_right::pt[x.pos]);
		if (x.pos == r) {
			ans += max(0ll, a[r] - x.d + 1);
		} else {
			if (resL.second == l) q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
			else if (resR.second == r)q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
			else if (resL.first < resR.first) q.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
			else q.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
		}
	}
	cout << ans << '\n';
}

Can you solve this problem in $$$\mathcal{O}(n\log n+n\log V)$$$ time complexity and $$$\mathcal{O}(n)$$$ space complexity?

The solution has nothing to do with data structures.

/*  
  hmz is cute!
--------------------------------------------
  You've got to have faith
  Don't let them cut you down cut you down once more
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define TY long long
#define IL inline
#define umap unordered_map
#define ull unsigned long long
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define mod (TY)(1e9+7)
#define MAXN 500005
#define MAXM 200005
#define MAXK 27
#define INF (TY)(1e9)
#define block 300
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
IL TY qr(){
	TY x=0,f=1;char op=getchar();
	for(;op<'0'||op>'9';op=getchar())if(op=='-')f=-1;
	for(;op>='0'&&op<='9';op=getchar())x=x*10+(op^48);
	return x*f;
}IL bool ischar(char op){
	if(op>='a'&&op<='z')return true;
	if(op>='A'&&op<='Z')return true;
	return false;
}IL char getc(){
	char op=getchar();
	while(!ischar(op))op=getchar();
	return op;
}IL string qs(){
	string op="";char u=getchar();
	while(!ischar(u))u=getchar();
	while(ischar(u))op+=u,u=getchar();
	return op;
}IL void qw(long long x){
	if(!x){putchar('0');return;}
	if(x<0)putchar('-'),x=-x;
	if(x>=10)qw(x/10);putchar(x%10+'0');
}IL void qw(long long x,char op){qw(x),putchar(op);}
IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
IL TY Ceil(TY a,TY b){return a/b+(a%b!=0);}
IL TY Mod(TY a){return (a>=mod?a-mod:a);}
IL TY Abs(TY a,TY b){return a>b?a-b:b-a;}
IL TY Pow(TY a,TY b){
	TY ans=1,base=a;
	while(b){
		if(b&1)ans=ans*base%mod;
		base=base*base%mod;b>>=1;
	}return ans;
}TY n,a[MAXN],b[MAXN],sum[MAXN],lenx[MAXN],leny[MAXN],ans;
vector<signed> e1[MAXN],e2[MAXN],HH;
TY Sum[MAXN],SSum[MAXN];
bool vis[MAXN];
signed L[MAXN],R[MAXN],LL[MAXN],RR[MAXN],ok[MAXN],nxtx[MAXN],nxty[MAXN];
struct node{TY l,r,tag,op;};queue<node> q;
IL void init(TY l,TY r,TY tag){
    For(i,l,r)e1[i].clear(),e2[i].clear();
    vector<pair<TY,TY> > pre,nxt;
    For(i,l,r){
        while(!pre.empty()){
            TY ch=(pre.back().second*-1+tag)*(i-pre.back().first)+sum[i]-sum[pre.back().first];
            if(ch<0){
                nxtx[pre.back().first]=i;
                pre.pop_back();continue;
            }else{
                lenx[i]=pre.back().second+Ceil(ch+1,i-pre.back().first);
                pre.push_back({i,pre.back().second+Ceil(ch+1,i-pre.back().first)});
                break;
            }
        }if(pre.empty()){
            lenx[i]=Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1);
            pre.push_back({i,Ceil(sum[i]-sum[l-1]+tag*(i-l+1)+1,i-l+1)});
        }
    }while(!pre.empty())nxtx[pre.back().first]=r+1,pre.pop_back();
    Rof(i,r,l){
        while(!nxt.empty()){
            TY ch=(nxt.back().second*-1+tag)*(nxt.back().first-i)-sum[i-1]+sum[nxt.back().first-1];
            if(ch<0){
                nxty[nxt.back().first]=i;
                nxt.pop_back();continue;
            }else{
                leny[i]=nxt.back().second+Ceil(ch+1,nxt.back().first-i);
                nxt.push_back({i,nxt.back().second+Ceil(ch+1,nxt.back().first-i)});
                break;
            }
        }if(nxt.empty()){
            leny[i]=Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1);
            nxt.push_back({i,Ceil(sum[r]-sum[i-1]+tag*(r-i+1)+1,r-i+1)});
        }
    }while(!nxt.empty())nxty[nxt.back().first]=l-1,nxt.pop_back();
    For(i,l,r)if(nxtx[i]!=r+1)e1[nxtx[i]].pb(i);
    Rof(i,r,l)if(nxty[i]!=l-1)e2[nxty[i]].pb(i);
}int main(){
    //freopen("data.in","r",stdin);
    /* init */
    n=qr();For(i,1,n)a[i]=qr(),sum[i]=sum[i-1]+a[i];
    q.push({1,n,0,0});
    while(!q.empty()){
        TY l=q.front().l,r=q.front().r,tag=q.front().tag,op=q.front().op;
        if(l>r||l<=0||r>n)continue;
        q.pop();
        if(op==0){
            vector<pair<TY,TY> > tmp;
            TY c=0;TY lst=-1;
            For(i,l,r)b[i]=a[i]+tag;
            For(i,l,r){
                if((b[i]>=0)!=lst){
                    lst=(b[i]>=0);
                    ++c;L[c]=R[c]=i;
                    Sum[c]=b[i];
                }else R[c]=i,Sum[c]+=b[i];
            }For(i,1,c)LL[i]=i,RR[i]=i,SSum[i]=Sum[i],ok[i]=0,vis[i]=1;
            Sum[c+1]=0;RR[c+1]=INF;
            For(i,1,c)if(Sum[i]<0){
                ok[i]=(Sum[i-1]+Sum[i]>=0)+(Sum[i+1]+Sum[i]>=0);
                if(ok[i]==2)HH.pb(i),ok[i]=INF;
            }else{
                ok[i]=(Sum[i-1]+Sum[i]<0)+(Sum[i+1]+Sum[i]<0);
                if(ok[i]==2)HH.pb(i),ok[i]=INF;
            }while(!HH.empty()){
                TY now=HH.back(),nowL=LL[now],nowR=RR[now];
                TY k=SSum[nowL]+SSum[nowL-1]+SSum[nowR+1],pre=LL[LL[nowL-1]-1],nxt=RR[nowR+1]+1;
                HH.pop_back();
                if(SSum[nowL]>=0){
                    if(pre>=1&&nxt<=c){
                        ok[LL[nowL-1]]=(k+SSum[pre]>=0)+(k+SSum[nxt]>=0);
                        if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
                    }else ok[LL[nowL-1]]=INF;
                    if(pre>=1){
                        ok[pre]+=-(SSum[nowL-1]+SSum[pre]<0)+(SSum[pre]+k<0);
                        if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]>=0)HH.pb(pre),ok[pre]=INF;
                    }if(nxt<=c){
                        ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]<0)+(SSum[nxt]+k<0);
                        if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]>=0)HH.pb(nxt),ok[nxt]=INF;
                    }
                }else{
                    if(pre>=1&&nxt<=c){
                        ok[LL[nowL-1]]=(k+SSum[pre]<0)+(k+SSum[nxt]<0);
                        if(ok[LL[nowL-1]]==2)HH.pb(LL[nowL-1]),ok[LL[nowL-1]]=INF;
                    }else ok[LL[nowL-1]]=INF;
                    if(pre>=1){
                        ok[pre]+=-(SSum[nowL-1]+SSum[pre]>=0)+(SSum[pre]+k>=0);
                        if(ok[pre]==2&&SSum[nowL-1]+SSum[pre]<0)HH.pb(pre),ok[pre]=INF;
                    }if(nxt<=c){
                        ok[nxt]+=-(SSum[nowR+1]+SSum[nxt]>=0)+(SSum[nxt]+k>=0);
                        if(ok[nxt]==2&&SSum[nowR+1]+SSum[nxt]<0)HH.pb(nxt),ok[nxt]=INF;
                    }
                }SSum[LL[nowL-1]]=SSum[RR[nowR+1]]=k;
                RR[LL[nowL-1]]=RR[nowR+1];
                LL[RR[nowR+1]]=LL[nowL-1];
            }Rof(i,c,1)if(Sum[i]>=0&&vis[i]){
                Rof(j,i,LL[i])vis[j]=0;
                tmp.pb({L[LL[i]],R[RR[i]]});
            }Rof(i,tmp.size()-1,0)q.push({tmp[i].first,tmp[i].second,tag,1});
        }else{
            if(l==r){
                ans+=a[l]+tag+1;
                continue;
            }queue<TY> fir,sec;
            init(l,r,tag);
            For(i,l,r)if(nxtx[i]==r+1)fir.push(i);
            Rof(i,r,l)if(nxty[i]==l-1)sec.push(i);
            TY lstl=l,lstr=r,lstcnt=0;
            while(lstl<lstr){
                while(!fir.empty()&&(lstl>fir.front()||fir.front()>lstr))fir.pop();
                while(!sec.empty()&&(lstl>sec.front()||sec.front()>lstr))sec.pop();
                TY id1=(fir.empty()?INF:fir.front()),id2=(sec.empty()?INF:sec.front());
                TY cnt1=(id1==INF?INF:lenx[id1]-lstcnt);
                TY cnt2=(id2==INF?INF:leny[id2]-lstcnt);
                if(cnt1<=cnt2){
                    fir.pop();
                    lstcnt=lenx[id1];
                    For(j,lstl,id1){FOR(i,0,e2[j].size())sec.push(e2[j][i]);e2[j].clear();}
                    q.push({lstl,id1,-lstcnt+tag,0});
                    lstl=id1+1;
                }else{
                    sec.pop();
                    lstcnt=leny[id2];
                    Rof(j,lstr,id2){FOR(i,0,e1[j].size())fir.push(e1[j][i]);e1[j].clear();}
                    q.push({id2,lstr,-lstcnt+tag,0});
                    lstr=id2-1;
                }
            }if(lstl==lstr)q.push({lstl,lstl,-lstcnt+tag,1});
            ans+=lstcnt;
        }
    }qw(ans);
    return 0;
}

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