This time I've been trying my best to make the problems use more varied algorithms instead of just dp problems, but sadly 2115C - Gellyfish and Eternal Violet was much harder than expected.

But it seems like people are complaining more about the narrow time limit, centered on 2116C - Gellyfish and Flaming Peony and 2115C - Gellyfish and Eternal Violet.

No one realized this before the contest, because none of the tester's code is get TLE except the wrong time complexity.

I actually don't see a problem with the Time Limit of 2116C - Gellyfish and Flaming Peony. Some of you may be puzzled, but let me try to explain this:

• The intended solution is $$$O(\sum n \max(a) + \max(a)^2)$$$ and does not contain $$$\log \max(a)$$$. Computing $$$\gcd(x, y)$$$ is not $$$O(1)$$$, if you don't preprocess, then it's not unusual to actually get a TLE.
• I believe the vast majority of people who get TLE do so for this reason, and you might argue that it's actually hard to tell whether it's the constant that's too large or the time complexity that's wrong. I would say that normally, if someone expects $$$O(n^2 \log n)$$$ to pass, then the questioner would set it to $$$n \leq 2000$$$ instead of $$$n \leq 5000$$$.
• I'll admit that $$$n, a_i \leq 2000$$$ would have been better, "Happy AC" isn't a bad thing, this is not Div.1 F and we shouldn't limit complexity to such a narrow range. I'm ignoring the fact that most people who get a TLE will assume that the constant is too large, and thus not even think about the large amount of time wasted from optimizing the complexity.
• If someone's solution is $$$O(\sum n \max(a) + \max(a)^2)$$$ and it gets TLE, I really don't know why. The speed performance of array accesses on Codeforces is very strange (also happens on 2115C - Gellyfish and Eternal Violet), the vast majority of $$$O(\sum n \max(a) + \max(a)^2)$$$ code which gets TLE performs quite well locally, I didn't realize this until after the contest. It's extremely hard for this to happen, I've tried various modifications to std, including swapping the order of the two dimensions of the array and the enumerations i, j, and none of them have gotten a TLE. it's only possible to get a TLE if your code is in an extremely unlucky situation, otherwise going beyond $$$1$$$ second is almost impossible if you are using C++.

For 2115C - Gellyfish and Eternal Violet, I'll admit it was a huge mistake:

• A $$$O(m^2 h)$$$ code is so fast that it takes less than $$$5$$$ seconds even at today's ranges, It runs so fast that I ignored the constants in order to prevent it from passing. The speed of std and testers' codes gave me too much confidence. (Although it was ultimately discovered that some testers' codes did not encounter the worst-case scenario) I should indeed guarantee $$$\sum n \leq 50 $$$ instead of $$$\sum n \leq 100$$$.
• Now I deeply realize that for all but the last few problems, the probability of unintended solutions passing due to extreme constant optimization is far less than the probability of intended solutions receiving TLE. Very few people master instruction sets and extreme constant optimization techniques, and their skill level is usually high enough to handle these problems. The effort required to pass these problems through extreme constant optimization often outweighs simply reconsidering the correct time complexity. I hope the failure of this contest will make future problem authors aware of this issue.
• In fact, the original constraints for 2115C - Gellyfish and Eternal Violet were $$$n \leq 100, m \leq 2000, h_i \leq 100$$$ which would have prevented the current situation. If someone passes your problem through extreme constant optimization, think carefully based on the problem's difficulty—whether you should increase the constraints or just give everyone a "Happy AC."

In any case, it's all over now. Though this wasn't a perfect ending, 'Life goes on.' Hope Codeforces contests will keep improving, and wish those reading this better results in future competitions.

Please think carefully about what happens after the death of either knight.

While a player who goes to $$$0$$$ HP will lose the game outright, when a player's knight dies, she loses the ability to attack; then in future rounds, she can only be attacked by her opponent and thus lose the game.

Thus it can be found that the player herself is as important as her knights, and she loses the game when either of them becomes $$$0$$$ HP.

Therefore, the optimal strategy for both of them is to attack the one with lower HP. So when $$$\min(a, c)$$$ is greater than or equal to $$$\min(b, d)$$$, Gellyfish wins, otherwise Flower wins.

Time complexity: $$$O(1)$$$ per test case.

Memory complexity: $$$O(1)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

inline void solve(){
	int a = 0, b = 0, c = 0, d = 0;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	if(min(a, c) >= min(b, d)) printf("Gellyfish\n");
	else printf("Flower\n");
}

int T = 0;

int main(){
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) solve();
	return 0;
}

How to quickly compare $$$2^a + 2^b$$$ and $$$2^c + 2^d$$$ for given integers $$$a, b, c, d$$$ is the key.

We are given two permutations of $$$p$$$ and $$$q$$$, which means that each element will appear only once in both $$$p$$$ and $$$q$$$, respectively. What's the point of this?

For given integers $$$a, b, c, d$$$ , if we want to compare $$$2^a+2^b$$$ and $$$2^c+2^d$$$, we actually need to compare $$$\max(a, b)$$$ with $$$\max(c, d)$$$ first, and $$$\min(a, b)$$$ with $$$\min(c, d)$$$ second. This is due to $$$2^k = 2^{k-1} + 2^{k-1}$$$; when $$$\max(c, d) \lt \max(a, b)$$$, $$$2^c + 2^d \leq 2 \times 2^{\max(c, d)} \leq 2^{\max(a, b)}$$$, and it's symmetric for $$$\max(a, b) \lt \max(c, d)$$$.

So for all $$$i$$$, we only need to find $$$j = \arg \max\limits_{1 \leq l \leq i} p_l, k = \arg \max\limits_{1 \leq l \leq i} q_l$$$, then $$$r_i = \max(2^{p_j} + 2^{q_{i-j}}, 2^{p_{i-k}} + 2^{q_k})$$$. This is easily done in $$$O(n)$$$ time.

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

Memory complexity: $$$O(n)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, Mod = 998244353;
int n = 0, s[N] = {}, p[N] = {}, q[N] = {}, r[N] = {};

inline void solve(){
	scanf("%d", &n);
	for(int i = 0 ; i < n ; i ++) scanf("%d", &p[i]);
	for(int i = 0 ; i < n ; i ++) scanf("%d", &q[i]);
	for(int i = 0, j = 0, k = 0 ; k < n ; k ++){
		if(p[k] > p[i]) i = k; if(q[k] > q[j]) j = k;
		if(p[i] != q[j]){
			if(p[i] > q[j]) printf("%d ", (s[p[i]] + s[q[k - i]]) % Mod);
			else printf("%d ", (s[q[j]] + s[p[k - j]]) % Mod);
		}
		else printf("%d ", (s[p[i]] + s[max(q[k - i], p[k - j])]) % Mod);
	}
	printf("\n");
}

int T = 0;

int main(){
	s[0] = 1; for(int i = 1 ; i < N ; i ++) s[i] = s[i - 1] * 2 % Mod;
	scanf("%d", &T);
	while(T --) solve();
	return 0;
}

Try to think about why Gellyfish can always achieve her goal, and ultimately what all the elements will turn into.

When you've figured out Hint 1, try using dynamic programming to reach your goal.

Let $$$g = \gcd(a_1, a_2, \dots, a_n)$$$, It can be shown that eventually all elements become $$$g$$$.

Consider the assumption that eventually all numbers are $$$x$$$. Then for all $$$i$$$, there is $$$x\ |\ a_i$$$; this is because as $$$a_i := \gcd(a_i, a_j)$$$, the new $$$a_i$$$ value will only be a factor of the original. It further follows that $$$x\ |\ g$$$.

Further analysis reveals that $$$x$$$ cannot be less than $$$g$$$, no matter how it is manipulated. Thus we have $$$x = g$$$.

Next we consider that after a certain number of operations, if there exists some $$$a_k$$$ equal to $$$g$$$. In the next operations, for each element $$$a_i$$$ that is not equal to $$$g$$$, we simply choose $$$j=k$$$ and then make $$$a_i := \gcd(a_i, a_k)$$$. After this, all elements will become $$$g$$$.

If $$$g$$$ is initially in $$$a$$$, then the problem is simple; we just need to count the number of elements in $$$a$$$ that are not equal to $$$g$$$.

But if the initial $$$g$$$ is not in $$$a$$$, we are actually trying to make an element equal to $$$g$$$ by minimizing the number of operations.

This is not difficult to achieve through dynamic programming, using $$$f_x$$$ to indicate that it takes at least a few operations to make an element equal to $$$x$$$.

The transition is simple, just enumerate $$$x$$$ from largest to smallest, and then for all $$$i$$$, use $$$f_{x}+1$$$ to update $$$f_{\gcd(x, a_i)}$$$.

But computing $$$\gcd(x, y)$$$ is $$$O(\log x)$$$, a direct transition takes $$$O(n \max(a) \log \max(a))$$$ time. So we need to preprocess this. Let $$$h_{x, y} = \gcd(x, y)$$$, then there is obviously $$$h_{x, y} = h_{y, x \bmod y}$$$. Before all test cases, $$$h$$$ can be preprocessed in $$$O(\max(a)^2)$$$ time complexity.

Time complexity: $$$O(n \max(a))$$$ per test case and $$$O(\max(a)^2)$$$ for preprocessing.

Memory complexity: $$$O(n+\max(a))$$$ per test case and $$$O(\max(a)^2)$$$ for preprocessing.

Try to solve $$$n, a_i \leq 2 \times 10^5$$$ with only one test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 5000 + 5;

inline void checkmax(int &x, int y){
	if(y > x) x = y;
}

inline void checkmin(int &x, int y){
	if(y < x) x = y;
}

int n = 0, m = 0, k = 0, a[N] = {}, f[N] = {};
int g[N][N] = {}, ans = 0;

inline void solve(){
	scanf("%d", &n); m = k = 0;
	for(int i = 1 ; i <= n ; i ++){
		scanf("%d", &a[i]);
		k = g[k][a[i]];
	}
	memset(f, 0x3f, sizeof(f));
	for(int i = 1 ; i <= n ; i ++) a[i] /= k, checkmax(m, a[i]), f[a[i]] = 0;
	for(int x = m ; x >= 1 ; x --) for(int i = 1 ; i <= n ; i ++){
		int y = a[i];
		checkmin(f[g[x][y]], f[x] + 1);
	}
	ans = max(f[1] - 1, 0);
	for(int i = 1 ; i <= n ; i ++) if(a[i] > 1) ans ++;
	printf("%d\n", ans);
}

int T = 0;

int main(){
	for(int x = 0 ; x < N ; x ++) g[x][0] = g[0][x] = g[x][x] = x;
	for(int x = 1 ; x < N ; x ++) for(int y = 1 ; y < x ; y ++) g[x][y] = g[y][x] = g[y][x % y];
	scanf("%d", &T);
	while(T --) solve();
	return 0;
}

Try working backwards from the final sequence, to the initial.

If you're confused about Hint 1, it's probably because the result isn't unique each time. Think carefully about whether you can just take the "tightest" result possible

Let's think of the problem in another way, if we only require that for all $$$i$$$, the final value of $$$c_i$$$ is greater than or equal to $$$b_i$$$, what will be the limitations for all $$$a_i$$$?

It is possible to prove that the restricted form exists as a sequence $$$l$$$. It is sufficient that $$$a_i \geq l_i$$$ for all $$$i$$$.

Next we try to illustrate this thing, we need to work backward from the last operation and observe the restrictions on $$$c$$$ in each step. After the last operation, we have $$$c_i \geq b_i$$$, which means $$$l = b$$$.

Consider an operation that replaces $$$c_z$$$ with $$$\min(c_x, c_y)$$$. If for a post-operation restriction of $$$l$$$, can we recover the pre-operation restriction $$$l'$$$? Let us think as follows:

