You are allowed to delete two elements in any valid subarray, but you only need to keep one.

A lower bound for the answer for each element is $$$2$$$ (or $$$1$$$ if $$$n=1$$$), as if the array size is $$$2$$$ or less, then no operations are even possible.

This bound is achievable for any element in any permutation. We can choose our subarray of size $$$3$$$ arbitrarily. Suppose $$$x$$$ is the value we want to keep in the array. If $$$x$$$ is the minimum element, we can delete the largest element. Otherwise, we can delete the smallest element.

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if n==1:
        print("1\n")
    else:
        for i in range(n):
            print("2 ")
        print("\n")

t = int(input())
for i in range(t):
    solve()

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Since the array consists only of $$$1$$$ and $$$-1$$$, the growth rate of the cumulative sum must be $$$1$$$ or $$$-1$$$. In other words, you can't skip a number. What can you say about a lower bound of the answer from this?

For an array $$$a$$$, denote $$$p_i=a_1+a_2+\ldots+a_i$$$. Define $$$p_0=0$$$. We can see that the sum of the subarray from $$$l$$$ to $$$r$$$ is $$$p_r-p_{l-1}$$$.

Let's lower bound our answer. First, suppose that $$$x \ne y$$$. Without loss of generality that $$$x \ge y$$$ (so $$$p_{x+y} \gt 0$$$). Fix $$$d$$$ to be a divisor of $$$|x-y|$$$. Since our array contains only $$$1$$$ and $$$-1$$$ (and thus $$$p_i$$$ changes by only $$$1$$$ or $$$-1$$$ every time), and that $$$p_0=0$$$ while $$$p_{x+y}=x-y$$$, there must exist an index $$$i$$$ where $$$p_i=d$$$ (this is the discrete version of the Intermediate Value Theorem). Let this index be $$$i_1$$$. By the same logic, there must be an index $$$i_2$$$ between $$$i_1$$$ and $$$x+y$$$ such that $$$p_{i_2}=2\cdot d$$$. Continuing this process, we can see that for every divisor $$$d$$$ of $$$x-y$$$, there must exist at least one valid partition with all subarrays having equal sum. Therefore, a lower bound for the answer is the number of divisors of $$$x-y$$$. The case of $$$x \le y$$$ is analogous.

Then, can we reach this lower bound? It turns out the construction $$$[1, 1, \ldots, 1, -1, -1, \ldots, -1]$$$ reaches this lower bound. For a fixed divisor $$$d$$$, there is only one valid index $$$i$$$ each time, except for $$$x-y$$$, of which there are two indices. However, since the last subarray in the partition must reach $$$n$$$, this doesn't matter to us.

This solves the case for $$$x \ne y$$$. But what about $$$x=y$$$? Our above analysis of Intermediate Value Theorem breaks, as the start and final value are both $$$0$$$. The answer is at least $$$1$$$, since the full array is valid. We can reach this lower bound using the same construction above (as there does not exist any indices other than $$$0$$$ and $$$x+y$$$ with $$$p_i=0$$$).

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    x, y = map(int, input().split())
    s = x - y
    
    a = []
    for _ in range(x):
        a.append(1)
    for _ in range(y):
        a.append(-1)
    
    ans = 0
    for i in range(1, abs(s) + 1):
        if s % i == 0:
            ans += 1
    
    if s == 0:
        ans = 1
    
    print(ans)
    print(*a)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider the cases of $$$k=n$$$ and $$$k=n-1$$$. What do you notice?

Our first observation is that $$$b$$$ has to be a permutation (after replacing all $$$-1$$$'s). This is because since $$$a$$$ is a permutation, and each element appears in at least one valid subarray, if $$$b$$$ is not a permutation then at least one element does not exist in $$$b$$$, meaning that the answer must be no.

It may help to visualize this problem using some examples first:

• If $$$k=n$$$, then the answer is only YES if there are no repeat elements in $$$b$$$.
• What if $$$k=n-1$$$? Now, the requirements are more strict. If you have $$$b_1 \ne a_1$$$, $$$a_1$$$ would need to appear somewhere later. But then this means that in the subarray $$$[2,n-1]$$$, $$$a_1$$$ appears in the subarray in $$$b$$$ but not in $$$a$$$. Similarly, $$$a_n$$$ must be the same as $$$b_n$$$. We can see that the remaining $$$n-2$$$ elements are allowed to be any rearrangement of the middle $$$n-2$$$ elements in $$$a$$$.

Continuing on to $$$k=n-2$$$, using the same logic, we see that the first and last $$$2$$$ elements of $$$a$$$ must match with the first and last $$$2$$$ elements of $$$b$$$, with the middle $$$n-4$$$ numbers being allowed to be anything.

We now see that this forms a pattern: the first $$$n-k$$$ elements and the last $$$n-k$$$ elements in $$$a$$$ and $$$b$$$ must match, and the middle $$$2k-n$$$ elements must be rearrangements of each other. If $$$2k \lt n$$$, then we must have $$$a=b$$$ naturally. Let's now show that it works.

Consider the union of all size $$$k$$$ intervals: starting from $$$[1,k]$$$, then $$$[2,k+1]$$$, and so on. The interval that is inside all of these intervals is the union of $$$[1,k]$$$ and $$$[n-k+1,n]$$$ (intuitively, we can see this is true because $$$[1,k]$$$ is the leftmost interval, and $$$[n-k+1,n]$$$ is the rightmost one. Therefore, any point inside both of these intervals must be shared among all length $$$k$$$ intervals). The length of the intersection is $$$\max(2k-n,0)$$$. Any point not in this common interval must be the same in $$$a$$$ and $$$b$$$, as there exists an interval that doesn't contain it.

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider the transition from the interval $$$[l,r]$$$ to $$$[l+1,r+1]$$$. What do you "gain"? What do you "lose"?

We need to take a different approach from problem C1. Consider transferring from the interval $$$[l,r]$$$ to $$$[l+1,r+1]$$$. In the multiset of $$$b$$$, we need to "lose" the element $$$a_l$$$ and "gain" the element $$$a_r$$$. At first glance, this seems very restrictive: is there even any cases where $$$a_l \ne b_l, a_r \ne b_r$$$ and this can still work out?

In fact, the only other case that doesn't break the condition is if $$$a_l=a_r$$$ and $$$b_l=b_r$$$. Otherwise, you would need $$$b_r$$$ to "recover" the lost element from $$$a_r$$$ and also whatever element was lost at $$$b_l$$$ at the same time, which is impossible (if $$$a_l=a_r$$$, then $$$a_r$$$ "recovered" the element $$$a_l$$$ in the multiset).

This motivates us to split the arrays $$$a$$$ and $$$b$$$ into $$$k$$$ subsequences, depending on their indices modulo $$$k$$$. In each subsequence, if all elements of $$$a$$$ are the same, then all elements of $$$b$$$ must be the same. Otherwise, we must have $$$a_i=b_i$$$ for each index in the subsequence.

There is one more requirement: we need to ensure that the first $$$k$$$ elements of $$$a$$$ and $$$b$$$ can match. Our transition conditions ensure that if $$$[l,r]$$$ works, then $$$[l+1,r+1]$$$ also does. But we would need the "base" interval $$$[1,k]$$$ to work first (this process is much like the process of induction). Once we fill in values of $$$b$$$ that is required in our previous step, all we need to do is ensure that no number in the first $$$k$$$ indices appears more often in $$$b$$$ than $$$a$$$.

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

void solve() {
	int n, k; cin >> n >> k;
	vector<int> a(n), b(n);
	for (auto &x : a) cin >> x;
	for (auto &x : b) cin >> x;
	
	vector<bool> vis(n);
	vector<int> pos(k);
	map<int, int> cnt;
	for (int i = 0; i < k; i++) {
		pos[i] = a[i];
		for (int j = i + k; j < n; j += k) {
			if (pos[i] != a[j]) pos[i] = -1;
		}
		if (pos[i] != -1) cnt[pos[i]]++;
		
		if (pos[i] == -1) {
			for (int j = i; j < n; j += k) {
				if (b[j] != -1 && b[j] != a[j]) {
					cout << "NO" << "\n";
					return;
				}
			}
		}
	}
	
	map<int, int> cnt2;
	vector<int> ans(k);
	for (int i = 0; i < k; i++) {
	if (pos[i] != -1) {
		set<int> d;
		for (int j = i; j < n; j += k)
			d.insert(b[j]);
		d.erase(-1);
		
		if (d.size() >= 2) {
			for (int j = i; j < n; j += k)
				if (b[j] != -1 && b[j] != a[j]) {
					cout << "NO" << "\n";
					return;
				}
		}
		if (d.size() == 1)
			cnt2[*d.begin()]++;
	}
	}
	
	for (auto [k, x] : cnt2) {
		if (x > cnt[k]) {
			cout << "NO" << "\n";
			return;
		}
	}
	
	cout << "YES" << "\n";
	
}

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

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

How is the checker implemented? In other words, given $$$a$$$ find $$$f(a)$$$.

Let $$$\text{cnt}_l$$$ be the number of $$$i$$$ such that $$$a_i$$$ has the bit $$$l$$$ set. $$$f(a)$$$ only depends on the array $$$\text{cnt}$$$.

$$$f(a)_k = \sum\limits_{l = 0}^{28} 2^l \cdot \binom{\text{cnt}_l}{k}$$$.

Look at $$$b_n$$$. This value tells us all the bits $$$l$$$ that have $$$\text{cnt}_l = n$$$.

We can remove all the bits in $$$b_n$$$: for all set bits in $$$b_n$$$ and $$$1 \le k \lt n$$$ set $$$b_k = b_k - \binom{n}{k} \cdot 2^l$$$. After that no bit occurs $$$n$$$ times in $$$a$$$, so set $$$n = n - 1$$$.

Since $$$a$$$ is guaranteed to exist, each bit will be removed at most once, so the time complexity is $$$O(n \log A)$$$.

Given $$$a$$$, how can we find $$$f(a)$$$? Consider each bit separately: assume $$$a_i$$$ is either $$$0$$$ or $$$1$$$. If there are $$$m$$$ ones in $$$a$$$, then $$$f(a)_k = \binom{m}{k}$$$ — the number of ways to pick $$$k$$$ ones from $$$m$$$, since every index in the subsequence has to be a $$$1$$$.

This can be generalized to all $$$a$$$: let $$$\text{cnt}_l$$$ be the number of $$$i$$$ such that $$$a_i$$$ has the bit $$$l$$$ set. $$$f(a)$$$ only depends on the array $$$\text{cnt}$$$, and $$$f(a)_k = \sum\limits_{l = 0}^{28} 2^l \cdot \binom{\text{cnt}_l}{k}$$$.

Now we need to restore $$$a$$$ from $$$f(a)$$$. Look at $$$b_n$$$. This value tells us all the bits $$$l$$$ that have $$$\text{cnt}_l = n$$$.

We can remove all the bits in $$$b_n$$$: for all set bits in $$$b_n$$$ and $$$1 \le k \lt n$$$ set $$$b_k = b_k - \binom{n}{k} \cdot 2^l$$$.

After that no bit occurs $$$n$$$ times, and since $$$f(a)$$$ only depends on the array $$$\text{cnt}$$$, we can assume that $$$n = n - 1$$$ and repeat the same procedure. This way we can uniquely determine the array $$$\text{cnt}$$$.

The only thing left is the actually find any feasible $$$a$$$. We can do that the following way: for all bits $$$l$$$ and $$$i$$$ in $$$[1, \text{cnt}_l]$$$ set the $$$l$$$-th bit in $$$a_i$$$. This $$$a$$$ corresponds to the found array $$$\text{cnt}$$$.

The only concern is the time complexity. However, since the answer is guaranteed to exist we will delete each bit at most once, so the final solution is $$$O(n \log A)$$$.

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int MAX = 2e5 + 5;
const int LG = 29;

int binpow(int x, int n) {
    int ans = 1;
    while(n) {
        if(n & 1) ans = (long long) ans * x % mod;
        n >>= 1;
        x = (long long) x * x % mod;
    }
    return ans;
}

int fact[MAX], inv[MAX];

int C(int n, int k) {
    if(n < k || k < 0) return 0;
    return (long long) fact[n] * inv[k] % mod * inv[n - k] % mod;
}

void solve() {
    int n;
    cin >> n;
    vector<int> b(n);
    for(auto &i : b) {
        cin >> i;
    }
    
    vector<int> cnt(LG);
    for(int i = n - 1; ~i; i--) {
        for(int l = 0; l < LG; l++) {
            if(b[i] >> l & 1) {
                cnt[l] = i + 1;
                
                for(int j = 0; j <= i; j++) {
                    int subtract = (long long) C(i + 1, j + 1) * (1 << l) % mod;
                    b[j] -= subtract;
                    if(b[j] < 0) b[j] += mod;
                }
            }
        }
    }
    
    vector<int> a(n);
    for(int l = 0; l < LG; l++) {
        for(int i = 0; i < cnt[l]; i++) {
            a[i] |= 1 << l;
        }
    }
    for(auto i : a) cout << i << " "; cout << '\n';
}

signed main() {
    fact[0] = 1; for(int i = 1; i < MAX; i++) fact[i] = (long long) fact[i - 1] * i % mod;
    inv[MAX - 1] = binpow(fact[MAX - 1], mod - 2);
    for(int i = MAX - 1; i; i--) inv[i - 1] = (long long) inv[i] * i % mod; assert(inv[0] == 1);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tests = 1;
    cin >> tests;
    for(int test = 0; test < tests; test++) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

The reason why most naive DP approaches fail is because you cannot factorize $$$2\cdot 10^5$$$ numbers of scale $$$10^{18}$$$ fast. How do you avoid this?

The solution to the problem does not change if "each node is covered by exactly one path" was replaced by "each node is covered by at least one path"

Read the hints.

The most naive approach is something like $$$dp(node,x)$$$ to the minimum number of paths used to cover the subtree of $$$node$$$, such that the path from $$$node$$$ has GCD $$$x$$$. With potentially up to $$$d(a_{node})$$$ different states of DP at each node (where $$$d(x)$$$ is the number of divisors of $$$x$$$), this will easily get the Time Limit Exceeded verdict.

However, we take advantage of the fact that in a tree, each node can have only one parent. In other words, there can only be one path going upwards starting at each node. For simplicity, assume that each path must end as a prime number (if the path instead ends with something like $$$6$$$, it is counted as both ending in $$$2$$$ and $$$3$$$). We can then perform a DP like $$$dp(node,x)$$$ being the smallest number of paths to cover the subtree of $$$node$$$, assuming that the path going up from $$$node$$$ is $$$x$$$ (where $$$x$$$ must be prime).

Unfortunately, finding the prime factors of the numbers is still impossible. However, what if we don't need to? Consider a greedy strategy where you extend every path from the children of node $$$x$$$ upwards if the GCD does not become $$$1$$$. (because of our analysis above, the solution to the problem does not change if "each node is covered by exactly one path" is replaced by "each node is covered by at least one path"). While we cannot store all possible values of a path, we can store the LCM of all such paths. It's not hard to show that storing the LCM is functionally the same as storing all possible values of a path.

So the solution is as follows: let $$$dp(x)$$$ represent the minimum number of paths to cover the subtree of $$$x$$$, and let $$$val(x)$$$ be the LCM of all paths that can pass through $$$x$$$. When trying to find the answers for $$$x$$$, we first set $$$val(x)=1$$$. For each child $$$c$$$ of $$$x$$$, set $$$val(x)=\text{LCM}(val(x), val(c))$$$. Set $$$dp(x)$$$ to be the sum of $$$dp(c)$$$, and add $$$1$$$ if $$$val(x)=1$$$ (as well as updating $$$val(x)=a_x$$$). This solution is very simple and runs in $$$O(n \log A)$$$

Since the values of $$$a_i$$$ are large, we must calculate LCM as $$$a/\text{GCD}(a,b)\cdot b$$$ instead of $$$(a\cdot b)/\text{GCD}(a,b)$$$. However, note that the calculations will never overflow $$$64$$$-bit integers, as they are upper bounded by $$$a_i$$$.

As an alternative to maintaining the LCM, you can actually maintain the set of possible GCD values, but ensure that they are pairwise coprime. This solution is expected to run in $$$O(n \log ^2{A})$$$

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=676767677;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int n,dp[N];
ll d[N],v[N];
ll a[N];
void solve() {
	scanf("%d",&n);
	per(i,1,n+1) {
		int k;
		scanf("%lld",&a[i]);
		scanf("%d",&k);
		VI s;
		dp[i]=0;
		bool val=0;
		rep(j,0,k) {
			int x;
			scanf("%d",&x);
			s.pb(x);
			dp[i]+=dp[x];
			d[x]=gcd(v[x],a[i]);
			val|=d[x]>1;
		}
		if (val) {
			ll z=1;
			for (auto x:s) if (d[x]>1) z=lcm(z,d[x]);
			v[i]=z;
		} else {
			dp[i]+=1;
			v[i]=a[i];
		}
		printf("%d\n",dp[i]);
		fflush(stdout);
	}
}

int _;
int main() {
	for (scanf("%d",&_);_;_--) {
		solve();
	}
}

Consider what the contribution of a number is.

Come up with $$$O(nm)$$$ or $$$O(n^2)$$$ solution first. There is an identity that can simplify.

Simulate the binary search so we get the weight of each index. Now, we want to partition it into $$$m$$$ segments (potentially empty) where the weight of each segment is the minimum number that it covers.

Suppose we fix the number $$$x$$$, as well as the interval that it covers $$$[l,r]$$$. This means that we need to cover the interval $$$[1,l-1]$$$ with the numbers $$$1$$$ through $$$x-1$$$, and the interval $$$[r+1,n]$$$ with the numbers $$$x+1$$$ through $$$m$$$. Denote $$$y=m-x$$$. Then, using stars and bars, we get the number of ways to fill other numbers as:

This sum is to be taken over all $$$x$$$ from $$$2$$$ to $$$m-1$$$ (ignore the edge cases of $$$x=1$$$ and $$$x=m$$$ for now). Using Vandermonde's identity, this simplifies to

As a further optimization, note that everything above is a constant except for $$$r-l$$$, which is dependent on the size of the interval. Therefore, we are motivated to loop over the size of $$$r-l$$$. Note that the above should also be multiplied by the minimum weight on the interval from $$$l$$$ to $$$r$$$. Therefore, our problem is now trying to find the sum of minimum of all length $$$k$$$ subarrays for all $$$k$$$ from $$$1$$$ to $$$n$$$.

To solve this subproblem, we can use a monotonic stack to calculate the bounds in which $$$i$$$ is the minimum (to break ties, we use strict inequality on one side but not the other). Then, noting that the contribution of an index for $$$k$$$ increases by $$$1$$$ until some point, then decreases by $$$1$$$. This can be optimized by creating the $$$2$$$-nd order difference array. The problem is solved in $$$O(n)$$$ time.

First, let’s count nondecreasing arrays.

How many nondecreasing arrays of length $$$n$$$ have last element exactly $$$m$$$?

This is a classical problem. Instead of looking at the array itself, look at its difference variables: $$$d_1 = a_1 - 1$$$ and $$$d_i = a_i - a_{i-1}$$$ for $$$i \ge 2$$$. Since the array is nondecreasing, every $$$d_i$$$ is non-negative, and $$$d_1 + d_2 + \cdots + d_n = a_n - 1 = m - 1.$$$ So this becomes the standard stars-and-bars count.

What about arrays where the last element is $$$\le m$$$?

This is equivalent to having $$$n$$$ non-negative variables with sum $$$\le m-1$$$. The standard trick is to introduce one extra variable that absorbs the remaining value, so this becomes counting $$$n+1$$$ non-negative variables with sum exactly $$$m-1$$$.

Now let’s solve the original problem. We simulate the binary search and go through all intervals $$$[l,r]$$$ that can appear in the recursion tree. For each such interval, let $$$mid = \lfloor (l+r)/2 \rfloor$$$. We count how many arrays make the search terminate at this state, and multiply that count by the current depth of the search.

Suppose we are at interval $$$[l,r]$$$. To terminate here, we need $$$a_{mid}$$$ to be the searched value. Also, if $$$l \gt 1$$$ then the search must previously have inspected position $$$l-1$$$ and concluded that its value is smaller than the target, so we need $$$a_{l-1} \lt a_{mid}$$$. Similarly, if $$$r \lt n$$$ then we need $$$a_{mid} \lt a_{r+1}$$$. Since we are already counting only nondecreasing arrays, these are the only extra constraints that matter.

So we are left with the following question: how many good arrays satisfy $$$a_{l-1} \lt a_{mid} \lt a_{r+1}$$$?

Let $$$S = \binom{n+m-1}{n}$$$ be the number of all good arrays. We now remove the bad arrays by inclusion-exclusion.

The bad arrays are those with $$$a_{l-1} = a_{mid}$$$ or $$$a_{mid} = a_{r+1}$$$. The condition $$$a_{l-1} = a_{mid}$$$ means that every difference variable corresponding to positions $$$l, l+1, \dots, mid$$$ must be $$$0$$$. So we can count such arrays by simply removing those variables from the stars-and-bars count. Similarly, the condition $$$a_{mid} = a_{r+1}$$$ means that every difference variable corresponding to positions $$$mid+1, mid+2, \dots, r+1$$$ must be $$$0$$$, and we count those in the same way.

Finally, we add back the arrays counted twice, namely those with $$$a_{l-1} = a_{mid} = a_{r+1}$$$, which is equivalent to forcing all difference variables for positions $$$l, l+1, \dots, r+1$$$ to be $$$0$$$.

One last thing to note is that if $$$l=1$$$ (or $$$r=n$$$), then the corresponding boundary restriction does not exist, so we do not subtract that case.

Since there are $$$O(n)$$$ intervals, and each interval can be computed in $$$O(1)$$$, the final complexity is $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

// using namespace std;
using ll = long long;
#define vt vector
#define int long long
#define add push_back 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
const ll mod = 676767677;
const ll inf = 1e18;
template<typename T> using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>; //defines min_pq

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand_num(int l, int r) {
    return rnd()%(r-l+1)+l;
}
int bexpo(int b, int e) {
    int ans = 1;
    while(e) {
        if(e&1) ans=ans*b%mod;
        e>>=1;
        b=b*b%mod;
    }
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    int t;
    cin >> t;
    vt<int> fact(2e6+5), ifact(2e6+5);
    fact[0]=ifact[0]=1;
    FOR(i, 1, 2e6+5) {
        fact[i]=fact[i-1]*i%mod;
        ifact[i]=bexpo(fact[i], mod-2);
    }
    auto nck = [&](int n, int k)->int{
        if(k<0 || k>n) {
            return 0;
        }
        return fact[n]*ifact[k]%mod*ifact[n-k]%mod;
    };
    while(t--) {
        int n,m;
        cin >> n >> m;
        vt<int> time(n);
        auto fill = [&](auto self, int l, int r, int start)->void{
            if(l>r) return;
            int mid = (l+r)/2;
            time[mid]=start;
            self(self, l, mid-1, start+1);
            self(self, mid+1, r, start+1);
        };
        fill(fill, 0, n-1, 1);
        vt<int> l(n,-1),r(n, n);
        stack<int> s;
        F0R(i, n) {
            while(s.size() && time[s.top()]>time[i]) {
                r[s.top()]=i;
                s.pop();
            }
            s.push(i);
        }
        while(s.size()) s.pop();
        R0F(i, n) {
            while(s.size() && time[s.top()]>=time[i]) {
                l[s.top()]=i;
                s.pop();
            }
            s.push(i);
        }
        // cout << time << " " << l << " " << r << endl;
        vt<int> v(n+10);
        F0R(i, n) {
            // cout << i << endl;
            int left = i-l[i]-1;
            int right = r[i]-i-1;
            if(left>right) swap(left,right);
            v[1]+=time[i];
            v[left+2]-=time[i];
            v[right+2]-=time[i];
            v[left+right+3]+=time[i];
        }
        FOR(i, 1, n+1) v[i]+=v[i-1];
        FOR(i, 1, n+1) v[i]+=v[i-1];
        // cout << v << endl;
        int ans = 0;
        FOR(sz, 1, n+1) {
            int out = n-sz;
            ans+=v[sz]*nck(out+m-2, m-3)%mod;
        }
        int mn = inf;
        F0R(i, n) {
            mn=min(mn, time[i]);
            ans+=nck(n-i-1+m-2, m-2)*mn;
            ans%=mod;
        }
        mn = inf;
        R0F(i, n) {
            mn=min(mn, time[i]);
            ans+=nck(i+m-2, m-2)*mn;
            ans%=mod;
        }
        cout << ans << endl;
    }
    return 0;

}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int>> vvi;
typedef vector<vector<pii>> vvpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int>> vpi;
typedef pair<ll, ll> pll;
#define MOD 676767677

template<int MODX>
struct ModInt {
  unsigned x;
  ModInt() : x(0) { }
  ModInt(signed sig) : x(((sig%MODX)+MODX)%MODX) {  }
  ModInt(signed long long sig) : x(((sig%MODX)+MODX)%MODX) { }
  int get() const { return (int)x; }
  ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
 
  ModInt &operator+=(ModInt that) { if ((x += that.x) >= MODX) x -= MODX; return *this; }
  ModInt &operator-=(ModInt that) { if ((x += MODX - that.x) >= MODX) x -= MODX; return *this; }
  ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MODX; if (x < 0) x += MODX; return *this; }
  ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MODX - 2); }
 
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  bool operator<(ModInt that) const { return x < that.x; }
  friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};