• It is not difficult to find that for $$$i \notin {x, y, z}$$$, $$$l'_i = l_i$$$.
• $$$l'_z = 0$$$, because the $$$c_z$$$ before the operation is overwritten, it will not actually have any restrictions.
• $$$l'_x = \max(l_x, l_z), l'_y = \max(l_y, l_z)$$$. Since the new $$$c_z$$$ is the original $$$\min(c_x, c_y)$$$, it can be found that for the original $$$c_x$$$, we have $$$c_x \geq \min(c_x, c_y) = c_z \geq l_z$$$, while for $$$y$$$ is symmetric.

We have thus proved that, according to the eventually obtained $$$l$$$, $$$a_i \geq l_i$$$ for all $$$i$$$ is a sufficient condition to eventually make all $$$c_i \geq b_i$$$ for all $$$i$$$ .

And ultimately all $$$c_i = b_i$$$, thus for all $$$i$$$, $$$a_i \geq l_i$$$ is necessary. In fact, we could just take $$$a=l$$$ and do all the operations sequentially to see if we end up with $$$c=b$$$. This is because as $$$a$$$ decreases, eventually $$$c$$$ decreases as well, and by the $$$l$$$ guarantee there is always $$$c_i \geq b_i$$$, so in effect we are trying to minimize all of $$$c$$$, and then minimizing all of $$$a$$$ is clearly an optimal decision.

Time complexity: $$$O(n + q)$$$ per test case.

Memory complexity: $$$O(n + q)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
int n = 0, q = 0, a[N] = {}, b[N] = {}, c[N] = {};
int x[N] = {}, y[N] = {}, z[N] = {};

inline void init(){
	for(int i = 1 ; i <= n ; i ++) a[i] = b[i] = c[i] = 0;
	for(int i = 1 ; i <= q ; i ++) x[i] = y[i] = z[i] = 0;
	n = q = 0;
}

inline void solve(){
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++){
		cin >> b[i];
		c[i] = b[i];
	}
	for(int i = 1 ; i <= q ; i ++) cin >> x[i] >> y[i] >> z[i];
	for(int i = q ; i >= 1 ; i --){
		int v = c[z[i]]; c[z[i]] = 0;
		c[x[i]] = max(c[x[i]], v), c[y[i]] = max(c[y[i]], v);
	}
	for(int i = 1 ; i <= n ; i ++) a[i] = c[i];
	for(int i = 1 ; i <= q ; i ++) c[z[i]] = min(c[x[i]], c[y[i]]);
	for(int i = 1 ; i <= n ; i ++) if(b[i] != c[i]){
		cout << "-1\n";
		return;
	}
	for(int i = 1 ; i <= n ; i ++) cout << a[i] << ' ';
	cout << '\n';
}

int T = 0;

int main(){
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	for(int i = 0 ; i < T ; i ++) init(), solve();
	
	return 0;
}

Try to find an $$$O(nm h^2)$$$ solution using dynamic programming.

Re-examining Gellyfish's strategy, there are definitely situations where she chooses to carry out an attack. Can we divide the $$$m$$$ rounds into two phases by some nature?

Considering all current monsters, if the lowest HP of the monsters is $$$l$$$, Gellyfish can only make at most $$$l-1$$$ "ranged" attacks.

So for each monster, if its HP is $$$h_i$$$, then it must be subject to at least $$$h_i - l$$$ "pointing" attacks. Further, we can see that we only care about $$$l$$$ and $$$\sum\limits_{i=1}^n (h_i - l)$$$.

Consider directly using $$$f_{i, l, x}$$$ to indicate that there are still $$$i$$$ rounds to go, the lowest HP of the monsters is $$$l$$$, and $$$x = \sum\limits_{i=1}^n (h_i - l)$$$, the probability that Gellyfish will reach her goal. This solves the problem within $$$O(nmh^2)$$$, but that's not enough.

Consider the initial HP of all monsters, let $$$l = \min\limits_{i=1}^n h_i, s = \sum\limits_{i=1}^n (h_i - l)$$$. For the first $$$s$$$ times the sword doesn't shine, Gellyfish will obviously launch an attack.

So we using $$$g_{i, j}$$$ to indicate the probability that the sword did not shine exactly $$$j$$$ times in the first $$$i$$$ rounds and the last time the sword did not shine. We then enumerate the $$$s$$$-th time that the sword didn't shine. We can divide the problem into two parts. The first half can be solved using $$$g$$$, while the second half can be solved using $$$f$$$, We just need to merge the results of the two parts, which is not difficult.

When we use f to solve the second part, it is easy to see that initially all monsters have the same HP, and each "pointing" attack can directly attacks the monster with the highest HP, which doesn't make the answer worse. So we have $$$h_i - l \leq 1$$$ for any time, and the range of $$$x$$$ that we actually need is compressed to $$$[0, n)$$$.

Time complexity: $$$O(nmh)$$$ per test case.

Memory complexity: $$$O(nmh)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 22, K = 4000 + 5, M = 400 + 5, Inf = 0x3f3f3f3f;

inline void checkmin(double &x, double y){
	if(y < x) x = y;
}

int n = 0, m = 0, s = 0, k = 0, p0 = 0, h[N] = {};
double p = 0, f[K][K] = {}, g[K][N][M] = {}, ans = 0;

inline void init(){
	for(int i = 0 ; i <= k ; i ++){
		for(int c = 0 ; c < n ; c ++) for(int x = 0 ; x <= m ; x ++) g[i][c][x] = 0;
		for(int x = 0 ; x <= s ; x ++) f[i][x] = 0;
	}
	m = Inf, s = 0, ans = 0;
}

inline void solve(){
	scanf("%d %d %d", &n, &k, &p0);
	p = 1.0 * p0 / 100;
	for(int i = 1 ; i <= n ; i ++){
		scanf("%d", &h[i]); h[i] --;
		m = min(m, h[i]);
	}
	for(int i = 1 ; i <= n ; i ++) s += h[i] - m;
	if(s > k){
	    printf("0.000000\n");
	    return;
	}
	g[0][0][0] = 1;
	for(int i = 1 ; i <= k ; i ++){
		g[i][0][0] = 1;
		for(int x = 1 ; x <= m ; x ++) g[i][0][x] = g[i - 1][0][x - 1] * p + max(g[i - 1][0][x], g[i - 1][n - 1][x - 1]) * (1 - p);
		for(int c = 1 ; c < n ; c ++){
			g[i][c][0] = g[i - 1][c][0] * p + g[i - 1][c - 1][0] * (1 - p);
			for(int x = 1 ; x <= m ; x ++) g[i][c][x] = g[i - 1][c][x - 1] * p + g[i - 1][c - 1][x] * (1 - p);
		}
	}
	f[0][0] = 1;
	for(int i = 0 ; i < k ; i ++) for(int x = 0 ; x < s ; x ++){
		f[i + 1][x] += f[i][x] * p;
		f[i + 1][x + 1] += f[i][x] * (1 - p);
	}
	for(int i = s ; i <= k ; i ++){
		double r = 0;
		for(int x = 0 ; x <= min(i - s, m) ; x ++) r = max(r, g[k - i][0][m - x]);
		ans += r * f[i][s];
	}
	printf("%.6lf\n", ans);
}

int T = 0;

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

Consider if $$$c$$$ consists only of $$$0$$$, this problem turned out to be another classic problem. So you need at least something that you know what it is.

"linear basis" is the answer to Hint 1. Please try to understand this: all addition operations are interpreted as XOR operations.

We can assume that the initial value of $$$x$$$ is $$$\sum a_i$$$. In each step, we can choose to add $$$c_i = a_i + b_i$$$ to $$$x$$$, or do nothing. Each suffix of the sequence can be seen as a subproblem, so we prove inductively that the answer, as a function $$$f(x)$$$ of the initial value of $$$x$$$, is an affine transformation, i.e., $$$f(x) = Ax + b$$$.

When $$$n = 0$$$, this is trivial: $$$f(x) = x$$$.

When $$$n \gt 1$$$, we can choose to add $$$c_i$$$ to $$$x$$$ or not. Let $$$f(x)$$$ denote the answer function from the second operation onward. The two possible outcomes correspond to:

• Not choosing $$$c_i$$$: result is $$$f(x)$$$
• Choosing $$$c_i$$$: result is $$$f(x + c_i) = f(x) + f(c_i) + b$$$.

Although we don't know the exact value of $$$x$$$, $$$f(c_i) + b$$$ is a constant. Suppose the highest set bit in the binary representation of $$$f(c_i) + b$$$ is at position $$$k$$$. Then, the decision of whether to apply this operation depends only on:

1. Whether we want to maximize or minimize the final answer
2. Whether the $$$k$$$-th bit of $$$f(x)$$$ is $$$0$$$ or $$$1$$$

It is easy to observe that the new function $$$g(x)$$$ (before this decision) remains a affine transformation, satisfying $$$g(x) = g(x + c_i)$$$.

Based on the above process, we can represent the answer function $$$f(x)$$$ using a orthogonal basis. Each element in the orthogonal basis represents a vector in the null space of $$$A$$$. Additionally, we keep a tag for each vector, indicating whether it is used to increase or decrease the value of $$$x$$$.

In each iteration, we try to insert $$$c_i$$$ into the linear basis, and associate it with a tag depending on the index $$$i$$$.

Time complexity: $$$O(n \log \max(a, b, x))$$$ per test case.

Memory complexity: $$$O(n + \log \max(a, b, x))$$$ per test case.

#include <bits/stdc++.h>
using i64 = long long;
constexpr int L = 60;
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0);
	int T;
	for(std::cin >> T; T; T --) {
		int n; 
		std::cin >> n;
		std::vector<i64> a(n), b(n);
		std::string str;
		i64 all = 0;
		for(auto &x : a) std::cin >> x, all ^= x;
		for(int i = 0; i < n; i ++) {
			std::cin >> b[i];
			b[i] ^= a[i];
		}
		std::cin >> str;
		std::vector<i64> bas(L);
		std::vector<int> bel(L, -1);
		i64 ans = 0;
		for(int i = n - 1; i >= 0; i --) {
			i64 x = b[i], col = str[i] - '0';
			for(int i = L - 1; i >= 0; i --) if(x >> i & 1) {
				if(bas[i]) {
					x ^= bas[i];
				} else {
					for(int j = i - 1; j >= 0; j --) if(x >> j & 1) {
						x ^= bas[j];
					}
					bas[i] = x;
					for(int j = L - 1; j > i; j --) if(bas[j] >> i & 1){
						bas[j] ^= bas[i];
					} 
					bel[i] = col;
					break;
				}
			}
		} 

		for(int i = L - 1; i >= 0; i --) if(all >> i & 1) {
			all ^= bas[i];
		}
		for(int i = 0; i < L; i ++) if(bel[i] == 1) ans ^= bas[i];
		std::cout << (all ^ ans) << '\n';
	}
	
	return 0;
}

There is an easy way to solve the problem in $$$O(m \max(r) + q)$$$ time complexity. Thus for cases with small $$$r$$$, we can easily solve them, but what about cases with large $$$r$$$?

There is a classic but mistaken greed where we only take the item with the largest $$$\frac w c$$$. This is obviously wrong, but Hint 1 lets us rule out the case where r is small; is there an efficient algorithm that can fix this greed for larger $$$r$$$?

Let $$$s$$$ be any path from vertex $$$1$$$ to vertex $$$p$$$, the vertices that pass through in turn are $$$s_1, s_2, \dots, s_k$$$.

Let $$$z$$$ be the vertex in $$$s$$$ with the largest $$$\frac {w} {c}$$$, and $C = c_z, W = w_z$​.

Let's call your cards you don't get from vertex $$$z$$$ as special cards.

Lemma1. There exists an optimal solution such that the number of special cards does not exceed $$$C$$$.

Proof. Let $$$c'_1, c'_2, \dots, c'_{k'}$$$ be the cost of the special cards, and $$$p'_i = \sum_{j=1}^i {c'}_j$$$. If there exists $$$0 \leq l \lt r \leq k',\ p'_l \equiv p'_r \bmod C$$$, we will get that $$$\sum_{i=l'+1}^{r'} p_i \equiv 0 \bmod C$$$. Then we can replaces these cards with $$$\frac {\sum_{i=l'+1}^{r'} p_i} C$$$ cards from vertex $$$z$$$, the answer won't be worse. Since there are only $$$C+1$$$ values of $$$x \bmod C$$$ for all non-negative integers $$$x$$$, there are no more than $$$C$$$ special cards.

So it's not hard to find the total cost of special cards won't exceed $$$\max(c)^2$$$.

Now we can use dynamic programming to solve this problem:

• $$$dp(u, v, x, 0/1)$$$ means we are current at vertex $$$u$$$, the vertex on the path with the largest $$$\frac {w} {c}$$$ is $$$v$$$, the total cost of the cards is $$$x$$$, we have reached the vertex $$$v$$$ or not, the maximum sum of the power of the cards.

Since the remainder will be filled by cards from $$$v$$$, We just need to find the value of $$$dp(u, v, x)$$$ that satisfies $$$1 \leq x \leq \max(c)^2$$$.

But unfortunately, the time complexity of the algorithm is $$$O(mn\max(c)^2)$$$. It's not fast enough.

At this point you'll find that solving the problem directly becomes incredibly tricky, so we'll try to split it into two problems.

We first consider the following problem: whether there is a better solution when $$$r$$$ is sufficiently large?

We need to broaden the problem, so we try to be able to buy a negative number of cards with the largest $$$\frac {w} {c}$$$.

Doing so would make the answer larger, but when $$$r$$$ is large enough, the answer won't change. Because according to Lemma1, if the total cost of special cards exceed $$$\max(c)^2$$$, there will be a solution that's at least not worse.

Thus when $$$r \gt \max(c)^2$$$, that's the answer of the problem. And we can use another dynamic programming to solve this problem:

• $$$g(u, v, x, 0/1)$$$ means we are current at vertex $$$u$$$, the vertex on the path with the largest $$$\frac {w} {c}$$$ is $$$v$$$, the total cost of the cards is $$$x$$$, we have reached the vertex $$$v$$$ or not, the maximum sum of the power of the cards.

But unlike the original, when $$$x$$$ is equal to or greater than $$$c_v$$$, we remove several cards from vertex $$$v$$$ to make $$$0 \leq x \lt c_v$$$.

The time complexity becomes $$$O(mn \max(c))$$$, now it's fast enough.

For each query, we can just enumerate $$$v$$$ in $$$O(n)$$$ time complexity.

As for $$$r \leq max(c)^2$$$? It's an easy problem:

• $$$f(u, x)$$$ means we are current at vertex $$$u$$$, the total cost of the cards is $$$x$$$, the maximum sum of the power of the cards.

The time complexity is $$$O(m \max(c)^2)​$$$.

For each query, we can get the answer directly from $$$f$$$ in $$$O(1)$$$ time complexity.

Over all, we have solved the problem.

Time complexity: $$$O(mn \max(c) + m \max(c)^2 + qn)$$$

Memory complexity: $$$O(n^2 \max(c) + n \max(c)^2)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 200 + 5, Inf = 0xcfcfcfcfcfcfcfcf;

inline ll sqr(ll x){
	return x * x;
}

inline ll gcd(ll x, ll y){
	if(y) return gcd(y, x % y);
	else return x;
}

inline void checkmax(ll &x, ll y){
	if(y > x) x = y;
}

ll n = 0, m = 0, magic = 0, w[N] = {}, c[N] = {};
ll f[N][N * N] = {}, g[N][N][N][2] = {};
vector<vector<ll> > G(N);

inline void main_min(){
	memset(f, 0xcf, sizeof(f));
	for(ll x = 0 ; x <= magic ; x ++) f[1][x] = 0;
	for(ll u = 1 ; u <= n ; u ++){
		for(ll x = 0 ; x + c[u] <= magic ; x ++) checkmax(f[u][x + c[u]], f[u][x] + w[u]);
		for(ll v : G[u]) for(ll x = 0 ; x <= magic ; x ++) checkmax(f[v][x], f[u][x]);
	}
}

inline void solve_max(ll i){
	ll a = c[i], b = w[i];
	for(ll x = 0 ; x < a ; x ++) g[i][1][x][0] = 0;
	for(ll u = 1 ; u <= n ; u ++){
		if(u == i) for(ll x = 0 ; x < a ; x ++) checkmax(g[i][u][x][1], g[i][u][x][0]);
		else if(w[u] * a > c[u] * b) memset(g[i][u], 0xcf, sizeof(g[i][u]));
		for(ll s = 0, k = gcd(c[u], a) ; s < k ; s ++) for(ll x = s, t = 0 ; t < 2 * (a / k) ; x = (x + c[u]) % a, t ++){
			checkmax(g[i][u][(x + c[u]) % a][0], g[i][u][x][0] + w[u] - ((x + c[u]) / a) * b);
			checkmax(g[i][u][(x + c[u]) % a][1], g[i][u][x][1] + w[u] - ((x + c[u]) / a) * b);
		}
		for(ll v : G[u]) for(ll x = 0 ; x < a ; x ++){
			checkmax(g[i][v][x][0], g[i][u][x][0]);
			checkmax(g[i][v][x][1], g[i][u][x][1]);
		}
	}
}

inline void main_max(){
	memset(g, 0xcf, sizeof(g));
	for(ll i = 1 ; i <= n ; i ++) solve_max(i);
}

int main(){
	scanf("%lld %lld", &n, &m);
	for(ll i = 1 ; i <= n ; i ++){
		scanf("%lld %lld", &c[i], &w[i]);
		magic = max(magic, sqr(c[i]));
	}
	for(ll i = 1, u = 0, v = 0 ; i <= m ; i ++){
		scanf("%lld %lld", &u, &v);
		G[u].push_back(v);
	}
	main_min(), main_max();
	ll q = 0, p = 0, r = 0;
	scanf("%lld", &q);
	while(q --){
		scanf("%lld %lld", &p, &r);
		if(r <= magic) printf("%lld\n", f[p][r]);
		else{
			ll ans = Inf;
			for(ll i = 1 ; i <= n ; i ++){
				ll a = c[i], b = w[i];
				checkmax(ans, g[i][p][r % a][1] + (r / a) * b);
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

We apply block decomposition to the operations, dividing every $$$B$$$ operations into a single round. Within each round, the sequence is partitioned into $$$O(B)$$$ segments. For each segment, we maintain a queue that records all elements added to that segment during the round.

• Type 1 and 2 operations can be handled directly by pushing into the appropriate segment’s queue or toggling a reversal flag.
• Type 3 (deletion) is handled by marking the element $$$x$$$ as deleted without immediately removing it from queues.

At the end of each round, we rebuild the sequence. Specifically, for each position in the sequence, we record which segment it belongs to, and treat the position as containing all elements currently in that segment's queue.

For queries, we process the contribution from each round one by one. In each round:

1. Identify the segment that contains position $$$p$$$.
2. Iterate through the queue of that segment.
3. For each element, if it has been marked as deleted, remove it from the front of the queue and continue; otherwise, consider it as present.

Since each element is inserted and deleted at most once per segment, and each segment has $$$O(1)$$$ amortized processing per round, the total cost per query remains efficient.

We choose $$$B = \sqrt{q}$$$, resulting in $$$O(\sqrt{q})$$$ rounds in total. The total time and space complexity is: $$$O((n + q)\sqrt{q})$$$

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
// template <typename T> T& read(T &x) {
// 	x = 0; int f = 1; char c = getchar();
// 	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
// 	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
// 	return x *= f;
// }
// bool be;
const int N = 1e5 + 1010, B = 500, B1 = N / B + 5, B2 = B + 5;
int n, q, ans, p[N], wp[N], tot, t[N], tl[N], tr[N];
bool rev[N];
bool ed[N];
// bool vv[N];
// struct Q1 {
// 	int tl = 1, tr;
// 	int a[B2];
// 	bool chk() {
// 		return tl <= tr;
// 	}
// 	int front() {
// 		return a[tl];
// 	}
// 	void pop() {
// 		tl++;
// 	}
// 	void push(int x) {
// 		a[++tr] = x;
// 	}
// } tq[N];
// struct Q2 {
// 	int tl = 1, tr;
// 	int a[B1];
// 	bool chk() {
// 		return tl <= tr;
// 	}
// 	int front() {
// 		return a[tl];
// 	}
// 	void pop() {
// 		tl++;
// 	}
// 	void push(int x) {
// 		a[++tr] = x;
// 	}
// } vq[N];
queue <int> tq[N], vq[N];
vector <int> cur;
int qq(int x) {
	while (tq[x].size()) {
		if (!ed[tq[x].front()]) return tq[x].front();
		tq[x].pop();
	}
	return 0;
}
int query(int x) {
	int s = 0;
	for (int i: cur) {
		s += tr[i] - tl[i] + 1;
		if (s >= x) {
			int g = s - x + 1;
			int y;
			if (rev[i]) {
				y = p[tl[i] + g - 1];
			} else {
				y = p[tr[i] - g + 1];
			}
			while (vq[y].size()) {
				int tmp = qq(vq[y].front());
				if (tmp) return tmp;
				vq[y].pop();
			}
			// int tmp = qq(i);
			// if (~tmp) return tmp;
			return qq(i);
		}
	}
	assert(false);
	// return -1;
}
// bool ee;
// int cnt = 0;
signed main() {
	ios::sync_with_stdio(0); // don't use puts
	cin.tie(0), cout.tie(0);
	// debug << abs(&ee - &be) / 1024 / 1024 << endl;
	cin >> n >> q;
	F(i, 1, n) p[i] = i;
	cur.push_back(++tot);
	tl[1] = 1, tr[1] = n;
	F(i, 1, q) {
		int f, x, y; cin >> f >> x >> y;
		if (f == 3) {
			x = (x + ans - 1) % q + 1;
		} else {
			x = (x + ans - 1) % n + 1;
		}
		y = (y + ans - 1) % n + 1;
		// auto split = [&] (int x) {
		// 	if (x > n || vv[x]) return;
		// 	// vv[x] = true;
		// 	for (auto [])
		// };
		if (f == 1) {
			int s = 0;
			for (int j: cur) {
				int w = tr[j] - tl[j] + 1;
				s += w;
				if (s >= x) {
					if (s > x) {
						tot++;
						tq[tot] = tq[j];
						int g = s - x;
						if (rev[tot] = rev[j]) {
							tl[tot] = tl[j];
							tr[tot] = (tl[j] += g) - 1;
						} else {
							tr[tot] = tr[j];
							tl[tot] = (tr[j] -= g) + 1;
						}
						cur.insert(next(find(all(cur), j)), tot);
					}
					tq[j].push(i);
					break;
				}
				tq[j].push(i);
			}
		}
		if (f == 2) {
			int s = 0, sz = 0;
			for (int j: cur) {
				sz++;
				int w = tr[j] - tl[j] + 1;
				s += w;
				if (s >= x) {
					if (s > x) {
						tot++;
						tq[tot] = tq[j];
						int g = s - x;
						if (rev[tot] = rev[j]) {
							tl[tot] = tl[j];
							tr[tot] = (tl[j] += g) - 1;
						} else {
							tr[tot] = tr[j];
							tl[tot] = (tr[j] -= g) + 1;
						}
						cur.insert(next(find(all(cur), j)), tot);
					}
					reverse(cur.begin(), cur.begin() + sz);
					F(j, 0, sz - 1) rev[cur[j]] ^= true;
					break;
				}
			}
		}
		if (f == 3) {
			if (x < i) ed[x] = true;
		}
		cout << (ans = query(y)) << '\n';
		if (cur.size() >= B) {
			int cnt = 0;
			for (int j: cur) {
				if (rev[j]) {
					DF(k, tr[j], tl[j]) {
						vq[wp[++cnt] = p[k]].push(j);
					}
				} else {
					F(k, tl[j], tr[j]) {
						vq[wp[++cnt] = p[k]].push(j);
					}
				}
			}
			F(j, 1, n) {
				p[j] = wp[j];
			}
			cur.clear();
			cur.push_back(++tot);
			tl[tot] = 1, tr[tot] = n;
		}
		// for (int j: cur) {
		// 	debug << tl[j] << " " << tr[j] << " " << rev[j] << endl;
		// }
	}
	return 0;
}

We consider using leafy persistent balanced trees to maintain the sequence. At each non-leaf node, we store a set $$$S_u$$$ as a lazy tag, indicating that every set in the subtree rooted at $$$u$$$ contains $$$S_u$$$. However, since $$$|S_u|$$$ can be large, it's difficult to push down the tag efficiently.

To address this, we split each set $$$S_u$$$ into two components:

1. $$$T_u$$$: A part of $$$S_u$$$ stored directly at node $$$u$$$
2. A collection of child nodes $$$v_{u,1}, v_{u,2}, \cdots, v_{u,k}$$$, each storing a subset of $$$S_u$$$

We maintain the invariant: $$$S_u = T_u + \sum_{i=1}^k S_{v_{u,i}}$$$.

Thus, we make the balanced tree persistent. When we create a new node $$$u$$$ and initialize its children as $$$ls(u)$$$ and $$$rs(u)$$$, we add $$$u$$$ into both $$$v_{ls(u)}$$$ and $$$v_{rs(u)}$$$. During split and merge, we do not modify $$$T_u$$$, which ensures these operations still run in logarithmic time.

1. Type 1 (Insert): We split the balanced tree into two parts. Let the root of the first part be $$$rt$$$, and simply add an element into $$$T_{rt}$$$.
2. Type 2 (Reverse a segment): Just mark the root of the relevant subtree with a "reverse" flag.
3. Type 3 (Delete): Since each element $$$x$$$ appears in only one $$$T$$$, we can directly remove it from that node's $$$T$$$.

For queries, We first locate the leaf node $$$u$$$. To compute $$$S_u$$$, we need to compute all $$$S_{v_{u,i}}$$$. Due to persistence, we can guarantee: $$$\max(S_{v_{u,i}}) \lt \min(S_{v_{u,i+1}})$$$

Thus, we can sequentially check whether each $$$S_{v_{u,i}}$$$ is empty.

We process this recursively. Every time we encounter a node $$$x$$$ with $$$S_x = \emptyset$$$ and $$$x$$$ is not part of the latest tree version, then $$$S_x$$$ will always be empty, and we can safely delete $$$x$$$. During a query, we encounter three types of nodes:

• Nodes with $$$|S_x| \ne 0$$$: We only encounter one such node per query — this is where we find the minimum value.
• Nodes with $$$|S_x| = 0$$$ and $$$x$$$ not in the latest tree: These nodes are deleted. Since the total number of persistent nodes is $$$O(q \log n)$$$, these nodes also appear at most that many times.
• Nodes with $$$|S_x| = 0$$$ and $$$x$$$ in the latest tree: These are ancestors of leaf $$$u$$$, so there are at most $$$O(\log n)$$$ of them per query.

Why can we just do $$$O(\log n)$$$ rounds of recursion? Because we replace all the nodes we pass through on the path, so the size of the subtree doesn't change from the time the node is created to the time it is removed from the tree. Furthermore, if we recurse from node $$$u$$$ to node $$$v$$$, this means that $$$v$$$ is the parent of $$$u$$$ at least at some point on the WBLT. Since the WBLT is weight-balanced, the size of the $$$v$$$ subtree is actually at least a constant multiple of the size of the $$$u$$$ subtree, and this constant greater than $$$1$$$ will be based on your WBLT.

Time complexity: $$$O(q \log n + n)$$$.

Memory complexity: $$$O(q \log n + n)$$$.

#include <bits/stdc++.h>
constexpr int N = 3e5 + 10, S = 1.1e7, SS = 2 * S;
int n, q;
int next[SS], val[SS], cnt;
struct queue {
	int head, tail;
	void push(int x) {
		if(head) {
			next[tail] = ++ cnt, val[cnt] = x; tail = cnt;
		} else {
			head = tail = ++ cnt, val[cnt] = x;
		}
		assert(cnt < SS - 100);
	}
	void pop() {head = next[head];}
	int front() {return val[head];}
	bool check() {return head == tail;}
	bool empty() {return head == 0;}
	void clear() {head = tail = 0;}
};
struct node {
	int ls, rs;
	queue fa;
	int val, exit;
	int size, rev;
}a[S];
int tot;
int id[N];
void pushup(int u) {
	a[u].size = a[a[u].ls].size + a[a[u].rs].size;
}
void setR(int u) {
	a[u].rev ^= 1;
	std::swap(a[u].ls, a[u].rs);
}
void setT(int u, int v) {
	a[u].fa.push(v);
}
void pushdown(int u) {
	if(a[u].rev) {
		setR(a[u].ls);
		setR(a[u].rs);
		a[u].rev = 0;
	}
}
int newnode() {
	int u = ++ tot;
	a[u].exit = 2;
	return u;
}
int newleaf() {
	int u = newnode();
	a[u].size = 1;
	return u;
}
int join(int x, int y) {
	int u = newnode();
	a[u].ls = x, a[u].rs = y;
	a[x].fa.push(u);
	a[y].fa.push(u);
	pushup(u);
	return u;
}
auto cut(int x) {
	pushdown(x);
	a[x].exit = 1;
	return std::make_pair(a[x].ls, a[x].rs);
}
int get_val(int u) {
	if(a[u].exit == 0) return 0;
	if(a[u].val != 0) return a[u].val;
	if(a[u].fa.empty()) return 0;
	int ans = 0;
	while(1) {
		ans = get_val(a[u].fa.front());
		if(ans) return ans;
		if(a[u].fa.check()) break;
		a[u].fa.pop();
	}
	if(a[u].exit == 1) {
		a[u].exit = 0;
		a[u].fa.pop();
		a[u].fa.clear();
	}
	return 0;
}
int newtag(int x) {
	int u = ++ tot;
	a[u].val = x;
	a[u].exit = 1;
	return u;
}
constexpr double ALPHA = 0.292;
bool too_heavy(int sx, int sy) {
	return sy < ALPHA * (sx + sy);
}
int merge(int x, int y) {
	if(!x || !y) return x + y;
	if(too_heavy(a[x].size, a[y].size)) {
		auto [u, v] = cut(x);
    	if(too_heavy(a[v].size + a[y].size, a[u].size)) {
    		auto [z, w] = cut(v);
    		return merge(merge(u, z), merge(w, y));
   		} else {
    		return merge(u, merge(v, y));
    	}
  	} else if(too_heavy(a[y].size, a[x].size)) {
		auto [u, v] = cut(y);
		if(too_heavy(a[u].size + a[x].size, a[v].size)) {
			auto [z, w] = cut(u);
			return merge(merge(x, z), merge(w, v));
		} else {
			return merge(merge(x, u), v);
		}
	} else {
		return join(x, y);
	}
}
std::pair<int, int> split(int x, int k) {
	if(!x) return {0, 0};
	if(!k) return {0, x};
	if(k == a[x].size) return {x, 0};
	auto [u, v] = cut(x);
	if(k <= a[u].size) {
		auto [w, z] = split(u, k);
		return {w, merge(z, v)};
	} else {
		auto [w, z] = split(v, k - a[u].size);
		return {merge(u, w), z};
	}
}
int find(int u, int k) {
	if(a[u].size == 1) return u;
	pushdown(u);
	if(k <= a[a[u].ls].size) return find(a[u].ls, k);
	else return find(a[u].rs, k - a[a[u].ls].size);
}
int build(int n) {
	if(n == 1) return newleaf();
	int x = build(n / 2);
	int y = build(n - n / 2);
	return join(x, y);
}
int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> q;
	int rt = build(n);
	int lastans = 0;
	for(int i = 1; i <= q; i ++) {
		int o;
		std::cin >> o;
		if(o == 1) {
			int p;
			std::cin >> p;
			p = (p + lastans - 1) % n + 1;
			auto [A, B] = split(rt, p);
			setT(A, id[i] = newtag(i));
			rt = merge(A, B);
		} else if(o == 2) {
			int p;
			std::cin >> p;
			p = (p + lastans - 1) % n + 1;
			auto [A, B] = split(rt, p);
			setR(A);
			rt = merge(A, B);
		} else if(o == 3) {
			int x;
			std::cin >> x;
			x = (x + lastans - 1) % q + 1;
			a[id[x]].exit = 0;
		} 
		int p;
		std::cin >> p;
		p = (p + lastans - 1) % n + 1;
		int u = find(rt, p);
		std::cout << (lastans = get_val(u)) << '\n';
	}
	return 0;
}

1. Kevin114514

2. jiangly

3. ksun48

4. ecnerwala

5. Nachia

1. ricefruit

2. last_warning

3. liudiao

4. Scean_Tong

5. randomp

A. Dominater069

B. maspy

C. Kevin114514

D. yosupo

E. Nachia

F1. qwef_ (after the contest)

F2. Nachia (after the contest)

A. Hriz

B. Ethan_Hunt_96

C. ElPelao

D. shivamsaktawat002991

E. liudiao

F. Yr2X

Yet Another Jellyfish and Mex

You are given an array of $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$, satisfying $$$\max(a) \lt m$$$.

Let $$$v$$$ be a variable that is initialized to $$$0$$$, Jellyfish will perform the following operation until $$$a$$$ is empty:

• Select a number $$$z$$$ satisfying $$$1 \leq z \leq k$$$ and select $$$z$$$ indices $$$i_1, i_2, \dots, i_z$$$ ($$$1 \leq i_1 \lt i_2 \lt ... \lt i_z \leq |a|$$$), then delete $$$a_{i_1}, a_{i_2}, \dots, a_{i_z}$$$ from $$$a$$$.
• add $$$\operatorname{MEX}(a)^{\dagger}$$$ to $$$v$$$.

Now Jellyfish wants to know the minimum possible final value of $$$v$$$ if he performs all the operations optimally.

$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
• The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
• The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not.

Input

The first line of each test contains three single integers $$$n\ (m \leq n \leq 10^8), m(1 \leq m \leq 2 \times 10^5), k(1 \leq k \leq 500)$$$.

Due to excessive input volume, we do not directly input $$$a$$$, but for each $$$x (0 \leq x \lt m)$$$, input the number of occurrences of $$$x$$$ in $$$a$$$.

The next line contains $$$m$$$ numbers $$$c_1, c_2, \dots, c_{m-1}\ (0 \leq c_i \leq n, \sum_{i=1}^n{c_i}=n)$$$. — the number of occurrences of $$$x$$$ in $$$a$$$.

It can prove that the order of the values is not important in $$$a$$$.

Output

Output a single integer. — the minimum possible final value of $$$v$$$.

Similar to the tutorial of 1875D - Jellyfish and Mex, We only care about the operation before $$$\text{MEX}(a)$$$ reaches $$$0$$$.

By using greedy we know that each time we should try to delete as many numbers as possible, which means every time we will delete $$$\min(|a|, k)$$$ values of $$$a$$$.

Lemma1. If $$$i \lt j$$$ and $$$c_i \leq c_j$$$, we won't delete $$$j$$$ from $$$a$$$.

Proof. Similar to the tutorial of 1875D - Jellyfish and Mex, if we have deleted $$$j$$$, we will delete all of $$$j$$$ in $$$a$$$, then make $$$\text{MEX}(a)$$$ to $$$j$$$, but because $$$c_i \leq c_j$$$, we can delete all of $$$i$$$ instead of $$$j$$$ in the same number of operations, but the $$$\text{MEX}(a)$$$ will become $$$i$$$, which is better than $$$j$$$.

Because $$$1 + 2 + \dots + \sqrt{2n} \gt n$$$, and according to Lemma1, there will be only $$$\min(\sqrt{2n}, m)$$$ possible values we will delete.

Lemma2. Every operation, there are at most two values of numbers we will delete. And if we delete two values of numbers, let's call them $$$x$$$ and $$$y$$$ $$$(x \lt y)$$$. We will delete all of $$$y$$$, and we can't delete all of $$$x$$$ in the operation.

Proof. For each operation, if we delete all the numbers of value $$$x$$$, we will have no need to delete $$$y$$$ satisfying $$$x \lt y$$$, because we have removed all of $$$x$$$, so $$$y$$$ will no longer have an effect on $$$\text{MEX}(a)$$$. And also, let's consider the next value of $$$\text{MEX}(a)$$$ after this operation, let's call it $$$x'$$$, except the value of the $$$\text{MEX}(a)$$$ after this operation, We won't delete other values except $$$x'$$$, because the deletion of these numbers can be delay to the operations after $$$\text{MEX}(a)$$$ reaches $$$x'$$$.

Now we can use dynamic programming to solve the problem. Let's define $$$dp(i, x)$$$ means the $$$\text{MEX}(a)$$$ after next operation will be $$$i$$$, and the number of $$$i$$$ in $$$a$$$ is $$$x$$$. We can't enumerate directly for transition, it's $$$O(\min(n, m^2) \times k)$$$, so we can use Convex Hull Optimisation to solve this problem. for each $$$x$$$, we build a convex of $$$(i, dp(i, x))$$$, Since both $$$c_i$$$ and $$$i$$$ are monotone while transiting, so we can use two pointers instead of binary searching.

Time complexity: $$$O(\min(\sqrt n, m) \times k)$$$

Memory complexity: $$$O(\min(\sqrt n, m) \times k)$$$

We can use one tool each time the timer reaches to $$$1$$$, then the answer will be $$$\sum_{i=1}^n \min(a - 1, x_i) + b$$$. This can prove to be optimal. Because for each tool, if we use it when the timer is $$$c$$$, its contribution to the answer is $$$\min(x_i, a - c)$$$. We can't use the tool when the timer is less than or equal to $$$0$$$ because the bomb will explode before that, so $$$c=1$$$ is the optimal.

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

Memory complexity: $$$O(1)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

int n = 0, a = 0, b = 0;
long long ans = 0;

inline void solve(){
	scanf("%d %d %d", &a, &b, &n);
	ans = b;
	for(int i = 0, x = 0 ; i < n ; i ++){
		scanf("%d", &x);
		ans += min(a - 1, x);
	}
	printf("%lld\n", ans);
}

int T = 0;

int main(){
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) solve();
	return 0;
}

Let us define $$$\min(a)$$$ to be the minimum value of $$$a$$$ in the current round, $$$\max(a)$$$ to be the maximum value of $$$a$$$ in the current round, $$$\min(b)$$$ to be the minimum value of $$$b$$$ in the current round, $$$\max(b)$$$ to be the maximum value of $$$b$$$ in the current round, $$$\text{MIN}$$$ to be the minimum value of all the apples, $$$\text{MAX}$$$ to be the maximum value of all the apples.

By greedy and induction, we would come to the following conclusion:

• If Jellyfish is the one operating this round: If $$$\min(a) \lt \max(b)$$$, she will swap this two apples, otherwise she will do nothing.
• If Gellyfish is the one operating this round: If $$$\max(a) \gt \min(b)$$$, he will swap this two apples, otherwise she will do nothing.

We consider who $$$\text{MAX}$$$ and $$$\text{MIN}$$$ will belong to after the first round.

In the first round:

• If $$$\max(a) \lt \max(b)$$$, $$$\text{MAX} = \max(b)$$$. And because $$$\min(a) \lt \max(b)$$$, Jellyfish will swap this two apples. So $$$\text{MAX}$$$ belongs to Jellyfish.
• If $$$\max(a) \gt \max(b)$$$, $$$\text{MAX} = \max(a)$$$. If $$$\min(a)=\max(a)$$$, then $$$\min(a) \gt \max(b)$$$, Jellyfish will do nothing. Otherwise Jellyfish won't swap the apple with value $$$\text{MAX}$$$. In conclusion $$$\text{MAX}$$$ belongs to Jellyfish

We can also show that $$$\text{MIN}$$$ belongs to Gellyfish, and the proof is symmetric with the above.

So in the second round, $$$\min(b) = \text{MIN}, \max(a) = \text{MAX}$$$, We have $$$\text{MIN} \lt \text{MAX}$$$. So Gellyfish will swap this two apples, in the third round, $$$\min(a)=\text{MIN}, \max(b) = \text{MAX}$$$, Jellyfish will swap this two apples.

So after the first round, the game will go two rounds at a time, with two people swapping two apples with the minimum value and the maximum value back and forth.

So we only need to know the answer for $$$k = 1$$$ and $$$k = 2$$$.

Time complexity: $$$O(n + m)$$$ per test case.

Memory complexity: $$$O(n + m)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 1000 + 5;
int n = 0, m = 0, k = 0, x = 0, y = 0, a[N] = {}, b[N] = {};

inline void solve(){
	scanf("%d %d %d", &n, &m, &k); k --;
	for(int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);
	for(int i = 0 ; i < m ; i ++) scanf("%d", &b[i]);
	x = y = 0;
	for(int i = 1 ; i < n ; i ++) if(a[i] < a[x]) x = i;
	for(int i = 1 ; i < m ; i ++) if(b[i] > b[y]) y = i;
	if(b[y] > a[x]) swap(a[x], b[y]);
	if(k & 1){
		x = 0, y = 0;
		for(int i = 1 ; i < n ; i ++) if(a[i] > a[x]) x = i;
		for(int i = 1 ; i < m ; i ++) if(b[i] < b[y]) y = i;
		swap(a[x], b[y]);
	}
	long long ans = 0;
	for(int i = 0 ; i < n ; i ++) ans += a[i];
	printf("%lld\n", ans);
	
}

int T = 0;

int main(){
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) solve();
	return 0;
}

Firstly, if $$$n \geq m$$$, we can make the problem transform $$$n \lt m$$$ by giving each person an apple at a time until there are not enough apples.

We can calculate the mass of apples that each person ends up with as $$$\frac n m$$$.

Since it's cut in half every time, if $$$\frac m {\gcd(n, m)}$$$ is not an integral power of $$$2$$$, there's no solution.

Since the number of apple pieces is added to exactly $$$1$$$ for each cut, So we just need to minimize the final number of apple pieces.

As the problem is transformed, $$$\frac n m$$$ is less than $$$1$$$, and $$$\frac m {\gcd(n, m)}$$$ is an integral power of $$$2$$$. So we can uniquely find a set of positive integers $$$S$$$ satisfying $$$\frac n m = \sum_{i \in S} \frac 1 {2^i}$$$. And this method can be proven to be optimal, if we find another multiset $$$T$$$ satisfying $$$S \neq T$$$, for every element $$$x$$$ that appears twice or more, We can make the answer better by removing two $$$x$$$ at a time from $$$T$$$ and adding one $$$x - 1$$$ to $$$T$$$. By repeating this process, eventually $$$T$$$ will become $$$S$$$.

We can use $$$\text{std::__builtin_popcount()}$$$ to get $$$|S|$$$, the answer is $$$m \times |S|-n$$$.

Time complexity: $$$O(\log m)$$$ per test case.

Memory complexity: $$$O(1)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

int n = 0, m = 0;

inline void solve(){
	scanf("%d %d", &n, &m); n %= m;
	int a = n / __gcd(n, m), b = m / __gcd(n, m);
	if(__builtin_popcount(b) > 1) printf("-1\n");
	else printf("%lld\n", 1ll * __builtin_popcount(a) * m - n);
}

int T = 0;

int main(){
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) solve();
	return 0;
}

We only care about the operation before $$$\text{MEX}(a)$$$ reaches $$$0$$$, because after that, $$$m$$$ will never change.

Lemma. Before $$$\text{MEX}(a)$$$ reaches $$$0$$$, we will choose a positive integer $$$x$$$ at a time that satisfies $$$x \lt \text{MEX}(a)$$$, and delete all $$$x$$$ from $$$a$$$, the $$$\text{MEX}(a)$$$ will become $$$x$$$.

Proof. Because if $$$x \gt \text{MEX}(a)$$$, we can place this operation after the $$$\text{MEX}(a)$$$ becomes $$$0$$$, if we don't delete all of $$$x$$$, $$$\text{MEX}(a)$$$ won't change, we can also put this operation later.

So before $$$\text{MEX}(a)$$$ reaches $$$0$$$, the $$$x$$$ we delete is non-increasing.

It means we can solve this problem by dynamic programming. Let $$$dp_i$$$ represents when $$$\text{MEX}(a)=i$$$, and we haven't delete any $$$x$$$ satisfying $$$x \lt i$$$,the minimum value of $$$m$$$.

Let $$$c_i$$$ represents the number of times $$$i$$$ appears in $$$a$$$, the transition is: $$$\forall j \lt i, dp_j \leftarrow dp_i + i \times (c_j - 1) + j$$$.

Time complexity: $$$O(n^2)$$$ per test case.

Memory complexity: $$$O(n)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 5000 + 5, Inf = 0x3f3f3f3f3f3f3f3f;
ll n = 0, m = 0, a[N] = {}, dp[N] = {};

inline void init(){
	for(ll i = 0 ; i <= n ; i ++) a[i] = 0, dp[i] = Inf;
	n = m = 0;
}

inline void solve(){
	scanf("%lld", &n);
	for(ll i = 1, x = 0 ; i <= n ; i ++){
		scanf("%lld", &x);
		if(x < n) a[x] ++;
	}
	while(a[m]) m ++;
	dp[m] = 0;
	for(ll i = m ; i >= 1 ; i --) for(ll j = 0 ; j < i ; j ++) dp[j] = min(dp[j], dp[i] + i * a[j]);
	printf("%lld\n", dp[0] - m);
}

ll T = 0;

int main(){
	memset(dp, 0x3f, sizeof(dp));
	scanf("%lld", &T);
	for(ll i = 0 ; i < T ; i ++) init(), solve();
	return 0;
}

First of all, since $$$\text{and}, \text{or}, \text{xor}$$$ are all bitwise operations, each bit is independent of the other.

We define $$$a_i$$$ as the $$$i$$$-th bit of $$$a$$$, $$$b_i$$$ as the $$$i$$$-th bit of $$$b$$$, $$$c_i$$$ as the $$$i$$$-th bit of $$$c$$$, $$$d_i$$$ as the $$$i$$$-th bit of $$$d$$$, $$$m_i$$$ as the $$$i$$$-th bit of $$$m$$$, $$$x_i$$$ as the $$$i$$$-th bit of $$$x$$$, $$$y_i$$$ as the $$$i$$$-th bit of $$$y$$$. (in binary)

Lemma. For all $$$i \neq j$$$, if $$$(a_i, b_i, m_i) = (a_j, b_j, m_j)$$$ and $$$(c_i, d_i) \neq (c_j, d_j)$$$, the goal cannot be achieved.

Proof. Because after every operation we will have $$$(x_i, y_i) = (x_j, y_j)$$$, so we can't achieve he goal.

Since $$$(a_i, b_i, m_i)$$$ has only $$$2^3=8$$$ cases, and $$$(c_i, d_i)$$$ has only $$$2^2=4$$$ cases, and there are some $$$(0/1, 0/1, 0/1)$$$ that do not appear in $$$\{(a_i, b_i, m_i)\ |\ 0 \leq i \leq \log \max(a, b, c, d, m)\}$$$, so there are only $$$(4+1)^8 \lt 4\times 10^5$$$ cases in this problem. We can use BFS(breadth-first search) for preprocessing.

Time complexity: $$$O(5^8)$$$ for preprocessing and $$$O(\log \max(a, b, c, d, m))$$$ per test case.

Memory complexity: $$$O(5^8)$$$ for preprocessing and $$$O(1)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int S = 4e5 + 5, Inf = 0x3f3f3f3f;
int pw5[10] = {}, dp[S] = {};
queue<int> Q;

inline void checkmin(int &x, int y){
	if(y < x) x = y;
}

inline int w(int mask, int i){
	return (mask / pw5[i]) % 5;
}

inline int f(int a, int b, int m){
	return (a << 2) | (b << 1) | m;
}

inline int g(int c, int d){
	return (c << 1) | d;
}

inline int work(int mask, int opt){
	int ret = 0;
	for(int a = 0 ; a < 2 ; a ++) for(int b = 0 ; b < 2 ; b ++) for(int m = 0 ; m < 2 ; m ++){
		int x = w(mask, f(a, b, m)), c = x >> 1, d = x & 1;
		if(opt == 1) c = c & d;
		else if(opt == 2) c = c | d;
		else if(opt == 3) d = c ^ d;
		else d = m ^ d;
		ret += pw5[f(a, b, m)] * g(c, d);
	}
	return ret;
}

inline void init(){
	pw5[0] = 1;
	for(int i = 1 ; i <= 8 ; i ++) pw5[i] = pw5[i - 1] * 5;
	memset(dp, 0x3f, sizeof(dp));
	int mask = 0;
	for(int a = 0 ; a < 2 ; a ++) for(int b = 0 ; b < 2 ; b ++) for(int m = 0 ; m < 2 ; m ++) mask += pw5[f(a, b, m)] * g(a, b);
	dp[mask] = 0, Q.push(mask);
	while(Q.size()){
		int s = Q.front(); Q.pop();
		for(int opt = 0 ; opt < 4 ; opt ++){
			int t = work(s, opt);
			if(dp[t] == Inf) dp[t] = dp[s] + 1, Q.push(t);
		}
	}
	for(int mask = 0 ; mask < pw5[8] ; mask ++) for(int i = 0 ; i < 8 ; i ++) if(w(mask, i) == 4){
		for(int x = 1 ; x <= 4 ; x ++) checkmin(dp[mask], dp[mask - x * pw5[i]]);
		break;
	}
}

inline void solve(){
	int A = 0, B = 0, C = 0, D = 0, M = 0, mask = pw5[8] - 1;
	scanf("%d %d %d %d %d", &A, &B, &C, &D, &M);
	for(int i = 0 ; i < 30 ; i ++){
		int a = (A >> i) & 1, b = (B >> i) & 1, c = (C >> i) & 1, d = (D >> i) & 1, m = (M >> i) & 1;
		if(w(mask, f(a, b, m)) == 4) mask -= (4 - g(c, d)) * pw5[f(a, b, m)];
		else if(w(mask, f(a, b, m)) != g(c, d)){
			printf("-1\n");
			return;
		}
	}
	printf("%d\n", (dp[mask] < Inf) ? dp[mask] : -1);
}

int T = 0;

int main(){
	init();
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) solve();
	return 0;
}