typedef ModInt<MOD> mint;

// N ~ 10^6
class Combinations {
public:
  vector<mint> inv, fact, ifact;

  Combinations(int N) {
    inv.resize(N+10), fact.resize(N+10), ifact.resize(N+10);
    inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
    for(int i=2;i<=N;++i) {
      inv[i] = inv[MOD%i] * (MOD - MOD/i);
      fact[i] = fact[i-1]*i;
      ifact[i] = ifact[i-1]*inv[i];
    }
  }
  // a > b
  mint comb(ll a, ll b) {
    if(a < b) return mint(0);
    return fact[a] * ifact[b] * ifact[a-b];
  }
};

Combinations comb(2010100);

// Stars and bars
mint SB(int K, int S) {
  return comb.comb(S+K-1, K-1);
}

int n,m;
mint ret = 0;
void dfs(int l, int r, int depth) {
  if (l > r) return;
  // Last two checked positions.
  int lp = l - 1;
  int rp = r + 1;
  
  int mid = (l + r)/2;
  mint TOT = SB(n+1, m);
  ret += TOT * depth;
  // If we saw a position for which ARR[l-1] < ARR[mid]
  if (lp != -1) {
    ret -= SB(n+1 - (mid - lp), m) * depth;
  }

  // If we saw a position for which a[mid] < a[r+1]
  if (rp != n) {
    ret -= SB(n+1 - (rp - mid), m) * depth;
  }

  // If we saw both a[l-1] < a[mid] < a[r+1] add the double counted arrays back
  if (lp != -1 && rp != n) {
    ret += SB(n + 1 - (rp - lp), m) * depth;
  }
  dfs(mid+1, r, depth+1);
  dfs(l, mid-1, depth+1);
}

int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while(T--) {
    cin >> n >> m;
    --m;
    ret = 0;
    dfs(0, n-1, 1);
    cout << ret << "\n";
  }
  return 0;
}

Solve this problem for $$$n,m \lt =10^6$$$ but there is no limit on sum of $$$n$$$ or $$$m$$$ across all test cases.

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider the graph of prefix sums.

Let's take the prefix sums $$$b_i=a_1+a_2+\ldots+a_i$$$ instead of $$$a_i$$$ (including $$$b_0=0$$$), and consider what it means when $$$a_i$$$ is sorted in non-decreasing order. We can see that $$$a_i$$$ being non-decreasing is equivalent to the points $$$(i,b_i)$$$ forming a chain that is convex from below. The operation on index $$$i$$$ makes the segment from $$$(i-1,b_{i-1})$$$ to $$$(i+1,b_{i+1})$$$ completely straight, and to sort $$$a$$$ we need to be able to make the chain convex using the operation.

Notice the following observation.

• Observation: any chain $$$(i-1,b_{i-1}),(i,b_i),\ldots,(j,b_j)$$$ can be made arbitrarily close to the line from $$$(i-1,b_{i-1})$$$ to $$$(j,b_j)$$$.

In other words, $$$a_i,a_{i+1},\ldots,a_j$$$ can be made arbitrarily close to their average value.

Because their mean is constant when we don't perform operations outside this range, we can easily reason about their variance. Let's say their mean is $$$\mu$$$. Then, $$$(a_i-\mu)^2+(a_{i+1}-\mu)^2 \ge 2 \cdot (\frac{a_i+a_{i+1}}{2}-\mu)^2$$$ due to the convexity of the function $$$f(x)=(x-\mu)^2$$$. Equality holds if and only if $$$a_i=a_{i+1}$$$. In other words, as long as there is at least one unequal adjacent pair (unless all $$$j-i+1$$$ values are equal, there definitely will be one), the variance can decrease indefinitely (that is, arbitrarily close to $$$0$$$). The variance becomes $$$0$$$ if and only if all $$$j-i+1$$$ values are equal.

Now, let's see if there is a point $$$(i,b_i)$$$ strictly below the line from $$$(0,0)$$$ to $$$(n,b_n)$$$. Then, we can make the segments almost straight from $$$(0,0)$$$ to $$$(i,b_i)$$$ and from $$$(i,b_i)$$$ to $$$(n,b_n)$$$. The fact that we can make a segment almost (yet not completely) straight is important. After we make them straight enough, let's call their slopes $$$\mu_{1,l}$$$ and $$$\mu_{1,r}$$$, and we can perform the operation on index $$$i$$$ so that the segment from $$$(i-1,b_{i-1})$$$ to $$$(i+1,b_{i+1})$$$ is straight. This slope $$$s_{1,1}$$$ certainly satisfies $$$\mu_l \lt s_{1,1} \lt \mu_r$$$. If this does not hold, then we could certainly go back, make the segments flatter, and it will definitely hold at some point when we perform the operation on index $$$i$$$.

We'll now set $$$l=i-1$$$, $$$r=i+1$$$, and maintain an invariant that the segment $$$[l,r]$$$ is convex. If we perform the operation on indices $$$i-1$$$ and $$$i+1$$$, we get two slopes $$$s_{2,1}$$$ and $$$s_{2,2}$$$ such that $$$\mu_{2,l} \lt s_{2,1} \lt s_{2,2} \lt \mu_{2,r}$$$, where $$$\mu_{2,l}$$$ is the slope from $$$(0,0)$$$ to $$$(l-1,b_{l-1})$$$ and $$$\mu_{2,r}$$$ is the slope from $$$(r+1,b_{r+1})$$$ to $$$(n,b_n)$$$. We have now expanded the segment to $$$[l-1,r+1]$$$ while maintaining convexity.

Repeating this process, we can expand $$$[l,r]$$$ to $$$[0,n]$$$, and the chain can become entirely convex.

Now the only case left is when all points are either on or above the line from $$$(0,0)$$$ to $$$(n,b_n)$$$. We can only make them non-decreasing by making them all equal. However, if two consecutive points are above the line, we can't put them right on the line because we're still moving a point to somewhere above the line. However, if only one point $$$(i,b_i)$$$ is above the line, we can make the segment from $$$(i-1,b_{i-1})$$$ to $$$(i+1,b_{i+1})$$$ completely straight. Therefore, if there are no two consecutive points above the line, we can perform the operation on all points above the line, and the chain will be completely straight. We have shown that the outlined two cases are the only cases in which we can make $$$a$$$ sorted in non-decreasing order.

The problem is solved in $$$\mathcal{O}(n)$$$ time.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