Let's solve this problem by dynamic programming, Let $$$f_u$$$ represents the max probability of reaching city $$$n$$$ starting from city $$$u$$$.

The problem is how to transition. for city $$$u$$$, we assume that there are $$$d$$$ roads from city $$$u$$$, the $$$i$$$-th road from city $$$u$$$ is to city $$$v_i$$$.

Let's sort $$$v$$$ by using $$$f_v$$$ as the keyword, with $$$v$$$ with the larger $$$f_v$$$ coming first.

Let's define an array $$$a$$$ of $$$d$$$ elements equals to $$$[f_{v_1}, f_{v_2}, \dots, f_{v_d}]$$$, according to the definition, $$$a$$$ is non-increasing.

That is, next we want to find an optimal solution such that the probability of going to city $$$v_i$$$ is $$$p_i$$$, maximizing the value of $$$\sum_{i=1}^d{a_i \times p_i}$$$.

Tips: the sum of $$$p_i$$$ may not be $$$1$$$, because it is possible to stay at city $$$u$$$ when $$$d$$$ is even.

For two choices of $$$p$$$, $$$p_1$$$ and $$$p_2$$$, Sometimes we can't which is better, for example:

$$$p_1 = [0.6, 0.2, 0.2], p_2 = [0.5, 0.5, 0]$$$

when $$$a=[1.0, 0.2, 0.2]$$$, $$$p_1$$$ is better than $$$p_2$$$. But when $$$a = [1.0, 0.8, 0]$$$, $$$p_2$$$ is better than $$$p_1$$$.

Tips. In fact, when $$$d=3$$$, $$$p$$$ has only one choice $$$[\frac 1 3, \frac 1 3, \frac 1 3]$$$, the above is just a hypothetical to illustrate the problem.

So when can we say, $$$p_1$$$ is always not worse than $$$p_2$$$?

Lemma. If there are two arrays $$$p_1$$$ and $$$p_2$$$, satisfying $$$\forall i \leq d, \sum_{j=1}^i{p_1}_j \geq \sum_{j=1}^i{p_2}_j$$$, $$$p_1$$$ is always not worse than $$$p_2$$$.

Proof. Let's consider $$$a_{d+1}$$$ as $$$0$$$ and define $$$a'_i = a_i - a_{i+1}$$$, $$${p_1'}_i = \sum_{j=1}^i{p_1}_j$$$ and $$${p_2'}_i = \sum_{j=1}^i{p_2}_j$$$, then $$$\sum_{i=1}^d a_i \times {p_1}_i = \sum_{i=1}^d a'_i \times {p_1'}_i, \sum_{i=1}^d a_i \times {p_2}_i = \sum_{i=1}^d a'_i \times {p_2'}_i$$$, Because $$$a$$$ is non-increasing, so $$$a'_i \geq 0$$$, and we have $$$\forall i \leq d, {p_1}_i \geq {p_2}_i$$$, so $$$\sum_{i=1}^d a_i \times {p_1}_i \geq \sum_{i=1}^d a_i \times {p_2}_i$$$.

Now the problem is, there is whether an array $$$p$$$ not worse than any other arrays for for all $$$d$$$.

For $$$d = 1$$$, $$$p = [1.0]$$$ satisfies the condition.

For $$$d = 2$$$, $$$p = [0.5, 0]$$$ satisfies the condition.

What about $$$d \gt 2$$$ ? After they choose the roads for the first time, The size of the problem will become $$$d - 2$$$.

For example, when $$$d = 4$$$, Let's assume Jellyfish choose $$$v_1$$$ for the first time, then there will be $$$4$$$ situations:

1. When Asuka chooses $$$v_1$$$ they will go to $$$v_1$$$.
2. When Asuka chooses $$$v_2$$$, the problem changes into the subproblem with $$$[v_3, v_4]$$$.
3. When Asuka chooses $$$v_3$$$, the problem changes into the subproblem with $$$[v_2, v_4]$$$.
4. When Asuka chooses $$$v_4$$$, the problem changes into the subproblem with $$$[v_2, v_3]$$$.

By calculating, $$$p = [0.25, 0.25, 0.125, 0]$$$, it also satisfies the condition.

Let's define $$$g_k$$$ as the best array $$$p$$$ when $$$d=k$$$, $$$g'_k$$$ as the the probabilities of going to cities except the city Jellyfish choose for the first time. By recursion, we can get $$$g'_k$$$ from $$$g_{k-2}$$$. After that, we insert $$$\frac 1 k$$$ into $$$g'_k$$$, keeping it non-increasing, we will get $$$g_k$$$.

By calculating, we will find $$$\frac 1 k$$$ is always the first element in $$$g_k$$$. So when $$$k \gt 2$$$, we have the following transition:

• $$$g_{k, 1} = \frac 1 k$$$

• $$$\forall 1 \lt i \leq k, g_{k, i} = g_{k-2, i - 2} \times \frac {i - 2} k + g_{k-2, i - 1} \times \frac {k - i} k$$$

In the above we consider $$$g_{k, x}$$$ as $$$0$$$ for all $$$x = 0$$$ or $$$x \gt k$$$.

Because $$$g_{k-2}$$$ satisfies the condition, by greedy and induction we can show that $$$g_k$$$ satisfies the condition.

Time complexity: $$$O(\max(n)^2)$$$ for preprocessing and $$$O(m \log n)$$$ per test case.

Memory complexity: $$$O(\max(n)^2)$$$ for preprocessing and $$$O(m)$$$ per test case.

#include<bits/stdc++.h>

using namespace std;

const int N = 5000 + 5;
int n = 5000, m = 0;
vector<vector<int> > G(N), Gx(N);
long double f[N] = {}, g[N][N] = {};

inline bool cmp(int u, int v){
	return f[u] > f[v];
}

inline void work(int u){
	if(u == n){
		f[u] = 1.00;
		return;
	}
	sort(G[u].begin(), G[u].end(), cmp);
	int k = G[u].size();
	for(int i = 0 ; i < k ; i ++){
		int v = G[u][i];
		f[u] += f[v] * g[k][i + 1];
	}
}

inline void init(){
	for(int u = 1 ; u <= n ; u ++){
		f[u] = 0.00;
		G[u].clear(), Gx[u].clear();
	}
	n = m = 0;
}

inline void solve(){
	scanf("%d %d", &n, &m);
	for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){
		scanf("%d %d", &u, &v);
		if(u != n){
			G[u].push_back(v);
			Gx[v].push_back(u);
		}
	}
	for(int u = n ; u >= 1 ; u --) work(u);
	printf("%.12Lf\n", f[1]);
}

int T = 0;

int main(){
	for(int i = 1 ; i <= n ; i += 2) for(int j = 1 ; j <= i ; j ++) g[i][j] = 1.00 / i;
	for(int i = 2 ; i <= n ; i += 2){
		g[i][1] = 1.00;
		for(int j = 1 ; j <= i ; j ++) g[i][j] /= i;
		if(i + 2 <= n) for(int j = 1 ; j <= i ; j ++) g[i + 2][j + 1] += g[i][j] * (i - j + 1), g[i + 2][j + 2] += g[i][j] * j;
	}
	scanf("%d", &T);
	for(int i = 1 ; i <= T ; i ++) init(), solve();
	return 0;
}

Let's assume that $$$a$$$ is given. We can use dynamic programming to solve the problem.

Let's define $$$f_i$$$ as the expected number of days Jellyfish needs to reach city $$$i$$$ from city $$$0$$$.

We will have:

• $$$f_0=0, f_1=1$$$

• $$$\forall i \gt 1, f_i=f_{i-1}+1+\frac {a_{i-1}} {a_{i-1}+a_i} \times (f_i - f_{i-2})$$$

Let's make it better:

• $$$f_i = f_{i-1} + 1 + \frac {a_{i-1}} {a_i} \times (f_{i-1}-f_{i-2}+1)$$$

What does this inspire us to do? Let's define $$$g_i=f_i-f_{i-1}$$$, then we will get:

• $$$g_1=1$$$

• $$$\forall i \gt 1, g_i = 1 + \frac {a_{i-1}} {a_i} \times (g_{i-1}+1)$$$

By induction, we will find $$$g_i = 1 + 2 \times \sum_{j=1}^{i-1} \frac {a_j} {a_i}$$$. According to the definition, $$$f_n = \sum_{i=1}^n g_n = n + 2 \times \sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$$$.

Then we can use dynamic programming to solve the problem itself.

Let's define $$$s_i = \sum_{j=1}^i a_j$$$, then $$$f_n = n + 2 \times \sum_{i=1}^n \frac{s_{i-1}}{a_i}$$$.

Let's define $$$dp_{i, x}$$$ as the minimum value of $$$\sum_{i=1}^n \frac{s_{i-1}}{a_i}$$$ when $$$s_i = x$$$.

We transit by enumerating the values of $$$a_{i+1}$$$, The transition is: $$$dp_{i+1, x+y} \leftarrow dp_{i, x} + \frac x y$$$.

But the time complexity is $$$O(n m^2)$$$, how can it becomes faster?

Let's take a closer look at $$$\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$$$. If there exists $$$i \lt n$$$ satisfying $$$a_i \gt a_{i+1}$$$. We can swap $$$a_i$$$ and $$$a_{i+1}$$$, the answer will be better! so $$$a$$$ is a non-decreasing array, which means $$$a_i \leq \frac m {n - i + 1}$$$.

Because $$$\sum_{i=1}^n \frac n i$$$ is $$$O(n \log n)$$$, so if we only enumerate the possible values of $$$a_i$$$ the time complexity will be $$$O(m^2 \log m)$$$.

Time complexity: $$$O(m^2 \log m)$$$

Memory complexity: $$$O(nm)$$$

#include<bits/stdc++.h>

using namespace std;

const int N = 3000 + 5;
const long double Inf = 1e18;
int n = 0, m = 0;
long double dp[N][N] = {};

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 0 ; i <= n ; i ++) for(int x = 0 ; x <= m ; x ++) dp[i][x] = Inf;
	dp[0][0] = 0.00;
	for(int i = 1 ; i <= n ; i ++) for(int x = 0 ; x <= m ; x ++) for(int y = 1 ; x + y * (n - i + 1) <= m ; y ++) dp[i][x + y] = min(dp[i][x + y], dp[i - 1][x] + 1.00 * x / y);
	printf("%.12Lf", 2 * dp[n][m] + n);
	return 0;
}

Firstly, if $$$lim \gt \frac {n(n+1)} 2$$$, the answer will be $$$0$$$. So we only need to solve the problem which satisfies $$$lim \leq \frac{n(n+1)} 2$$$.

We can use dynamic programming to solve the problem:

Let's define $$$dp_{i, a}$$$ means the number of the permutations $$$P$$$ of $$$[1, 2, \dots, i]$$$, satisfying $$$\mathrm{fun(P)} = a$$$.

Since only relative rankings are useful, we have the following transition:

• $$$dp_{0, 0} = 1$$$

• $$$\forall i \gt 0, dp_{i, a} = \sum_{j=1}^i \binom {i-1} {j-1} \sum_{b=0}^{a - i} dp_{j - 1, b} \times dp_{i - j, a - b - i}$$$

The time complexity is $$$O(n^6)$$$, because $$$a \leq \frac {i(i+1)} 2$$$, how can it becomes faster?

FFT (Fast Fourier Transform) might come to mind first. If we use FFT instead of enumerating $$$t$$$, The time complexity will become $$$O(n^4 \log n)$$$. This is not enough because $$$n$$$ is large and $$$10^9+7$$$ is not a modulus suitable for NTT (Number-theoretic Transform).

Tips. Also, if you use divide and conquer and FFT, The time complexity will be $$$O(n^3 \text{poly}(\log n))$$$, but because FFT have a big constant factor, this still can't pass the problem.

But we can do something similar to what the FFT does. We define $$$F_i = \sum_{a=1}^{\frac {n(n + 1)} 2} dp_{i, a} \times x^a$$$, then we will have the following transition:

• $$$F_0=1$$$

• $$$F_i = x^i \times \sum_{j=1}^i \binom{i - 1}{j - 1} F_{j-1} \times F_{i-j}$$$

For all $$$1 \leq i \leq n$$$, The degree of $$$F_i$$$ won't exceed $$$\frac {n(n+1)} 2$$$. So if we have $$$\frac{n(n+1)} 2 + 1$$$ points on $$$F_n$$$, We can get $$$F_n$$$ by in time complexity $$$O(n^4)$$$ using Lagrange Interpolation. The only thing we need to do is the dot product of the functions, so the time complexity of the transition is also $$$O(n^4)$$$.

Time complexity: $$$O(n^4)$$$

Memory complexity: $$$O(n^3)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 200 + 5, Mod = 1e9 + 7;

inline ll power(ll x, ll y){
	ll ret = 1;
	while(y){
		if(y & 1) ret = ret * x % Mod;
		x = x * x % Mod, y >>= 1;
	}
	return ret;
}

ll n = 0, k = 0, lim = 0;
ll C[N][N] = {}, pw[N * N][N] = {}, iv[N * N] = {}, ifac[N * N] = {}, dp[N][N * N] = {};
ll a[N * N] = {}, b[N * N] = {}, ans = 0;

int main(){
	scanf("%lld %lld", &n, &k); lim = n * (n + 1) / 2;
	for(ll i = 0 ; i <= n ; i ++){
		C[i][0] = 1;
		for(ll j = 1 ; j <= i ; j ++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
	}
	ifac[0] = 1;
	for(ll x = 0 ; x <= lim ; x ++){
		pw[x][0] = 1;
		if(x) iv[x] = power(x, Mod - 2), ifac[x] = ifac[x - 1] * iv[x] % Mod;
		for(ll i = 1 ; i <= n ; i ++) pw[x][i] = pw[x][i - 1] * x % Mod;
	}
	for(ll x = 0 ; x <= lim ; x ++) dp[0][x] = 1;
	for(ll i = 1 ; i <= n ; i ++){
		for(ll j = 0 ; j < i ; j ++) for(ll x = 0 ; x <= lim ; x ++) dp[i][x] = (dp[i][x] + dp[j][x] * dp[i - 1 - j][x] % Mod * C[i - 1][j]) % Mod;
		for(ll x = 0 ; x <= lim ; x ++) dp[i][x] = dp[i][x] * pw[x][i] % Mod;
	}
	a[0] = 1;
	for(ll i = 0 ; i <= lim ; i ++){
		for(ll x = lim ; x >= 1 ; x --) a[x] = (a[x - 1] + a[x] * (Mod - i)) % Mod;
		a[0] = a[0] * (Mod - i) % Mod;
	}
	for(ll i = 1 ; i <= lim ; i ++) if(dp[n][i]){
		ll w = dp[n][i] * ifac[i] % Mod * ifac[lim - i] % Mod;
		if((lim - i) & 1) w = Mod - w;
		b[0] = a[0] * (Mod - iv[i]) % Mod;
		for(ll x = 1 ; x <= lim ; x ++) b[x] = (a[x] - b[x - 1] + Mod) * (Mod - iv[i]) % Mod;
		for(ll x = k ; x <= lim ; x ++) ans = (ans + b[x] * w) % Mod;
	}
	printf("%lld\n", ans);
	return 0;
}

Let's call a section $$$[l, r]$$$ bad if $$$[p_l, p_{l+1}, \dots, p_{r-1}, p_r]$$$ is a permutation of $$$[l, l + 1, \dots, r - 1, r]$$$ and $$$l \leq r \leq m_l$$$.

Let's call a section $$$[l, r]$$$ primitive if it's a bad section and there are no section $$$[l', r']$$$ satisfying $$$[l', r']$$$ is also a bad section and $$$[l, r]$$$ covers $$$[l', r']$$$.

Lemma. For all primitive sections, none two of them intersect.

Proof. If $$$[l_1, r_1]$$$ is a bad section, $$$[l_2, r_2]$$$ is a bad section and $$$l_1 \lt l_2 \lt r_1 \lt r_2$$$, the section $$$[l_2, r_1]$$$ will also be a bad section, but both $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ covers $$$[l_2, r_1]$$$, so $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ can't be primitive at the same time.

Let's use the principle of inclusion-exclusion and dynamic programming to solve the problem.

Let's define $$$f(l, r)$$$ as the number of $$$p_l, p_{l+1}, \dots, p_{r-1}, p_r$$$ which is a primitive section. By the principle of inclusion-exclusion, we count the ways to fix $$$k$$$ primitive sections in range $$$[l, r]$$$, and arrange the rest arbitrarily.

Then we can define $$$g_{1/2}(l, r, x)$$$ as the number of ways to fix $$$k$$$ ($$$k$$$ is odd/even) primitive sections in range $$$[l, r]$$$, and the number of the positions which doesn't cover by any primitive section is $$$x$$$.

Finally we define $$$g(l, r, x) = g_2(l, r, x) - g_1(l, r, x)$$$, We will have the following transition:

• $$$\forall l \leq r \leq m_l, f(l, r) = \sum_{x=0}^{r-l+1} g(l, r, x) \times x! + f(l, r)$$$

• $$$g(l, r, x) = g(l, r - 1, x - 1) - \sum_{mid=l}^r g(l, mid - 1, x )\times f(mid, r)$$$

Tips. In the transition of $$$f(l, r)$$$, We add $$$f(l, r)$$$ because $$$f(l, r)$$$ contributes to $$$g(l, r, 0)$$$, but it should not contribute to $$$f(l, r)$$$, This problem can be solved by ordering the transitions.

According to the definition, $$$\sum_{x=0}^{n} g(1, n, x) \times x!$$$ is the answer.

Time complexity: $$$O(n^4)$$$

Memory complexity: $$$O(n^3)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 200 + 5, Mod = 1e9 + 7;
ll n = 0, m[N] = {}, fac[N] = {}, f[N][N] = {}, g[N][N][N] = {};

int main(){
	scanf("%lld", &n);
	for(ll i = 1 ; i <= n ; i ++) scanf("%lld", &m[i]);
	if(m[1] == n){
		printf("0");
		return 0;
	}
	fac[0] = 1;
	for(ll i = 1 ; i <= n ; i ++) fac[i] = fac[i - 1] * i % Mod;
	for(ll i = 1 ; i <= n ; i ++) g[i][i - 1][0] = 1;
	for(ll l = n ; l >= 1 ; l --) for(ll r = l ; r <= n ; r ++){
		for(ll x = 1 ; x <= r - l + 1 ; x ++) g[l][r][x] = g[l][r - 1][x - 1];
		for(ll mid = l ; mid < r ; mid ++) if(r <= m[mid + 1]) for(ll x = 0 ; x <= mid - l + 1 ; x ++) g[l][r][x] = (g[l][r][x] + g[l][mid][x] * (Mod - f[mid + 1][r])) % Mod;
		for(ll x = 0 ; x <= r - l + 1 ; x ++) f[l][r] = (f[l][r] + g[l][r][x] * fac[x]) % Mod;
		if(r <= m[l]) g[l][r][0] = (g[l][r][0] + (Mod - f[l][r])) % Mod;
	}
	printf("%lld", f[1][n]);
	return 0;
}

For convenience, let's define $$$k = \max(a, b, x, y)$$$, use operation 1 for "You will get a card with $$$a$$$ HP, and $$$b$$$ damage", operation 2 for "If you have at least one card, choose one of your cards and increase its HP by $$$x$$$" and operation 3 for "If you have at least one card, choose one of your cards and increase its damage by $$$y$$$", operation 4 for "You will get a prop with $$$w$$$ power", operation 5 for "You can choose at most one of your cards and multiply its damage by $$$10^9$$$", "the $$$i$$$-th card" for the card we get from vertex $$$i$$$ (It must be operation 1 on vertex $$$i$$$), "do operation 2/3/5 onto card $$$i$$$" for "When we do this operation 2/3/5, we will choose the card $$$i$$$ and increase his HP or damage".

Let us consider the problem without the operation 5, what's the maximum possible answer. If you want to maximize the the sum of the power of your cards, the answer will not exceeding $$$(100 \times 200)^2 = 4 \times 10^8$$$; If you you want to maximize the the sum of the power of your props, the answer will not exceeding $$$200 \times 10^6 = 2 \times 10^8$$$. Because $$$4 \times 10^8 + 2 \times 10^8 = 6 \times 10^8 \lt 10^9$$$, so the operation $$$n$$$ is the most important. Let's called the card we wil do the operation 5 onto it the "flash card". Let's use meet-in-the-middle, the problem is divided into two subproblems — the game before we get the flash card and the game after we get the flash card.

1. The game after we get the flash card

It's a easy problem, we can use dynamic programming to solve this problem.

Since the most important thing is the HP and damage of the flash card, so we define the following dynamic programming state:

• $$$dp_b(u, a)$$$ means we are current at vertex $$$u$$$, the current HP of the flash card is $$$a$$$, the maximum damage of the flash card.
• $$$dp_c(u, a)$$$ means we are current at vertex $$$u$$$, the current HP of the flash card is $$$a$$$, the damage of the flash card is $$$dp_b(u, a)$$$, the maximum sum of the power of all the other cards and props.

Since $$$a \leq nk$$$, the time complexity of the transition is $$$O(m \times n \times k)$$$.

2. The game before we get the flash card

This is the key of the problem, and since it's much more difficult, we first consider the subproblems of this problem.

I. If the graph is a chain, and all the operation 2 and operation 3 is after the operation 1

Lemma. We will do all the operation 2 onto one of the cards, symmetrically we will also do all the operation 3 onto one of the cards.

Proof. We consider a sequence of operations, let's consider if we do all the operation 1 on the card with the max damage after doing all the operation 2, the answer won't be worse, we can do all the operation 1 onto this card instead, then we make a symmetrical adjustment, the answer won't be worse, and all the operation 2 is done onto one of the cards, all the operation 3 is done onto one of the cards.

II. If the graph is a chain

It's similar to the subproblem I. If we say subproblem I is like a "global max value", then subproblem II is like a "prefix max value".

Let's define $$$p_i$$$ means we will do the operation 2/3 on vertex $$$i$$$ onto the $$$p_i$$$-th card.

Lemma1. If there is a operation 2 on vertex $$$i$$$ and a operation 2 on vertex $$$j$$$, if $$$p_i \lt j \lt i$$$, we will have $$$p_j = p_i$$$.

Proof. Let's consider the final HP and damage of the cards after all the operations. Because we do the operation 2 on vertex $$$i$$$ onto the $$$p_i$$$-th card, for all $$$i' \lt i$$$, the damage of the $$$i'$$$-th card is not larger than the $$$p_i$$$-th card. So for $$$j$$$, if we don't do the operation 2 on vertex j onto the $$$p_i$$$-th card, we can do it onto the $$$p_i$$$-th card instead, the answer won't be worse.

Symmetrically, Lemma1 is also correct for operation 3.

Now we can use dynamic programming to solve the problem, we define the following dynamic programming state:

• $$$f(u, a, b)$$$ means we are current at vertex $$$u$$$, we will do the next several operation 3 onto a card with $$$a$$$ HP after all the operations and we will do the next several operation 2 onto a card with $$$b$$$ damage after all the operations, and this two cards are not the same.
• $$$g(u, a, b)$$$ means we are current at vertex $$$u$$$, We will do the next several operation 2 and operation 3 onto a card currently having $$$a$$$ HP and $$$b$$$ damage.

The time complexity is $$$O(m \times n^2 \times k^2)$$$, but it's not enough.

Lemma2. If a card has $$$a$$$ HP and $$$b$$$ damage after all the operations and it's not the flash card, $$$\min(a, b) \leq k$$$.

Proof. If we use this card as the flash card instead of the last one, and do all the operations done onto the last flash card onto this card, the power of the flash card will be larger. So it won't exist in this half problem.

Now the time complexity becomes $$$O(m \times n \times k^2)$$$, it's still not enough.

Lemma3. Let's define $$$A$$$ as the maximum HP of all the cards except the flash card after all the operations, $$$B$$$ as the maximum damage of all the cards except the flash card after all the operations, $$$\min(A, B) \leq k$$$.

Proof. Let's assume that the $$$i$$$-th card has $$$A$$$ HP after all the operations, the $$$j$$$-th card has $$$B$$$ damage after all the operations and $$$A \gt k, B \gt k$$$. If $$$i = j$$$, it conflicts with Lemma 2; If $$$i \lt j$$$, because of the Lemma 2, the HP of the $$$j$$$-th card after all the operations won't exceed $$$k$$$, let's use $$$A'$$$ as the HP of the $$$j$$$-th card after all the operations, and $$$B \gt k$$$, so we have done some operation 3 onto the $$$j$$$-th card. But because $$$A \gt k \geq A'$$$, if we do these operations onto the $$$i$$$-th card, the answer will be better; If $$$i \gt j$$$, it's symmetric with $$$i \lt j$$$.

But we can make the dynamic programming state better:

• $$$f(u, a, b)$$$ means we are current at vertex $$$u$$$, we will do the next several operation 3 onto a card with $$$a$$$ HP after all the operations and we will do the next several operation 2 onto a card with $$$b$$$ damage after all the operations, and this two cards are not the same.

• $$$g_a(u, a, a')$$$ means we are current at vertex $$$u$$$, we will do the next several operation 3 onto a card with $$$a$$$ HP after all the operations, we will do the next several operation 2 onto a card and totally increase $$$a'$$$ HP in the next several operations to reach it's HP after all the operations.

• $$$g_b(u, b, b')$$$ it's symmetric with $$$g_a$$$, just swap "HP" and "damage".

Let's define $$$A$$$ as the maximum HP of all the cards except the flash card after all the operations, $$$B$$$ as the maximum damage of all the cards except the flash card after all the operations. We will find the $$$a, a', b, b'$$$ in $$$f, g_a, g_b$$$ is $$$O(k)$$$ because if $$$A \leq k$$$, using $$$g_a$$$ we can get the right answer, if $$$B \leq k$$$, using $$$g_b$$$ we can get the right answer.

the time complexity of the transition is $$$O(m \times k^2)$$$.

The transition is very complex, you can see more details in my code : )

In my code, I use $$$g(u)$$$ to make the transition better. When $$$a'$$$ or $$$b'$$$ reaches $$$0$$$, we reaches the vertex $$$u$$$ and there is a operation 1 on vertex $$$u$$$, I don't enumerate the value of the next $$$a$$$ and $$$b$$$ while transiting. I transit it to $$$g(u)$$$ first, and enumerate the value of the next $$$a$$$ and $$$b$$$ together.

III. the problem itself

Since the path is a chain, and we use dynamic programming to solve the problem. There's no difference whether the graph is a chain.

Time complexity: $$$O(m(nk+k^2))$$$

Memory complexity: $$$O(n^2k+nk^2)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 200 + 5;
const ll lim = 1e9;

inline void checkmax(int &x, int y){
	if(y > x) x = y;
}

inline void checkmax(ll &x, ll y){
	if(y > x) x = y;
}

inline void checkmax(pair<int, int> &x, pair<int, int> y){
	if(y > x) x = y;
}

int n = 0, m = 0, k = 0, opt[N] = {}, a[N] = {}, b[N] = {}, w[N] = {};
int f[N][N][N] = {}, g[N] = {}, g_a[N][N][N] = {}, g_b[N][N][N] = {};
pair<int, int> dp[N][N * N] = {};
vector<vector<int> > G(N);

int main(){
	scanf("%d %d", &n, &m);
	for(int u = 1 ; u <= n ; u ++){
		scanf("%d", &opt[u]);
		if(opt[u] == 1) scanf("%d %d", &a[u], &b[u]);
		else if(opt[u] == 2) scanf("%d", &a[u]);
		else if(opt[u] == 3) scanf("%d", &b[u]);
		else if(opt[u] == 4) scanf("%d", &w[u]);
		k = max(k, max(a[u], b[u]));
	}
	for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
	}
	memset(f, -1, sizeof(f));
	memset(g, -1, sizeof(g)), memset(g_a, -1, sizeof(g_a)), memset(g_b, -1, sizeof(g_b));
	memset(dp, -1, sizeof(dp));
	f[1][0][0] = 0;
	for(int u = 1 ; u <= n ; u ++){
		if(opt[u] == 1 && g[u] != -1){
			for(int x = a[u] ; x <= k ; x ++) checkmax(g_a[u][x][x - a[u]], g[u] + x * b[u]);
			for(int x = b[u] ; x <= k ; x ++) checkmax(g_b[u][x][x - b[u]], g[u] + x * a[u]);
			checkmax(dp[u][a[u]], make_pair(b[u], g[u]));
		}
		for(int v : G[u]){
			if(opt[v] == 1){
				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
					if(f[u][x][y] != -1){
						checkmax(f[v][max(x, a[v])][max(y, b[v])], f[u][x][y] + a[v] * b[v]);
						checkmax(g[v], f[u][x][y]);
					}
					if(g_a[u][x][y] != -1){
						checkmax(g_a[v][max(x, a[v])][y], g_a[u][x][y] + a[v] * b[v]);
						if(!y){
							checkmax(g[v], g_a[u][x][y]);
							checkmax(f[v][x][b[v]], g_a[u][x][y] + a[v] * b[v]);
						}
					}
					if(g_b[u][x][y] != -1){
						checkmax(g_b[v][max(x, b[v])][y], g_b[u][x][y] + a[v] * b[v]);
						if(!y){
							checkmax(g[v], g_b[u][x][y]);
							checkmax(f[v][a[v]][x], g_b[u][x][y] + a[v] * b[v]);
						}
					}
				}
				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
					int y = dp[u][x].first, z = dp[u][x].second;
					checkmax(dp[v][x], make_pair(y, z + a[v] * b[v]));
				}
			}
			else if(opt[v] == 2){
				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
					if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + a[v] * y);
					if(g_a[u][x][y] != -1 && y >= a[v]) checkmax(g_a[v][x][y - a[v]], g_a[u][x][y]);
					if(g_b[u][x][y] != -1) checkmax(g_b[v][x][y], g_b[u][x][y] + a[v] * x);
				}
				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
					int y = dp[u][x].first, z = dp[u][x].second;
					checkmax(dp[v][x + a[v]], make_pair(y, z));
				}
			}
			else if(opt[v] == 3){
				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
					if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + x * b[v]);
					if(g_a[u][x][y] != -1) checkmax(g_a[v][x][y], g_a[u][x][y] + x * b[v]);
					if(g_b[u][x][y] != -1 && y >= b[v]) checkmax(g_b[v][x][y - b[v]], g_b[u][x][y]);
				}
				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
					int y = dp[u][x].first, z = dp[u][x].second;
					checkmax(dp[v][x], make_pair(y + b[v], z));
				}
			}
			else{
				for(int x = 0 ; x <= k ; x ++) for(int y = 0 ; y <= k ; y ++){
					if(f[u][x][y] != -1) checkmax(f[v][x][y], f[u][x][y] + w[v]);
					if(g_a[u][x][y] != -1) checkmax(g_a[v][x][y], g_a[u][x][y] + w[v]);
					if(g_b[u][x][y] != -1) checkmax(g_b[v][x][y - b[v]], g_b[u][x][y] + w[v]);
				}
				for(int x = 0 ; x <= n * k ; x ++) if(dp[u][x] != make_pair(-1, -1)){
					int y = dp[u][x].first, z = dp[u][x].second;
					checkmax(dp[v][x], make_pair(y, z + w[v]));
				}
			}
		}
	}
	ll ans = f[n][0][0];
	for(int x = 0 ; x <= n * k ; x ++) if(dp[n][x] != make_pair(-1, -1)){
		int y = dp[n][x].first, z = dp[n][x].second;
		checkmax(ans, lim * x * y + z);
	}
	printf("%lld", ans);
	return 0;
}

1. zhoukangyang

2. tourist

3. Benq

4. Qingyu

5. EvenImage

1. Rapturelike

2. FlyBell

3. rainboy

4. ImaginaryCat

5. WanYuanShenWanDe

A. H_stove

B. tourist

C. ksun48

D. ooOAM

E. RanRankeainie

F. i_will_be_less_than_blue

G. jiangly (after the contest)

A. Azaml

B. Shirotsume

C. viveksingh912

D. kaiboy

E. FlyBell

F. Rapturelike

G. rainboy