signed main(){
  ios_base::sync_with_stdio(0),cin.tie(0);
  int t;cin>>t;
  while(t--)
  {
    ll n; cin >> n;
    vector<ll> a(n);
    for(int i=0; i<n; ++i) cin >> a[i];
    vector<ll> sum(n+1);
    for(int i=0; i<n; ++i) sum[i+1]=sum[i]+a[i];
    vector<ll> exact(n+1);
    exact[0]=exact[n]=1;
    bool found=0;
    for(int i=1; i<n; ++i){
        if(1ll*sum[i]*(n-i)<1ll*(sum[n]-sum[i])*i){
            cout << "Yes\n";
            found=1;break;
        }
        if(1ll*sum[i]*(n-i)==1ll*(sum[n]-sum[i])*i){
            exact[i]=1;
        }
    }
    if(found)continue;
    for(int i=0; i+1<=n; ++i){
        if(!exact[i]&&!exact[i+1]){
            cout << "No\n";
            found=1;break;
        }
    }
    if(found)continue;
    cout << "Yes\n";
  }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

We can reduce a fixed subarray $$$[l, r]$$$ of $$$p$$$ to two elements: the minimum and the maximum.

The answer is at most $$$5$$$. Try to determine whether we can get the answer of $$$4$$$.

Consider the minimum/maximum in $$$[1, i - 1]$$$ and minimum/maximum in $$$[i + 1, n]$$$. There is only one non-trivial case: $$$[1, 4, 3, 5, 2, 6]$$$ for $$$p_i = 3$$$.

Let $$$a, b$$$ be the positions of prefix minimum and prefix maximum in $$$[1, i - 1]$$$ accordingly, and $$$c, d$$$ be the positions suffix minimum and suffix maximum. WLOG assume that $$$a \lt b$$$. The case is $$$a \lt b \lt i \lt c \lt d$$$, WLOG assume we have to remove $$$p_b$$$ using an element from $$$[i + 1, c - 1]$$$.

Apart from the trivial cases the condition is this: let $$$l = \max(a, b)$$$ and $$$r = \min(c, d)$$$, then the answer is $$$\le 4$$$ iff there is an element $$$l \le j \le r$$$ such that $$$p_j \lt \min(p_l, p_r)$$$ or $$$p_j \gt \max(p_l, p_r)$$$.

To determine if it's $$$3$$$ consider two cases: $$$\text{pos}_1 \lt i \lt \text{pos}_n$$$ and $$$\text{pos}_1 \lt \text{pos}_n \lt i$$$. The first case is significantly easier.

If the answer is at most $$$4$$$ when $$$\text{pos}_1 \lt i \lt \text{pos}_n$$$, we can reduce $$$[\text{pos}_1, \text{pos}_n]$$$ to only $$$[1, p_i, n]$$$.

If there is an extremum before $$$\text{pos}_1$$$ or after $$$\text{pos}_n$$$, we can't do anything about it. Now consider the $$$\text{pos}_1 \lt \text{pos}_n \lt i$$$ case.

The two main cases are: $$$[1, n, p_i, H, L]$$$ and $$$[1, n, p_i, L, H]$$$, where $$$L = p_c$$$ and $$$H = p_d$$$. Consider $$$[1, n, p_i, L, H]$$$ first.

We can remove any element bigger than $$$p_i$$$ using $$$n$$$. Since the answer is at least $$$4$$$, we can remove $$$L$$$. After that we remove $$$H$$$ using $$$n$$$, so the answer is $$$3$$$. Now consider $$$[1, n, p_i, H, L]$$$

We could easily remove $$$H$$$ using $$$n$$$, however after that we wouldn't be able to remove $$$L$$$. It is sometimes possible to remove both, consider $$$p = [1, 7, 2, 6, 4, 5, 3]$$$ for $$$p_i = 4$$$.

We do $$$[1, 7, 2, 6, 4, 5, 3] \rightarrow [1, 7, 2, 6, 4, 3] \rightarrow [1, 7, 2, 4, 3] \rightarrow [1, 7, 2, 4, 3] \rightarrow [1, 7, 2, 4] \rightarrow [1, 7, 4]$$$. So we need to find indices $$$j$$$ and $$$k$$$ such that: $$$\text{pos}_n \lt k \lt j \lt i$$$, $$$p_k \lt L \lt p_i \lt H \lt p_j$$$, and we can first clear $$$[j + 1, i - 1]$$$ and then clear $$$[k + 1, j]$$$. Greedy does not work as we have to be able to clear the intervals. For example, for $$$p = [1, 8, 3, 7, 2, 5, 6, 4]$$$ and $$$p_i = 5$$$ the answer is $$$4$$$, not $$$3$$$, as we cannot remove $$$2$$$ after choosing $$$p_k = 3$$$ and $$$p_j = 7$$$.

Choose $$$k$$$ to be the minimum in $$$[\text{pos}_n, i]$$$, $$$j$$$ to be the maximum in $$$[k + 1, i]$$$, then you can always clear the intervals.

First of all, we trivially can never delete $$$1$$$ or $$$n$$$, since they are always the smallest and the largest elements. Furthermore, for a fixed subarray $$$[l, r]$$$, where $$$p_x$$$ is the minimum and $$$p_y$$$ is the maximum in the subarray, we can trivially turn it $$$[p_l, p_{l + 1}, \ldots, p_r]$$$ into $$$[p_x, p_y]$$$ or $$$[p_y, p_x]$$$ (depending on their order) by continuously applying operation on the subarray. We call that sequence operations a reduction of $$$[l, r]$$$.

From this immediately follows that the answer for any $$$p_i$$$ is at most $$$5$$$: leave at most $$$2$$$ elements in $$$[1, i - 1]$$$, leave $$$p_i$$$, and at most $$$2$$$ elements in $$$[i + 1, n]$$$. Moreover, if $$$p_i$$$ is not $$$1$$$ or $$$n$$$, the answer is at least $$$3$$$, since we can't delete $$$1$$$ or $$$n$$$. Therefore, the problem is determining whether the answer is $$$3$$$, $$$4$$$ or $$$5$$$ (for $$$p_i = 1$$$ or $$$p_i = n$$$ it is trivially $$$2$$$).

Let's try to determine if we can get an answer $$$\le 4$$$ first. Let's get rid of the trivial cases first: if $$$p_i$$$ is suffix/prefix minimum/maximum, one of $$$[1, i]$$$ or $$$[i, n]$$$ can be reduced to only $$$2$$$ elements, and the other part can be reduced to $$$2$$$ elements as well, so an answer of $$$4$$$ can be trivially achieved.

Now assume that $$$p_i$$$ is not a suffix/prefix minimum/maximum. Let $$$a, b$$$ be the positions of prefix minimum and prefix maximum in $$$[1, i - 1]$$$ accordingly, and $$$c, d$$$ be the positions suffix minimum and suffix maximum. WLOG assume that $$$a \lt b$$$, so the prefix minimum appears earlier than the prefix maximum.

Notice that since $$$i$$$ is not an extrema we must have $$$p_a, p_c \lt p_i \lt p_b, p_d$$$. Therefore, if $$$d \lt c$$$ we can reduce both $$$[1, i - 1]$$$ and $$$[i + 1, n]$$$, and then do an operation on $$$[p_b, p_i, p_d]$$$ which will delete either $$$p_b$$$ or $$$p_d$$$ and achieve an answer of $$$4$$$.

Therefore assume that the elements are positioned as $$$[\ldots, p_a, \ldots, p_b, \ldots, p_i, \ldots, p_c, \ldots, p_d, \ldots]$$$. Notice that we cannot remove $$$p_a$$$ or $$$p_d$$$ without removing $$$p_i$$$, $$$p_b$$$ or $$$p_c$$$. For example to delete $$$p_a$$$ we need an element greater than $$$p_a$$$, and the next one can only be located after $$$p_i$$$, so we have to remove either $$$p_b$$$ or $$$p_i$$$.

Therefore we need to remove $$$p_b$$$ or $$$p_c$$$. WLOG assume that we are trying to remove $$$p_b$$$ first. We cannot do that only with elements in $$$[1, i]$$$, so assume that we use an index $$$i \lt j \lt c$$$ for that. We perform an operation on $$$[p_b, p_i, p_j]$$$. This deletes $$$p_b$$$ iff $$$p_b \lt p_j$$$.

Therefore, there needs be an index $$$j$$$ satisfying $$$i \lt j \lt c$$$ and $$$p_j \gt p_b$$$ for $$$p_b$$$ to be deletable. For simplicity, take $$$j$$$ to be the maximum of $$$[i, c]$$$. Then we can achieve an answer of $$$4$$$ this way: reduce $$$[i + 1, c]$$$ which will leave us with $$$[p_j, p_c]$$$, reduce $$$[1, i - 1]$$$, reduce $$$[c, n]$$$. After this we end up with $$$[p_a, p_b, p_i, p_j, p_c, p_d]$$$. Remove $$$p_b$$$ in $$$[p_b, p_i, p_j]$$$ and then remove $$$p_j$$$ in $$$[p_j, p_c, p_d]$$$. At the end we will have $$$[p_a, p_i, p_c, p_d]$$$.

The case of removing $$$p_c$$$ is identical. Therefore we have a complete solution for determining whether the answer is $$$\le 4$$$. A simple way to frame it is this: let $$$l$$$ be $$$\max(a, b)$$$ and $$$r$$$ be $$$\min(c, d)$$$. The answer is $$$3$$$ or $$$4$$$ iff one of the following holds: $$$i = l$$$, $$$i = r$$$, $$$\max([p_l, p_{l + 1}, \ldots, p_r]) \gt \max(p_l, p_r)$$$ or $$$\min([p_l, p_{l + 1}, \ldots, p_r]) \lt \min(p_l, p_r)$$$. The last two conditions mean that there is an element that we can use to remove $$$p_l$$$ or $$$p_r$$$.

Now we have to determine if the answer is $$$3$$$ or $$$4$$$. From now assume that the condition above holds. Note that to get $$$3$$$ we have to end up with exactly $$$3$$$ elements: $$$1$$$, $$$n$$$ and $$$p_i$$$. Denote $$$\text{pos}_x = i$$$ as $$$i$$$ such that $$$p_i = x$$$. WLOG assume that $$$\text{pos}_1 \lt \text{pos}_n$$$. Consider two cases: $$$\text{pos}_1 \lt i \lt \text{pos}_n$$$ and $$$\text{pos}_n \lt i$$$. The case of $$$\text{pos}_1 \gt i$$$ is identical to $$$\text{pos}_n \lt i$$$.

Consider $$$\text{pos}_1 \lt i \lt \text{pos}_n$$$ first. Notice that we can remove everything in $$$[\text{pos}_1, \text{pos}_n]$$$ while keeping $$$p_i$$$. Since the answer is $$$\le 4$$$ we can leave at most $$$4$$$ elements in $$$[\text{pos}_1, \text{pos}_n]$$$, let them be $$$1$$$, $$$n$$$, $$$p_i$$$ and $$$p_j$$$. Then if $$$p_i \lt p_j$$$ we remove $$$p_j$$$ using $$$n$$$ and if $$$p_i \gt p_j$$$ we remove it using $$$1$$$. Therefore we only need to make sure that there is nothing left in $$$[1, \text{pos}_1 - 1]$$$ and $$$[\text{pos}_n + 1, n]$$$.

Remember that we already proved that if the prefix maximum of $$$[1, i]$$$ is in $$$[1, \text{pos}_1 - 1]$$$ we cannot remove it without removing $$$1$$$, and if the suffix minimum of $$$[i, n]$$$ is in $$$[\text{pos}_n + 1, n]$$$ we cannot remove it without removing $$$n$$$.

Therefore let $$$b$$$ be the index of prefix maximum in $$$[1, i]$$$ and $$$c$$$ be the index of prefix minimum in $$$[i, n]$$$. The answer is $$$3$$$ iff $$$b \ge \text{pos}_1$$$ and $$$c \le \text{pos}_n$$$ and $$$4$$$ otherwise.

Now the last case is $$$\text{pos}_1 \lt \text{pos}_n \lt i$$$. Let $$$a$$$ be the suffix minimum of $$$[i, n]$$$ and $$$b$$$ be the suffix maximum, and $$$p_a = L$$$ and $$$p_b = H$$$.

Let's get rid of trivial cases. If $$$a = i$$$ we can reduce $$$[\text{pos}_n, n]$$$ and then $$$[1, \text{pos}_n]$$$ to get an answer of $$$3$$$. If $$$b = i$$$ we need to remove $$$p_a$$$ with something in $$$[\text{pos}_n, i - 1]$$$. Similarly to our solution for $$$\le 4$$$ we need $$$\min(p_{\text{pos}}, \ldots, p_{i - 1}) \lt p_a$$$ for this, which is sufficient.

Now assume $$$a \neq i$$$ and $$$b \neq i$$$. If $$$a \lt b$$$, since the answer is $$$\le 4$$$ we can remove $$$p_a$$$ using $$$[\text{pos}_n, i - 1]$$$, so the case is the same as $$$a = i$$$ and is always $$$3$$$.

The only case left is $$$b \lt a$$$, which is $$$[1, n, p_i, H, L]$$$. We need to remove $$$H$$$ using $$$[\text{pos}_n, i - 1]$$$ and then remove $$$L$$$ using that same interval. Assume we will remove $$$H$$$ using $$$p_j$$$ and $$$L$$$ using $$$p_k$$$.

To do this we need to have $$$p_k \lt L \lt H \lt p_j$$$. Since we first remove $$$H$$$ then $$$L$$$, we need to clear $$$[j + 1, i - 1]$$$ without removing $$$p_k$$$, therefore we also need to have $$$k \lt j$$$. We also need to clear $$$[k + 1, j]$$$ after that to remove $$$L$$$.

Claim: it is optimal to choose $$$k$$$ to be the index of minimum in $$$[\text{pos}_n, i]$$$. Suppose we don't and the index of the minimum is $$$l$$$.

If we choose $$$k \lt l$$$ we cannot clear $$$[k + 1, j]$$$ since we cannot delete $$$l$$$: $$$[i + 1, b - 1]$$$ can't be used for that because it needs to be cleared to remove $$$H = p_b$$$, and $$$[1, \text{pos}_n - 1]$$$ can't be used as well because $$$n$$$ and $$$p_k$$$ cannot be removed.

Therefore, $$$p_k \ge p_l$$$ and $$$p_j \le \max(p_{l + 1}, \ldots, p_i)$$$. Notice that choosing $$$k$$$ and $$$j$$$ to be exactly these value is always optimal: we can clear $$$[j + 1, i - 1]$$$ by reducing $$$[k, i - 1]$$$, and then remove $$$p_j$$$ in $$$[n, p_k, p_j]$$$. Since we need to have $$$p_k \lt L \lt H \lt p_j$$$, minimizing $$$p_k$$$ and maximizing $$$p_j$$$ is needed.

Therefore, the condition is: let $$$k$$$ be the minimum in $$$[\text{pos}_n, i]$$$ and $$$j$$$ be the maximum in $$$[k + 1, i]$$$. Then the answer is $$$3$$$ iff $$$p_k \lt L \lt H \lt p_j$$$ and $$$4$$$ otherwise. This covers all the cases and solves the problem.

The final solution is $$$O(n)$$$ or $$$O(n \log n)$$$ depending on the implementation. It can be implemented without considering too much symmetrical cases, refer to the code below.

#include <bits/stdc++.h>

using namespace std;

const int LG = 20;

vector<int> get_default(vector<int> p) {
    int n = p.size();
    vector<int> pos(n + 1);
    for(int i = 0; i < n; i++) pos[p[i]] = i;

    vector<int> ans(n, 5);

    int pos_1 = pos[1], pos_n = pos[n];
    if(pos_1 > pos_n) return ans;

    vector<int> pos_suff_min(n, n - 1), pos_suff_max(n, n - 1);
    for(int i = n - 2; ~i; i--) {
        pos_suff_min[i] = pos_suff_min[i + 1];
        if(p[i] < p[pos_suff_min[i]]) pos_suff_min[i] = i;

        pos_suff_max[i] = pos_suff_max[i + 1];
        if(p[i] > p[pos_suff_max[i]]) pos_suff_max[i] = i;
    }

    vector<int> pos_pref_min(n), pos_pref_max(n);
    for(int i = 1; i < n; i++) {
        pos_pref_min[i] = pos_pref_min[i - 1];
        if(p[i] < p[pos_pref_min[i]]) pos_pref_min[i] = i;

        pos_pref_max[i] = pos_pref_max[i - 1];
        if(p[i] > p[pos_pref_max[i]]) pos_pref_max[i] = i;
    }

    vector<vector<int>> t_min(n, vector<int>(LG));
    for(int i = 0; i < n; i++) t_min[i][0] = p[i];
    for(int l = 1; l < LG; l++) {
        for(int i = 0; i + (1 << l) <= n; i++) {
            t_min[i][l] = min(t_min[i][l - 1], t_min[i + (1 << l - 1)][l - 1]);
        }
    }
    auto get_min = [&](int l, int r) {
        int L = __lg(r - l + 1);
        return min(t_min[l][L], t_min[r - (1 << L) + 1][L]);
    };

    vector<vector<int>> t_max(n, vector<int>(LG));
    for(int i = 0; i < n; i++) t_max[i][0] = p[i];
    for(int l = 1; l < LG; l++) {
        for(int i = 0; i + (1 << l) <= n; i++) {
            t_max[i][l] = max(t_max[i][l - 1], t_max[i + (1 << l - 1)][l - 1]);
        }
    }
    auto get_max = [&](int l, int r) {
        int L = __lg(r - l + 1);
        return max(t_max[l][L], t_max[r - (1 << L) + 1][L]);
    };

    for(int i = pos_1; i < n; i++) {
        if(p[i] == 1 || p[i] == n) {
            ans[i] = 2;
            continue;
        }
        if(i == 0 || i == n - 1) {
            ans[i] = 3;
            continue;
        }

        int a = pos_pref_min[i], b = pos_pref_max[i];
        int c = pos_suff_min[i], d = pos_suff_max[i];
        int l = max(a, b), r = min(c, d);
        int min_all = get_min(l, r), max_all = get_max(l, r);
        if(l == i && r == i) {
            ans[i] = 3;
            continue;
        }

        if(l == i || r == i) ans[i] = 4;
        if(abs(p[r] - p[l]) != max_all - min_all) ans[i] = 4;
        if(ans[i] != 4) continue;

        // 1 p[i] n
        if(i < pos_n) {
            // H 1 p[i] n
            if(b < pos_1) continue;
            // 1 p[i] n L
            if(c > pos_n) continue;
            ans[i] = 3;
            continue;
        }

        // 1 n p[i]

        // 1 n p[i] H
        if(pos_suff_min[i] == i) ans[i] = 3;
        // 1 n p[i] L H, can't remove L
        if(get_min(l, i) > p[pos_suff_min[i]]) continue;
        // 1 n p[i] L, can remove L
        if(r == i) ans[i] = 3;
        // 1 n p[i] L H, first remove L, then H
        if(c < d) ans[i] = 3;

        // 1 n p[i] H L, pick k and j
        int k = pos[get_min(pos_n, i)];
        int j = pos[get_max(k, i)];
        if(p[k] < p[c] && p[d] < p[j]) ans[i] = 3;
    }

    for(auto &i : ans) i = min(i, n);
    return ans;
}

vector<int> get(vector<int> p) {
    int n = p.size();

    vector<int> ans(n, n);
    for(int t_reverse = 0; t_reverse < 2; t_reverse++) {
        for(int t_invert = 0; t_invert < 2; t_invert++) {
            auto curr_ans = get_default(p);
            if(t_reverse) reverse(curr_ans.begin(), curr_ans.end());
            for(int i = 0; i < n; i++) ans[i] = min(ans[i], curr_ans[i]);

            for(auto &i : p) i = n + 1 - i;
        }
        reverse(p.begin(), p.end());
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for(auto &i : p) {
        cin >> i;
    }

    auto ans = get(p);
    for(auto i : ans) cout << i << " "; cout << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

One of the authors is personally working on an anti-cheat engine for Competitive Programming contests. If you cheat in this round, there might be a possibility that he might happily use you as training data without your consent. It's not like a 100% probability, but just so you know...

The reverse of the Collatz conjecture can be written as follows:

• Multiply $$$x$$$ by $$$2$$$ (if $$$2x$$$ was even)
• Subtract $$$1$$$ from $$$x$$$, then divide by $$$3$$$ (if $$$\frac{x-1}{3}$$$ is an integer and is odd).

In this problem, we can ignore the second type completely, because $$$2x$$$ is always an integer and is always even. We can simply print out $$$x\cdot 2^k$$$ as our answer.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,k = map(int,input().split())
    print(k<<n)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

We can show that the permutation $$$q$$$ defined by $$$q_i=n+1-p_i$$$ satisfies all required properties.

• Proof $$$q$$$ is a permutation: Since $$$p_i+q_i=n+1$$$ and elements of $$$p$$$ ranges from $$$1$$$ to $$$n$$$, elements of $$$q$$$ will also range from $$$1$$$ to $$$n$$$. Additionally, since $$$p$$$ is a permutation (all elements are distinct), $$$q$$$ must also be a permutation.
• Proof $$$GCD(p_i+q_i, p_{i+1}+q_{i+1})\geq 3$$$: Since $$$n\geq2$$$, $$$n+1\geq 3$$$. The GCD of any number with itself is itself.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = [n - i + 1 for i in a]
    print(*b)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, observe that in order to maximize the sum of two positive numbers given that their product must stay constant, it is optimal to minimize one number as much as possible (and in the process, maximize the other).

Let's do casework on the parity of $$$a$$$ and $$$b$$$:

• $$$a$$$, $$$b$$$ are both even: in this case, we cannot choose a $$$k$$$ such that $$$\frac{b}{k}$$$ is odd, as $$$a$$$ will stay even, and $$$a+b$$$ will be odd. The optimal $$$k$$$ here is $$$\frac{b}{2}$$$.
• $$$a$$$ is even, but $$$b$$$ is odd: In this case, we should print $$$-1$$$, as it is impossible to make $$$a+b$$$ even.
• $$$a$$$ is odd, $$$b$$$ is divisible by $$$2$$$ and not $$$4$$$: This case is also impossible. No matter what $$$k$$$ we choose, one of $$$a$$$ and $$$b$$$ will always be odd.
• $$$a$$$ is odd, $$$b$$$ is divisible by $$$4$$$: Even though $$$a+b$$$ is initially odd, it is possible to make $$$a+b$$$ even in this case by choosing a $$$k$$$ so that $$$k$$$ and $$$\frac{b}{k}$$$ are both even. Once again, the optimal $$$k$$$ to use is $$$\frac{b}{2}$$$.
• $$$a$$$ and $$$b$$$ are both odd: In this case, the optimal $$$k$$$ to use is $$$b$$$. Note that $$$a+b$$$ will always be even no matter what $$$k$$$ is chosen.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    b,a = map(int,input().split())
    sol = -1
    if (a + b) & 1 == 0: sol = a + b
    if a % 2 == 1 and b % 2 == 1: sol = max(sol, a * b + 1)
    elif a % 2 == 0 and (a % 4 == 0 or b % 2 == 0): sol = max(sol, 2 + (a * b) // 2)
    print(sol)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, we should observe that the number of occurrences of $$$x$$$ in $$$b$$$ must be a multiple of $$$x$$$. This is true because if we have $$$b_i=k$$$, then there are $$$k$$$ occurrences of $$$a_i$$$ in the original array. Suppose we group up all equal elements in the array $$$a$$$. If the number of occurrences of $$$b_i$$$ is not a multiple of $$$b_i$$$, then there is at least one group which doesn't have $$$b_i$$$ elements. This is a contradiction.

If the number of occurrences of $$$b_i$$$ is a multiple of $$$b_i$$$ for all $$$i$$$, then we can construct as follows:

• keep a varible $$$z=1$$$.
• For each $$$x$$$ from $$$1$$$ to $$$n$$$, iterate through the all indices $$$i$$$ with $$$b_i=x$$$. Label the first $$$x$$$ numbers as $$$z$$$, then increase $$$z$$$ by $$$1$$$. Continue until all indices are labeled.

This solution works in $$$O(n)$$$.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    FRQ = [[] for _ in range(n+1)]
    for i in range(n): FRQ[a[i]].append(i)
    b = [0 for _ in range(n)]
    cnt = 1
    for i in range(1,n+1):
        if len(FRQ[i]) % i: print(-1);break
        else:
            c=0
            while c < len(FRQ[i]):
                for v in range(i):
                    b[FRQ[i][c]] = cnt
                    c+=1
                cnt+=1
    else:print(*b)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let's first determine how to run the operation a single time.

Let $$$m$$$ be the MEX of the array, and let $$$occ_i$$$ be the number of occurrences of the number $$$i$$$. We have these cases:

• If $$$a_i \gt m$$$, then $$$a_i$$$ will become $$$m$$$.
• If $$$occ_{a_i}=1$$$ and $$$a_i \lt m$$$, then $$$a_i$$$ will still be itself after the operation. This is because after we remove $$$a_i$$$ from the array, $$$a_i$$$ will be the new MEX.
• if $$$occ_{a_i} \gt 1$$$ and $$$a_i \lt m$$$, then $$$a_i$$$ will become $$$m$$$. This is because even after removing $$$a_i$$$, there will still be at least one more occurrence of $$$a_i$$$, so $$$a_i$$$ will simply become the MEX of the whole array.

From this, we notice that numbers with frequency $$$1$$$ and less than the MEX will not change, while other numbers will map to the MEX. We now discuss several possible cases:

• If $$$a$$$ is a permutation of $$$[0,1,\ldots,n-1]$$$, then doing operations on $$$a$$$ will not change anything about the array.
• Otherwise, let $$$x$$$ be the smallest number with $$$occ_x \neq 1$$$. If $$$occ_x=0$$$, then $$$x$$$ is the MEX of $$$a$$$. After the first operation, all numbers greater than $$$x$$$ will get mapped to $$$x$$$ while all numbers less than $$$x$$$ will map to themselves (because $$$occ_i=1$$$ for all $$$i\leq n$$$. Now, all occurrences of $$$x$$$ (if there are more than $$$1$$$) will map to $$$x+1$$$. The array will then continuously alter between these two states. Be careful of the edge case $$$[0,1,\ldots,n-2,n]$$$, where it will map to the permutation case and not change again.
• Otherwise, $$$occ_x \gt 1$$$. Let $$$m$$$ be the MEX of $$$a$$$. After the first operation, all numbers less than $$$x$$$ will map to itself, while all occurrences of $$$x$$$ will map to $$$m$$$. This array is now the case of the previous one (where the smallest $$$x$$$ with $$$occ_x \neq 1$$$ will have $$$occ_x=0$$$), meaning that it will continuously alter between two states.

In all cases, after at most two operations, the array will only alter between two states after at most one operation. So it is possible to simulate the operation $$$min(k, k MOD 2 + 2)$$$ times and print out the sum.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,k = map(int,input().split())
    a = list(map(int,input().split())); l = []; sl = -1
    a.sort()
    while k and l != a:
        k -= 1
        sl = list(l)
        l = list(a)
        F = [0 for _ in range(n+1)]
        for i in a:F[i] += 1
        B = []
        mex = 0
        while F[mex]: mex += 1
        mm = 0
        for i in a:
            if F[i] > 1: B.append(mex)
            else: B.append(mm)
            if i == mm: mm += 1
        B.sort()
        a = B
        if a == sl:
            k &= 1
    print(sum(a))

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What is the condition for being able to make $$$x_i=y_i$$$? It is always possible if $$$x_i=y_i$$$ already. If $$$x_i \gt y_i$$$, it's only possible if $$$a_i$$$ is not already a prefix maximum. If $$$x_i \lt y_i$$$, it's only possible if there is a prefix maximum in the array before $$$i$$$ that is at least equal to $$$y_i$$$.

Let's formalize the conditions for the last two cases. If $$$x_i \gt y_i$$$, then there must exist an index $$$j \lt i$$$ such that $$$x_j \gt x_i$$$ (as this guarantees $$$a_i$$$ to not be a prefix maximum). If $$$x_i \lt y_i$$$, then there must exist an index $$$j \lt i$$$ such that $$$x_j \geq y_i$$$, as this ensures you can change $$$x_i$$$ to $$$y_i$$$. Let's calculate the correct $$$j$$$ for each $$$i$$$ in the original array $$$a$$$. This can be done in a variety of data structures. I used a set, but it is possible to use a segment tree or a stack as well.

Finally, to find the sum over all subarrays in $$$a$$$, for each index $$$i$$$ we need to calculate the number of subarrays containing $$$i$$$ where we can make $$$a_i=b_i$$$. If $$$x_i=y_i$$$, all subarrays containing $$$i$$$ counts, so we add $$$(i)(n-i+1)$$$ to our answer. Otherwise, let $$$prev_i$$$ be the number we calculated before. We can add $$$(i-prev_i+1)(n-i+1)$$$ to our answer.

import sys
input = sys.stdin.readline
class SparseTarble():
    def __init__(self,arr,op=min):
        self.n = len(arr)
        self.log = self.n.bit_length()
        self.PRE = [0 for _ in range(self.log * self.n)]
        for i in range(self.n):
            lsb = (i+1) & (-i-1)
            v = lsb.bit_length() - 1
            jo = self.n * v
            self.PRE[jo + i] = arr[i]
            for j in range(i+1,min(self.n,i+lsb)):
                self.PRE[jo + j] = op(self.PRE[jo+j-1],arr[j])
            for j in range(i-1, i - lsb, -1):
                self.PRE[jo + j] = op(arr[j],self.PRE[jo+j+1])
        self.op = op
    def query(self,l,r):
        assert(l < r)
        bit = (r ^ l).bit_length() - 1
        return self.op(self.PRE[bit * self.n + l], self.PRE[bit * self.n + r - 1])
for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    sq = SparseTarble(a,max)
    sol = 0
    for i in range(n):
        if a[i] == b[i]: sol += (n * n + n) // 2; continue
        lo = -1; hi = i
        while lo + 1 < hi:
            mid = (lo + hi) // 2
            if sq.query(mid,i) >= max(a[i],b[i]): lo = mid
            else: hi = mid
        lo+=1
        sol += lo * (n - i)
    print(sol)

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$dp_1(i)$$$ be a boolean on whether Cry will win if the token is on node $$$i$$$ and it is currently Cry's turn, and let $$$dp_2(i)$$$ be a boolean on whether Cry will win a game if we are on node $$$i$$$ and it is currently River's turn. Initially, $$$dp_1(i)=1$$$ and $$$dp_2(i)=1$$$ for all $$$1 \leq i \leq n$$$. Assuming we maintain the correct $$$dp$$$ values all the time, queries of the second type is easily answered by looking at the dp state.

How can we maintain the correct $$$dp$$$ values after a node is painted red? Consider BFS on the reverse graph. Suppose node $$$u$$$ was turned red. First, node $$$u$$$ becomes winning for River immediately no matter whose turn it is. Now, if a node becomes losing on Cry's turn, all nodes that are adjacent to that node in the reverse graph becomes winning on River's turn (as River can move the node to a node that loses on Cry's turn). If a node becomes losing on River's turn, consider the set of nodes adjacent on the reverse graph. If all nodes adjacent to that node (on the original graph) is losing on River's turn, then that node is also losing on Cry's turn, as no matter which node he decides to move to, it will be going to a lost node.

Keeping track of the DP states seems like it will be $$$O(n^2)$$$ complexity. However, since each node is visited only twice (once for updating $$$dp_1$$$ and once for updating $$$dp_2$$$, this solution will amortize to $$$O(n+m)$$$. Keep note that we should maintain a third array that counts how many adjacent nodes are losing on River's turn, so we don't have to check manually every time.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,m,q = map(int,input().split())
    G = [[] for _ in range(n+1)]
    A = [1 for _ in range(n+1)]
    B = [0 for _ in range(n+1)]
    C = [0 for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
        G[b].append(a)
        C[a] += 1
    for _ in range(q):
        a,b = map(int,input().split())
        if a == 2:
            if A[b]: print("yes")
            else: print("no")
        else:
            q = []
            if A[b] == 1: q.append((b,0))
            if B[b] == 0: q.append((b,1)); B[b] = 1
            for x,t in q:
                if t:
                    for c in G[x]:
                        C[c] -= 1
                        if C[c] == 0:
                           q.append((c,0))
                else:
                    if A[x] == 0: continue
                    A[x] = 0
                    for c in G[x]:
                        if B[c]: continue
                        B[c] = 1
                        q.append((c,1))

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

When is there definitely not a solution?

First, note that since relative order is preserved no matter which elements are deleted, if $$$a$$$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted.

If $$$a$$$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n;

    cin >> n;

    vector<int> arr(n);
    for(auto &x : arr) cin >> x;

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(arr[i] > arr[j]){
                cout << "YES\n2\n";
                cout << arr[i] << " " << arr[j] << "\n";
                return;
            }
        }
    }

    cout << "NO\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--) solve();
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Write some examples of arrays down.

The answer is $$$\min(a_1,a_2)+a_1$$$.

If $$$a_1 \gt a_2$$$, we can perform the operation with $$$i=1$$$ and $$$j=2$$$, so that the prefix minimum after index $$$2$$$ will always be $$$0$$$ to get $$$a_1+a_2$$$ as our answer.

If $$$a_1 \lt a_2$$$, we can perform the operation with $$$i=2$$$ and $$$j=3$$$. Since $$$a_1 \lt a_2, min(a_1,a_2)=a_1$$$. The prefix minimum will be $$$0$$$ in index $$$3$$$ and later. We should be careful about the edge case $$$n=2$$$, as there is no index $$$3$$$ we can use. However, if $$$n=2$$$, we can simply not perform the operation.

We can easily show that the above cases are optimal for this problem. The code runs in $$$O(n)$$$, bottlenecked by reading the array.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(min(2*a[0], a[0] + a[1]))

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Come up with some numbers that $$$x$$$ must be a multiple of.

Take the LCM. Prove its sufficient (optional).

First, note that in order for $$$b$$$ to be obtainable after an array $$$a$$$, each $$$a_i$$$ should be a factor of $$$b_i$$$. We can find that $$$x$$$ must be a multiple of $$$b_i/gcd(b_i, b_{i+1})$$$ for each $$$1 \leq i \lt n$$$ as a lower bound for the answer.

Let's prove that these conditions are also sufficient. To do this, let's analyze each pair $$$(i,i+1)$$$ separately. We analyze the following cases:

• if $$$b_i=a_i\cdot x$$$ and $$$b_{i+1}=a_{i+1}\cdot x$$$, or $$$b_i=a_i$$$ and $$$b_{i+1}=a_{i+1}$$$: in both cases, the choice of $$$x$$$ does not matter. The array is good if $$$b_i$$$ divides $$$b_{i+1}$$$ initially.
• If $$$b_i=a_i\cdot x$$$ and $$$b_{i+1}=a_{i+1}$$$, then taking the LCM over all $$$1 \leq i \lt n$$$ should ensure this case is always correct.
• If $$$b_i=a_i$$$ and $$$b_{i+1}=a_{i+1}\cdot x$$$, then a larger value of $$$x$$$ cannot possibly be beneficial, as the product $$$\frac{a_{i+1}}{a_i}$$$ decreases.

Since the problem guarantees $$$x$$$ exists, taking the LCM and outputting suffices. The solution runs in $$$O(n \log{a_i})$$$.

import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    gcd = 0
    lcm = 1
    for i in range(n-1,-1,-1):
        gcd = math.gcd(gcd, a[i])
        lcm = math.lcm(lcm, a[i] // gcd)
    print(lcm)

Solve the old version of this problem: given the array $$$b$$$ (where a solution is no longer guaranteed), output any array $$$a$$$ or claim it is not possible to obtain $$$b$$$ through a valid array $$$a$$$.

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Determine which elements you can delete with the operation.

Come up with a greedy solution that erases as little elements as possible.

First, let's come up with some conditions that determines whether erasing an element is possible.

Claim: as long as the $$$k-1$$$ smallest elements remain in the array, we can erase other elements in any way we want.

Proof: It is obvious why we cannot erase the $$$k-1$$$ smallest elements. If we want to erase any other element, we can simply start the following process to determine a pair of $$$(l,r)$$$ where we can erase the element: initially, start $$$l=1$$$ and $$$r=n$$$. Clearly, the element we want to erase is at least the $$$k$$$-th smallest element. After that, we can incrementally either increase $$$l$$$ or decrease $$$r$$$ until the element is exactly the $$$k$$$-th smallest. This process should always terminate because after $$$r-l+1 \lt k$$$, the element we want to delete is definitely less than the $$$k$$$-th smallest.

Let the $$$k-1$$$-th smallest element be $$$x$$$. Now, we can categorize each element in the array into three groups: elements less than $$$x$$$, elements equal to $$$x$$$, and elements greater than $$$x$$$. Note there is no point in keeping any elements in the third group, so we can erase them first (by creating a second array $$$b$$$ filled with only elements of the first and second groups). Now, we must strategically delete elements of the second group to make a palindrome. Note that we should try to erase as little elements as possible, because we must ensure the number of elements we don't erase is at least $$$k-1$$$. We can maintain this process with a two-pointers approach. Initialize $$$l=1$$$ and $$$r=|b|$$$. Then, if $$$b_l=b_r$$$, we can keep both. If $$$b_l\neq b_r$$$ and neither elements is $$$x$$$, we can conclude it's impossible. If one of $$$b_l,b_r$$$ is equal to $$$x$$$, we should flag the one equal to $$$x$$$ as being deleted and move the pointer. In the end, we can do a final check to ensure we did not erase too many elements.

The final solution runs in $$$O(n \log(n))$$$ due to sorting to find the $$$k$$$-th smallest element.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define all(x) x.begin(), x.end()
#define vecin(name, len) vector<int> name(len); for (auto &_ : name) cin >> _;
#define vecout(v) for (auto _ : v) cout << _ << " "; cout << endl;
 
 
void solve() {
    int n; cin >> n;
    int k; cin >> k;
    vecin(aa, n);
    if (k == 1) {
        cout << "YES" << endl;
        return;
    }
 
    vector<int> bb = aa;
    sort(all(bb));
    int cutoff = bb[k - 2];
    vector<int> cc;
    for (auto a : aa)
        if (a <= cutoff)
            cc.push_back(a);
    int spare = cc.size() - k + 1;
    int L = 0, R = cc.size() - 1;
    bool bad = false;
    while (L < R) {
        if (cc[L] != cc[R]) {
            if (spare == 0) {
                bad = true; break;
            }
            if (cc[L] == cutoff) {
                L ++;
                spare --;
            } else if (cc[R] == cutoff) {
                R --;
                spare --;
            } else {
                bad = true; break;
            }
            continue;
        }
        L ++;
        R --;
    }
    if (bad) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}
 
int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;
 
    cin >> tt;
 
    while (tt--) solve();
    return 0;
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Solve the $$$n=3$$$ case first.

The answer is either $$$-1$$$, $$$1$$$, or $$$2$$$.

First, find a construction in $$$3$$$. Then, optimize that to be done in $$$2$$$ moves.

First, let's determine when the answer is $$$-1$$$. Let $$$s$$$ be the sum of all elements in the array. The answer is $$$-1$$$ if:

• $$$s$$$ is odd, or
• There exists an element that is greater than half of $$$s$$$.

If neither of the above conditions hold, we can definitely get a solution in finitely many moves by simply subtracting $$$1$$$ from the largest element and $$$1$$$ from an arbitrary element in one move.

Let's now solve the $$$n=3$$$ case to grab some intuition. There's of course trivial cases where the answer is $$$1$$$ (where the first or last element is the sum of the other two). One array we may want to examine is where the second element is the sum of the first and last, like $$$[1,3,2]$$$. We can of course solve this in two moves, by setting $$$a_1$$$ to $$$0$$$ and $$$a_2$$$ to $$$a_3$$$ on the first move. What about some array where the middle element is less than the sum of the other two? For example, the array $$$[3,4,3]$$$. One thing we can try is trying to subtract from $$$a_1$$$ and $$$a_3$$$ so we can reduce to the $$$a_1+a_3=a_2$$$ case. Is this always possible? Turns out, it is always possible as long as $$$a_2 \lt a_1+a_3$$$ and $$$a_1+a_2+a_3$$$ is even (in this case, we would turn it into $$$[2,4,2]$$$ after our first move). We can even optimize it to two moves by combining two moves into one. In the case of $$$[3,4,3]$$$, we can transform the array to $$$[2,2,0]$$$ after the first move, combining two of the moves.

It turns out we can generalize the $$$n=3$$$ case for any $$$n$$$, by simply finding one "pivot" element to act as $$$a_2$$$, then letting $$$a_1$$$ be the sum of prefix before that and $$$a_3$$$ be the sum of suffix after that. Let $$$pos$$$ be the unique position in the array where $$$a_1+a_2+\ldots+a_{pos-1} \lt \frac{s}{2}$$$ and $$$a_1+a_2+\ldots+a_{pos}\geq\frac{s}{2}$$$. Let $$$x,y,z$$$ denote $$$a_1+a_2+\ldots+a_{pos-1}$$$, $$$a_{pos}$$$, and $$$a_{pos+1}+a_{pos+2}+\ldots+a_n$$$ respectively. Precisely, our goal is to make $$$x+z=y$$$ in the first move after subtracting a non-negative integer $$$w$$$ from both $$$x$$$ and $$$y$$$, make $$$x=0$$$ and $$$z=y$$$ after the second move, and $$$x=y=z=0$$$ after the third. To prove the first move is always possible, note that $$$x+z-y$$$ is always even (since sum of all elements in the array is even), and because $$$y\leq \frac{s}{2}$$$ implies $$$x+z\geq\frac{s}{2}$$$.

Finally, to optimize this solution to $$$2$$$ moves, instead of subtracting $$$w$$$ from both $$$x$$$ and $$$z$$$ in the first move, let's subtract $$$x$$$ from the first block, $$$x-w$$$ from the second block, and $$$w$$$ from the third block. Essentially, we are combining the first two operations into one.

The solution runs in $$$O(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
const ll MOD = 1E9 + 7;
const int INF = 1E9; const ll INFLL = 1E18;
 
int n;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    int T; cin >> T;
    for(int test = 1; test <= T; test++) {
        cin >> n;
        vector<ll> a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        ll sum = 0;
        for(ll i : a) {
            sum += i;
        }
        if(sum % 2) {
            cout << "-1\n";
            continue;
        }
        ll mx = 0;
        for(ll i : a) {
            mx = max(mx, i);
        }
        if(mx * 2 > sum) {
            cout << "-1\n";
            continue;
        }
        ll cur = 0; int ind = 0;
        for(; ind < n; ind++) {
            if(cur + a[ind] > sum / 2) {
                ind--;
                break;
            }
            cur += a[ind];
        }
        if(cur == sum / 2) {
            cout << "1\n";
            for(ll i : a) {
                cout << i << " ";
            }
            cout << "\n";
        } else {
            cout << "2\n";
            vector<ll> aa(n);
            ll extra = sum - 2 * cur;
            aa[ind + 1] = extra / 2;
            a[ind + 1] -= aa[ind + 1];
            extra /= 2;
            for(int i = n - 1; i > ind + 1 && extra; i--) {
                if(a[i] >= extra) {
                    aa[i] = extra;
                    a[i] -= extra;
                    extra = 0;
                } else {
                    aa[i] = a[i];
                    extra -= a[i];
                    a[i] = 0;
                }
            }
            for(int i = 0; i < n; i++) {
                cout << a[i] << " ";
            }
            cout << "\n";
            for(int i = 0; i < n; i++) {
                cout << aa[i] << " ";
            }
            cout << "\n";
        }
    }
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Given an integer $$$n$$$ and no restrictions, count the number of possible arrays you can form $$$(n \leq 2\cdot 10^5)$$$.

Characterize the arrays that we might overcount.

Optimize the DP using some cumulative sums.

Coming up with a polynomial solution

It's clear we need to do some sort of dynamic programming to count for this task. Initially, one may come up with let $$$dp_i$$$ be the number of ways to fill completely permutations with total length $$$i$$$.

Unfortunately, one downfall of the above solution is that some arrays are obtainable through many ways: for example, the array $$$[1,2,1]$$$ can be constructed with $$$[1]+[2,1]$$$ or $$$[1,2]+[1]$$$.

Upon further investigation, we can see that this occurs when we add two identity permutations of size $$$x$$$ and $$$y$$$ with $$$x \gt y$$$, as this can also be counted with a permutation of size $$$y$$$ and a shifted permutation of size $$$x$$$. We will choose to ban the second option (appending a shifted permutation that starts with $$$y+1$$$ when we just added a permutation of size $$$y$$$). We can come up with a counterexample to banning two identity permutations (a bigger one following a smaller one) with the array $$$[1,2,3,1,2,1]$$$, which can be counted as both $$$[1,2]+[3,1,2]+[1]$$$ and $$$[1]+[2,3,1]+[2,1]$$$.

This gives us a $$$O(n^4)$$$ solution. Let $$$dp(i,j)$$$ be the number of ways to make the sequence from indices $$$1$$$ through $$$i$$$, such that the last permutation added was an identity permutation of length $$$j$$$ (or not an identity permutation if $$$j=0$$$). We can build a solution by looping through (index, length of permutation, which cyclic shift to use), and checking if we can add this permutation naively.

Optimizing the solution to $$$O(n^2)$$$

There are several ways to do this part. Below shows one approach.

First, let's precalculate $$$chain(i,j)$$$, which returns the largest integer $$$k$$$ such that it is possible to fill numbers $$$i, i+1, \ldots, i+k-1$$$ with numbers $$$j,j+1,\ldots,j+k-1$$$. We can calculate this as $$$chain(i,j)=0$$$ if $$$a_i\neq j$$$ is a requirement, and $$$1+chain(i+1,j+1)$$$ otherwise. Let

• $$$dp(i,j)$$$ be the number of ways to fill indices $$$i,i+1,\ldots,n$$$ such that $$$a_i=j$$$
• $$$dp_2(i)$$$ be the sum of $$$dp(i,j)$$$ over all $$$1 \leq j \leq n$$$.
• $$$suff(i,j)$$$ be the number of ways such that we are ready to insert $$$j$$$ to complete the suffix from $$$i$$$ to $$$n$$$, but without taking into account restrictions.

We can calculate $$$suff(i,j)$$$ as $$$\sum_{x=i}^n(chain(x,1)\geq j-1)\cdot dp_2(x+j-1)$$$. Why is this helpful? Let's create an example. Suppose we fix $$$j=3$$$, and we have $$$chain(x,1)\geq 2$$$ is true for $$$x=3,4,6$$$. That is, it's possible to place $$$1$$$ and $$$2$$$ in positions $$$(3,4)$$$, $$$(4,5)$$$, and $$$(6,7)$$$. Then, we should have $$$suff(2,3)=dp_2(5)+dp_2(6)+dp_2(8)$$$. This is because suppose we set $$$a_2=3$$$. Then our $$$suff(2,3)$$$ means that we can theoretically put $$$(3,1,2), (3,4,1,2), (3,4,5,6,1,2)$$$ starting at index $$$2$$$, assuming there are no further restrictions.

Now our actual DP loop:

• Calculate $$$suff(i,j)$$$ as above
• Calculate $$$dp(i,1)$$$ by looping through all identity permutations we can append at index $$$i$$$. Say we are trying to add identity permutation of length $$$x$$$. We should add $$$dp_2(i+x)$$$ and subtract $$$dp(i+x,x+1)$$$ (this is to prevent overcounting as outlined before).
• Calculate $$$dp(i,j)$$$ for $$$j \gt 1$$$ as $$$suff(i+1,j)-suff(i+1+chain(i,j),j)$$$. The subtraction is to remove contribution from $$$suff$$$ that is not accessible due to constraints on $$$a_i \neq j$$$ using our chain array.

This solution works in $$$O(n^2+m)$$$. $$$m$$$ was kept low to allow $$$O(nm+n^2)$$$ to pass as well.

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

const int MOD = 998244353;
template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[ ";
    for(const auto& elem : vec) {
        os << elem << " ";
    }
    os << "]";
    return os;
}
struct Mint {
    int v;
    Mint(long long val = 0) {
        v = int(val % MOD);
        if (v < 0) v += MOD;
    }
    Mint operator+(const Mint &o) const { return Mint(v + o.v); }
    Mint operator-(const Mint &o) const { return Mint(v - o.v); }
    Mint operator*(const Mint &o) const { return Mint(1LL * v * o.v); }
    Mint operator/(const Mint &o) const { return *this * o.inv(); }
    Mint& operator+=(const Mint &o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
    Mint& operator-=(const Mint &o) { v -= o.v; if (v < 0) v += MOD; return *this; }
    Mint& operator*=(const Mint &o) { v = int(1LL * v * o.v % MOD); return *this; }
    Mint pow(long long p) const {
        Mint a = *this, res = 1;
        while (p > 0) {
            if (p & 1) res *= a;
            a *= a;
            p >>= 1;
        }
        return res;
    }
    Mint inv() const { return pow(MOD - 2); }
    friend ostream& operator<<(ostream& os, const Mint& m) {
        os << m.v;
        return os;
    }
};
void solve() {
    int N, K;
    cin >> N >> K;

    vector<vector<bool>> banned(N, vector<bool>(N));
    for (int i = 0; i < K; ++i) {
        int x, y;
        cin >> x >> y;
        banned[x - 1][y - 1] = true;
    }

    vector<Mint> tot(N + 1);
    tot[N] = 1;
    vector<vector<Mint>> dp(N + 1, vector<Mint>(N + 1));
    vector<vector<int>> chain(N + 1, vector<int>(N + 1));

    for (int i = N - 1; i >= 0; --i) {
        for (int j = N - 1; j >= 0; --j) {
            chain[i][j] = 1 + chain[i + 1][j + 1];
            if (banned[i][j]) chain[i][j] = 0;
        }
    }

    vector<vector<Mint>> ssum(N + 2, vector<Mint>(N + 1));

    for (int i = N - 1; i >= 0; --i) {
        for (int j = 0; j <= N - i; ++j) {
            if (j == 0) {
                for (int len = 1; len <= N - i; ++len) {
                    bool ok = chain[i][0] >= len;
                    if (!ok) break;
                    dp[i][j] += tot[i + len];
                    dp[i][j] -= dp[i + len][j + len];
                }
            } else {
                if (chain[i][j]) {
                    dp[i][j] += ssum[i + 1][j];
                    if (i + 1 + chain[i][j] <= N) {
                        dp[i][j] -= ssum[i + 1 + chain[i][j]][j];
                    }
                }
            }
            tot[i] += dp[i][j];
        }

        for (int j = 1; j < N; ++j) {
            ssum[i][j] = ssum[i + 1][j];
            if (chain[i][0] >= j) {
                ssum[i][j] += tot[i + j];
            }
        }
    }
    // cout << dp << endl;
    // cout << ssum << endl;
    cout << tot[0].v << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    
    return 0;
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Disregard cost first. Find the maximum sum of prefix minimums.

Come up with a way to have $$$O(n)$$$ $$$(i,j)$$$ pairs to test.

Let $$$f(a)=\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n)$$$. Can you come up with a way to solve $$$q$$$ queries of what $$$f(a)$$$ will be after performing the operation on $$$(i,j)$$$? (queries are not persistent here)

Let's disregard the cost part of the problem completely and try to solve the problem just for the maximum sum.

To solve this problem, we make the following observations:

1. If $$$i$$$ is not a prefix minimum, there is no point in using the operation to increase $$$a_i$$$.
2. If $$$j$$$ is not a suffix maximum, there is no point in using the operation to set $$$a_j:=0$$$. This is because we can instead use the closest suffix maximum to its right, and the final answer can only be larger.

Knowing this, let's enumerate $$$i$$$. If $$$i$$$ is not a prefix minima, we can skip it. Otherwise, there is no point to increasing $$$a_i$$$ past the previous prefix minima. Let's enumerate the number that we would like to increase $$$a_i$$$ to, and there should be a clear candidate on which suffix maximum to use as $$$j$$$. Since each $$$a_i$$$ is bounded by $$$n$$$, there is only $$$O(n)$$$ pairs of $$$(i,j)$$$ produced.

We now have to solve for what the score is after each operation. Suppose we increased $$$a_i$$$ to $$$x$$$. Let $$$k$$$ be the smallest index $$$k \gt i$$$ with $$$a_k\leq x$$$ ($$$k$$$ can be found by using a sparse table and binary search). We can now decompose $$$score(a)$$$ into the sum of the following four parts:

1. The prefix sum up to index $$$i$$$ — this can be precomputed easily
2. The score from $$$i$$$ to $$$k-1$$$ — this can be calculated easily as $$$x\cdot(k-i)$$$.
3. The score from $$$k$$$ to $$$n$$$ assuming $$$a_k$$$ is the prefix minimum. Call this $$$suffix(k)$$$. This can be precalculated as well using a monotonic stack. We can find the smallest number $$$l \gt k$$$ with $$$a_l \lt a_k$$$, then compute the answer as $$$suffix(l)+a_k\cdot(l-k)$$$.
4. Finally, we have to subtract the contribution from $$$j$$$ to $$$n$$$ since we set $$$a_j:=0$$$. Note that up to index $$$j$$$, the minimum $$$M$$$ is now $$$\min(a_1,a_2,\ldots,a_i-1, x, a_{i+1},a_{i+2},\ldots,a_{j-1})$$$. Now, we can use the same trick — binary search and sparse table to find the first $$$m\geq j$$$ with $$$a_m\leq M$$$, and subtract $$$suffix(m)+M(m-j)$$$ from our count here.

Now that we have a way to solve the full array, let's solve for all possible costs.

It can be shown that the same $$$O(n)$$$ queries from before will necessarily obtain the correct answers (proof is left as an exercise). Thus, to solve the problem, let's create an array $$$ans$$$, and while processing each $$$(i,j)$$$ pair, update $$$ans_{j-i}$$$. After that, taking the suffix maximum will suffice.

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "lib/debug.h"
#else
#define debug(...) 228
#endif
 
#define pb push_back
 
typedef long long ll;
typedef long double ld;
 
int n;
const int maxN = 1e6 + 10;
int a[maxN];
ll best[maxN];
ll pref[maxN];
int sec_mn[maxN];
ll pref_sec[maxN];
int MN[maxN];
int f[maxN];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n - 1; i++) {
        best[i] = 0;
    }
    vector<int> suf_max;
    suf_max.reserve(n);
    for (int i = n; i >= 1; i--) {
        if (suf_max.empty() || a[i] > a[suf_max.back()]) {
            suf_max.emplace_back(i);
        }
    }
    int mn = 1e9;
    sec_mn[0] = 1e9;
    MN[0] = 1e9;
    int ind = -1;
    for (int i = 1; i <= n; i++) {
        sec_mn[i] = sec_mn[i - 1];
        if (a[i] < mn) {
            if (ind != -1) {
                f[ind] = i;
            }
            sec_mn[i] = mn;
            mn = a[i];
            ind = i;
        }
        else if (a[i] < sec_mn[i]) {
            sec_mn[i] = a[i];
        }
        MN[i] = mn;
        pref[i] = pref[i - 1] + mn;
        pref_sec[i] = pref_sec[i - 1] + sec_mn[i];
    }
    assert(ind != -1);
    f[ind] = n + 1;
    best[0] = pref[n];
    vector<int> st{n + 1};
    a[n + 1] = -1e9;
    for (int i = n; i >= 1; i--) {
        if (MN[i - 1] > a[i]) {
            for (int id: suf_max) {
                if (id <= i) break;
                int cur_mn = min(a[i] + a[id], MN[i - 1]);
                int l = 0;
                int r = st.size();
                while (r - l > 1) {
                    int mid = (l + r) / 2;
                    if (a[st[mid]] <= cur_mn) l = mid;
                    else r = mid;
                }
                int upto = min(id - 1, st[l] - 1);
                ll val = pref[i - 1] + cur_mn * 1LL * (upto - i + 1);
//                if (i == 3 && id == 5) {
//                    cout << " HI " << endl;
//                    cout << val << " " << cur_mn << " " << upto << endl;
//                }
                if (upto + 1 < id) {
                    int upup = min(f[i], id);
//                    if (i == 1 && id == 4) {
//                        cout << val << " ???? " << upup << endl;
//                    }
                    assert(upup - 1 >= upto);
                    val += pref_sec[upup - 1] - pref_sec[upto];
                    val += pref[id - 1] - pref[upup - 1];
                }
                best[id - i] = max(best[id - i], val);
                if (a[i] + a[id] >= MN[i - 1]) break;
            }
        }
        while (!st.empty() && a[i] <= a[st.back()]) st.pop_back();
        st.emplace_back(i);
    }
    for (int i = n - 2; i >= 0; i--) best[i] = max(best[i], best[i + 1]);
    for (int i = 0; i < n; i++) cout << best[i] << " ";
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    auto start = std::chrono::high_resolution_clock::now();
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Characterize what a good subsequence is.

Use a range DP approach and some greedy techniques to find the answer

Let's first determine whether a given sequence can be good. We claim that a sequence $$$b$$$ is good if for each index $$$1 \leq i \leq |b|$$$, if $$$b_i=x$$$, then one of the following must be true:

1. $$$x=i$$$
2. $$$b_x=x$$$ and $$$min(b_x,b_{x+1},\ldots,b_i)\geq x$$$.

To prove this, we can note that this is necessary by transitivity of $$$ \gt $$$, and sufficient as we can construct a permutation (the method of doing so is left as an exercise to the reader).

Another way of thinking about this is: let $$$(i,j)$$$ be an interval where $$$b_i=i$$$, $$$b_j=i$$$, and there exists no index $$$k \gt j$$$ such that $$$b_k=i$$$. The condition $$$b_p \geq i$$$ should be satisfied for all indices $$$i \leq p \leq j$$$.

Uisng the above, we can construct a range DP solution. Let $$$dp(i,j)$$$ be the maximum length of a sequence if $$$b_{a_i}=a_i$$$, and we only consider numbers greater than or equal to $$$a_i$$$ from $$$i$$$ to $$$j$$$ while building the subsequence (essentially, this acts as one complete segment). We can initialize $$$dp(i,i)=a_i$$$ for each $$$i$$$. Then, we can enumerate $$$i$$$ from the back, and calculate the answer for each possible $$$j$$$. As we travel from $$$dp(i,j-1)$$$ to $$$dp(i,j)$$$, there are a few cases to consider:

1. $$$a_j=a_i$$$: we can simply add $$$1$$$ to $$$dp(i,j-1)$$$ to get $$$dp(i,j)$$$ as we can append it to our sequence for no cost.
2. $$$a_j \lt a_i$$$: we cannot append this due to the definition of good, so $$$dp(i,j)=dp(i,j-1)$$$.
3. $$$a_j \gt a_i$$$: Let's use a greedy approach to find where the segment beginning with $$$a_j$$$ should start. Clearly, it should start as soon as possible (since the starting point must have length $$$j$$$ already, and we cannot append anything less than $$$j$$$ before we begin). To do this, maintain a new array $$$first$$$ such that $$$first_k$$$ holds the smallest index $$$y$$$ where $$$dp(i,y)\geq a_y$$$ (so it is possible to start another segment with $$$a_y$$$ here, since we can delete any elements from a good sequence, and the sequence will still be good). Then, we can make the transition $$$dp(i,j)=\max(dp(i,j-1), dp(y,j))$$$.

The problem is solved in $$$O(n^2)$$$ time.

#include <bits/stdc++.h>
using namespace std;
#define int short
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    
    for (int i = n; i >= 1; i--){
        vector <int> good(n + 1, -1);
        int curr = a[i];
        
        dp[i][i] = curr;
        
        for (int j = i + 1; j <= n; j++){
            if (a[j] < a[i]){
                continue;
            }
            
            if (a[j] == a[i]){
                curr += 1;
                dp[i][j] = curr;
                continue;
            }
            
            if (good[a[j]] == -1 && a[j] <= curr + 1){
                good[a[j]] = j;
            }
            
            if (good[a[j]] != -1){
                int idx = good[a[j]];
                curr = max(curr, dp[idx][j]);
            }
        }
    }
    
    // for (int l = 1; l <= n; l++){
    //     for (int r = l; r <= n; r++){
    //         if (dp[l][r])
    //         cout << l << " " << r << " " << dp[l][r] << "\n";
    //     }
    // }
    
    int curr = 0;
    vector <int> good(n + 1, -1);
    for (int j = 1; j <= n; j++){
        if (good[a[j]] == -1 && a[j] <= curr + 1){
            good[a[j]] = j;
        }
        
        if (good[a[j]] != -1){
            int idx = good[a[j]];
            curr = max(curr, dp[idx][j]);
        }
    }
    
    cout << curr << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

Solve the inverse of this problem first. That is, given a permutation $$$p$$$, output $$$f(p)$$$.

Analyze the case of $$$x=[1,2,2,3,3]$$$. There is no solution to this $$$x$$$. Why?

Let's first come up with an algorithm to find $$$b$$$ given $$$p$$$.

Let $$$i$$$ be the first index with $$$p_i \lt p_1$$$. We can easily prove that the first subarray cannot go up to index $$$i$$$. This is because otherwise, the first element in $$$b$$$ will decrease, and this will be lexicographically smaller than a partition that does not include $$$i$$$.

Now, if $$$i=2$$$, then of course we should partition $$$p_1$$$ by itself. Otherwise, we should find the index $$$j$$$ with $$$1 \leq j \leq i$$$ and $$$p_j$$$ is the maximum element in the segment $$$[1,i]$$$, and partition up to $$$j-1$$$ (since this maximises the second element, which is what we want to do after maximising the first). We can now continue the process recursively, but assuming that $$$p_j$$$ is the front of the array.

Let's solve the actual problem now. Suppose we have $$$x_i=k$$$. Let $$$j$$$ be the largest index with $$$j \lt i$$$ and $$$x_j=k-1$$$. We can show that the sequence we obtain up to $$$i$$$ is the sequence up to $$$j$$$, plus $$$p_i$$$. This means that we can see the input array $$$b$$$ as the depths in a tree, where $$$j$$$ is the parent of $$$i$$$. We make the following observations:

1. If $$$x_i-x_{i-1} \gt 1$$$, then this is a trivial impossible case (the sequence up to $$$i$$$ or $$$i-1$$$ is invalid).
2. What does it mean if $$$i-j \gt 1$$$? This means that the sequence up to $$$i$$$ is an extension of $$$j$$$ (which is more than $$$1$$$ index ago), plus one number. From our analysis above, we know this means that all of $$$p_{j+1},p_{j+2},\ldots,p_i$$$ is greater than $$$p_j$$$, and $$$p_i$$$ is the largest of them all.
3. What does it mean if $$$i-j=1$$$? In this case, we cannot make any conclusions about the comparison of $$$p_i$$$ and $$$p_{i-1}$$$. Because index $$$i$$$ will be included no matter the comparison.
4. What does point $$$2$$$ mean? Observe the $$$[1,2,2,3,3]$$$ case again. Here, we should have $$$p_1 \lt p_2 \lt p_3$$$ and $$$p_3 \lt p_4 \lt p_5$$$. This implies $$$p_1 \lt p_2 \lt p_3 \lt p_4 \lt p_5$$$, but if this were the case then the array $$$x$$$ would be $$$[1,2,2,2,2]$$$ instead. More formally, looking at the tree, if node $$$i$$$ has more than one children, all of its children must have at most one children, or this contradiction will occur.

Using this, let's come up with a recursive function that traverses this tree and finds the permutation. Let $$$f(i,j,a,b)$$$ fill in $$$p_i,p_{i+1},p_{i+2},\ldots,p_j$$$ with numbers $$$a,a+1,a+2,\ldots,b$$$, where $$$i$$$ to $$$j$$$ is one full subtree, assuming that $$$i$$$ is already filled. First, let's find all direct children of node $$$i$$$ — that is all of the indices with $$$x_k=x_i+1$$$. If $$$i$$$ has more than one child and any of its children has more than one child, this is the impossible case as above. If $$$i$$$ has more than one child, then each of its children should have at most one child. First, let's assume that $$$p_i$$$ is already the smallest in the entire subtree. Let the sizes of subtrees of children be $$$b_1,b_2,\ldots,b_y$$$. We can reserve $$$b_i$$$ numbers for each subtree, and set each direct child to the largest number possible in each interval, and call our function recursively. Finally, if there is only one direct child, we can assume that $$$p_i$$$ is the largest number in the subtree, and we can assign the direct child to either be the largest or smallest number, depending on the number of children. We can first assign $$$p_1$$$ to be either $$$1$$$ or $$$n$$$ depending on how many indices $$$x_i=2$$$ there are, then call the recursive function. This will create the valid permutation.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define vt vector

vt<int> solve(const vt<int>& b, vt<vt<int>>& inv) {
    int n = b.size();
    if (inv[1].size() > 1) return {};

    vt<int> a(n);
    stack<array<int,5>> s;
    if (inv[2].size() > 1) {
        a[0] = 1;
        s.push({0, n-1, 2, n, 1});
    } else {
        a[0] = n;
        s.push({0, n-1, 1, n-1, 1});
    }

    while (!s.empty()) {
        auto tp = s.top(); 
        s.pop();
        int l = tp[0], r = tp[1], leftNum = tp[2], rightNum = tp[3], ok = tp[4];
        if (l == r) continue;
        if(b[l+1]!=b[l]+1) return {};
        int num = b[l] + 1;
        if (num >= inv.size()) return {};

        vt<int> nxt;
        while (inv[num].size() && inv[num].back() > l) {
            nxt.push_back(inv[num].back());
            inv[num].pop_back();
        }
        if (nxt.size()==0) return {};  
        if(!ok && nxt.size()!=1) return {};
        if (nxt.size() == 1) {
            if (num+1 < inv.size() && inv[num+1].size() > 1 && inv[num+1][inv[num+1].size()-2] > l) {
                a[nxt[0]] = leftNum++;
            } else {
                a[nxt[0]] = rightNum--;
            }
            s.push({l+1, r, leftNum, rightNum, 1});
        } else {
            rightNum -= nxt.size();
            int nx = rightNum + 1;
            reverse(nxt.begin(), nxt.end());
            int curLeft = leftNum;
            for (int i = 0; i < (int)nxt.size(); ++i) {
                int pos = nxt[i];
                a[pos] = nx++;
                int nextInd = (i+1 < (int)nxt.size() ? nxt[i+1] - 1 : r);
                int sz = nextInd - pos - 1;
                s.push({pos, nextInd, curLeft, curLeft + sz, 0});
                curLeft += sz + 1;
            }
        }
    }

    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vt<int> x(n);
        for (int i = 0; i < n; ++i) cin >> x[i];

        vt<vt<int>> inv(n+3);
        for (int i = 0; i < n; ++i) inv[x[i]].push_back(i);

        auto a = solve(x, inv);
        if (a.empty()) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
            for (int v : a) cout << v << ' ';
            cout << "\n";
        }
    }
    return 0;
}

• Great Problem
• Good Problem
• Okay Problem
• Bad Problem
• Did not solve

This can be solved by printing the zero-th index of each string in sequence. For example, suppose your strings are $$$a$$$, $$$b$$$, and $$$c$$$. Then in C++, you can use cout << a[0] << b[0] << c[0] << '\n';, and similarly, in Python you can use print(a[0] + b[0] + c[0]). See your preferred language's syntax for how to obtain a given indexed character from a string.

t = int(input())
for _ in range(t):
    inp = input()
    for w in inp.split():
        print(w[0],end="")
    print()

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What is the condition for $$$l'$$$ and $$$r'$$$ to be valid?

The problem reduces to finding $$$l'$$$ and $$$r'$$$ such that $$$r' - l' = m$$$ and $$$l\leq l' \leq 0 \leq r'\leq r$$$. There are several different approaches; two are outlined below.

One approach which runs in $$$O(1)$$$ time is to case on whether $$$m\leq r$$$. If $$$m\leq r$$$, we can choose $$$l' = 0$$$ and $$$r' = m$$$, and then we see that $$$r' - l' = m - 0 = m$$$ and $$$l \leq 0 \leq 0 \leq m \leq r$$$ as desired. If $$$m \gt r$$$, we can choose $$$l' = r-m$$$ and $$$r' = r$$$, and then we see that $$$r' - l' = r - (r-m) = m$$$ and $$$l \leq r-m \leq 0 \leq r \leq r$$$, where $$$l \leq r-m$$$ holds because $$$r-l = n \geq m$$$.

An alternative approach which runs in $$$O(m)$$$ time is to simply simulate the process; expand in an arbitrary direction which satisfies the desired inequalities until $$$r' - l' = m$$$.

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

void solve() {
    int n, m, l, r; cin >> n >> m >> l >> r;
    int diff = n - m;
    l = abs(l);
    if (l >= diff) {
        l -= diff;
        diff = 0;
    }
    else {
        diff -= l;
        l = 0;
    }
    cout << -l << " " << r - diff << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

How can we find $$$p_i$$$ for $$$2\leq i\leq n$$$? How can we find $$$p_i$$$ for $$$n+1\leq i\leq 2n$$$?

Observe that for all $$$2\leq i\leq n$$$, we can find $$$p_i$$$ by checking $$$G_{1, i-1}$$$. Then for all $$$n+1\leq i\leq 2n$$$, we can find $$$p_i$$$ by checking $$$G_{n, i-n}$$$. Now, we only have to find the value of $$$p_1$$$. However, each value from $$$1$$$ to $$$2n$$$ must appear exactly once in $$$p$$$. Thus, we can simply find the value which has not appeared yet, and choose that as $$$p_1$$$. This can be done by storing which values have been seen in a boolean array, and then finding which one remains false.

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

void solve() {
    int n; cin >> n;
    vector<int> ans(2*n+1, 0);
    vector<bool> used(2*n+1, false);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x; cin >> x;
            ans[i + j] = x;
            used[x] = true;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (ans[i] != 0) cout << ans[i] << " ";
        else {
            for (int j = 1; j <= n * 2; j++) {
                if (!used[j]) {
                    used[j] = true;
                    cout << j << " ";
                    break;
                }
            }
        }
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What would happen if $$$s_1$$$ consists of only $$$L$$$?

First, let us consider a simpler case of the problem: suppose that there is only $$$L$$$ in both $$$s_1$$$ and $$$s_2$$$. Then it is clear that the answer is yes if and only if $$$|s_1| \leq |s_2| \leq 2|s_1|$$$. If this holds (in particular, we also necessitate that $$$s_1$$$ and $$$s_2$$$ consist of only a single character, and the same character), we will call $$$s_2$$$ an extension of $$$s_1$$$.

Now, observe that the problem given is simply the simpler version, repeated several times alternating between $$$L$$$ and $$$R$$$. So we can partition $$$s_1$$$ into "blocks" (where we define a block to be a maximal group of contiguous identical characters). Then the answer is yes if and only if $$$s_2$$$ is the concatenation of extensions of blocks in $$$s_1$$$. For example, consider $$$s_1 = LLLLLRL$$$. We see that this consists of five $$$L$$$s, one $$$R$$$, and one $$$L$$$. So the answer is yes if and only if $$$s_2$$$ consists of between five and ten $$$L$$$s (inclusive), between one and two $$$R$$$s, and between one and two $$$L$$$ 's, concatenated in that order.

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

void solve() {
    string a, b; cin >> a >> b;
    int n = a.size();
    int m = b.size();
    if (m < n || m > 2 * n || a[0] != b[0]) {
        cout << "NO\n";
        return;
    }
    vector<int> aa, bb;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i-1]) {
            aa.push_back(cnt);
            cnt = 1;
        }
        else cnt++;
    }
    aa.push_back(cnt);
    cnt = 1;
    for (int i = 1; i < m; i++) {
        if (b[i] != b[i-1]) {
            bb.push_back(cnt);
            cnt = 1;
        }
        else cnt++;
    }
    bb.push_back(cnt);
    if (aa.size() != bb.size()) {
        cout << "NO\n";
        return;
    }
    n = aa.size();
    for (int i = 0; i < n; i++) {
        if (aa[i] > bb[i] || aa[i] * 2 < bb[i]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Consider each bit independently.

Suppose we fix $$$k$$$. How can we compute the desired sum quickly? Note that this may require preprocessing.

Here, it suffices to consider each bit independently, because addition is both commutative and associative. For $$$0\leq i \lt 30$$$, let $$$cnt_i$$$ denote the number of elements of $$$a$$$ which have the $$$i$$$-th bit set (where bits are indexed from the least significant bit being the $$$0$$$-th bit); note that these can be found in $$$O(30n)$$$ time (more generally, we need $$$O(\log\max{a_i})$$$ operations per element).

Now, suppose we choose a particular $$$k$$$. Then we can find the sum $$$(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$$$ as follows: for a given bit position $$$i$$$, the number of elements $$$a_j$$$ such that $$$a_k \oplus a_j$$$ has the $$$i$$$-th bit set will be $$$cnt_i$$$ if the $$$i$$$-th bit of $$$a_k$$$ is not set, and $$$n-cnt_i$$$ if the $$$i$$$-th bit of $$$a_k$$$ is set. So we can simply add $$$cnt_i \cdot 2^i$$$ to our sum if the $$$i$$$-th bit of $$$a_k$$$ is not set, and add $$$(n-cnt_i) \cdot 2^i$$$ to our sum if the $$$i$$$-th bit of $$$a_k$$$ is set.

This allows us to compute $$$(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$$$ for any $$$k$$$ in $$$O(30)$$$ time, so we can now compute this sum for all $$$k$$$ in $$$O(30n)$$$ time and output the maximum.

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

void solve() {
    int n; cin >> n;
    int arr[n+1];
    vector<int> cnt(30, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int j = 0; j < 30; j++) {
            cnt[j] += ((arr[i] >> j) & 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int tot = 0;
        for (int j = 0; j < 30; j++) {
            bool f = ((arr[i] >> j) & 1);
            if (f) tot += (1 << j) * (n - cnt[j]);
            else tot += (1 << j) * cnt[j];
        }
        ans = max(ans, tot);
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What would happen if we tried outputting the numbers $$$1, \dots, k, 1, \dots, k, \dots$$$ in the natural reading order? For example, for $$$n=3$$$, $$$m=4$$$, and $$$k=6$$$, we would output the following:

In which cases does this fail?

There are many working constructions for this problem; one of them is to case on whether or not $$$m$$$ is a multiple of $$$k$$$.

Suppose $$$m$$$ is not a multiple of $$$k$$$. For example, consider the second sample, where $$$n=3$$$, $$$m=4$$$, and $$$k=6$$$. Then we can output the numbers $$$1, \dots, k, 1, \dots, k, \dots$$$ in the natural reading order, as follows:

and we see that any two horizontally adjacent elements differ by $$$1\pmod k$$$, whereas any two vertically adjacent elements differ by $$$m\pmod k$$$, so no two adjacent elements are the same, as desired.

Now, suppose $$$m$$$ is a multiple of $$$k$$$. For example, consider the case $$$n=4$$$, $$$m=6$$$, and $$$k=3$$$. Suppose we were to try the above strategy, then we get:

which doesn't work, since vertically adjacent elements are the same. We can fix this by cyclically shifting every other row as follows:

and we see that any two horizontally adjacent elements differ by $$$1\pmod k$$$ as before, whereas any two vertically adjacent elements also differ by $$$1\pmod k$$$, so no two adjacent elements are the same, as desired.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,m,k = map(int,input().split())
    LAST = [-1 for _ in range(m)]
    for i in range(n):
        shift = False
        CUR = [0 for _ in range(m)]
        for j in range(m):
            elm = ((i * m + j) % k) + 1
            if elm == LAST[j]:
                shift = True
            CUR[j] = elm
        if shift:
            CUR = [CUR[(j+1)%m] for j in range(m)]
        print(*CUR)
        LAST = CUR

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Note that reversing an array then pushing an element to the back is similar to simply pushing an element to the front. Thus, we would like to push elements to both ends of the array. What data structure supports this?

What other values do we need to maintain in order to keep track of score?

We can solve this using a deque. Let $$$score$$$ denote the current score, and $$$rscore$$$ denote the score of the array if it were backwards. Let $$$size$$$ denote the size of the array, and $$$sum$$$ denote the sum of the array. Then we consider how these three values change as each operation is performed.

Suppose operation 1 is performed. This is equivalent to popping the back element of the array and pushing it in the front. When you pop the back element of the array, $$$score$$$ decreases by $$$a_n \cdot size$$$. Then when you push it to the front, $$$score$$$ increases by $$$sum$$$ because $$$a_n$$$ is pushed to the first spot and every element from $$$a_1$$$ to $$$a_{n-1}$$$ moves forward one spot. Notice that $$$rscore$$$ changes in the reverse way; this is equivalent to popping the front element of the array and pushing it to the back. When you pop the front element of the array, $$$rscore$$$ decreases by $$$sum$$$, and when you push it to the back, $$$rscore$$$ increases by $$$a_n \cdot size$$$. Note that $$$size$$$ and $$$sum$$$ remain unchanged.

Suppose operation 2 is performed. Then we swap $$$score$$$ and $$$rscore$$$, and we also want to "reverse" the array. However, it is costly to entirely reverse the deque. Instead, we will set a flag to indicate that the array has been reversed (and similarly, if the flag is already set, we will unset it). If the flag is set, we simply switch the front and back ends whenever we access or modify the deque while performing operations 1 or 3.

Suppose operation 3 is performed. Then we see that $$$size$$$ increases by $$$1$$$ and $$$sum$$$ increases by $$$k$$$. Then $$$score$$$ increases by $$$k \cdot size$$$ and $$$rscore$$$ increases by $$$sum$$$ (using the new value of $$$sum$$$), by identical reasoning to that in operation 1.

Additional optimization: we don't actually have to maintain $$$rscore$$$; we can obtain it with the expression: $$$(n+1)\sum_{i=1}^na_i-score$$$. This is because $$$score + rscore = (n+1)\sum_{i=1}^na_i$$$ since the $$$i$$$-th term is counted $$$i$$$ times in $$$score$$$ and $$$n+1-i$$$ times in $$$rscore$$$.

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

void solve() {
    int norm = 0, rev = 0;
    int q; cin >> q;
    int tot = 0;
    int n = 0;
    deque<int> qNorm, qRev;
    int p = 0;
    while (q--) {
        int s; cin >> s;
        if (s == 1) {
            int last = qNorm.back();
            qNorm.pop_back();
            qNorm.push_front(last);
            norm += (tot - last);
            norm -= last * n;
            norm += last;

            last = qRev.front();
            qRev.pop_front();
            qRev.push_back(last);
            rev -= (tot - last);
            rev += last * n;
            rev -= last;
        }
        else if (s == 2) {
            swap(rev, norm);
            swap(qNorm, qRev);
        }
        else if (s == 3) {
            n++;
            int k; cin >> k;
            qNorm.push_back(k);
            qRev.push_front(k);
            norm += k * n;
            rev += tot;
            rev += k;
            tot += k;
        }
        cout << norm << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

What must the value of $$$a[i]$$$ be in order for $$$k$$$ to change?

Can we use this to bound the number of times $$$k$$$ changes?

Consider a particular query. We make the following two observations: first, the value of $$$k$$$ only changes if $$$a[i]$$$ is a divisor of $$$k$$$, and second, if there exists $$$a[i_1] = a[i_2]$$$ with $$$l\leq i_1 \lt i_2 \leq r$$$, then the value of $$$k$$$ will not change at $$$i=i_2$$$ (because after the iteration $$$i=i_1$$$, we have that $$$k$$$ is no longer divisible by $$$a[i_2]$$$).

This allows us to bound the number of times $$$k$$$ changes by $$$d(k)$$$, where $$$d(k)$$$ is the number of divisors of $$$k$$$. Note that the divisors of $$$d(k)$$$ can be found in $$$O(\sqrt{k})$$$ time by checking if $$$a$$$ divides $$$k$$$ for every $$$a$$$ from $$$2$$$ to $$$\sqrt{k}$$$, and if so, $$$a$$$ and $$$\frac{k}{a}$$$ are both divisors of $$$k$$$. Furthermore, at the scale constrained by the problem bounds, $$$d(k)$$$ is around $$$O(\sqrt[3]{k})$$$, so we only have to update $$$k$$$ at most $$$O(\sqrt[3]{k})$$$ times.

Now, we would like to find the first time each divisor of $$$k$$$ appears in $$$a[l], \dots, a[r]$$$. This can be done by storing the array $$$a$$$ in a map, where each value is mapped to a vector of indices where that values appears. Then for a given divisor of $$$k$$$, we can use lower_bound() (or generally, binary search) to find the smallest index at or after $$$l$$$ where this divisor appears, and we can check if it is no greater than $$$r$$$.

Now, we have a list of indices at which $$$k$$$ might change. So, suppose that $$$k$$$ changes to $$$k'$$$ at index $$$i_1$$$, and then changes to $$$k' '$$$ at index $$$i_2$$$ (and these are adjacent changes). Then we know that we have a value of $$$k'$$$ from $$$i=i_1$$$ to $$$i_2-1$$$, so we can add $$$k' \cdot (i_2 - i_1)$$$ to $$$ans$$$. We can then do this for all changes. This allows us to solve the problem in $$$O(n\log{n})$$$ preprocessing time and $$$O(\sqrt{k} + d(k)\log{n})$$$ time per query.

There are a few ways to optimize the runtime further, if your implementation is too slow. We can use a vector (of vectors) instead of a map, since $$$A = \max a_i = 10^5$$$ is reasonably small. Note that instantiating a vector of this size in every test case is too slow, so you may have to instantiate it globally and clear the vectors that were used after each test case.

Another optimization is to preprocess divisors instead of computing them on the spot. We can compute and store the divisors of all integers $$$2\leq a_i\leq 10^5$$$ in $$$O(A\log A)$$$ time in a vector of vectors where $$$divisor[a_i]$$$ contains all divisors of $$$a_i$$$ as follows: for all $$$2\leq i\leq A$$$, we push $$$i$$$ into $$$divisors[j]$$$ for all multiples $$$j$$$ of $$$i$$$. (The runtime follows from the fact that there are $$$\lfloor\frac{A}{i}\rfloor$$$ multiples of $$$i$$$ which are at most $$$A$$$, so across all $$$i$$$, we have at most $$$\frac{A}{1} + \frac{A}{2} + \cdots + \frac{A}{A} = A(\frac{1}{1} + \cdots + \frac{1}{A}) = AH(A) = O(A\log A)$$$ computations). This allows us to remove the $$$\sqrt{k}$$$ term in the runtime of each query.

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

void solve() {
    map<int, vector<int>> pos;
    map<int, int> ptr;
    int n, q; cin >> n >> q;
    int arr[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        pos[arr[i]].push_back(i);
        ptr[arr[i]] = 0;
    }
    vector<tuple<int, int, int, int>> qr(q);
    int c = 0;
    for (auto &[l, r, v, i]: qr) {
        cin >> v >> l >> r;
        i = c++;
    }
    vector<int> anss(q);
    sort(qr.begin(), qr.end());
    int prevL = 1;
    for (auto [l, r, v, idd]: qr) {
        for (int j = prevL; j < l; j++) {
            ptr[arr[j]]++;
        }
        prevL = l;
        vector<pair<int, int>> facts;
        for (int i = 1; i * i <= v; i++) {
            if (v % i == 0) {
                int fact1 = v / i;
                if (!(pos[fact1].size() == 0 || ptr[fact1] >= pos[fact1].size() || pos[fact1][ptr[fact1]] > r || fact1 == 1)) {
                    facts.push_back({pos[fact1][ptr[fact1]], fact1});
                }
                int fact2 = i;
                if (fact2 == fact1) continue;
                if (!(pos[fact2].size() == 0 || ptr[fact2] >= pos[fact2].size() || pos[fact2][ptr[fact2]] > r || fact2 == 1)) {
                    facts.push_back({pos[fact2][ptr[fact2]], fact2});
                }
            }
        }
        sort(facts.begin(), facts.end());
        int pr = l;
        int ans = 0;
        for (auto [idx, val]: facts) {
            int rr = idx - pr;
            ans += v * rr;
            while (v % val == 0) v /= val;
            pr = idx;
        }
        if (facts.empty()) ans = v * (r - l + 1);
        else ans += (r - pr + 1) * v;
        anss[idd] = ans;
    }
    for (int i = 0; i < q; i++) cout << anss[i] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$n$$$ be the length of the string. Output the first $$$n-2$$$ characters of the string (to remove the suffix "us"), then the lowercase letter "i".

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
 
void tc () {
    string str;
    cin >> str;
    str.pop_back();
    str.pop_back();
    cout << str + "i" << '\n';
}
 
int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Note that if you can ever do an operation, the answer is $$$1$$$. This is because once you've done an operation on a string of length $$$k$$$, you are free to choose any character to replace $$$s_i$$$ with. Therefore, if you replace $$$s_i$$$ either with the character directly before it, or the character directly after it, you will end up with a string with length $$$k-1$$$ upon which you can do an operation again. Therefore, by induction, it's clear that you can keep operating on the string until only one character remains.

However, if you cannot perform any operations, the answer is $$$|s|$$$, because you have not modified the original string.

Therefore, the answer is $$$1$$$ if $$$s_i = s_{i+1}$$$ for some $$$i$$$, or $$$n$$$ otherwise.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    string str;
    cin >> str;
    for (ll i = 1; i < str.size(); i++) {
        if (str[i-1] == str[i]) {
            cout << "1\n";
            return;
        }
    }
    cout << str.size() << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

The overall idea for both subtasks is that you need to iterate from left to right, and upon each element, pick the operation such that you obtain the smallest value of $$$a_i$$$ that is greater than $$$a_{i-1}$$$.

For C1, you only have two values to consider for each index — $$$b_1-a_i$$$ and $$$a_i$$$. First, set $$$a_1 = min(a_1, b_1-a_1)$$$, then for each subsequent element $$$i$$$, consider the two values $$$b_1-a_i$$$ and $$$a_i$$$. If the smaller of these values is greater than or equal to $$$a_{i-1}$$$, then set $$$a_i$$$ to this value. Otherwise, check the larger value. If this value is less than $$$a_{i-1}$$$, you can straight away output $$$NO$$$ and move onto the next testcase. Otherwise, set $$$a_i$$$ as the larger of the two aforementioned values. Time complexity: $$$\mathcal{O}(n)$$$ per testcase.

For C2, you now have $$$m$$$ values in the array $$$b$$$. Clearly, we now need to consider $$$m+1$$$ different possible values per index of $$$a$$$. Solving this problem in $$$\mathcal{O}(nm)$$$ is clearly too slow. Therefore, we need to employ a different technique.

Note that instead of trying every value, you can sort all the values in $$$m$$$, and then binary search for the minimal value of $$$b_j$$$ such that $$$b_j-a_i \gt = a_{i-1}$$$. Then, you're left with the original problem, where you either leave $$$a_i$$$ untouched or you set it to $$$b_j - a_i$$$ for this optimal index $$$j$$$ that you found using binary search. Now, by proceeding as before, the problem is solved in $$$\mathcal{O}(n \log m)$$$ time.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
 
const ll INF = ll(1E18)+16;
 
void tc () {
    ll n, m;
    cin >> n >> m;
    vll va(n), vb(m);
    for (ll &i : va) cin >> i;
    for (ll &i : vb) cin >> i;
    sort(vb.begin(), vb.end());
    va.insert(va.begin(), -INF);
    n++;
    for (ll i = 1; i < n; i++) {
        auto it = lower_bound(vb.begin(), vb.end(), -15, [&](ll a, ll _) {
            assert(_ == -15);
            return a-va[i] < va[i-1];
        });
        if (it == vb.end()) continue;
        ll j = *it;
        if (va[i] < va[i-1] && j-va[i] < va[i-1]) continue; // OH MY GOD
        va[i] = min((va[i] < va[i-1] ? INF : va[i]), (j-va[i] < va[i-1] ? INF : j-va[i]));
    }
    cout << (is_sorted(va.begin(), va.end()) ? "YES" : "NO") << '\n';
}
 
int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

It is clear that the score of an array $$$b$$$ of length $$$n$$$ can be expressed as $$$n * b_1 + (n-1) * b_2 + (n-2) * b_3 \dots + 1 * b_n$$$.

Let's solve this problem with $$$m=1$$$ for $$$n$$$ arrays with $$$1$$$ element in each. Due to the above fact, it's clear that the optimal way to arrange this array is to sort the elements from largest to smallest.

Now, we come to the issue of combining arrays. Suppose you have two arrays $$$a$$$ and $$$b$$$, both of length m. Is there a nice way of expressing the score of $$$a+b$$$ and the score of $$$b+a$$$ (where $$$+$$$ represents concatenation) in terms of $$$score(a)$$$ and $$$score(b)$$$?

Turns out there is. The score of $$$a+b$$$ is equal to $$$n * sum(a) + score(a) + score(b)$$$. This is because of the following:

$$$score(a+b) = (2n * a_1) + ((2n-1) * a_2) \dots + ((n+1) * a_n) + (n * b_1) \dots + (1 * b_n)$$$

Now, we can clearly replace all the $$$b$$$ terms with $$$score(b)$$$ as follows: $$$score(a+b) = (2n * a_1) + ((2n-1) * a_2) \dots + ((n+1) * a_n) + score(b)$$$

Now, we can take out a factor of $$$n$$$ as follows: $$$score(a+b) = ((n+n) * a_1) + ((n + (n-1)) * a_2) \dots + ((n+1) * a_n) + score(b)$$$ $$$score(a+b) = (n * (a_1 + a_2 + a_3)) + (n * a_1) + ((n-1) * a_2) \dots + (1 * a_n) + score(b)$$$ $$$score(a+b) = (n * sum(a)) + score(a) + score(b)$$$

Therefore, whichever of $$$a$$$ and $$$b$$$ has the larger sum should go first, because then you get a larger overall score. This argument also extends beyond two arrays, so the solution is as follows:

Sort the arrays themselves in terms of their sum, from largest sum to smallest Put together the final array Take the score This score is guaranteed to be maximal.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
 
void tc () {
    ll n, m;
    cin >> n >> m;
    vector <vll> ve(n, vll(m));
    for (vll &ve2 : ve) {
        for (ll &i : ve2) cin >> i;
    }
    vll vsum(n, 0);
    for (ll i = 0; i < n; i++) {
        for (ll j : ve[i]) vsum[i] += j;
    }
    vll th(n);
    iota(th.begin(), th.end(), 0);
    sort(th.begin(), th.end(), [&](ll a, ll b) {
        return vsum[a] > vsum[b];
    });
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ans += vsum[th[i]]*(n-1-i)*m;
    }
    for (vll ve2 : ve) {
        for (ll i = 0; i < m; i++) {
            ans += ve2[i]*(m-i);
        }
    }
    cout << ans << '\n';
}
 
int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Claim 1: It is impossible when $$$k \lt |n-m|$$$

Proof 1: The entire string will have a balance value greater than $$$k$$$.

Claim 2: It is impossible when $$$k \gt max(n, m)$$$

Proof 2: The maximal possible balance value of any string with $$$n$$$ ones and $$$m$$$ zeroes is $$$max(m, n)$$$, as it is impossible due to the balance value definition.

To complete the construction, WLOG $$$n \ge m$$$ (because you can invert the string to get the solution for $$$n \lt m$$$. Output $$$k$$$ zeroes, then output alternating ones and zeroes, then output the remaining ones at the end. Note that with this construction, a substring with balance value $$$k$$$ exists (as you can take the first $$$k$$$ numbers), but a substring with balance value $$$ \gt k$$$ does not exist (as taking more of the string cannot increase the balance value).

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

int main(){
	int t; cin >> t;
	while(t--){
		int n, m, k; cin >> n >> m >> k;
		if(max(n, m) - min(n, m) > k || k > max(n, m)){
			cout << "-1" << endl;
			continue;
		}
		else{
			pair<int, int> use1 = {n, 0}, use2 = {m, 1};
			if(m > n) swap(use1, use2);
			for(int i = 0; i < k; i++){
				cout << use1.second;
				use1.first--;
			}
			while(use2.first > 0){
				cout << use2.second;
				use2.first--;
				swap(use1, use2);
			}
			while(use1.first > 0){
				cout << use1.second;
				use1.first--;
			}
			cout << "\n";
		}
	}
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Assume that a sequence a of length $$$n$$$ contains two types of elements, $$$1$$$ denoting majority and $$$0$$$ denoting "not majority".

Then, if a contains a majority and $$$n \ge 2$$$, the following condition holds. a must contain either $$$[1,1]$$$ or $$$[1,0,1]$$$.

This can be shown by contradiction. It is given that there are $$$k$$$ instances of $$$1$$$ and $$$n-k$$$ instances of $$$0$$$. Then it is known that $$$k \gt n-k$$$, so $$$2k \gt n$$$. If a does not contain $$$[1,1]$$$, then it needs a $$$0$$$ between every $$$1$$$. The only way this can happen is when $$$n-k \ge k-1$$$. This means $$$n+1 \ge 2k$$$, but because $$$n \lt 2k \le n+1$$$ the only value $$$k$$$ can take is $$$\frac{n+1}{2}$$$. When this happens, the only valid orientation of $$$a$$$ is $$$[1,0,1,0,\ldots,0,1,0,1]$$$, but still this contains $$$[1,0,1]$$$. Therefore, it definitely contains either $$$[1,1]$$$ or $$$[1,0,1]$$$.

But we can notice, the subarrays $$$[1,1]$$$ and $$$[1,0,1]$$$ already contain the majority $$$1$$$. So due to this, we conclude that the tree containing the pattern $$$[k,k]$$$ or $$$[k,x,k]$$$ for some value $$$k$$$, is an equivalent condition to the tree containing a non-trivial path with majority $$$k$$$.

Checking the existence of $$$[k,k]$$$ and $$$[k,x,k]$$$ in the tree for all k can be done in $$$\mathcal{O}(n)$$$ time, due to $$$\sum{\text{deg}} = 2m = 2(n-1)$$$. The problem has been solved in $$$\mathcal{O}(n)$$$ time.

You can solve this problem using the Auxiliary Tree technique. Formally, the auxiliary tree of $$$k$$$ specified vertices is the tree consisting of the specified vertices and their pairwise lowest common ancestors. It can be shown that such a tree will always have $$$\mathcal{O}(k)$$$ vertices and can be found in $$$\mathcal{O}(k \log n)$$$ time using widely known algorithms.

Observe the fact that, when you transform the value $$$x$$$ into $$$1$$$ and all other values into $$$-1$$$, $$$x$$$ is the majority of the sequence if and only if the transformed sequence has a positive sum. This hints us towards finding the maximum sum of any non-trivial path under the transformed tree. If the maximum sum is found to be positive, then we can determine that there exists a path with $$$x$$$ as its majority.

This subproblem can be solved by running a modified version of Kadane's algorithm, adapted for use on a tree. This adaptation is widely known for the case when the given tree is a binary tree, and it is trivial to modify it for use on any tree while keeping the time complexity to be $$$\mathcal{O}(n)$$$.

The only problem is that solving this for all values is $$$\mathcal{O}(n^2)$$$, so we compress the tree for each value using the Auxiliary Tree technique. By getting the auxiliary tree for the specified vertices, you get the specified vertices and their LCAs. If some vertex is specified, the value on it is transformed into $$$1$$$. Otherwise, the value on it is transformed into $$$-1$$$. Meanwhile, now there are lengths on edges, and an edge with length greater than $$$1$$$ means that there are unspecified vertices compressed in the edge. Therefore, if an edge has length $$$l$$$ which is greater than $$$1$$$, make sure to make a new vertex with value $$$-l+1$$$ in the middle of the edge as it means that $$$l-1$$$ vertices are compressed into the edge.

As there are $$$n$$$ specified vertices in total, finding each auxiliary tree takes $$$\mathcal{O}(n \log n)$$$ time. Solving the rest of the problem for each $$$i$$$ only takes $$$\mathcal{O}(n)$$$ time trivially. Thus, the problem has been solved in $$$\mathcal{O}(n \log n)$$$ time.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 5E5+16;
vll adj[MAXN];

void tc () {
    ll n;
    cin >> n;
    vll ve(n);
    for (ll &i : ve) cin >> i, i--;
    fill(adj, adj+n, vll({}));
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    string ans = string(n, '0');
    for (ll u = 0; u < n; u++) {
        map <ll, ll> mp;
        for (ll v : adj[u]) {
            mp[ve[v]]++;
        }
        mp[ve[u]]++;
        for (auto [a, b] : mp) {
            if (b >= 2) ans[a] = '1';
        }
    }
    cout << ans << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

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

#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)

vector<int> adj[500005];
int a[500005];
int s[500005];
int d[500005];
int t[1000005];
vector<int> v[500005];

int timer = 0;
void dfs(int node, int pa) {
    d[node] = d[pa]+1;
    s[node] = ++timer;
    t[timer] = node;
    v[a[node]].push_back(node);
    for (auto it : adj[node]) {
        if (it == pa)continue;
        dfs(it,node);
        t[++timer] = node;
    }
}

// sparse table
pii spt[1000005][20];

void buildspt(int n) {
    for (int i = 1; i <= 2*n-1; ++i) {
        spt[i][0] = {d[t[i]],i};
    }
    for (int j = 1; (1<<j) <= 2*n-1; ++j) {
        for (int i = 1; i+(1<<j)-1 <= 2*n-1; ++i) {
            spt[i][j] = min(spt[i][j-1],spt[i+(1<<(j-1))][j-1]);
        }
    }
    return;
}

pii qry(int l, int r) {
    int dd = __lg(r-l+1);
    return min(spt[l][dd],spt[r-(1<<dd)+1][dd]);
}

int _lca(int l, int r) {
    return t[qry(s[l],s[r]).s];
}

int dp[500005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for (int i = 1; i <= n-1; ++i) {
            int u, _v;
            cin >> u >> _v;
            adj[u].push_back(_v);
            adj[_v].push_back(u);
        }
        timer = 0;
        dfs(1,0);
        buildspt(n);
        for (int i = 1; i <= n; ++i) {
            vector<int> v2;
            int ans = -2e9;
            for (auto it : v[i]) {
                dp[it] = 1;
                if (v2.size()) {
                    int lca = _lca(v2.back(),it);
                    while (v2.size() && d[lca] < d[v2.back()]) {
                        int z = v2.back();
                        v2.pop_back();
                        if (v2.empty() || d[v2.back()] < d[lca]) {
                            dp[lca] = (a[lca] == i ? 1 : -1);
                            v2.push_back(lca);
                        }
                        amax(ans,dp[v2.back()]+dp[z]-(d[z]-d[v2.back()]-1));
                        amax(dp[v2.back()],dp[z]+(a[v2.back()] == i ? 1 : -1)-(d[z]-d[v2.back()]-1));
                    }
                }
                v2.push_back(it);
            }
            while ((int)v2.size() > 1) {
                int z = v2.back();
                v2.pop_back();
                amax(ans,dp[v2.back()]+dp[z]-(d[z]-d[v2.back()]-1));
                amax(dp[v2.back()],dp[z]+(a[v2.back()] == i ? 1 : -1)-(d[z]-d[v2.back()]-1));
            }
            cout << (ans > 0);
        } cout << '\n';
        for (int i = 1; i <= n; ++i) {
            adj[i].clear();
            v[i].clear();
        }
    }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$a_i=x$$$ and $$$a_j=y$$$ for any pair $$$(i,j)$$$ that we count.

First, let's note that since $$$x|lcm(x,y)$$$, we don't need to consider any cases where $$$x$$$ or $$$y$$$ has more than two prime factors. There are three cases we must consider:

1. $$$x$$$ and $$$y$$$ are primes, and $$$x\neq y$$$. Then, $$$lcm(x,y)=x\cdot y$$$ and has two prime factors.

2. $$$x$$$ is a semiprime, and $$$y$$$ is a prime factor of $$$x$$$. Then, $$$lcm(x,y)=x$$$.

3. $$$y$$$ is a semiprime, and $$$y=x$$$.

To count this, let's first factorize each number in the array (either by trial division in $$$O(n\sqrt{a_i})$$$ or $$$O(n\log(n))$$$ sieve precomputation). Let's maintain two maps, one mapping each semiprime present in the array to its number of occurrences, and one mapping each prime present in the array to its number of occurrences. Let $$$cnt[x]$$$ be the number of occurrences of $$$x$$$. Then, we can count each case as follows:

1. Let the total number of primes be $$$P$$$. For each prime $$$p$$$, its contribution will be $$$cnt[p]\cdot(P-cnt[p])$$$. Note that we must divide our result by $$$2$$$ as we would have counted each pair twice.

2. For each semiprime $$$pq$$$, add $$$cnt[pq]\cdot cnt[p]+cnt[pq]\cdot cnt[q]$$$.

3. For each semiprime $$$pq$$$, add $$$cnt[pq]\cdot (cnt[pq]+1)/2$$$.

All of these can be done in $$$O(n\log n)$$$ time. Be sure to not use dictionary, counter, or unordered_map as they can be hacked!

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

vector<int> prime_factors(int x){
	vector<int> pf;
	for(ll i = 2; i * i <= x; i++){
		while(x % i == 0){
			pf.push_back(i);
			x /= i;
		}
	}
	if(x > 1) pf.push_back(x);
	return pf;
}

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		ll ans = 0;
		vector<int> one(n+1), two_same(n+1), two_diff(n+1), cnt(n+1);
		int prime_so_far = 0;
		for(int i = 0; i < n; i++){
			int x; cin >> x;
			vector<int> pf = prime_factors(x);
			if(pf.size() > 2) continue;
			if(pf.size() == 1){
				one[x]++;
				prime_so_far++;
				ans += two_same[x] + two_diff[x] + (prime_so_far - one[x]);
			}
			else if(pf[0] == pf[1]){
				two_same[pf[0]]++;
				ans += one[pf[0]] + two_same[pf[0]];
			}
			else{
				two_diff[pf[0]]++;
				two_diff[pf[1]]++;
				cnt[x]++;
				ans += one[pf[0]] + one[pf[1]] + cnt[x];
			}
		}
		cout << ans << "\n";
	}
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

A brute attempt at a solution would be to go through each non-empty subset of $$${1,2,...,n}$$$ and, for every pair of adjacent indices $$$(i, j)$$$ in the subset, increase $$$ans$$$ if $$$s[i] \neq s[j]$$$ In other words, increase ans every time $$$s[i]$$$ and $$$s[j]$$$ create a new border

This is extremely slow at $$$O(2^n*n)$$$; however, we can notice that every adjacent pair is independent from the rest in the subset. We may ask ourselves: for a fixed $$$(i, j)$$$, how many subsets increase ans through that $$$(i, j)$$$? The conditions are that:

• $$$i$$$ and $$$j$$$ are in the subset
• $$$i$$$ and $$$j$$$ are adjacent in the subset (there's no other included value in between)
• $$$s[i] \neq s[j]$$$

Which leaves us free to choose the prefix and the suffix. $$$(2^{i-1}*2^{n-j})$$$.

An $$$O(n^2)$$$ solution is:

ans := 2^n-1
for j (1<=j<=n):
    for i (1<=i<j):
        if (s[i] != s[j])
            ans += 2^(i-1)*2^(n-j)

The rest of the solution will try to optimize how to compute that sum, and then how to maintain the answer through updates. We may notice we can pull out the $$$2^{n-j}$$$ factor and rewrite the loops as:

ans := 2^n-1
for j (1<=j<=n):
    sumI := 0
    for i (1<=i<j):
        if (s[i] != s[j])
            sumI += 2^(i-1)
    ans += sumI*2^(n-j)

Since the second for loop only cares about what $$$s[j]$$$ is (nothing else about $$$j$$$), we can again easily optimize it as:

ans := 2^n-1
sumI := [0, 0]
for j (1<=j<=n):
    ans += sumI[s[j]]*2^(n-j)
    sumI[s[j]\oplus1] += 2^(j-1)

In other words, we don't need to recalculate $$$sumI$$$ each new $$$j$$$. Instead, we can maintain its $$$2$$$ possible values ($$$s[j]=0, s[j]=1$$$) as we increase $$$j$$$ (since $$$sumI$$$ cares about ($$$1\leq i \lt j$$$))

We can run this $$$O(n)$$$ solution once before any updates, but not after each update because $$$O(q*n)$$$ is too slow. Instead, we can make the minimal adjustments needed to maintain ans correctly. Let's call the toggled index $$$k$$$: How much does $$$s[k]$$$ contribute to ans in the first place? We can partition $$$s[k]$$$'s contribution to the answer in $$$2$$$ cases: - When $$$j=k$$$, $$$ans += sumI[s[k]]*2^{n-k}$$$ - After $$$sumI[s[k]\oplus1] += 2^{k-1}$$$, every time $$$sumI[s[k]\oplus 1]$$$ is used to increase ans

As for the first case, we can calculate the value of $$$sumI[s[k]]$$$ at $$$j=k$$$ using the sum of $$$2^{i-1}$$$ for $$$i \lt k$$$ and $$$s[i]=s[k]\oplus1$$$. As for the second case, it's only slightly trickier, but along the same general idea. It can be calculated using the sum of $$$2^{n-j}$$$ for $$$j \gt k$$$ and $$$s[j]=s[k]\oplus 1$$$.

Fenwick (or segment) tree solves both cases, which are essentially dynamically calculating range sums on an array. Since for both cases we may consider when $$$s[k]=0$$$ or $$$s[k]=1$$$, a total of $$$4$$$ different fenwick trees will be needed. $$$(2^{i-1}$$$ when $$$s[i]=0, 0$$$ otherwise); ($$$2^{i-1}$$$ when $$$s[i]=1, 0$$$ otherwise); $$$(2^{n-j}$$$ when $$$s[j]=0, 0$$$ otherwise); $$$(2^{n-j}$$$ when $$$s[j]=1, 0$$$ otherwise)

The procedure is thus: before toggling a bit, subtract its contribution from ans. After toggling the bit, add its new contribution to ans. Also, update the $$$4$$$ fenwick trees accordingly. This correctly maintains ans in $$$O(log(n))$$$ per update.

So, the final complexity is $$$O(n+q*log(n))$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 2E5+16, MOD = 998244353;
ll pw2[MAXN];

struct SegTree {
    vll tree;
    ll n;

    SegTree (ll n): tree(2*n, 0), n(n) {}

    void update (ll id, ll val) {
        for (tree[id += n] = val; id > 1; id >>= 1)
            tree[id>>1] = (tree[id] + tree[id^1]) % MOD;
    }

    ll query (ll ql, ll qr) {
        ll ans = 0;
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) (ans += tree[ql++]) %= MOD;
            if (qr&1) (ans += tree[--qr]) %= MOD;
        }
        return ans;
    }
};

void tc () {
    string str;
    cin >> str;
    ll n = str.size();
    SegTree stFreq0(n), stFreq1(n), st0(n), st1(n);
    for (ll i = 0; i < n; i++) {
        (str[i] == '0' ? stFreq0 : stFreq1).update(i, pw2[n-1-i]);
        (str[i] == '0' ? st0 : st1).update(i, pw2[i]);
    }
    ll ans = pw2[n]-1;
    {ll acc0 = 0, acc1 = 0;
    for (ll i = 0; i < n; i++) {
        (ans += (str[i] == '0' ? acc1 : acc0)*pw2[n-1-i]) %= MOD;
        ((str[i] == '0' ? acc0 : acc1) += pw2[i]) %= MOD;
    }}
    ll Q;
    cin >> Q;
    while (Q--) {
        ll at;
        cin >> at;
        at--;
        (ans -= (str[at] == '0' ? st1 : st0).query(0, at-1)*pw2[n-1-at]) %= MOD;
        (ans -= (str[at] == '0' ? stFreq1 : stFreq0).query(at+1, n-1)*pw2[at]) %= MOD;
        (ans += MOD) %= MOD;
        (str[at] == '0' ? stFreq0 : stFreq1).update(at, 0);
        (str[at] == '0' ? st0 : st1).update(at, 0);
        str[at] = (str[at] == '0' ? '1' : '0');
        (str[at] == '0' ? stFreq0 : stFreq1).update(at, pw2[n-1-at]);
        (str[at] == '0' ? st0 : st1).update(at, pw2[at]);
        (ans += (str[at] == '0' ? st1 : st0).query(0, at-1)*pw2[n-1-at]) %= MOD;
        (ans += (str[at] == '0' ? stFreq1 : stFreq0).query(at+1, n-1)*pw2[at]) %= MOD;
        cout << ans << ' ';
    }
    cout << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    pw2[0] = 1;
    for (ll i = 1; i < MAXN; i++) pw2[i] = pw2[i-1]*2 % MOD;
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve