Notice that if we pair each odd-indexed element with an even-indexed element, it sums to $$$0$$$.

Therefore, our strategy is to pair the $$$2i$$$'th element with the $$$(2i+1)$$$th element until there are no more elements to pair. Note that if $$$n$$$ is odd, then there exists an unpaired odd element at the end. In this case, the answer will just be that ending element, which will be $$$x$$$. Otherwise, when $$$n$$$ is even, we paired every element perfectly and the sum will be $$$0$$$.

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

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int x, n;
        cin >> x >> n;
        if (n % 2 == 0)
            cout << 0;
        else
            cout << x;
        cout << endl;
    }
}

Since our path is continuous, whatever route we take will always pass through all vertical and horizontal lasers in the region from $$$(0,0)$$$ to $$$(x,y)$$$ since our movement is bounded inside the region. Therefore, the answer is simply $$$n + m$$$.

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

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, m, x, y, s = 0;
        cin >> n >> m >> x >> y;

        forn(i, n)
            cin >> s; 
        forn(i, m)
            cin >> s; 

        cout << n + m << endl;

    }
}

In this problem, we want to maximize the amount of points between consecutive requirements. We can ask ourselves the following questions:

What is the maximum number of points we can obtain between requirements $$$i$$$ and $$$i+1$$$? The answer is $$$a_{i+1} - a_i$$$, by running every minute. When can we run every minute? Only if $$$(a_{i+1} - a_i)$$$ and $$$|b_{i+1} - b_i|$$$ have the same parity.

What if they don't have the same parity? Well we can stay in place for one minute, then we can gain $$$a_{i+1} - a_i - 1$$$ points.

The start can be represented by a requirement where $$$a_0 = 0$$$ and $$$b_0 = 0$$$. Summing up the number of points between all consecutive requirements yields the answer. Remember to add $$$m - a_n$$$ to the answer, since we are running until the $$$m$$$'th minute.

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

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


int main(){
	int T;
	cin >> T;
	while(T--){
		int n, m, x , y;
		cin >> n >> m;
		int px = 0, py = 0;
		int points = 0;
		while(n--){
			cin >> x >> y;
			points += x - px;
			if(((x - px + 2) % 2) != ((y - py + 2) % 2))points--;
			px = x;
			py = y;
		}
		if(px != m){
			points += m - px;
		}
		cout << points << endl;
	}
}	 

Firstly, if there is no odd farm, then the answer is $$$0$$$ by default since we can never turn the lawnmower on.

Otherwise, let's first visit an odd farm to turn the lawnmower on. To maximize the number of grass, let's visit the odd farm with the maximum number of grass. Now that the lawnmower is on, we can visit any farm. Since the lawnmower can never turn off when we visit an even farm, let's take advantage of this and visit all the even farms.

Finally, we are forced to visit odd farms. Note that every other odd farm we visit will turn the lawnmower off. From this, we can see that it is optimal to visit the half of the odd farms with the largest amounts; we will visit them when the lawnmower is on.

Time complexity: $$$\mathcal{O}(n \log n)$$$ per test case. The $$$\log n$$$ complexity comes from sorting.

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    vector<int> p[2];
    for (int i : a) p[i%2].push_back(i);
    long long ans = 0;
    if (p[1].size()) ans += accumulate(p[0].begin(), p[0].end(), 0LL);
    sort(p[1].rbegin(), p[1].rend());
    int m = p[1].size();
    for (int i = 0; i < (m+1)/2; i++) ans += p[1][i];
    cout << ans << '\n';
}

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

First, let's highlight the important parts of the statement. In my opinion, the most important part is the actual condition for determining whether subarray $$$a[l, r]$$$ is awesome, That is: there is some way to place items outside the subarray such that all multisets contain must the exact same elements (ignoring ordering).

There can only be one way that all multisets can contain must the exact same elements. Let $$$\texttt{cnt}_i$$$ denote the number of times element $$$i$$$ occurs in $$$a$$$. Then all multisets must contain exactly $$$\frac{\texttt{cnt}_i}{k}$$$ copies of element $$$i$$$.

Now, let's find a closed form for how we determine $$$a[l, r]$$$ is awesome. Firstly, we can note that the ordering of elements in the subarray does not matter; only the counts matter. Therefore, let's denote $$$c_i$$$ as the number of elements with value $$$i$$$ in the subarray. The claim is that the subarray is awesome if and only if $$$c_i \leq \frac{\texttt{cnt}_i}{k}$$$ over all $$$i$$$. We can show this through some casework:

• If $$$c_i \leq \frac{\texttt{cnt}_i}{k}$$$, then we can place $$$\frac{\texttt{cnt}_i}{k} - c_i$$$ occurrences inside multiset $$$1$$$. We can place the other elements such that there are exactly $$$\frac{\texttt{cnt}_i}{k}$$$ occurrences in all other multisets as well.

• Otherwise, if $$$c_i \gt \frac{\texttt{cnt}_i}{k}$$$. We can never make the other multisets have $$$\frac{\texttt{cnt}_i}{k}$$$ occurrences because we don't have enough occurrences to do so.

Therefore, the problem simplifies to: Count the number of subarrays such that $$$c_i \leq \frac{\texttt{cnt}_i}{k}$$$ over all $$$i$$$. We can do so using two-pointers.

Say our left pointer $$$l$$$ is fixed. Until the inequality is satisfied, we will keep increasing the right pointer $$$r$$$. Then, we will add $$$r - l$$$ to the answer since all subarrays $$$a[l, l], a[l, l+1], \ldots, a[l, r - 1]$$$ are satisfied. Then, increment the left pointer by $$$1$$$ and repeat.

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

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), cnt(n + 1), ct(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    for (int i = 0; i <= n; i++) {
        if (cnt[i] % k) {
            return void(cout << 0 << endl);
        } else {
            cnt[i] /= k;
        }
    }
    int res = 0;
    for (int l = 0, r = 0; r >= l and r < n; r++) {
        ct[a[r]]++;
        while (ct[a[r]] > cnt[a[r]]) {
            ct[a[l]]--;
            l++;
        }
        res += (r - l + 1);
    }
    cout << res << endl;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    cin >> tc;
    while (tc--) solve();
}

Firstly, note the last row must have a length of $$$\texttt{max_k}$$$, the maximum $$$k$$$ among all arrays. Next, we can think about stacking as appending a suffix of the array on top to the array on the bottom. For example, if we stack an array $$$p$$$ of length $$$y$$$ on top of an array $$$q$$$ of length $$$x$$$ where $$$y \gt x$$$, then we append the suffix of $$$p$$$ that starts at index $$$x + 1$$$ to $$$q$$$ after gravity takes place.

Let $$$b_1, b_2, \ldots, b_i$$$ denote the lexicographically minimum possible bottom row if we have a prefix of length $$$i$$$ already fixed. From what array (out of the $$$n$$$ given arrays) should we append next to $$$b$$$?

The answer is: among all arrays with length greater than $$$i$$$, we want to append the array with the lexicographically minimum suffix starting at index $$$i+1$$$. We must append the entire suffix of that array to $$$b$$$.

We will repeat this process until $$$b$$$ has $$$\texttt{max_k}$$$ elements. Now, we just need to find the array to append at each step efficiently.

Approach 1: $$$\mathcal{O}(\sum k \log n)$$$

Iterate $$$i$$$, denoting the current length of prefix, backwards from $$$\texttt{max_k}$$$. We will keep track of the indices of all arrays that have length at least $$$i$$$. At each $$$i$$$, sort the array with the indices using a comparator with the following priority, from high to low:

• the element at index $$$i$$$.

• The "rank" of the suffix starting at index $$$i+1$$$ (i.e. its relative order in the previous sorting). If the rank doesn't exist (i.e. the array is exactly length $$$i$$$), then we can denote the rank as $$$-1$$$ as shorter arrays are more optimal when suffix are tied.

After the sorting, update the "rank" of each array with the current relative ordering. The first element in the sorted array will be the array you choose to append, if you ever end up with a fixed prefix of $$$i$$$ when you build $$$b$$$.

Now that we have the "next array to append" precalculated for every length, we build $$$b$$$ from left to right. Since we are sorting at most $$$\sum k$$$ elements and at most $$$n$$$ array indices can be tracked, the complexity is $$$\mathcal{O}(\sum k \log n)$$$

Approach 2: $$$\mathcal{O}(\sum k \sqrt{\sum k})$$$

Every time we want to append the suffix starting at index $$$i$$$ of some array, let's say array $$$c$$$, then $$$c$$$ must have at least $$$i$$$ elements. Additionally, the sum of lengths of all arrays (i.e. $$$\sum k$$$) is bounded by $$$2 \cdot 10^5$$$.

The essential observation is: There exist at most $$$\sqrt{\sum k}$$$ distinct values of $$$k$$$ among the $$$n$$$ arrays. This also means that we are appending a non-empty suffix of some array at most $$$\sqrt{\sum k}$$$ times.

You can think of this as: if we have multiple arrays with the same length, then we only care to append the lexicographically minimum out of those arrays. Besides the array we will append, we don't care about any other arrays with that length.

Now, at each iteration of $$$i$$$, it suffices to manually iterate through all the suffixes of all $$$n$$$ arrays with lengths at least $$$i+ 1$$$ to find the lexicographically minimum one. You are iterating through at most $$$\sum k$$$ elements per step, so the complexity is
$$$\mathcal{O}(\sum k \sqrt{\sum k})$$$.

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)
#define sz(x) (int)x.size()
template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
 
void solve() {
	int n; cin >> n;
	vector<vector<int>> g(n), relevant;
	int max_k = 0;
	FOR(i,0,n){
		int k; cin >> k;
		g[i].resize(k);
		ckmax(max_k, k);
		FOR(j,0,k){
			cin >> g[i][j];
			if(sz(relevant) == j) relevant.pb({});
			relevant[j].pb(i);
		}
	}
	vector<int> lex_min(max_k), rank(n, -1);
	ROF(i,max_k-1,0){
		vector<array<int, 3>> cur;
		trav(j, relevant[i]){
			cur.pb({g[j][i], rank[j], j});
		}
		sort(all(cur));
		lex_min[i] = cur[0][2];
		int rk = 0;
		trav(j, cur) rank[j[2]] = rk++;
	}
	vector<int> ans;
	while(sz(ans) < max_k){
		int tmp = sz(ans);
		auto& v = g[lex_min[tmp]];
		FOR(i,tmp,sz(v)) ans.pb(v[i]);
	}
	assert(sz(ans) == max_k);
	cout << ans << "\n";
}
 
signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}
 
/*   /\_/\
*   (= ._.)
*   / >  \>
*/

from collections import deque


def solve():
    n = int(input())
    a = [deque(list(map(int, input().split()))[1:]) for i in range(n)]
    a.sort(key=lambda x: -len(x))
    ans = []
    while a:
        cur = min(a)
        ans += cur
        while a and len(a[-1]) <= len(cur):
            a.pop()
        for i in range(len(a)):
            for j in range(len(cur)):
                a[i].popleft()
    print(*ans)


for _ in range(int(input())):
    solve()

Let's start by understanding how $$$f(a)$$$ works. The definition essentially asks for the largest index $$$k$$$ such that the $$$\gcd$$$ of the first $$$k$$$ elements is strictly greater than the $$$\gcd$$$ of the first $$$k+1$$$. In other words, we're looking for the last point at which the running gcd 'drops'.

A useful observation is that scaling the entire array (multiplying or dividing every element by the same integer) does not affect where this drop occurs; each $$$\gcd$$$ value is just scaled accordingly. This allows us to 'normalize' the problem: divide each $$$a_i$$$ by the $$$\gcd$$$ of the whole array. After this, the $$$\gcd$$$ of the full array becomes $$$1$$$, and the question reduces to:

What is the last index where the prefix GCD is still greater than $$$1$$$?

Now, note that $$$\gcd \gt 1$$$ for a prefix means there exists some integer $$$d \gt 1$$$ that divides every element in that prefix. So, the problem boils down to constructing the largest prefix that shares a common divisor greater than $$$1$$$.

To handle this, let’s think in terms of divisors. For each number $$$a_i$$$, compute all of its divisors. Maintain a frequency array $$$\text{div}$$$, where $$$\text{div}[d]$$$ stores how many elements seen so far are divisible by $$$d$$$. The maximum value of $$$\text{div}[d]$$$ tells us the largest prefix size where all elements share divisor $$$d$$$. That gives us $$$f(a)$$$.

Extending to Prefixes

The problem, however, doesn’t just ask for $$$f(a)$$$ of the entire array. We need $$$g(p)$$$ for every prefix $$$p = [a_1, a_2, \dots, a_i]$$$, considering all permutations. Fortunately, the divisor-counting approach extends naturally: as we iterate through the array from left to right, we update the divisor frequencies for each new element and recompute the maximum.

There is a subtle edge case here. Suppose the array is $$$[8,4,2,1]$$$ and we are at prefix $$$[8, 4, 2]$$$. All three numbers are divisible by 2, so $$$\max(\text{div}) = 3$$$. But the true answer is not 3, it’s 2, because the gcd only drops before the last element (the full prefix always ends with $$$\gcd = 1$$$ by normalization). To handle this, we should ignore the trivial case where every element of the prefix shares a divisor. In other words, the correct answer is

ensuring we don’t mistakenly include the full prefix.

Complexity

For each element, computing divisors takes $$$O(\sqrt{a_i})$$$. Updating frequencies and maintaining the maximum is $$$O(1)$$$ per divisor. Across all elements, the time complexity is:

where $$$A$$$ is the maximum element. This is efficient enough given the constraints.

For every prefix of length $$$i$$$ ($$$1 \leq i \leq n$$$), the most optimal reordering is to reorder all prefix elements such that the $$$k$$$ first elements of $$$a$$$ can all be divided by the same divisor while the $$$(k+1)$$$'th element can't. This ensures that $$$gcd(a_1,...,a_k) \gt gcd(a_1,...,a_{k+1})$$$ is always true.

Thus, we have reduced the problem to : Find a divisor that can divide the most elements for every prefix of length $$$i$$$. To solve this, we can simply precompute divisors of all numbers and increase their count by $$$1$$$ as we iterate through the array and take the maximum $$$count[x]$$$ as answer.

A special case where maximum $$$count[x] = i$$$ is invalid, as $$$gcd(a_1, ..., a_k) \gt gcd(a_1, ..., a_{k+1})$$$ is no longer true. We can save all such $$$x$$$ into an array and check for every $$$i$$$ if $$$count[x] \lt i$$$ is true with bruteforce, since the number of divisors for a number $$$x$$$ is roughly at most $$$\sqrt[3]{x}$$$.

The final complexity will be $$$O(N \log N + N \sqrt[3]{N})$$$.

#include<bits/stdc++.h>

#define pb push_back 
using namespace std;

const int mxN = 2e5 + 2;

vector<int> divs[mxN];

void pre(){
    for(int i = 2; i<mxN; i++){
        for(int j = i; j<mxN; j+=i)divs[j].pb(i);
    }
}

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1), cnt(n+1, 0), max_nums;
    vector<bool> vis(n+1, 0);
    for(int i = 1; i<=n; i++)cin>>a[i];

    int ans = 0;
    for(int i = 1; i<=n; i++){
        int x = a[i];
        vector<int> next;
        for(auto &num : divs[x]){
            cnt[num]++;
            if(cnt[num] != i)ans = max(ans, cnt[num]);
            else if(!vis[num]){
                next.pb(num);
                vis[num] = 1;
            }
        }

        for(auto &num : max_nums){
            if(cnt[num] != i){
                ans = max(ans, cnt[num]);
                vis[num] = 0;
            } else next.pb(num);
        }
        max_nums = next;
        cout<<ans<<" \n"[i == n];
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t = 1;
    cin>>t;
    pre();
    while(t--)solve();
    return 0;
}

Consider each distinct value separately. Say we are focused on $$$x$$$ and denote the indices where $$$x$$$ occurs in $$$a$$$ as $$$b_1, b_2, \ldots, b_k$$$. We want to count the number of subarrays that covers at least one element in $$$b$$$. Let's break $$$[1, n]$$$ into intervals separated by each $$$b_i$$$, so we have intervals $$$[1, b_1], [b_1 + 1, b_2], \ldots, [b_{k-1} + 1, b_k]$$$.

We can consider each interval independently. Suppose the left bound of our subarray lies in $$$[b_i + 1, b_{i+1}]$$$, then the right bound of our subarray must contain at least $$$b_{i+1}$$$, so it can lie anywhere in $$$[b_{i+1}, n]$$$. Therefore, we have $$$(b_{i+1} - b_i) \cdot (n - b_{i+1} + 1)$$$ choices of subarrays for this fixed interval.

We can iterate over all intervals and add the product — this is the contribution for this integer $$$x$$$. Additionally, these subarrays are clearly distinct because their left bound is restricted to different, disjoint intervals. To obtain the answer, We can iterate over all distinct $$$x$$$ and add up the contributions. This is equivalent to the original $$$d(a, b)$$$ function because each distinct $$$x$$$ contributes $$$1$$$ to this function.

https://cses.fi/paste/2d15c9c12179f830d3d8d7/ $$$\mathcal{O}(n)$$$

Let's solve an easier problem. Consider this: You are given an array of $$$n$$$ integers and an integer $$$k$$$. Count the number of ways to split the array into continuous segments of lengths at most $$$k$$$.

Let $$$dp[i]$$$ denote the number of ways to split the prefix of length $$$i$$$. Our transition is simply $$$dp[i] = \sum_{j=1}^{\min(i,k)} dp[i-j]$$$, since we are adding the number of ways over all lengths $$$j \in [1, k]$$$ that the previous segment could be. Our base case is $$$dp[0] = 1$$$.

Going back to the actual problem. The only difference is that our segments has to contain all distinct elements, and we need to know the maximum length that our current segment can be. We can initialize a variable $$$l$$$ that tracks the minimum left bound such that the segment $$$a_l, \ldots, a_i$$$ contains all distinct elements.

We can initialize a map $$$\texttt{lst}$$$ that tracks the last encounter of each integer. Our segment cannot contain two of any integer, so at each index $$$i$$$ we should set $$$l = \max(l, \texttt{lst}[a[i]] + 1)$$$. Now it's the same problem as our easy problem. Our transition is simply $$$dp[i] = \sum_{j=l}^{i-1} dp[j]$$$.

https://cses.fi/paste/66e4b8951387ad02d3d9b1/ $$$\mathcal{O}(n \log n)$$$. Note that $$$\mathcal{O}(n)$$$ is perfectly possible using prefix sums but I was lazy.

You should recursively build the permutation until you successfully make a permutation of length $$$n$$$. At each step, find the minimum number that satisfies the difference greater than one condition and add it to the permutation. It turns out the number of backtracking calls is not that many before you find a valid permutation.

https://cses.fi/paste/4044f0215e650326d4383f/ $$$\mathcal{O}(n \log n)$$$

In bubble sort, if a smaller element is to the right of a larger number, it is swapped. Then, the bubble sort moves past the larger number. You can see that in each iteration, the smaller number only gets moved one spot left towards its correct position in the sorted array. Also, note that bubble sort is stable — it guarantees not to change the relative order of elements that compare equal.

Let's denote array $$$b = \texttt{sorted}(a)$$$. We want to find the maximum difference between each $$$a_i$$$ and its corresponding position in $$$b$$$. Since bubble sort is stable, we also must match the same numbers to $$$b$$$ in the same relative position in $$$a$$$.

https://cses.fi/paste/df74b084e298a14cd3f447/ $$$\mathcal{O}(n \log n)$$$

Read the solution to the previous problem for the bubble sort observation.

For this problem, $$$a[i]=$$$ the smallest untaken (i.e. not taken by previous positions) number among $$$a_1, \ldots, a_{i+k}$$$. This is because we cannot swap any numbers after index $$$i+k$$$ with only $$$k$$$ rounds. Any untaken numbers to the left of $$$i$$$ will also bubble past $$$i$$$ as smaller numbers are swapped to the left of $$$i$$$.

https://cses.fi/paste/681585dabfba0bd2d3f3a7/ $$$\mathcal{O}(n \log n)$$$

Let's inspect the manhattan distance formula. For each free campsite $$$f$$$, we should find the maximum value of $$$|x_r - x_f| + |y_r - y_f|$$$. A very common technique to deal with absolute value signs break it up into cases. For example,

Since we have two absolute value signs, there are $$$4$$$ cases we need to consider. Specifically:

All four cases can be done with sweep line and a segment tree. Consider the first case. If we know $$$x_f + y_f$$$, then we want to query for the minimum value of $$$x_r + y_r$$$ such that $$$x_r \geq x_f \text{ and } y_r \geq y_f$$$. We can we sort all the points such the $$$x$$$ inequality holds and query in a way such that the $$$y$$$ inequality holds. A relevant usaco.guide module

https://cses.fi/paste/1ddc2ecc75f59ff5d45f32/ $$$\mathcal{O}((n+m) \log (n+m))$$$

Let's prime factorize $$$k$$$ into $$$p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_m^{e_m}$$$. Let's look at each prime $$$p_i$$$ separately. We can guarantee $$$lcm(a_i, a_{i+1}) = k$$$ if the maximum of adjacent powers of $$$p_i$$$ is equal to $$$e_i$$$. For a single prime $$$p_i$$$, we must count the number of arrays $$$b$$$ of length $$$n$$$ such that $$$0 \leq b_i \leq e_i$$$ and $$$\max(b_i, b_{i+1}) = e_i$$$. Let's try to do this with DP.

Let $$$dp[i][j]$$$ denote the number of ways to make an array of length $$$i$$$ with $$$j$$$ as a boolean denoting whether $$$b_i = e_i$$$. We have:

• $$$dp[i][0] = dp[i-1][1] \cdot e_i$$$. This is because $$$b_{i-1} = e_i$$$ must hold if $$$b_i \neq e_i$$$. Here $$$b_i$$$ can take any integer $$$\in [0, e_i-1]$$$.

• $$$dp[i][1] = dp[i-1][0] + dp[i-1][1]$$$. We know this $$$b_i = e_i$$$ so it is just the sum of all possible previous ways.

However, $$$k$$$ can be up to $$$10^9$$$ so this is just a standard case of matrix exponentiation. We must find a vector $$$M$$$ such that:

It should be simple to see that

So the answer is simply stored in the entries of

.

Multiplying the number of ways over all $$$p_i$$$ yields the answer.

https://cses.fi/paste/73e8bad653ea3c2ad40ddc/ $$$\mathcal{O}(\text{fast enough})$$$

The same problem actually appeared in codeforces: 895C - Square Subsets, but with vastly different constraints. However the solution is still highlighted by this comment.

Let $$$p_1, p_2, \ldots, p_k$$$ denote primes up to $$$5000$$$. It can be shown that $$$k \approx 670$$$. We can break down each number $$$a_i$$$ as a vector $$$v_i \in GF(2)^k$$$ such that $$$v_{i, j}$$$ denotes whether $$$v_i$$$ has an odd number of factors of $$$p_j$$$. We can see that a subset $$$S$$$ is the product of a perfect square if $$$\sum_{i \in S} v_i = 0$$$.

We can lay all $$$v_i$$$ as columns of a $$$k$$$ by $$$n$$$ matrix $$$M$$$ over $$$GF(2)$$$. Picking a subset corresponds to finding a vector $$$v \in {0,1}^n$$$ such that $$$Mv = 0$$$. This should remind you of the null space of $$$M$$$. Additionally, the nullity represents how many independent vectors there are in the null space, and we can choose any subset of them.

We can find the nullity of $$$M$$$ using the rank-nullity theorem. Let $$$r$$$ denote its rank, then we are looking for $$$n - r$$$. The answer is just $$$2^{n-r}$$$. We can find the rank of a matrix using Gaussian Elimination.

https://cses.fi/paste/c34e063a9ce96269d4328a/ $$$\mathcal{O}(nk^2)$$$

Consider the prefix sum array $$$p$$$. Each of the constraints $$$(l, r, s)$$$ represents $$$p_r - p_{l-1} = s$$$ or $$$p_r = p_{l-1} + s$$$.

Consider the graph with vertices from $$$0$$$ to $$$n$$$. We can add an edge from $$$(l-1) \rightarrow r$$$ with weight $$$s$$$ and an edge $$$r \rightarrow (l-1)$$$ with weight $$$-x$$$. We can start a DFS at any unvisited vertex and assign each element of $$$p$$$ with the sum of weights so far. If there is a conflict of assigned weights, then it is impossible.

We can extract the original array using $$$a_i = p_i - p_{i-1}$$$.

https://cses.fi/paste/7bcc5dba172caa2ad427fe/ $$$\mathcal{O}(n+m)$$$

Boring dijkstra.

https://cses.fi/paste/2ecb38a2d1c174c1d42893/ $$$\mathcal{O}(ab \log ab)$$$

We can notice that every operation preserves the total amount of water modulo $$$\gcd(a, b)$$$. Since both containers start with $$$0$$$ water, we can only have a total amount of water $$$t \equiv 0 \pmod{\gcd(a,b)}$$$ in any of the containers. Therefore, we just need to check $$$x \leq a$$$ and $$$x \equiv 0 \pmod{\gcd(a,b)}$$$.

https://cses.fi/paste/15e63aaa270cd243d428a7/ $$$\mathcal{O}(\text{skibidi})$$$

ABC 341G is an extremely similar problem. View the editorial for this for a much more detailed explanation.

We can think of each index $$$i$$$ as a point in the plane $$$(i, p[i])$$$ where $$$p$$$ is the prefix sum array. The problem becomes find the index $$$j$$$ that maximizes the slope from $$$pt_j$$$ to $$$pt_i$$$. Therefore, $$$pt_j$$$ should be the previous point on the upper convex hull.

https://cses.fi/paste/9e277db6d5eb2b2ed46c31/ $$$\mathcal{O}(\text{tralalero})$$$

Let's create an array $$$b$$$ where $$$b_i = x_i - a$$$. Now we know a subset $$$S$$$ has average $$$a$$$ if $$$\sum_{i \in S} b_i = 0$$$, Now we just need to use standard knapsack to find the number of subsets that sum up to $$$0$$$. Make sure to make the knapsack array at least length $$$2n500$$$ since $$$b$$$ can worst case have a sum of positive/negative $$$500n$$$,

https://cses.fi/paste/137f3e4836558116d42ad3/ $$$\mathcal{O}(n^3)$$$

Binary search for the average $$$x$$$. Then, find the maximum prefix of $$$a_i - x$$$ and $$$b_i - x$$$. If the sum of maximum prefixes across both arrays is at least $$$0$$$, then it is possible to choose an average at least $$$x$$$.

https://cses.fi/paste/e3956942d84fc717d42b04/ $$$\mathcal{O}(n \log A)$$$

Let's create an array $$$p_i$$$ where it stores the index of element $$$i$$$ in $$$a$$$. We can then replace the elements in $$$b$$$ with $$$p$$$ (i.e. set $$$b_i = p_{b_i}$$$). Now the problem turns into finding the longest increasing subsequence in $$$b$$$.

https://cses.fi/paste/b4931c61c6f863cdd42c80/ $$$\mathcal{O}(m \log n)$$$

We can notice that the possible values of $$$a_3$$$ ranges from $$$-99$$$ to $$$200$$$. Thus, we can iterate over all values of $$$a_3$$$ from $$$-99$$$ to $$$200$$$, and for each value, compute the Fibonacciness of the sequence. The maximal of all these values gives the solution to the problem.

Time Complexity : $$$O(3*a_{max})$$$

$$$a_3$$$ can be represented as either of the following:

$$$a_3 = a_1 + a_2$$$, or

$$$a_3 = a_4 - a_2$$$, or

$$$a_3 = a_5 - a_4$$$.

These are at most 3 possible values. Notice that any value of $$$a_3$$$ which increases the Fibonacciness must belong to one of the above values (Think why!). So, in order to increase the Fibonacciness of the sequence, we should choose the most frequent of the above values. Then, in the end, we can calculate the Fibonacciness of the sequence after choosing the best value for $$$a_3$$$.

Time Complexity : $$$O(1)$$$

#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 () {
    vll ve(4);
    for (ll &i : ve) cin >> i;
    set <ll> st;
    st.insert(ve[3]-ve[2]);
    st.insert(ve[2]-ve[1]);
    st.insert(ve[0]+ve[1]);
    cout << 4-st.size() << '\n';
}

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

• Heat
• Mid
• Horrendous
• Didn't Solve

Assume the cows are initially ordered correctly. A solution exists if the first cow can place $$$0$$$, the second cow can place $$$1$$$, and so on, continuing with the first cow placing $$$n$$$, the second cow placing $$$n+1$$$, and so forth. Observing the pattern, the first cow must be able to place $$${0, n, 2n, \dots}$$$, the second $$${1, n+1, 2n+1, \dots}$$$, and in general, the $$$i$$$-th cow (where $$$i \in [0, n-1]$$$) must be able to place $$${i, n+i, 2n+i, \dots}$$$.

For each cow, sorting their cards reveals whether they satisfy this condition: the difference between adjacent cards in the sorted sequence must be $$$n$$$. If any cow's cards do not meet this criterion, the solution does not exist, and we output $$$-1$$$.

If the cows are not ordered correctly, we need to rearrange them. To construct the solution, find the index of the cow holding card $$$i$$$ for each $$$i \in [0, n-1]$$$. Since the cards of each cow are sorted, denote $$$\texttt{min_card}$$$ as the smallest card a cow holds. Using an array $$$p$$$, iterate over each cow $$$c$$$ from $$$0$$$ to $$$n-1$$$ and set $$$p_\texttt{min_card} = c$$$. Finally, iterate $$$i$$$ from $$$0$$$ to $$$n-1$$$ and output $$$p_i$$$.

Time Complexity : $$$O(nmlog(m))$$$. Note that sorting is not necessary, and a solution with complexity up to $$$O((nm)^2)$$$ will still pass.

#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));
    vll p(n, -16);
    bool val = true;
    ll c = 0;
    for (vll &we : ve) {
        for (ll &i : we) cin >> i;
        ll minN = *min_element(we.begin(), we.end());
        if (minN < n) p[minN] = c++;
        val &= minN < n;
        sort(we.begin(), we.end());
        ll last = we[0]-n;
        for (ll i : we) {
            val &= last+n == i;
            last = i;
        }
    }
    if (!val) {
        cout << "-1\n";
        return;
    }
    for (ll i : p) cout << i+1 << ' ';
    cout << '\n';
}

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

• Heat
• Mid
• Horrendous
• Didn't Solve

Note that Bob has all the power in this game, because the order in which Alice picks numbers is irrelevant, since Bob can always pick the optimal number to give himself a point. Therefore, we can just ignore Alice and play the game from Bob's perspective.

From this point on, a "paired" number is any number $$$a$$$ on the blackboard such that there exists a $$$b$$$ on the blackboard such that $$$a+b=k$$$.

Bob's strategy is as follows:

• if Alice picks a paired number, Bob should pick the other number in the pair.

• if Alice picks an unpaired number, Bob can pick any other unpaired number, it doesn't matter which.

This always works because the number of "unpaired numbers" is always even, since $$$n$$$ is even and the number of "paired numbers" will always be even. Therefore, for every unpaired number Alice picks, Bob will always have an unpaired number to respond with.

Therefore, the final score is just the number of pairs in the input. To count them, use a map of counts $$$c$$$ such that $$$c_x$$$ is the number of occurrences of $$$x$$$ on the whiteboard. Then, for each number from $$$1$$$ to $$$\lfloor \frac{k}{2} \rfloor$$$, take the minimum of $$$c_x$$$ and $$$c_{k-x}$$$, and add that to the total. Remember the edge case where $$$k$$$ is even and $$$x = \frac{k}{2}$$$. The number of pairs here is just $$$\lfloor \frac{c_x}{2} \rfloor$$$.

#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, k;
    cin >> n >> k;
    vll ve(n);
    for (ll &i : ve) cin >> i;
    vll th(k+1, 0);
    for (ll i : ve) {
        if (i >= k) continue;
        th[i]++;
    }
    ll ans = 0;
    for (ll i = 1; i < k; i++) {
        if (i == k-i) {
            ans += th[i]/2;
            continue;
        }
        ll minN = min(th[i], th[k-i]);
        th[i] -= minN;
        th[k-i] -= minN;
        ans += minN;
    }
    cout << ans << '\n';
}

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

• Heat
• Mid
• Horrendous
• Didn't Solve

For clarity, let's denote $$$op_i$$$ as an operation performed on $$$a_i$$$ and $$$a_{i+1}$$$.

Claim: if it is possible, then the sequence of operations $$$op_1,op_2,\ldots,op_{n-1}$$$ will sort the array.

Proof: Let $$$b$$$ be any sequence of operations that will sort the array. Let's transform the sequence $$$b$$$ such that it becomes $$$[op_1,op_2,\ldots,op_{n-1}]$$$.

First, let's note that an $$$op_i$$$ does nothing if $$$a_i=0$$$ or $$$a_{i+1}=0$$$. Additionally, after $$$op_i$$$, at least one of $$${a_i,a_{i+1}}$$$ will become zero. Thus, we can remove all duplicates in $$$b$$$ without altering the result.

Now, let $$$x$$$ be the largest number such that $$$op_x$$$ is in $$$b$$$. Since at least one of $$$a_x,a_{x+1}$$$ will be zero, operations must be performed such that each of $$$a_1,a_2,\ldots,a_{x-1}$$$ are zero. Let $$$S$$$ be the set of indices with $$$i \lt x$$$ such that $$$op_i$$$ is not in $$$b$$$. Note that we can simply append each operation in $$$S$$$ at the end of $$$b$$$ without altering the result, since all elements before $$$a_x$$$ are already zero.

Our sequence of operations now contain a permutation of $$$op_1,op_2,\ldots,op_x$$$, and we have ensured that all of $$$a_1,a_2,\ldots,a_x=0$$$. Since the sequence is now sorted, we can in fact continue performing $$$op_{x+1},op_{x+2},\ldots,op_{n-1}$$$ in this order. Notice that this sequence of operations will keep our array sorted, as $$$op_y$$$ will make $$$a_y=0$$$ (since $$$a_y \lt a{y+1}$$$).

Let's show that we can rearrange our operations such that $$$1$$$ comes first. There are two cases: either $$$op_1$$$ comes before $$$op_2$$$, or $$$op_2$$$ comes before $$$op_1$$$. In the first case, notice that no operation done before $$$op_1$$$ will impact either the value of $$$a_1$$$ or $$$a_2$$$, so rearranging such that $$$op_1$$$ comes first does not impact the final results. In the second case, notice that after $$$op_2$$$ is done, we must have $$$a_1=a_2$$$, as otherwise $$$op_1$$$ will not simultaneously make $$$a_1=a_2=0$$$. This implies that right before $$$op_2$$$ is performed, we must have $$$a_1+a_3=a_2$$$. Then, rearranging the operations such that $$$op_1$$$ comes first will not impact the final result.

Using the same line of reasoning, we can make $$$op_2$$$ the second operation, then $$$op_3$$$, and so on. To solve the problem, we can simply simulate the operations in this order, and then check if the array is sorted at the end.

Time Complexity : $$$O(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>;

void tc () {
    ll n;
    cin >> n;
    vll ve(n);
    for (ll &i : ve) cin >> i;
    ll j = 0;
    for (ll i = 1; i < n; i++) {
        if (ve[i-1] > ve[i]) j = i;
    }
    if (j == 0) { // all done
        cout << "YES\n";
        return;
    }
    auto fop = [&](ll i) {
        ll minN = min(ve[i], ve[i+1]);
        ve[i] -= minN;
        ve[i+1] -= minN;
    };
    for (ll i = 0; i < j; i++) {
        fop(i);
    }
    cout << (is_sorted(ve.begin(), ve.end()) ? "YES" : "NO") << '\n';
}

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

• Heat
• Mid
• Horrendous
• Didn't Solve

Let's solve the problem for each operation.

First, consider the operation that removes an edge from $$$ F $$$. Divide $$$ G $$$ into its connected components and assign each vertex a component index. Then, for each edge in $$$ F $$$, if it connects vertices with different component indices, remove it and increment the operation count.

This guarantees no path between $$$ x $$$ and $$$ y $$$ in $$$ F $$$ if there is none in $$$ G $$$. Next, to ensure a path exists between $$$ x $$$ and $$$ y $$$ in $$$ F $$$ if there is one in $$$ G $$$, we divide $$$ F $$$ into connected components. After removing excess edges, each component of $$$ F $$$ only contains vertices of the same component index. The number of operations needed now is the difference between the number of connected components in $$$ F $$$ and $$$ G $$$.

All operations can be efficiently performed using DFS or DSU.

#include <bits/stdc++.h>

#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long double ld;
typedef long long ll;

using namespace std;

mt19937 rnd(time(nullptr));

const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;

void Gdfs(int v, vector<vector<int>> &sl, vector<int> &col, int c){
    col[v] = c;
    for(int u: sl[v]){
        if(col[u] == 0){
            Gdfs(u, sl, col, c);
        }
    }
}

int Fdfs(int v, vector<vector<int>> &sl, vector<int> &col, vector<int> &old_col, int c){
    col[v] = c;
    int res = 0;
    for(int u: sl[v]){
        if(col[u] == 0){
            if(old_col[u] != c) res++;
            else res += Fdfs(u, sl, col, old_col, c);
        }
    }
    return res;
}

void read_con_list(vector<vector<int>> &sl, int m){
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].emplace_back(--v);
        sl[v].emplace_back(u);
    }
}

void solve(int tc){
    int n, mf, mg;
    cin >> n >> mf >> mg;
    vector<vector<int>> fsl(n), gsl(n);
    read_con_list(fsl, mf);
    read_con_list(gsl, mg);

    vector<int> fcol(n), gcol(n);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(gcol[i] == 0){
            Gdfs(i, gsl, gcol, i + 1);
        }
        if(fcol[i] == 0){
            ans += Fdfs(i, fsl, fcol, gcol, gcol[i]);
            if(gcol[i] < i + 1) ans++;
        }
    }
    cout << ans;
}

bool multi = true;

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

    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

When $$$n$$$ is large, many of the array's elements will be $$$1$$$.

The number of non-$$$1$$$ elements can't be so large.

Try to precompute all arrays without $$$1$$$ and then use combinatorics.

The naive solution is to define $$$f_k(n)$$$ as the number of arrays containing $$$n$$$ elements with a product of $$$k$$$. We could then try to compute this by considering the last element of the array among the divisors of $$$k$$$, giving us:

with $$$f_k(1)=1$$$.

The answers would then be $$$\sum_{i=1}^{n}f_1(i),\sum_{i=1}^{n}f_2(i),\dots,\sum_{i=1}^{n}f_k(i)$$$. However, this leads to an $$$O(nk\log k)$$$ solution, which exceeds our time constraints. We need to optimize this approach.

We can prove that there are at most $$$16$$$ non-$$$1$$$ elements in our arrays. This is because:

• The prime factorization of $$$k=p_1p_2\cdots p_t$$$ divides $$$k$$$ into the most non-$$$1$$$ elements.
• With $$$17$$$ non-$$$1$$$ elements, the smallest possible value would be $$$k=2^{17}=131072 \gt 10^5$$$.

Based on this observation, we can define our dynamic programming state as:

• Let $$$dp[i][j]$$$ represent the number of arrays with product $$$i$$$ containing only $$$j$$$ non-$$$1$$$ elements.
• The recurrence relation becomes: $$$dp[i][j]=\sum_{p|i,p \gt 1}dp[\frac{i}{p}][j-1]$$$.
• Base case: $$$dp[i][1]=1$$$ for $$$i \gt 1$$$.

This computation has a time complexity of $$$O(k\log^2k)$$$, as we perform $$$\sum_{j=1}^{k}d(j)=O(k\log{k})$$$ additions for each $$$i$$$.

To calculate $$$f_k(n)$$$, we:

1. Enumerate the number of non-$$$1$$$ elements from $$$1$$$ to $$$16$$$.
2. For $$$j$$$ non-$$$1$$$ elements in the array:

• We have $$$n-j$$$ elements that are $$$1$$$.
• We need to choose $$$j$$$ positions for non-$$$1$$$ elements.
• Fill these positions with $$$dp[k][j]$$$ possible sequences.

This gives us:

Therefore:

Note that $$$\sum_{i=1}^{n}\binom{i}{j} = \binom{n+1}{j+1}$$$ is given by the Hockey Stick Identity.

Each answer can be calculated in $$$O(\log^2k)$$$ time, giving an overall time complexity of $$$O(k\log^2k)$$$.

Let's revisit the naive approach and define $$$S_k(n)=\sum_{i=1}^{n}f_{k}(n)$$$ as our answers. We can observe:

Accumulating Formula $$$(1)$$$ yields:

By induction, we can prove that both $$$f_{k}(n)$$$ and $$$S_k(n)$$$ are polynomials. Let's denote:

• Degree of $$$f_k(n)$$$ as $$$p(k)$$$.
• Degree of $$$S_k(n)$$$ as $$$q(k)$$$.

From the definition of $$$S_k(n)$$$, we have $$$q(k)=p(k)+1$$$. Formula $$$(2)$$$ gives us:

with $$$p(1)=0$$$. By induction, we can show that $$$p(k)$$$ equals the number of primes in $$$k$$$'s prime factorization. Therefore, $$$p(k)\le16$$$ and $$$q(k)\le17$$$.

Since $$$q(k)$$$ doesn't exceed $$$17$$$, we can:

1. Precompute $$$S_k(1),S_k(2),S_k(3),\dots,S_k(18)$$$.
2. Use Lagrange Interpolation to compute any $$$S_k(n)$$$.

This also yields an $$$O(k\log^2k)$$$ time complexity.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Runtime.Serialization.Json;
using System.Text;
using System.Threading.Tasks;
using TemplateF;

#if !PROBLEM
SolutionF a = new();
a.Solve();
#endif

namespace TemplateF
{
    internal class SolutionF
    {
        private readonly StreamReader sr = new(Console.OpenStandardInput());
        private T Read<T>()
            where T : struct, IConvertible
        {
            char c;
            dynamic res = default(T);
            dynamic sign = 1;
            while (!sr.EndOfStream && char.IsWhiteSpace((char)sr.Peek())) sr.Read();
            if (!sr.EndOfStream && (char)sr.Peek() == '-')
            {
                sr.Read();
                sign = -1;
            }
            while (!sr.EndOfStream && char.IsDigit((char)sr.Peek()))
            {
                c = (char)sr.Read();
                res = res * 10 + c - '0';
            }
            return res * sign;
        }

        private T[] ReadArray<T>(int n)
            where T : struct, IConvertible
        {
            T[] arr = new T[n];
            for (int i = 0; i < n; ++i) arr[i] = Read<T>();
            return arr;
        }

        public void Solve()
        {
            StringBuilder output = new();
            const int maxk = 100000, mod = 998244353, bw = 20;
            List<int>[] d = new List<int>[maxk + 1];
            for (int i = 1; i <= maxk; ++i) d[i] = new() { 1 };
            for (int i = 2; i <= maxk; ++i) {
                for (int j = i; j <= maxk; j += i) d[j].Add(i);
            }
            int[,] dp = new int[bw + 1, maxk + 1], S = new int[bw + 1, maxk + 1];
            for (int k = 1; k <= maxk; ++k) dp[1, k] = S[1, k] = 1;
            for (int i = 2; i <= bw; ++i) {
                for (int j = 1; j <= maxk; ++j) {
                    foreach (var k in d[j]) {
                        dp[i, j] += dp[i - 1, k];
                        dp[i, j] %= mod;
                    }
                    S[i, j] = (S[i - 1, j] + dp[i, j]) % mod;
                }
            }
            int T = Read<int>();
            while (T-- > 0)
            {
                int k = Read<int>(), n = Read<int>();
                if (n <= bw) {
                    for (int j = 1; j <= k; ++j) output.Append(S[n, j]).Append(' ');
                } else {
                    int _k = k;
                    for (k = 1; k <= _k; ++k)  {
                        long ans = 0;
                        for (int i = 1; i <= bw; ++i) {
                            long t = S[i, k];
                            for (int j = 1; j <= bw; ++j) {
                                if (j == i) continue;
                                t *= n - j;
                                t %= mod;
                                t *= Inv((mod + i - j) % mod, mod);
                                t %= mod;
                            }
                            ans = (ans + t) % mod;
                        }
                        output.Append(ans).Append(' ');
                    }
                }
                output.AppendLine();
            }
            Console.Write(output.ToString());
        }
        public static long Inv(long a, long Mod) {
            long u = 0, v = 1, m = Mod;
            while (a > 0) {
                long t = m / a;
                m -= t * a; (a, m) = (m, a);
                u -= t * v; (u, v) = (v, u);
            }
            return (u % Mod + Mod) % Mod;
        }
    }
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Consider $$$(a_i, b_i)$$$ as the $$$i$$$-th pair. Can two elements ever become unpaired?

The operations allow us to swap two pairs, but it also results in both of them getting flipped. Is there any way to swap two pairs without flipping anything?

Can you flip two pairs without swapping them?

Can you flip one pair on its own?

Read the hints first.

Key observation:

In the final solution, the pairs must be sorted in increasing order of $$$\min(a_i, b_i)$$$. We prove this by contradiction. Suppose there exists a pair $$$(a_i, b_i)$$$, where $$$a_i \lt b_i$$$ and $$$a_i$$$ is smaller than the minimum element in the previous pair. In this case, it becomes impossible to place this pair after the previous one, as $$$a_i$$$ would always be smaller than the preceding element, regardless of orientation.

Since all $$$a_i$$$ and $$$b_i$$$ are distinct, there is exactly one valid final ordering of the pairs. Moreover, this ordering is always reachable because we previously proved that any two pairs can be swapped without flipping their elements. Since swapping any two items in an array an arbitrary number of times allows for sorting by definition, we can sort the pairs in this order. Thus, the solution is to initially sort the pairs based on $$$\min(a_i, b_i)$$$.

Solution:

The problem simplifies to determining whether flipping pairs allows sorting. We can solve this using dynamic programming (DP), defined as follows:

$$$dp[1][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an even number of flips, where pair $$$i$$$ is not flipped.
$$$dp[2][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an even number of flips, where pair $$$i$$$ is flipped.
$$$dp[3][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an odd number of flips, where pair $$$i$$$ is not flipped.
$$$dp[4][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an odd number of flips, where pair $$$i$$$ is flipped.

The base cases are as follows:

$$$dp[1][1] = 1$$$, because this represents the state where the first pair is not flipped, resulting in zero flips (which is even)
$$$dp[4][1] = 1$$$, because this represents the state where the first pair is flipped, resulting in one flip (which is odd).

There are eight possible transitions, as you can reach each of the four states from two previous states: you either choose to flip the current element or you don't.

The final answer is $$$dp[1][n]$$$ $$$\texttt{OR}$$$ $$$dp[2][n]$$$, because by Hints 3 and 4, we can only reach states where an even number of pairs are flipped from the starting position.

#include <bits/stdc++.h>
using namespace std;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define print pair<int, int>
#define vp vector<print>
#define ALL(x) (x).begin(), (x).end()

void solve()
{
    int n;
    cin >> n;
    vp pairs(n);
    F0R(i, n)
    {
        cin >> pairs[i].first;
    }
    F0R(i, n)
    {
        cin >> pairs[i].second;
    }

    sort(ALL(pairs), [](print a, print b)
         { return min(a.first, a.second) < min(b.first, b.second); });

    vector<vector<int>> dp(4, vector<int>(n, 0));
    dp[0][0] = 1;
    dp[3][0] = 1;
    FOR(i, 1, n)
    {
        if (pairs[i - 1].first < pairs[i].first and pairs[i - 1].second < pairs[i].second)
        {
            dp[0][i] |= dp[0][i - 1];
            dp[1][i] |= dp[1][i - 1];
            dp[2][i] |= dp[3][i - 1];
            dp[3][i] |= dp[2][i - 1];
        }
        if (pairs[i - 1].first < pairs[i].second and pairs[i - 1].second < pairs[i].first)
        {
            dp[0][i] |= dp[2][i - 1];
            dp[1][i] |= dp[3][i - 1];
            dp[2][i] |= dp[1][i - 1];
            dp[3][i] |= dp[0][i - 1];
        }
    }
    cout << ((dp[0][n - 1] | dp[2][n - 1]) ? "YES" : "NO") << endl;
}

signed main()
{
    int tests;
    cin >> tests;
    F0R(test, tests)
    {
        solve();
    }

    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

For any $$$n$$$, Cube can set $$$a$$$ = any integer between $$$1$$$ and $$$n-1$$$ inclusive, and set $$$b = n - a$$$. $$$a$$$ cannot be less than $$$1$$$, because then it would be non-positive, and $$$a$$$ cannot be greater than $$$n-1$$$, because then $$$b$$$ would be less than $$$1$$$, which would make it non-positive. Therefore the answer is just $$$n-1$$$ for all $$$n$$$.

input = sys.stdin.readline
for _ in range(int(input())):
    print(int(input())-1)

The letters she reads that comprise string $$$b$$$ are just the letters that comprise string $$$a$$$, flipped left-to-right. This means that 'p' becomes 'q', 'q' becomes 'p', and 'w' stays 'w', since it is vertically symmetrical. The order in which the letters are read is also reversed, because what used to be the left side of string $$$a$$$ gets flipped over to the right side of string $$$b$$$, and vice versa.

We now have an algorithm for constructing string $$$b$$$, which is to iterate from right-to-left on string $$$a$$$, outputting 'p' when there is a 'q', 'q' when there is a 'p', and 'w' when there is a 'w'.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>

int t;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());
		for (char &c : s) if (c == 'q') c = 'p'; else if (c == 'p') c = 'q';
		cout << s << '\n';
	}
}

Let $$$A$$$, $$$B$$$, $$$C$$$ be three sets of monkeys, such that monkeys in $$$A$$$ can only sit in row $$$1$$$, $$$B$$$ in row $$$2$$$, and $$$C$$$ can sit anywhere. It is clear that if there is free space in row $$$1$$$, and there are monkeys left in set $$$A$$$, it is optimal to seat a monkey from set $$$A$$$ onto row $$$1$$$. This is because a monkey from set $$$C$$$ can be seated on either row, and there might be space left on the other row for that same monkey in set $$$C$$$ after you've already seated the monkey from set $$$A$$$. However, this is not the case if you start by seating the monkeys in set $$$C$$$ in the front row, since you might now leave empty seats at the back, but then have monkeys from set $$$A$$$ still left unseated.

Therefore, the strategy is as follows: seat as many monkeys from set $$$A$$$ as you can in the front row, then seat as many monkeys from set $$$B$$$ as you can in the back row, then seat as many monkeys from set $$$C$$$ as you can, and that yields the answer.

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--)
    {
        int m,a,b,c;
        cin>>m>>a>>b>>c;
        int ans=0,rem=0;
        ans+=min(m,a);rem+=m-min(m,a);
        ans+=min(m,b);rem+=m-min(m,b);
        ans+=min(rem,c);
        cout<<ans<<'\n';
    }
    return 0;
}

Observe that if you have an array where all elements are unique, they will all have frequency $$$1$$$, therefore they can all be classified as the mode. Therefore, it follows that the strategy for the construction is to just construct an array where for each prefix, the last element of this prefix appears in the array at least once. An easy way of doing is this is such:

For each element $$$a_i$$$, if this value has appeared previously in the array (you can use a set to check this), set $$$b_i$$$ equal to some random integer that isn't used elsewhere in the list $$$a$$$, and keep going. Otherwise, set $$$b_i = a_i$$$.

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        vector<int> a(n+1),b(n);
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            if(!a[x])
            {
                b[i]=x;
                a[x]=1;
            }
        }
        queue<int> q;
        for(int i=1;i<=n;i++)
            if(!a[i])
                q.push(i);
        for(int i=0;i<n;i++)
        {
            if(!b[i])
            {
                b[i]=q.front();
                q.pop();
            }
        }
        for(int i=0;i<n;i++)
            cout<<b[i]<<" \n"[i==n-1];
    }
    return 0;
}

Clearly, trying to bruteforce over all possible values of $$$x$$$ or $$$y$$$ is too slow, because the bounds are $$$1 \leq l_1 \leq r_1 \leq 10^9$$$. However, there is another variable that you can actually bruteforce over — and that is $$$n$$$. This is because exponentiation famously makes numbers very big very quickly — and if we set $$$k$$$ as small as possible (i.e. $$$2$$$), we only need to check $$$1 \leq n \leq 32$$$. This is because $$$2^{32} \gt 10^9$$$, so there cannot possibly be any solutions for $$$n \gt 32$$$ for any $$$k$$$.

Now, let's rephrase the problem. We need to find pairs $$$(x, y)$$$ such that $$$x \cdot k^n = y$$$. Now, we can check every value of $$$n$$$ from $$$1$$$ to $$$32$$$, and for each, binary search to find the smallest $$$x$$$ such that $$$y$$$ fits the conditions, and the largest $$$x$$$. Now, we can subtract these two values and add this to the answer.

Note that we do not need to care about more than $$$32$$$ different values of $$$k^n$$$, because obviously $$$k^{32} \ge 2^{32} \gt 10^9$$$. From here and on, we focus on solving for only one value of $$$k^n$$$.

When $$$k^n$$$ is fixed and you are given $$$\frac{y}{x}=k^n$$$, notice $$$y$$$ is fixed as $$$x k^n$$$. Therefore, if we count the values $$$x$$$ such that $$$y$$$ is in the given interval as well, we will be properly counting the ordered pairs.

Formally, this condition can be cleared out as:

• $$$l_2 \le x k^n \le r_2$$$
• $$$\frac{l_2}{k^n} \le x \le \frac{r_2}{k^n}$$$
• Because $$$x$$$ is an integer, $$$\left \lceil {\frac{l_2}{k^n}} \right \rceil \le x \le \left \lfloor {\frac{r_2}{k^n}} \right \rfloor$$$

Thus, when we intersect the two intervals, we get the following interval at last.

Compute the size of this interval for all $$$k^n$$$ (at most $$$32$$$ values) and the answer can be found.

Do note the following details while implementing:

• When $$$r \lt l$$$, the size of the interval is $$$0$$$, not negative.
• Beware of overflows. Dealing with big integers can be helpful in avoiding this, but it may make your solution slow.
• Do not round up a fraction using the ceil function; This has been a recurring issue in almost every Div.4!

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--)
    {
        ll k,l1,r1,l2,r2;
        cin>>k>>l1>>r1>>l2>>r2;
        ll kn=1,ans=0;
        for(int n=0;r2/kn>=l1;n++)
        {
            ans+=max(0ll,min(r2/kn,r1)-max((l2-1)/kn+1,l1)+1ll);
            kn*=k;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

This is an anti-hash test for python sets and dictionaries. Before you call us evil, we saved you from getting hacked in open hack phase. Beware!

Let's denote the beauty of the matrix as $$$B$$$, and denote $$$\text{SumA}$$$ as the sum of all the elements in the array $$$a$$$, and $$$\text{SumB}$$$ as the sum of all the elements in the array $$$b$$$.

Before applying an operation, the beauty of the matrix can be expressed as:

$$$B = b_1 \cdot a_1 + b_1 \cdot a_2 + b_1 \cdot a_3 + b_2 \cdot a_1 + b_2 \cdot a_2 + \ldots$$$

After factoring, this simplifies to:

$$$ B = b_1 \cdot (a_1 + a_2 + a_3 + \ldots) + b_2 \cdot (a_1 + a_2 + a_3 + \ldots) + \ldots $$$

Further factoring gives:

$$$ B = (a_1 + a_2 + a_3 + a_4 + \ldots) \cdot (b_1 + b_2 + b_3 + \ldots) $$$

This can be written as:

$$$ B = \text{SumA} \cdot \text{SumB}$$$

Now, consider the effect of an operation on a column $$$C$$$. The beauty decreases by $$$A_c \cdot \text{SumB}$$$. Similarly, when an operation is done on a row $$$R$$$, the beauty decreases by $$$B_r \cdot \text{SumA}$$$.

An important observation is that the element at position $$$(r, c)$$$ is counted twice, so we must account for this in the formula.

After considering this, let the beauty after the operations be denoted as $$$X$$$. Using the observations above:

$$$X = B - (b_i \cdot \text{SumA} + a_j \cdot \text{SumB} - a_j \cdot b_i)$$$

Simplifying further:

$$$X = \text{SumA} \cdot \text{SumB} - b_i \cdot \text{SumA} - a_j \cdot \text{SumB} + a_j \cdot b_i$$$

Factoring terms, we obtain:

$$$X = \text{SumA} \cdot (\text{SumB} - b_i) - a_j \cdot (\text{SumB} - b_i)$$$

Finally:

$$$X = (\text{SumB} - b_i) \cdot (\text{SumA} - a_j)$$$

At this stage, it is sufficient to iterate over the divisors of $$$X$$$. For each ordered pair of divisors whose product is $$$X$$$, we check whether the required values of $$$\text{SumB} - b_i$$$ and $$$\text{SumA} - a_j$$$ can be achieved.

This can be implemented using a simple map or boolean vector for faster computation, although such optimization is not required for this problem.

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define int long long
#define vt vector
#define endl "\n"

const int N = 4e5 + 5;
bool apos[N], aneg[N], bpos[N], bneg[N], posspos[N], possneg[N];

signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int> a(n), b(m);
    int asum = 0, bsum = 0;
    F0R(i, n) {
        cin >> a[i];
        asum += a[i];
    }
    F0R(i, m) {
        cin >> b[i];
        bsum += b[i];
    }
    F0R(i, n) {
        if(abs(asum-a[i]) < N) {
            if(asum-a[i]<0) aneg[a[i]-asum]=true;   
            else apos[asum-a[i]]=true;
        } 
    }
    F0R(i, m) {
        if(abs(bsum-b[i]) < N) {
            if(bsum-b[i]<0) bneg[b[i]-bsum]=true;   
            else bpos[bsum-b[i]]=true;
        } 
    }
    FOR(i, 1, N) {
        FOR(j, 1, N) {
            if(i * j > N) break;
            if(apos[i]&&bpos[j]) posspos[i*j]=true;
            if(apos[i]&&bneg[j]) possneg[i*j]=true;
            if(aneg[i]&&bpos[j]) possneg[i*j]=true;
            if(aneg[i]&&bneg[j]) posspos[i*j]=true;
        }
    }
    while(q--) {
        int x;
        cin >> x;
        if(x>0) {
            if(posspos[x]) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        } else {
            if(possneg[-x]) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

This problem deals with a specific subclass of graphs called "functional graphs", also known as "successor graphs". The key feature that they have is that each node only has one successor. Therefore, the graph in the problem will necessarily be split into $$$k \geq 1$$$ components, where each component necessarily contains one cycle, and each node will either be in the cycle, or it will be on a path leading towards the cycle.

Observe that if a node that is not on a cycle currently has a plushie, this plushie will cause the arrangement to be unstable until the plushie reaches the cycle. Proof: suppose node $$$u$$$ has the plushie on day $$$i$$$. On the next day, $$$u$$$ will no longer have this plushie, because they will have passed it down to $$$r_u$$$, therefore, the arrangement has changed. This continues inductively until the plushie reaches the cycle of its component.

From this, we know that the answer is at least the distance of any node to the cycle. Now, since every node in the cycle already has a plushie, we know that these plushies just get passed round and round, so actually, nodes within the cycle cannot change the answer. Therefore, we've already found the final answer.

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        vector<int> r(n+1),d(n+1);
        for(int i=1;i<=n;i++)
        {
            cin>>r[i];
            d[r[i]]++;
        }
        set<pair<int,int> > s;
        for(int i=1;i<=n;i++)
            s.insert({d[i],i});
        int ans=2;
        queue<int> q;
        while(!s.empty()&&(*s.begin()).first==0)
        {
            while(!s.empty()&&(*s.begin()).first==0)
            {
                int k=(*s.begin()).second;
                auto it=s.find({d[r[k]],r[k]});
                d[r[k]]--;
                if(it!=s.end())
                {
                    s.erase(it);
                    q.push(r[k]);
                }
                s.erase(s.begin());
            }
            while(!q.empty())
                s.insert({d[q.front()],q.front()}),q.pop();
            ans++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Note that similarly to G1, once all plushies end up in the hands of spiders who are in a loop, the process becomes stable.

Let's model the input as a collection of rooted forests. For each spider $$$i$$$, if $$$i$$$ is part of a loop, then let's compress the loop into a single node and use that as the root of a tree. Otherwise, if spider $$$i$$$ gives a present to spider $$$r_i$$$, then let's draw an edge from $$$i$$$ to $$$r_i$$$. Now, let $$$i$$$ be any node that is not part of a loop. How long will it take until spider $$$i$$$ runs out of presents? We can see that it is the subtree size of $$$i$$$, as one present leaves the subtree each year.

Thus, our challenge now is to process the nodes in an efficient order such that we can find the subtree size of all nodes. This can be done with topological sorting, which gives us an order that processes all nodes starting from the leaf upwards. After the topological sort, we may do dynamic programming to find subtree sizes of all nodes. Let $$$dp[i]$$$ be the number of days until spider $$$i$$$ runs out of presents. Let's suppose that we already calculated $$$dp[i]$$$ (we initialize it to be $$$1$$$ for all nodes since each spider starts with a present). Then, we should add $$$dp[i]$$$ to $$$dp[r_i]$$$. Doing this and adding up all $$$dp$$$ values of nodes directly before a cycle will yield the answer.

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        vector<int> r(n+1),d(n+1),v(n+1,1);
        for(int i=1;i<=n;i++)
        {
            cin>>r[i];
            d[r[i]]++;
        }
        set<pair<int,int> > s;
        for(int i=1;i<=n;i++)
        {
            s.insert({d[i],i});
        }
        int ans=2;
        queue<int> q;
        while(!s.empty()&&(*s.begin()).first==0)
        {
            while(!s.empty()&&(*s.begin()).first==0)
            {
                int k=(*s.begin()).second;
                ans=max(ans,v[k]+2);v[r[k]]+=v[k];
                auto it=s.find({d[r[k]],r[k]});
                d[r[k]]--;
                if(it!=s.end())
                {
                    s.erase(it);
                    q.push(r[k]);
                }
                s.erase(s.begin());
            }
            while(!q.empty())
                s.insert({d[q.front()],q.front()}),q.pop();
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Consider translating the sum back onto the matrix. For simplicity we discuss about querying the whole matrix.

The sum we would like to find is $$$\sum_i i\cdot A_i$$$. Here, $$$A_i$$$ corresponds to $$$M_{(x,y)}$$$, so we will translate this to $$$\sum_{x,y} i\cdot M_{(x,y)}$$$. The issue left is on the $$$i$$$ multiplied to it.

Remember that we index the entries in increasing order of $$$y$$$, and then increasing order of $$$x$$$. Assuming $$$y$$$ and $$$x$$$ were $$$0$$$-indexed, this will mean entry $$$(x,y)$$$ corresponds to $$$x\cdot n + y$$$ (also $$$0$$$-indexed). You can notice that this naturally corresponds to the order we had defined as well.

Then, what we want to find is $$$\sum_{x,y} (x \cdot n + y + 1)\cdot M_{(x,y)}$$$. Notice $$$x \cdot n$$$, $$$y$$$, $$$1$$$ are independent, and we can split them into sums $$$\sum_x x \cdot n \cdot M_{(x,y)}$$$, $$$\sum_y y \cdot M_{(x,y)}$$$, $$$\sum M_{(x,y)}$$$. Each of these three sums can be precomputed entry by entry, and a 2D prefix sum can solve the answer for the entire matrix.

The query for a submatrix is very similar. Formally, you have to care about:

• That we have $$$y_2-y_1+1$$$ columns instead of $$$n$$$ now;
• That the precomputed values might not start from $$$0$$$ on the first row/column of the query.

Still, these two issues can be fixed using the three sums we have precomputed. The time complexity becomes $$$\mathcal{O}(n^2+q)$$$.

#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, Q;
    cin >> n >> Q;
    vector <vll> mat(n, vll(n));
    for (vll &ve : mat) {
        for (ll &i : ve) cin >> i;
    }
    vector <vll> psR(n, vll(n+1)), psRr(n, vll(n+1)), psRc(n+1, vll(n+1)), ps(n+1, vll(n+1)), psRrc(n+1, vll(n+1));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            psR[i][j+1] = psR[i][j] + mat[i][j];
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            psRr[i][j+1] = psRr[i][j] + mat[i][j]*(j+1);
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j <= n; j++) {
            psRc[i+1][j] = psRc[i][j] + psR[i][j]*(i+1);
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j <= n; j++) {
            psRrc[i+1][j] = psRrc[i][j] + psRr[i][j];
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j <= n; j++) {
            ps[i+1][j] = ps[i][j] + psR[i][j];
        }
    }
    while (Q--) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;
        ll ans = 0;
        ans += -(ps[x2+1][y2+1]-ps[x2+1][y1]-ps[x1][y2+1]+ps[x1][y1])*x1*(y2-y1+1);
        ans += (psRc[x2+1][y2+1] - psRc[x1][y2+1] - (ps[x2+1][y2+1]-ps[x1][y2+1]))*(y2-y1+1);

        ans += (psRc[x2+1][y1] - psRc[x1][y1] - (ps[x2+1][y1]-ps[x1][y1]))*-(y2-y1+1);
        ans += (ps[x2+1][y2+1]-ps[x1][y2+1])*-y1;
        ans += (ps[x2+1][y1]-ps[x1][y1])*y1;

        ans += psRrc[x2+1][y2+1] - psRrc[x1][y2+1];
        ans +=-(psRrc[x2+1][y1] - psRrc[x1][y1]);
        cout << ans << ' ';
    }
    cout << '\n';
}

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

We want to count how many times we can choose $$$i$$$ and $$$j$$$ such that $$$a_i = a_j$$$. Suppose $$$f_x$$$ stores the frequency of $$$x$$$ in $$$a$$$. Once we choose $$$a_i = a_j = x$$$, $$$f_x$$$ is subtracted by $$$2$$$. Thus, the answer is the sum of $$$\lfloor \frac{f_x}{2} \rfloor$$$ over all $$$x$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    print(sum([a.count(x) // 2 for x in range(n + 1)]))

It is worth noting that test $$$4$$$ is especially made to blow up python dictionaries, sets, and Collections.counter. If you are time limit exceeding, consider using a frequency array of length $$$n$$$.

You must check if you can find two integers $$$n$$$ and $$$m$$$, such that $$$n \cdot m+2=k$$$. You can either use a counter, or use two pointers. Do note that $$$n^2+2=k$$$ is an edge case that must be separated if you use a counter to implement it. This edge case does not appear in the two pointers approach. Time complexity is $$$O(n \log n)$$$ (assuming you are wise enough to not use a hash table).

testcases = int(input())
for _ in range(testcases):
    k = int(input())
    list = input().split()
    freq = []
    for i in range(k+1):
        freq.append(0)
    for x in list:
        freq[int(x)] = freq[int(x)]+1
    solution = (-1,-1)
    for i in range(1,k+1):
        if i*i==k-2:
            if freq[i]>1:
                solution = (i,i)
        elif (k-2)%i==0:
            if freq[i]>0 and freq[(k-2)//i]>0:
                solution = (i, (k-2)//i)
    print(solution[0], solution[1])

Remember that all even numbers greater than $$$2$$$ are composite. As $$$1+3 \gt 2$$$, any two numbers with same parity sum up to a composite number. Now you only have to find one odd number and one even number that sum up to a composite number. One can manually verify that there is no such pair in $$$n \leq 4$$$, but in $$$n=5$$$ there exists $$$(4,5)$$$ which sums up to $$$9$$$, a composite number.

for _ in range(int(input())):
    n = int(input())
    if n < 5:
        print(-1)
        continue
    for i in range(2,n+1,2):
        if i != 4:
            print(i,end=" ")
    print("4 5",end=" ")
    for i in range(1,n+1,2):
        if i != 5:
            print(i, end = " ")
    print()

Process from earliest to latest. Maintain a priority queue of power-ups left so far. If Mualani meets a power-up, add it to the priority queue. Otherwise (Mualani meets a hurdle), take power-ups in the priority queue from strongest to weakest until you can jump over the hurdle. This guarantees that each time Mualani jumps over a hurdle, she takes the minimum number of power-ups necessary. Time complexity is $$$O((n+m)\log m)$$$, where $$$O(\log m)$$$ is from the priority queue.

Note that the hurdle intervals are inclusive. If there is a hurdle at $$$[l, r]$$$, she must jump from position $$$l-1$$$ to $$$r+1$$$.

import sys
import heapq
input = sys.stdin.readline
for _ in range(int(input())):
    n,m,L = map(int,input().split())
    EV = []
    for _ in range(n):
        EV.append((*list(map(int,input().split())),1))
    for _ in range(m):
        EV.append((*list(map(int,input().split())),0))
    EV.sort()
    k = 1
    pwr = []
    for a,b,t in EV:
        if t == 0:
            heapq.heappush(pwr,-b)
        else:
            while pwr and k < b-a + 2:
                k -= heapq.heappop(pwr)
            if k < b-a + 2:
                print(-1)
                break
    else:
        print(m-len(pwr))

Notice that for if for some $$$r$$$ we have $$$f(1, r) \lt f(1, r + 1)$$$ then we can conclude that $$$s_{r + 1} = 1$$$ (if it is $$$0$$$ then $$$f(1, r) = f(1, r + 1)$$$ will be true) and if $$$f(1, r)$$$ is non-zero and $$$f(1, r) = f(1, r + 1)$$$ then $$$s_{r + 1}$$$ is $$$0$$$.

Unfortunately this is only useful if there is a $$$0$$$ in $$$s_1,s_2,...,s_r$$$, so the next thing can try is to find is the value of the longest prefix such that $$$f(1, r)$$$ is $$$0$$$ (after this point there will be a zero in all prefixes).

See that if $$$f(1, r) = 0$$$ and $$$f(1, r + 1) = k$$$ then $$$s_{r + 1} = 1$$$, the last $$$k$$$ characters of $$$s_1,s_2,...,s_r$$$ must be $$$0$$$ and the first $$$r - k$$$ characters must be $$$1$$$. To prove this we can argue by contradiction, suppose it is not true and then it will become apparent that some shorter prefix will be non-zero when we query it.

The one case that this does not cover is when all prefixes are zero, from similar contradiction argument as above we can see that the string must look like $$$111...1100....000$$$ in this case, in this case it is not hard to see that all queries will give a value of zero, and thus we can report that it is impossible.

So we should query all prefixes, the first one which is non-zero (if this does not exist we can report impossible) we can deduce its value as discussed above, then there will be a $$$0$$$ in the prefix so we can deduce all subsequent characters as discussed at the start.

def qu(a,b):
    if (a,b) not in d:
        print("?", a+1,b+1)
        d[(a,b)] = int(input())
    return d[(a,b)]
for _ in range(int(input())):
    d = dict()
    n = int(input())
    SOL = ["0"] * n
    last = qu(0,n-1)
    if last:
        z = 1
        for i in range(n-2,0,-1):
            nw= qu(0,i)
            if nw != last:
                SOL[i+1] = "1"
            last = nw
            if last == 0:
                z = i+1;break
        if last:
            SOL[1] = "1"
            SOL[0] = "0"
        else:
            last = 1
            for j in range(z-2,-1,-1):
                nw = qu(j,z)
                if nw == last:
                    SOL[j] = "1"
                last = nw
        print("!","".join(SOL))
    else:
        print("! IMPOSSIBLE")

Let's perform binary search on the minimum number of hits to kill at least $$$k$$$ enemies. How do we check if a specific answer is possible?

Let's consider a single enemy for now. If its health is $$$h_i$$$ and we need to kill it in at most $$$q$$$ attacks, then we need to be doing at least $$$\lceil\frac{h_i}{q}\rceil$$$ damage per attack to this enemy. If this number is greater than $$$m$$$, then obviously we cannot kill this enemy in at most $$$q$$$ attacks as the maximum damage Xilonen can do is $$$m$$$ damage per hit. Otherwise, we can model the enemy as a valid interval where we can place Xilonen. Specifically, the inequality $$$m-|p-x|\geq\lceil\frac{h_i}{q}\rceil$$$ must be satisfied.

Now that we have modeled each enemy as an interval, the problem is reduced to finding whether or not there exists a point on at least $$$k$$$ intervals. This is a classic problem that can be approached by a sweep-line algorithm, sorting the events of intervals starting and ending by time and adding $$$1$$$ to your counter when an interval starts and subtracting $$$1$$$ to your counter when an interval ends.

Note that the maximum possible answer to any setup with a solution is $$$\max( h_i)=10^9$$$, so if we cannot kill at least $$$k$$$ enemies in $$$10^9$$$ attacks then we can just output $$$-1$$$ as our answer.

The total time complexity is $$$O(n\log({n})\log({\max(h_i)})$$$.

import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(1):
    n,m,k = map(int,input().split())
    h = list(map(int,input().split()))
    x = list(map(int,input().split()))
    lo = 0
    hi = int(1e10)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        ev = defaultdict(int)
        for i in range(n):
            ma = (h[i] + mid - 1) // mid
            if ma > m: continue
            ev[x[i]-m+ma] += 1
            ev[x[i]+m-ma+1] -= 1
        sc = 0
        for y in sorted(ev.keys()):
            sc += ev[y]
            if sc >= k:
                hi = mid
                break
        else:
            lo = mid
    if hi == int(1e10):
        print(-1)
    else:
        print(hi)

Denote $$$dp[i]=$$$ the number of ways to get to city $$$i$$$. Brute-forcing all possible previous cities is out of the question, as this solution will take $$$O(n^2\cdot\log({\max{a_i}}))$$$ time complexity. What else can we do?

Instead, consider caseworking on what the greatest common factor can be. Let's keep track of an array $$$count$$$ which for index $$$i$$$ keeps track of the sum of $$$dp$$$ values of all previous cities who has a factor of $$$i$$$. Say the current city has attractiveness $$$a_i$$$. We can almost recover $$$dp[i]$$$ by adding up the $$$count$$$ values of all factors of $$$a_i$$$. Unfortunately, this fails as it overcounts many instances. For example, if $$$\gcd(a_i, a_j)=12$$$ the $$$dp$$$ state from $$$i$$$ will be counted five times: $$$2, 3, 4, 6, 12$$$.

Note that we don't actually care what the greatest common factor is, since the only requirement is that the greatest common factor is not $$$1$$$. This also means that repeat appearances of the same prime number in the factorization of $$$a_i$$$ doesn't matter at all — we can assume each prime factor occurs exactly once. Now, if $$$\gcd(a_i, a_j)=12$$$, it is only counted three times: $$$2,3,6$$$. Now, instead of blindly adding the $$$count$$$ values from all previous states, let's instead apply the Principle of Inclusion-Exclusion on the prime factors. Let's first add the $$$count$$$ values from all prime factors, then subtract the $$$count$$$ values from all factors with two prime factors, then add the $$$count$$$ values from all factors with three prime factors, and so on. It can be seen that actually, the value is only counted one time now.

So what's the time complexity of this solution? Precomputing the set of all prime number takes $$$O(\max(a_i)\log(\max(a_i)))$$$ time (by the harmonic series $$$\frac{n}{1}+\frac{n}{2}+\ldots+\frac{n}{n}\approx n\log(n)$$$). For each number $$$a_i$$$, we have to consider all $$$2^{f(a_i)}$$$ subsets of prime factors, where $$$f(a_i)$$$ is the number of prime factors of $$$a_i$$$. The number with the most distinct prime factors is $$$510510=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17$$$, so worst case $$$2^7=128$$$ operations are needed per number. This goes to a total operation count of approximately $$$128\cdot n$$$ which will pass in the time limit.

Note that we may also use the Mobius function to compute the answer. The Mobius function's properties makes it utilize the Principle of Inclusion-Exclusion efficiently. The time complexity of this solution is $$$O(\max(a_i)\log(\max(a_i))+n\max(d(a_i)))$$$ where $$$d(a_i)$$$ is the maximum number of factors of $$$a_i$$$. This time complexity can be shown to be the same as the above time complexity.

import sys

def input():
    return sys.stdin.buffer.readline().strip()

MOD = 998244353
ma = int(1e6 + 5)
P = [1] * ma
D = [[] for _ in range(ma)]
for i in range(2, ma):
    if P[i] == 1:
        for j in range(i, ma, i):
            P[j] = i
F = [0] * ma
LU = [0] * ma
BMS = [[] for _ in range(ma)]
RES = []
from itertools import combinations
def getBMS(x):
    if not BMS[x]:
        y = help(x)
        for i in range(len(y)):
            p = combinations(y, i + 1)
            for a in p:
                xx = 1
                for j in a:
                    xx *= j
                BMS[x].append((xx,i))
    return BMS[x]
def helps(x):
    y = x
    while x != 1:
        s = P[x]
        D[y].append(s)
        while x % s == 0:
            x //= s


def help(x):
    if not D[x]: helps(x)
    return D[x]




for yy in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    for xx,i in getBMS(A[0]):
        F[xx] = 1
        LU[xx] = yy
    for i in range(1, n - 1):
        tot = 0
        for xx, j in getBMS(A[i]):
            if LU[xx] != - 1 and LU[xx] != yy:
                F[xx] = 0
            LU[xx] = yy
            if F[xx]:
                if j % 2:
                    tot -= F[xx]
                    tot %= MOD
                else:
                    tot += F[xx]
                    tot %= MOD
        for xx, j in getBMS(A[i]):
            F[xx] += tot
            F[xx] %= MOD
    S = 0
    for xx,i in getBMS(A[-1]):
        if LU[xx] != - 1 and LU[xx] != yy:
            LU[xx] = yy
            F[xx] = 0
        if F[xx]:
            if i % 2:
                S -= F[xx]
                S %= MOD
            else:
                S += F[xx]
                S %= MOD

    RES.append(str(S))
print("\n".join(RES))

To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be bolded. For dates, I will use the american standard notation (mm/dd).

Also, I will not go in detail about why problems were rejected/unused because they might appear in the future.

8/11: Codeforces Round 965 (Div. 2) has just concluded and sum has shipped himself off to college and won't have time due to attending frat parties his studies. I invite Proof_by_QED to problemset with me. We decide to get cooking straight away.

8/12: Proof_by_QED proposes D'. Gets accepted.

8/13: Proof_by_QED proposes E'. Problem accepted for backup.

8/14: Proof_by_QED proposes D''. Problem accepted for backup.

8/19: Proof_by_QED proposes E'', F' and G'. Both gets accepted for main set at the time. Seriously, bro just became the new BledDest.

8/21: We got bored and decided to focus on Codeforces Round 971 (Div. 4). Due to difficulty issues, we transfered problem E from that contest to problem B1 and B2 for this contest. B2 ultimately became D :)

8/22: Proof_by_QED proposes B', but satyam343 buffs it into F instead. Somewhere along the lines I also came up with A' and B'', both getting initially accepted.

8/23: Round gets put up for testing with 7 problems.

8/25: I came up with an idea for D'''. Also, Proof_by_QED proposes C, but initially gets ignored lmao.

8/26: satyam343 modifies B'' into D''''. Later, I also propose E''''.

8/28: satyam343 tries to modifies B'' again into C''. sum wakes up from his slumber and proposes F''.

8/29: I propose A''.

8/31: Proof_by_QED proposes D''''' and gets accepted.

9/2: satyam343 buffs D''' and it became NOTEQUALTREE.

9/6: Proof_by_QED and satyam343 modifies D' and it becomes G (G1). Later, A_G solved it in subquadratic, and it became G2.

9/9: I modify B'' into D''''''.

9/11: satyam343 modifies B'' into D'''''''. We hold a poll in our testing server to choose the victor among D'''''' and D'''''''.

9/12: I invent and propose C''', but wasn't accepted. satyam343 modifies B'' into D'''''''', but unused due to difficulty issues.

9/14: I invent and propose D''''''''', which was unused due to difficulty issues. Later that night, the aforementioned poll concludes, crowning D'''''' with 7 votes to 2. However, both candidates had difficulty issues so we still decided against using any of them (essentially we polled for nothing).

9/15: Proof_by_QED proposes B'''' and gets initially accepted, however, was later rejected.

9/17: I propose A''' but it wasn't great.

9/20: Proof_by_QED brings C up again and it gets prepared.

9/23: satyam343 modifies B'' into D'''''''''', but as the original author of B'', I didn't like it.

9/24: satyam343 modifies D''''''''' into D''''''''''', and it gets prepared.

9/28: Proof_by_QED modifies a unused problem I proposed for Codeforces Round 965 (Div. 2) into A'''', but unused due to difficulty issues.

9/30: Proof_by_QED proposes and prepares B. Later that night, satyam343 has conflicting thoughts whether to replace D''''''''''' yet again, but I held him at gunpoint to accept the problem spent 30 minutes convincing him that it is a good problem. This problem became E. For those of you who enjoyed the problem, you're welcome lmao.

10/02 — 10/17: Final testing and preparation.

10/13: Proof_by_QED proposes current A.

First, what is the maximum possible value of $$$c_i-b_j$$$ for any $$$i,j$$$? Since $$$c_i$$$ is the maximum element of some subset of $$$a$$$ and $$$b_i$$$ is the minimum element of some subset of $$$a$$$, the maximum possible value of $$$c_i-b_j$$$ is $$$max(a)-min(a)$$$.

Also note that $$$c_1=b_1$$$ for any reordering of $$$a$$$. By reordering such that the largest element of $$$a$$$ appears first and the smallest element of $$$a$$$ appears second, the maximum possible value of the score is achieved. This results in a score of $$$(max(a)-min(a))\cdot(n-1)$$$.

for i in range(int(input())):
    n = int(input())
    mx = 0
    mn= 1000000
    lst = input().split()
    for j in range(n):
        x = int(lst[j])
        mx = max(mx, x)
        mn = min(mn, x)
    print((mx-mn)*(n-1))

Observation: $$$f(t)-g(t)$$$ is odd.

Proof: $$$f(t)+g(t)$$$ is the set of all non-empty subsets of $$$t$$$, which is $$$2^{|t|}-1$$$, which is odd. The sum and difference of two integers has the same parity, so $$$f(t)-g(t)$$$ is always odd.

By including exactly one $$$1$$$ in the string $$$s$$$, we can make $$$f(s)=2^{n-1}-1$$$ and $$$g(s)=2^{n-1}$$$, or $$$f(s)-g(s)=1$$$ by the multiplication principle. Clearly, this is the best we can do. So, we print out any string with exactly one $$$1$$$.

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

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        cout << '1';
        for(int i = 1; i < n; i++) cout << '0';
        cout << endl;
    }
}

Let's understand what Alice wants to do. She wants to separate a statement that evaluates to true between two or's. This guarantees her victory since or is evaluated after all and's.

First, if the first or last boolean is true, then Alice instantly wins by placing or between the first and second, or second to last and last booleans.

Otherwise, if there are two true's consecutively, Alice can also win. Alice may place or before the first of the two on her first move. If Bob does not put his operator between the two true's, then Alice will put an or between the two true's on her next move and win. Otherwise, Bob does place his operator between the two true's. However, no matter what Bob placed, the two true's will always evaluate to true, so on her second move Alice can just place an or on the other side of the two true's to win.

We claim these are the only two cases where Alice wins. This is because otherwise, there does not contain two true's consecutively. Now, whenever Alice places an or adjacent to a true, Bob will respond by placing and after the true, which will invalidate this clause to be false.

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

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> v(n);
        for(int i = 0; i < n; i++) {
            if(s[i]=='1') v[i]=1;
        }
        bool win = false;
        if(v[0]||v[n-1]) win=true;
        for(int i = 1; i < n; i++) {
            if(v[i]&&v[i-1]) win=true;
        }
        if(win) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Observation: Through a series of swaps, we can swap an element from position $$$i$$$ to position $$$j$$$ (WLOG, assume $$$i \lt j$$$) if there is no such $$$k$$$ such that $$$i \leq k \lt j$$$ such that $$$s_k = \texttt{L}$$$ and $$$s_{k+1} = \texttt{R}$$$.

Let's mark all indices $$$i$$$ such that $$$s_i = \texttt{L}$$$ and $$$s_{i+1} = \texttt{R}$$$ as bad. If $$$pos_i$$$ represents the position of $$$i$$$ in $$$p$$$, then we must make sure it is possible to swap from $$$\min(i, pos_i)$$$ to $$$\max(i, pos_i)$$$. As you can see, we can model these conditions as intervals. We must make sure there are no bad indices included in any intervals.

We need to gather indices $$$i$$$ such that $$$i$$$ is included in at least one interval. This can be done with difference array. Let $$$d_i$$$ denote the number of intervals that include $$$i$$$. If $$$d_i \gt 0$$$, then we need to make sure $$$i$$$ is not a bad index.

We can keep all bad indices in a set. Notice that when we update $$$i$$$, we can only potentially toggle indices $$$i$$$ and $$$i-1$$$ from good to bad (or vice versa). For example, if $$$s_i = \texttt{L}$$$, $$$s_i = \texttt{R}$$$, $$$d_i \gt 0$$$ and index $$$i$$$ is not in the bad set, then we will insert it. After each query, if the bad set is empty, then the answer is "YES".

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n,q;
        cin >> n >> q;
        vector<int> perm(n);
        for(int i = 0; i < n; i++) cin >> perm[i];
        for(int i = 0; i < n; i++) perm[i]--;
        vector<int> invperm(n);
        for(int i = 0; i < n; i++) invperm[perm[i]]=i;
        vector<int> diffArr(n);
        for(int i = 0; i < n; i++) {
            diffArr[min(i, invperm[i])]++;
            diffArr[max(i, invperm[i])]--;
        }
        for(int i = 1; i < n; i++) diffArr[i]+=diffArr[i-1];
        string s;
        cin >> s;
        set<int> problems;
        for(int i = 0; i < n-1; i++) {
            if(s[i]=='L'&&s[i+1]=='R'&&diffArr[i]!=0) {
                problems.insert(i);
            } 
        }
        while(q--) {
            int x;
            cin >> x;
            x--;
            if(s[x]=='L') {
                s[x]='R';
            } else {
                s[x]='L';
            }
            if(s[x-1]=='L'&&s[x]=='R'&&diffArr[x-1]!=0) {
                problems.insert(x-1);
            } else {
                problems.erase(x-1);
            }
            if(s[x]=='L'&&s[x+1]=='R'&&diffArr[x]!=0) {
                problems.insert(x);
            } else {
                problems.erase(x);
            }
            if(problems.size()) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        }
    }
}

Observation: The score of $$$b$$$ is equivalent to $$$f_0$$$ + $$$\min(f_0, f_1)$$$ + $$$\ldots$$$ + $$$\min(f_0, \ldots, f_{n-1})$$$ where $$$f_i$$$ stores the frequency of integer $$$i$$$ in $$$b$$$.

Intuition: We can greedily construct the $$$k$$$ arrays by repeating this step: Select the minimum $$$j$$$ such that $$$f_j = 0$$$ and $$$\min(f_0, \ldots f_{j-1}) \gt 0$$$, and construct the array $$$[0, 1, \ldots, j-1]$$$. This is optimal because every element we add will increase the MEX by $$$1$$$, which will increase the score by $$$1$$$. If we add $$$j$$$, the MEX will not increase. Also, when we add an element, we cannot increase the score by more than $$$1$$$. Adding less than $$$j$$$ elements cannot increase MEX for future arrays.

From this observation, we can see that only the frequency array of $$$a$$$ matters. From now on, let's denote the frequency of $$$i$$$ in $$$a$$$ as $$$f_i$$$. We can find the sum over all subsequences using dynamic programming.

Let's denote $$$dp[i][j]$$$ as the number of subsequences containing only the first $$$i$$$ integers and $$$min(f_0, \ldots, f_i) = j$$$. Initially, $$$dp[0][i] = \binom{f_0}{i}$$$. To transition, we need to consider two cases:

In the first case, let's assume $$$j \lt \min(f_0, \ldots, f_{i-1})$$$. The number of subsequences that can be created is $$$(\sum_{k=j+1}^n dp[i-1][k]) \cdot \binom{f_i}{j}$$$. That is, all the subsequences from previous length such that it is possible for $$$j$$$ to be the new minimum, multiplied by the number of subsequences where $$$f_i = j$$$.

In the second case, let's assume $$$j \geq \min(f_0, \ldots, f_{i-1})$$$. The number of subsequences that can be created is $$$(\sum_{k=j}^{f_i} \binom{f_i}{k}) \cdot dp[i-1][j]$$$. That is, all subsequences containing at least $$$j$$$ elements of $$$i$$$, multiplied by all previous subsequences with minimum already equal to $$$j$$$.

The total score is $$$dp[i][j] \cdot j \cdot 2^{f_{i+1} + \dots + f_{n-1}}$$$ over the length of the prefix $$$i$$$ and prefix minimum $$$j$$$.

We can speed up the calculations for both cases using suffix sums, however, this still yields an $$$O(n^2)$$$ algorithm. However, $$$j$$$ is bounded to the interval $$$[1, f_i]$$$ for each $$$i$$$. Since the sum of $$$f_i$$$ is $$$n$$$, the total number of secondary states is $$$n$$$. This becomes just a constant factor, so the total complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define pii pair<int,int> 
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

const int MX = 2e5;
ll fact[MX+1];
ll ifact[MX+1];
ll MOD=998244353;
 
ll binPow(ll base, ll exp) {
    ll ans = 1;
    while(exp) {
        if(exp%2) {
            ans = (ans*base)%MOD;
        }
        base = (base*base)%MOD;
        exp /= 2;
    }
    return ans;
}
 
int nCk(int N, int K) {
    if(K>N||K<0) {
        return 0;
    }
    return (fact[N]*((ifact[K]*ifact[N-K])%MOD))%MOD;
}
 
void ICombo() {
	fact[0] = 1;
    for(int i=1;i<=MX;i++) {
        fact[i] = (fact[i-1]*i)%MOD;
    }    
    ifact[MX] = binPow(fact[MX],MOD-2);
    for(int i=MX-1;i>=0;i--) {
        ifact[i] = (ifact[i+1]*(i+1))%MOD;
    }
}

void solve() {
    int n, ans=0; cin >> n;
    vector<int> c(n);
    for (int r:c) {
        cin >> r; c[r]++; 
    }
    vector<vector<int>> dp(n,vector<int>(1));
    vector<int> ps, co; 
    for (int i = 1; i <= c[0]; i++) dp[0].push_back(nCk(c[0],i));
    for (int i = 1; i < n; i++) {
        ps.resize(1); co=ps; 
        for (int r:dp[i-1]) ps.push_back((ps.back()+r)%MOD); 
        int m=ps.size()-1;
        dp[i].resize(min(m,c[i]+1));
        for (int j = 0; j <= c[i]; j++) co.push_back((co.back()+nCk(c[i],j))%MOD);
        for (int j = 1; j < dp[i].size(); j++) dp[i][j]=nCk(c[i],j)*(ps[m]-ps[j]+MOD)%MOD+(co.back()-co[j+1]+MOD)*dp[i-1][j]%MOD; 
    }
    int j=0;
    for (auto r:dp) {
        n-=c[j++];
        for (int i = 1; i < r.size(); i++) (ans+=i*r[i]%MOD*binPow(2,n))%=MOD;
    }
    cout << ans << "\n"; 
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
        ICombo();
	int t = 1; cin >> t;
	while (t--) solve();
}

First, let's try to find whether a single array is orangutan-approved or not.

Claim: The array $$$b$$$ of size $$$n$$$ is not orangutan-approved if and only if there exists indices $$$1\leq w \lt x \lt y \lt z \leq n$$$ such that $$$b_w=b_y$$$, $$$b_x=b_z$$$, and $$$b_w\neq b_x$$$.

Proof: Let's prove this with strong induction. For $$$n=0$$$, the claim is true because the empty array is orangutan-approved. Now, let's suppose that the claim is true for all $$$m \lt n$$$.

Now, let $$$s$$$ be a sorted sequence such that $$$x$$$ is in $$$s$$$ if and only if $$$b_x=b_1$$$. Suppose $$$s$$$ is length $$$k$$$. We can split the array $$$b$$$ into disjoint subarrays $$$c_1, c_2, \ldots, c_k$$$ such that $$$c_i$$$ is the subarray $$$b[s_i+1\ldots s_{i+1}-1]$$$ for all $$$1 \leq i \lt k$$$ and $$$c_k=b[s_k+1\ldots n]$$$ That is, $$$c_i$$$ is the subarray that lies between each occurrence of $$$b_1$$$ in the array $$$b$$$.

First, we note that the set of unique elements of $$$c_i$$$ and $$$c_j$$$ cannot contain any elements in common for all $$$i\neq j$$$. This is because suppose that there exists $$$i$$$ and $$$j$$$ such that $$$i \lt j$$$ and the set of unique values in $$$c_i$$$ and $$$c_j$$$ both contain $$$y$$$. Then, in the original array $$$b$$$, there must exist a subsequence $$$b_1, y, b_1, y$$$. This makes our premise false.

By our inductive claim, each of the arrays $$$c_1, c_2, \ldots, c_k$$$ must be orangutan-approved. Since there are no overlapping elements, we may delete each of the arrays $$$c_1, c_2, \ldots, c_k$$$ separately. Finally, the array $$$b$$$ is left with $$$k$$$ copies of $$$b_1$$$, and we can use one operation to delete all remaining elements in the array $$$b$$$.

Now, how do we solve for all queries? First, precompute the array $$$last$$$, which is the array containing for each $$$i$$$ the largest index $$$j \lt i$$$ such that $$$a[j]=a[i]$$$. Let's then use two pointers to compute the last element $$$j \lt i$$$ such that $$$a[j\ldots i]$$$ is orangutan-approved but $$$a[j-1\ldots i]$$$ is not, and store this in an array called $$$left$$$. Let's also keep a maximum segment tree $$$next$$$ such that $$$next[i]$$$ is the first element $$$j \gt i$$$ such that $$$a_j=a_i$$$. As we sweep from $$$i-1$$$ to $$$i$$$, we do the following:

1. Set $$$L=left[i-1]$$$

2. Otherwise, while $$$\max(next[L...last[i]-1] \gt last[i]$$$ and $$$last[i]\neq-1$$$), increment $$$L$$$ by $$$1$$$.

3. Set $$$left[i]=L$$$

When the $$$left$$$ array is fully calculated, we can solve each query in $$$O(1)$$$.

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define nline "\n"
#define f first
#define s second
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF_ADD=1e18;
const ll MOD=1e9+7;
const ll MAX=1048579;
class ST {
public:
    vector<ll> segs;
    ll size = 0;
    ll ID = 0;
 
    ST(ll sz) {
        segs.assign(2 * sz, ID);
        size = sz;  
    }   
   
    ll comb(ll a, ll b) {
        return max(a, b);  
    }
 
    void upd(ll idx, ll val) {
        segs[idx += size] = val;
        for(idx /= 2; idx; idx /= 2) segs[idx] = comb(segs[2 * idx], segs[2 * idx + 1]);
    }
 
    ll query(ll l, ll r) {
        ll lans = ID, rans = ID;
        for(l += size, r += size + 1; l < r; l /= 2, r /= 2) {
            if(l & 1) lans = comb(lans, segs[l++]);
            if(r & 1) rans = comb(segs[--r], rans);
        }
        return comb(lans, rans);
    }
}; 
void solve(){
  ll n,q,l=1; cin>>n>>q;
  ST track(n+5);
  vector<ll> a(n+5),last(n+5,0),lft(n+5);
  for(ll i=1;i<=n;i++){
    cin>>a[i];
    ll till=last[a[i]];
    while(track.query(l,till)>=till+1){
      l++;
    }
    if(till){
      track.upd(till,i);
    }
    lft[i]=l;
    last[a[i]]=i;
  }
  while(q--) {
    ll l,r; cin>>l>>r;
    if(lft[r]<=l){
      cout<<"YES\n";
    } 
    else{
      cout<<"NO\n";
    }
  }
}
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                                  
  ll test_cases=1;                 
  cin>>test_cases;
  while(test_cases--){
    solve();
  }
} 

To find the score of a set of intervals $$$([l_1, r_1], [l_2, r_2], \ldots, [l_v, r_v])$$$, we follow these steps:

Initially, the score is set to $$$0$$$.

We perform the following process repeatedly:

• Let $$$x$$$ be the interval with the smallest $$$r_i$$$ among all active intervals.
• Let $$$y$$$ be the interval with the largest $$$l_i$$$ among all active intervals.
• If $$$r_x \lt l_y$$$, add $$$l_y - r_x$$$ to the score, mark intervals $$$x$$$ and $$$y$$$ as inactive, and continue the process.
• If $$$r_x \geq l_y$$$, stop the process.

At the end of this process, all active intervals will intersect at least one common point.

Now, we need to prove that the process indeed gives us the minimum possible score. We can prove this by induction.

Let $$$S$$$ be some set of intervals, and let $$$x$$$ and $$$y$$$ be the intervals defined above. Consider the set $$$S' = S \setminus {x, y}$$$ (i.e., $$$S'$$$ is the set $$$S$$$ excluding $$$x$$$ and $$$y$$$). We claim that:

This is true because, for $$$x$$$ and $$$y$$$ to intersect, we must perform at least $$$\text{distance}(x, y)$$$ operations. Our construction achieves the lower bound of $$$\text{score}(S') + \text{distance}(x, y)$$$. Thus,

During the process, we pair some intervals (possibly none). Specifically, in the $$$k$$$-th step, we pair the interval with the $$$k$$$-th smallest $$$r_i$$$ with the interval having the $$$k$$$-th largest $$$l_j$$$, and add the distance between them to the score.

In the problem G1, we can compute the contribution of each pair of intervals as follows:

Suppose we consider a pair $$$(i, j)$$$. Without loss of generality, assume that $$$r_i \lt l_j$$$.

The pair $$$(i, j)$$$ will be considered in some subset $$$S$$$ if there are exactly $$$x$$$ intervals $$$p$$$ such that $$$r_p \lt r_i$$$ and exactly $$$x$$$ intervals $$$p$$$ such that $$$l_p \gt l_j$$$, for some non-negative integer $$$x$$$.

Let there be $$$g$$$ intervals $$$p$$$ such that $$$r_p \lt r_i$$$ and $$$h$$$ intervals $$$p$$$ such that $$$l_p \gt l_j$$$.

For $$$(i, j)$$$ to be paired in some subset $$$S$$$, we must choose $$$x$$$ intervals from the $$$g$$$ intervals on the left and $$$x$$$ intervals from the $$$h$$$ intervals on the right, for some non-negative integer $$$x$$$. There are no restrictions on the remaining $$$n - 2 - g - h$$$ intervals.

Therefore, the contribution of $$$(i, j)$$$ is:

We can simplify this sum using the identity:

(This is a form of the Vandermonde Identity.)

Thus, the contribution of $$$(i, j)$$$ becomes:

This can be computed in $$$O(1)$$$ time.

Note that in the explanation above, we assumed that the interval endpoints are distinct for simplicity. If they are not, we can order the intervals based on their $$$l_i$$$ values to maintain consistency.

Let us find the contribution of $$$r[i]$$$, the right endpoint of $$$i$$$-th interval.

Let $$$x$$$ be the number of intervals $$$j$$$ such that $$$r[j] \lt r[i]$$$, and let $$$y$$$ be the number of intervals $$$j$$$ such that $$$l[j] \gt r[i]$$$.

To determine the contribution of $$$r[i]$$$ to the final answer, we consider selecting $$$p$$$ intervals from the $$$x$$$ intervals to the left and $$$q$$$ intervals from the $$$y$$$ intervals to the right, with the constraint that $$$p \lt q$$$. We require $$$p \lt q$$$ so that interval $$$i$$$ is paired with some other interval on the right (as discussed in the solution for G1). Therefore, the contribution of $$$r[i]$$$ can be expressed as:

Here, $$$\text{ways}(x, y)$$$ represents the number of valid selections where $$$p \lt q$$$.

Calculating $$$\text{ways}(x, y)$$$

To compute $$$\text{ways}(x, y)$$$, we can use the Vandermonde identity to simplify the expression:

This can be rewritten as:

Define the function $$$g(k)$$$ as:

By applying the Vandermonde identity, we get:

Thus, the total number of ways is:

We can simplify this summation using the property of binomial coefficients:

where the function $$$h(p, q)$$$ is defined as:

Efficient Computation of $$$h(p, q)$$$

Note that:

Suppose throughout the solution, we call the function $$$h(p, q)$$$ $$$d$$$ times for pairs $$$(p_1, q_1), (p_2, q_2), \ldots, (p_d, q_d)$$$, in that order. We can observe that:

Since $$$h(p_i, q_i)$$$ can be computed from $$$h(p_{i-1}, q_{i-1})$$$ in $$$|p_i - p_{i-1}| + |q_i - q_{i-1}|$$$ operations, the amortized time complexity for this part is $$$O(n)$$$.

Final Contribution

Combining the above results, the contribution of $$$r[i]$$$ to the answer is:

A similar calculation can be applied to the contribution of $$$l[i]$$$. By summing these contributions across all relevant intervals, we obtain the final answer.

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define ld long double
#define nline "\n"
#define f first
#define s second
#define sz(x) (ll)x.size()
#define vl vector<ll>
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
const ll MOD=998244353;
const ll MAX=500500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
}
ll l[MAX],r[MAX],lft[MAX],rght[MAX],power[MAX];
void solve(){ 
  ll n; cin>>n;
  power[0]=1;
  for(ll i=1;i<=n;i++){
    cin>>l[i]>>r[i];
    power[i]=(power[i-1]*2ll)%MOD;
  }
  for(ll i=1;i<=n;i++){
    lft[i]=rght[i]=0;
    for(ll j=1;j<=n;j++){
      if(make_pair(r[i],i)>make_pair(r[j],j)){
        lft[i]++;
      }
      if(make_pair(l[i],i)<make_pair(l[j],j)){
        rght[i]++;
      }
    }
  }
  ll ans=0;
  for(ll i=1;i<=n;i++){
    for(ll j=1;j<=n;j++){
      if(r[i]<l[j]){
        ll found=lft[i]+rght[j];
        ll now=nCr(found,lft[i],MOD)*(l[j]-r[i]);
        now%=MOD;
        ll remaining=n-found-2;
        ans=(ans+now*power[remaining])%MOD;
      }
    }
  }
  cout<<ans<<nline;
  return;    
}  
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                              
  ll test_cases=1;                 
  cin>>test_cases;
  precompute(MOD);
  while(test_cases--){
    solve();
  }
  cout<<fixed<<setprecision(12);  
  cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define ld long double
#define nline "\n"
#define f first
#define s second
#define sz(x) (ll)x.size()
#define vl vector<ll>
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
const ll MOD=998244353;
const ll MAX=5000500;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
}
ll l[MAX],r[MAX],power[MAX];
ll ans=0,on_left=0,on_right,len;
ll x=0,y=0,ways=0,inv2;
ll getv(){
  while(x>=len+1){
    ways=((ways+nCr(x-1,y,MOD))*inv2)%MOD;
    x--;
  }
  while(x<=len-1){
    ways=(2ll*ways-nCr(x,y,MOD)+MOD)%MOD;
    x++;
  }
  while(y<=on_left-1){
    ways=(ways+nCr(x,y+1,MOD))%MOD;
    y++;
  }
  return ways;
}
void solve(){ 
  ll n; cin>>n;
  power[0]=1;
  vector<array<ll,2>> track;
  multiset<ll> consider;
  for(ll i=1;i<=n;i++){
    cin>>l[i]>>r[i];
    track.push_back({r[i],l[i]});
    consider.insert(l[i]);
    power[i]=(power[i-1]*2ll)%MOD;
  }
  ans=on_left=0;
  on_right=len=n;
  x=y=0; ways=1;
  sort(all(track));
  for(auto it:track){
    while(!consider.empty()){
      if(*consider.begin() <= it[0]){
        consider.erase(consider.begin());
        on_right--,len--;
      }
      else{
        break;
      }
    }
    ll now=power[len]-getv();
    now=(now*power[n-1-len])%MOD;
    now=(now*it[0])%MOD;
    ans=(ans+MOD-now)%MOD;
    on_left++,len++;
  }
  track.clear(); consider.clear();
  for(ll i=1;i<=n;i++){
    track.push_back({l[i],r[i]});
    consider.insert(r[i]);
  }
  sort(all(track));
  reverse(all(track));
  on_left=0;
  on_right=len=n;
  x=y=0; ways=1;
  for(auto it:track){
    while(!consider.empty()){
      if(*(--consider.end()) >= it[0]){
        consider.erase(--consider.end());
        on_right--,len--;
      }
      else{
        break;
      }
    }
    ll now=power[len]-getv();
    now=(now*power[n-1-len])%MOD;
    now=(now*it[0])%MOD;
    ans=(ans+now)%MOD;
    on_left++,len++;
  }
  ans=(ans+MOD)%MOD;
  cout<<ans<<nline;
  return;    
}  
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                              
  ll test_cases=1;                 
  cin>>test_cases;
  precompute(MOD);
  inv2=inverse(2,MOD);
  while(test_cases--){
    solve();
  }
  cout<<fixed<<setprecision(12);  
  cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 

We choose $$$c$$$ between $$$a$$$ and $$$b$$$ $$$(a \leq c \leq b)$$$. The distance is $$$(c - a) + (b - c) = b - a$$$. Note that the distance does not depend on the the position $$$c$$$ at all.

for _ in range(int(input())):
    a,b = map(int,input().split())
    print(b-a)

Implement the statement. Iterate from $$$n-1$$$ to $$$0$$$ and use the .find() method in std::string in C++ (or .index() in python) to find the '#' character.

import sys
input=lambda:sys.stdin.readline().rstrip()

for i in range(int(input())):
    n=int(input())
    print(*reversed([input().index("#")+1 for i in range(n)]))

Consider the $$$x$$$ and $$$y$$$ directions separately and calculate the jumps we need in each direction. The number of jumps we need in the $$$x$$$ direction is $$$\lceil \frac{x}{k} \rceil$$$ and similarily $$$\lceil \frac{y}{k} \rceil$$$ in the $$$y$$$ direction. Now let's try to combine them to obtain the total number of jumps. Let's consider the following cases:

• $$$\lceil \frac{y}{k} \rceil \geq \lceil \frac{x}{k} \rceil$$$. In this case, there will need to be $$$\lceil \frac{y}{k} \rceil - \lceil \frac{x}{k} \rceil$$$ extra jumps in the $$$y$$$ direction. While Freya performs these extra jumps, she will choose $$$d = 0$$$ for the $$$x$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{y}{k} \rceil$$$ jumps.

• $$$\lceil \frac{x}{k} \rceil \gt \lceil \frac{y}{k} \rceil$$$. We can use the same reasoning as the previous case, but there's a catch. Since Freya is initially facing the $$$x$$$ direction, for the last jump, she does not need to jump in the $$$y$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{x}{k} \rceil - 1$$$ jumps.

for _ in range(int(input())):
    x,y,k = map(int,input().split())
    print(max(2*((x+k-1)//k)-1,2*((y+k-1)//k)))

Initially, the obvious case one might first consider is an upright right triangle (specifically, the triangle with one of its sides parallel to the $$$y$$$-axis). This side can only be made with two points in the form $$$(x, 0)$$$ and $$$(x,1)$$$. We only need to search third point. Turns out, the third point can be any other unused vertex! If the third point has $$$y = 0$$$, then it will be an upright triangle, but if the third point has $$$y = 1$$$, it will simply be upside down.

One of the other case is in the form of $$$(x,0), (x+1,1), (x+2, 0)$$$. Let's see why this is a right triangle. Recall that in right triangle, the sum of the squares of two of the sides must equal to the square of the third side. The length between the first and the second point is $$$\sqrt 2$$$ because it is the diagonal of $$$1$$$ by $$$1$$$ unit block. Similarily, the second and third point also has length $$$\sqrt 2$$$. Obviously, the length between the first and third point is $$$2$$$. Since we have $$$\sqrt 2^2 + \sqrt 2^2 = 2^2$$$, this is certainly a right triangle. Of course, we can flip the $$$y$$$ values of each point and it will still be a valid right triangle, just upside down.

from collections import Counter
for _ in range(int(input())):
    n = int(input())
    nums = []
    for i in range(n):
        x,y = map(int,input().split())
        nums.append((x,y))
    ans = 0
    b = Counter(x[0] for x in nums)
    check = set(nums)
    for i in b:
        if b[i]==2: ans += n-2
    for p in check:
        if (p[0]-1,p[1]^1) in check and (p[0]+1,p[1]^1) in check: 
            ans +=1
    print(ans)
    

We can rewrite $$$x$$$ as $$$|a_1+\dots+a_i-(a_{i+1}+\dots+a_n)|$$$. Essentially, we want to minimize the absolute value difference between the sums of the prefix and the suffix. With absolute value problems. it's always good to consider the positive and negative cases separately. We will consider the prefix greater than the suffix separately with the less than case.

We can use binary search to search for the greatest $$$i$$$ such that $$$a_1 + \dots + a_i \leq a_{i+1} + \dots + a_n$$$. Note that here, the positive difference is minimized. If we move to $$$i+1$$$, then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.

To evaluate $$$a_1 + \dots + a_i$$$ fast, we can use the sum of arithmetic sequence formula.

from collections import Counter
def val(mid):
    val1 = (mid+k-1+k)*mid//2
    val2 = (k+n-1+k)*n//2 - val1
    return val1,val2
for _ in range(int(input())):
    n,k = map(int,input().split())
    lo = 1
    hi = n
    curr = 1
    while lo <= hi:
        mid = (lo+hi)//2
        a,b = val(mid)
        if b>a:
            curr = mid
            lo = mid+1
        else:
            hi = mid-1
    a1,b1 = val(curr)
    a2,b2 = val(curr+1)
    print(min(b1-a1,a2-b2))

import sys
input=sys.stdin.readline

from math import floor,sqrt

f=lambda x: (2*x*x + x*(4*k-2) + (n-n*n-2*k*n))//2

t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    D=4*k*k + 4*k*(n-1) + (2*n*n-2*n+1)
    i=(floor(sqrt(D))-(2*k-1))//2
    ans=min(abs(f(i)),abs(f(i+1)))
    print(ans) 

Let's duplicate the array $$$a$$$ and concatenate it with itself. Now, $$$a$$$ should have length $$$2n$$$ and $$$a_i = a_{i-n}$$$ for all $$$n \lt i \leq 2n$$$. Now, the $$$j$$$'th element of the $$$i$$$'th rotation is $$$a_{i+j-1}$$$.

It can be shown for any integer $$$x$$$, it belongs in rotation $$$\lfloor \frac{x-1}{n} \rfloor + 1$$$ and at position $$$(x-1) \mod n + 1$$$. Let $$$rl$$$ denote the rotation for $$$l$$$ and $$$rr$$$ denote the rotation for $$$r$$$. If $$$rr - rl \gt 1$$$, we are adding $$$rr-rl-1$$$ full arrays to our answer. The leftovers is just the suffix of rotation $$$rl$$$ starting at position $$$l$$$ and the prefix of rotation of $$$rr$$$ starting at position $$$r$$$. This can be done with prefix sums. You may need to handle $$$rl=rr$$$ separately.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, q;
        cin >> n >> q;
        vector<ll> a(n), ps(1);
        for (ll &r : a) {
            cin >> r;
            ps.push_back(ps.back() + r);
        }
        for (ll &r : a) {
            ps.push_back(ps.back() + r);
        }
        while (q--) {
            ll l, r;
            cin >> l >> r;
            l--; r--;
            ll i = l / n, j = r / n;
            l %= n; r %= n;
            cout << ps[n] * (j - i + 1) - (ps[i + l] - ps[i]) - (ps[j + n] - ps[j + r + 1]) << "\n";
        }
    }
}

We first make the sequence $$$b_i=a_i-i$$$ for all $$$i$$$. Now, if $$$b_i=b_j$$$, then $$$i$$$ and $$$j$$$ are in correct relative order.

Now, to solve the problem, we precompute the answer for every window of $$$k$$$, and then each query is a lookup. We use a sliding window, maintaining a multiset of frequencies of values of $$$b$$$ in the current window. To move from the window $$$[i\ldots i+k-1]$$$ to $$$i+1 \ldots i+k$$$, we lower the frequency of $$$b_i$$$ by $$$1$$$, and increase the frequency of $$$b_{i+k}$$$ by $$$1$$$.

#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

void solve(){
    int n, k, q; cin >> n >> k >> q;
    int a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
    map <int,int> m;
    multiset <int> tot;
    for(int i = 1; i <= n; i++) tot.insert(0);
    for(int i = 1; i < k; i++){
        tot.erase(tot.find(m[a[i] - i]));
        m[a[i] - i]++;
        tot.insert(m[a[i] - i]);
    }
    int ret[n + 1];
    for(int i = k; i <= n; i++){
        tot.erase(tot.find(m[a[i] - i]));
        m[a[i] - i]++;
        tot.insert(m[a[i] - i]);
        int p = i - k + 1;
        ret[p] = k - *tot.rbegin();
        tot.erase(tot.find(m[a[p] - p]));
        m[a[p] - p]--;
        tot.insert(m[a[p] - p]);
    }
    while(q--){
        int l, r ; cin >> l >> r;
        cout << ret[l] << endl;
    }
    tot.clear();
    m.clear();
}

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

First, read the solution to the easy version of the problem to compute the answer for every window of $$$k$$$. Let $$$c_i=f([a_i, ..., a_{i+k-1}])$$$. Now, the problem simplifies to finding

$$$\sum_{j=l}^{r-k+1} ( \min_{i=l}^{j} c_i)$$$

We will answer the queries offline in decreasing order of $$$l$$$. We maintain a lazy segment tree. We have a variable $$$x$$$ sweeping from $$$n-k$$$ to $$$0$$$. As the variable sweeps leftwards, in node $$$i$$$ of the segment tree, we keep track of $$$\min_{j=x}^{i}c_i$$$.

To decrease the value of $$$x$$$, we note that the range $$$[x-1, y]$$$ in the segment tree will be set to $$$c_{x-1}$$$, where $$$y$$$ is the largest value such that $$$c_y \gt c_{x-1}$$$ but $$$c_{y+1}\leq c_{x-1}$$$ (or $$$y=n-1$$$). To find the $$$y$$$ for each $$$x$$$, we may either walk/binary search in the segment tree, or use a monotonic stack.

#include "bits/stdc++.h"
#define int long long

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;
}

using namespace std;

int getAns(int& k, multiset<int>& ms) { return k - (*ms.rbegin()); }
struct SegTree {
    int n;
    vector<int> tree, setLazy, begin, end;
    void prop(int i) {
        if (setLazy[i] != -100) {
            setLazy[2 * i + 1] = setLazy[2 * i] = setLazy[i];
            tree[2 * i] = tree[2 * i + 1] =
                setLazy[i] * (end[2 * i + 1] - begin[2 * i + 1] + 1);
            setLazy[i] = -100;
        }
    }
    SegTree(int nn) {
        n = 1;
        while (n < nn) n *= 2;
        tree.resize(2 * n);
        setLazy.resize(2 * n, -100);
        begin.resize(2 * n);
        end.resize(2 * n);
        for (int i = n; i < 2 * n; i++) {
            begin[i] = end[i] = i - n;
        }
        for (int i = n - 1; i > 0; i--) {
            begin[i] = begin[2 * i];
            end[i] = end[2 * i + 1];
        }
    }
    void rangeSet(int i, int amt, int lo, int hi) {
        if (i < n) prop(i);
        if (begin[i] == lo && end[i] == hi) {
            tree[i] = amt * (hi - lo + 1);
            setLazy[i] = amt;
            return;
        }
        if (begin[2 * i] <= hi && end[2 * i] >= lo) {
            rangeSet(2 * i, amt, lo, min(hi, end[2 * i]));
        }
        if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
            rangeSet(2 * i + 1, amt, max(lo, begin[2 * i + 1]), hi);
        }
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    int query(int i, int lo, int hi) {
        if (i < n) prop(i);
        if (begin[i] == lo && end[i] == hi) return tree[i];
        int ans = 0;
        if (begin[2 * i] <= hi && end[2 * i] >= lo) {
            ans += query(2 * i, lo, min(end[2 * i], hi));
        }
        if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
            ans += query(2 * i + 1, max(lo, begin[2 * i + 1]), hi);
        }
        return ans;
    }
};
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k, q;
        cin >> n >> k >> q;
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            v[i] = v[i] - i;
        }
        vector<int> ans(n);  // ans[i] is answer from i to i+k-1
        map<int, int> mp;
        multiset<int> active;
        for (int i = 0; i < k; i++) {
            if (mp[v[i]] == 0) {
                mp[v[i]] = 1;
                active.insert(1);
            } else {
                active.erase(active.find(mp[v[i]]));
                mp[v[i]]++;
                active.insert(mp[v[i]]);
            }
        }
        ans[0] = getAns(k, active);
        for (int i = k; i < n; i++) {
            // erase v[i-k]
            active.erase(active.find(mp[v[i - k]]));
            mp[v[i - k]]--;
            if (mp[v[i - k]] != 0) active.insert(mp[v[i - k]]);

            if (mp[v[i]] == 0) {
                mp[v[i]] = 1;
                active.insert(1);
            } else {
                active.erase(active.find(mp[v[i]]));
                mp[v[i]]++;
                active.insert(mp[v[i]]);
            }
            ans[i - k + 1] = getAns(k, active);
        }
        vector<array<int, 3>> queries(q);
        vector<int> an(q);
        for (int i = 0; i < q; i++) {
            queries[i][2] = i;
            cin >> queries[i][0] >> queries[i][1];
            queries[i][0]--;
            queries[i][1]--;
            queries[i][0] *= -1;
        }
        sort(begin(queries), end(queries));
        for (int i = 0; i < q; i++) queries[i][0] *= -1;
        SegTree st(n);
        st.rangeSet(1, ans[n - k], n - k, n - k);
        int cur = n - k;
        stack<pair<int, int>> s;
        s.push({ans[n - k], n - k});
        for (int i = 0; i < q; i++) {
            while (cur != queries[i][0]) {
                cur--;
                int here = cur;
                while (s.size() && s.top().first > ans[cur]) {
                    here = s.top().second;
                    s.pop();
                }
                s.push({ans[cur], here});
                st.rangeSet(1, ans[cur], cur, here);
            }
            an[queries[i][2]] =
                st.query(1, queries[i][0], queries[i][1] - k + 1);
        }
        for (auto x : an) cout << x << endl;
    }
}

Let $$$p_i$$$ be the smallest value $$$j \gt i$$$ such that $$$c_j \lt c_i.$$$ We can calculate these values using a monotonic stack and iterating through $$$c$$$ backwards. If such $$$j$$$ does not exist, then we let $$$p_i=n.$$$ Then $$$f(h,i)=c_i$$$ for all $$$i\le h-k+1 \lt p_i.$$$ Further, $$$f(h,i)=c_{p_i}$$$ for $$$p_i\le h-k+1 \lt p_{p_i},$$$ and so on.

Now, let $$$w(0,i)=i,$$$ and $$$w(h,i)=p_{w(h-1,i)}$$$ for $$$h \gt 0.$$$ To calculate the answer for a query $$$(l,r),$$$ consider the largest value of $$$j$$$ such that $$$w(j,l)\le r.$$$ Then we can take the sum $$$c_{w(j,l)}\cdot(r-w(j,l)+1)+\sum_{i=1}^jc_{w(i-1,l)}\cdot(w(i,l)-w(i-1,l)).$$$

Now it remains to quickly calculate this sum. We can use binary lifting to solve this. Specifically, we create an $$$n\times20$$$ data table where $$$d[i][j]=\sum_{h=1}^{2^j}c_{w(h-1,i)}\cdot(w(h,i)-w(h-1,i)),$$$ if $$$w(2^j,i)$$$ exists, and $$$-1$$$ otherwise. We can precompute this table recursively, as $$$d[i][0]=c_i\cdot(w(1,i)-i)$$$ and $$$d[i][j]=d[i][j-1]+d[w(2^{j-1},i)][j-1].$$$

Then, to answer queries, we iterate $$$j$$$ from $$$19$$$ to $$$0,$$$ and if $$$w(2^j,l)\le r,$$$ we add $$$d[l][j]$$$ to our answer, and set $$$l=w(2^j,l).$$$ At the end, we add $$$c_l\cdot(r-l+1)$$$ to our answer.

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int &r : a) cin >> r;
    vector<int> c(3 * n), v(n);
    multiset<int> s;
    for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    for (int r : c) s.insert(r);
    v[k - 1] = k - *s.rbegin();
    for (int i = k; i < n; i++) {
        int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
        c[x]++;
        s.erase(s.find(c[x] - 1));
        s.insert(c[x]);
        c[y]--;
        s.erase(s.find(c[y] + 1));
        s.insert(c[y]);
        v[i] = k - *s.rbegin();
    }
    vector<int> l(n, -1);
    stack<pii> t;
    for (int i = k - 1; i < n; i++) {
        while (!t.empty()) {
            if (t.top().se <= v[i]) break;
            l[t.top().fi] = i;
            t.pop();
        }
        t.push({i, v[i]});
    }
    vector<vector<pii>> w(n, vector<pii>(20, {-1, -1}));
    for (int i = n - 1; i >= k - 1; i--) {
        w[i][0].se = l[i];
        if (l[i] < 0) {
            w[i][0].fi = (n - i) * v[i];
            continue;
        }
        w[i][0].fi = (l[i] - i) * v[i];
        for (int j = 1; j < 20; j++) {
            if (w[w[i][j - 1].se][j - 1].se < 0) break;
            w[i][j].se = w[w[i][j - 1].se][j - 1].se;
            w[i][j].fi = w[i][j - 1].fi + w[w[i][j - 1].se][j - 1].fi;
        }
    }
    while (q--) {
        int l, r, ans = 0;
        cin >> l >> r;
        l--;
        r--;
        l += k - 1;
        for (int j = 19; ~j; j--) {
            if (w[l][j].se < 0) continue;
            if (w[l][j].se > r) continue;
            ans += w[l][j].fi;
            l = w[l][j].se;
        }
        cout << ans + v[l] * (r - l + 1) << "\n";
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

I decided to write the Editorial for this problem in a step-by-step manner. Some of the steps are really short and meant to be used as hints but i decided to have a uniform naming for everything.

#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define pii pair<int,int> 
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
struct segtree {
    const static int INF = 1e18, INF2 = 0;
    int l, r;
    segtree* lc, * rc;
    int v = INF, v2=0, v3=0, v4=0;
    segtree* getmem();
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        if (l == r) return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    int op(int a, int b) {
        return min(a,b); 
    }
    int op2(int a, int b) {
        return a+b; 
    }
    void add(int qi, int qv, int h, int h4=0) {
        if (r < qi || l > qi) return;
        if (l == r) { if (v==INF) v=qv; v2+=qv, v3+=qv*h; v4+=qv*h4; return;}
        lc->add(qi, qv, h, h4); rc->add(qi, qv, h, h4);
        v = op(lc->v, rc->v);
        v2 = op2(lc->v2, rc->v2); 
        v3 = op2(lc->v3, rc->v3); 
        v4 = op2(lc->v4, rc->v4); 
    }
    int qrr(int ql, int qx) {
        if (v>=qx||r<ql) return 1e9; 
        if (l==r) return l; 
        int k=lc->qrr(ql,qx); 
        if (k<1e9) return k; 
        return rc->qrr(ql,qx); 
    }
    int q2(int ql, int qr) {
        if (l > qr || r < ql) return INF2;
        if (ql <= l && r <= qr) return v2;
        return op2(lc->q2(ql, qr), rc->q2(ql, qr));
    }
    int q3(int ql, int qr) {
        if (l > qr || r < ql) return INF2;
        if (ql <= l && r <= qr) return v3;
        return op2(lc->q3(ql, qr), rc->q3(ql, qr));
    }
    int q4(int ql, int qr) {
        if (l > qr || r < ql) return INF2; 
        if (ql <= l && r <= qr) return v4; 
        return op2(lc->q4(ql, qr), rc->q4(ql, qr)); 
    }
};
segtree mem[2000005];int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int &r : a) cin >> r;
    vector<int> c(2 * n), v(n);
    multiset<int> s;
    for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    for (int r : c) s.insert(r);
    v[k - 1] = k - *s.rbegin();
    for (int i = k; i < n; i++) {
        int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
        c[x]++;
        s.erase(s.find(c[x] - 1));
        s.insert(c[x]);
        c[y]--;
        s.erase(s.find(c[y] + 1));
        s.insert(c[y]);
        v[i] = k - *s.rbegin();
    }
    vector<int> ans(q);
    vector<vector<pii>> w(n); 
    segtree co(0, n+2), lb(0, n+2), e(0,n+2),e2(0,n+2); 
    vector<int> rb(n); 
    stack<int> t; 
    for (int i = 0; i < q; i++) {
        int l,r; cin >> l >> r; 
        w[l+k-2].push_back({i,r-1}); 
    }
    for (int i = n-1; ~i; i--) {
        e.add(i,v[i],i,i*i); 
        int j=min(n,e.qrr(i,v[i])); 
        rb[i]=j; 
        e.add(j-1,-v[i],i,i*i);
        e2.add(j,v[i]*(j-i),i);
        while (!t.empty()) {
            int x=t.top(); 
            if (v[x]<v[i]) break;
            t.pop(); 
            co.add(rb[x],v[x]*(rb[x]-x)*(x-i),0); 
            lb.add(x,v[x]*(x-i),x);
            lb.add(rb[x]-1,-v[x]*(x-i),x); 
            e.add(x,-v[x],x,x*x);
            e.add(rb[x]-1,v[x],x,x*x);
            e2.add(rb[x],-v[x]*(rb[x]-x),x); 
        }
        t.push(i); 
        int l=i;
        for (auto [p,r]:w[i]) {
            int x=e.q2(l,r), y=e.q3(l,r), z=e.q4(l,r);
            int f=y*(r+1)-z, g=x*(r+1)-y; 
            int lx=lb.q2(l,r), ly=lb.q3(l,r); 
            ans[p]=co.q2(l,r+1)+lx*(r+1)-ly+e2.q3(l,r+1)-e2.q2(l,r+1)*(i-1)+f-g*(i-1);
        }
    }
    for (int r:ans) cout << r << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t = 1; cin >> t;
	while (t--) solve();
}

If $$$n$$$ is a multiple of $$$4$$$, then you can have $$$\frac{n}{4}$$$ cows. Otherwise, you must have at least one chicken, so you can have $$$\frac{n-2}{4}$$$ cows and $$$1$$$ chicken.

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--){
        int n;
        cin >> n;

        cout << (n + 2) / 4 << "\n";
    }
}

Let's define every $$$k$$$ by $$$k$$$ block of cells by its value in the top left corner, since all cells in the block must have the same value. So, we can just print out the value of the cell in every $$$k$$$'th row and every $$$k$$$'th column.

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--){
        int n, k;
        cin >> n >> k;

        char A[n][n];
        
        for (auto &row : A)
            for (char &c : row)
                cin >> c;
        
        for (int i = 0; i < n; i += k){
            for (int j = 0; j < n; j += k){
                cout << A[i][j];
            }
            cout << "\n";
        }
    }
}

For two strings to be the same after sorting, they must have the same occurrences of every possible lowercase letter. To answer the query for a range $$$[l, r]$$$, we must ensure that after the operations, $$$cnt_c = cnt2_c$$$ must where $$$cnt_c$$$ is the number of times character $$$c$$$ occurs in the range for $$$a$$$ and $$$cnt2_c$$$ is defined similarly for $$$b$$$. Both $$$cnt_c$$$ and $$$cnt2_c$$$ can be obtained by doing prefix sums for character $$$c$$$ specifically. Note that since there are only $$$26$$$ possible $$$c$$$, you can afford to create $$$26$$$ length $$$n$$$ prefix sum arrays.

In one operation, you can replace one occurrence of a character $$$c$$$ with another character $$$c2$$$. Essentially, you are subtracting one from $$$cnt_c$$$ and adding one to $$$cnt_{c2}$$$. Obviously, you must choose $$$c$$$ and $$$c2$$$ such that $$$cnt_c \gt cnt2_c$$$ and $$$cnt_{c2} \lt cnt2_{c2}$$$. So, we only have to focus on $$$c$$$ or $$$c2$$$ since one decreasing will automatically lead to the other increase. The answer is just the sum of $$$cnt_c - cnt2_c$$$ if $$$cnt_c \gt cnt2_c$$$ over all possible lowercase characters $$$c$$$.

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

void solve(){
    int n, q;
    cin >> n >> q;

    vector<vector<int>> pre1(n + 1, vector<int>(26, 0));
    vector<vector<int>> pre2(n + 1, vector<int>(26, 0));

    for (int i = 1; i <= n; i++){
        char c;
        cin >> c;
        pre1[i][c - 'a']++;

        for (int j = 0; j < 26; j++)
            pre1[i][j] += pre1[i - 1][j];
    }
    for (int i = 1; i <= n; i++){
        char c;
        cin >> c;
        pre2[i][c - 'a']++;

        for (int j = 0; j < 26; j++)
            pre2[i][j] += pre2[i - 1][j];
    }
    while (q--){
        int l, r;
        cin >> l >> r;

        int dif = 0;

        for (int c = 0; c < 26; c++){
            int v1 = pre1[r][c] - pre1[l - 1][c];
            int v2 = pre2[r][c] - pre2[l - 1][c];

            dif += abs(v1 - v2);
        }
        cout << dif / 2 << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

There are several solutions to this problem, The easiest way is to just fix either $$$a$$$, $$$b$$$ or $$$c$$$. Let's fix $$$a$$$. Since $$$ab + ac + bc \leq n$$$, we know at the minimum, $$$ab \leq n$$$. Divide on both sides to get $$$b \leq \frac{n}{a}$$$. When $$$a = 1$$$, there are $$$n$$$ choices for $$$b$$$. When $$$a = 2$$$, there are $$$\frac{n}{2}$$$ choices for $$$b$$$. So in total, there are $$$n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}$$$ total choices for $$$b$$$. This is just the harmonic series, so over all possible $$$a$$$, there are about $$$n \log n$$$ choices for $$$b$$$. Therefore, we can afford to loop through both $$$a$$$ and $$$b$$$.

Now that we have $$$a$$$ and $$$b$$$, all that's left is to solve for $$$c$$$. Let's solve for $$$c$$$ in both equations. In the first equation, we can factor $$$c$$$ out to obtain $$$ab + c(a+b) \leq n$$$. So, $$$c \leq \frac{n-ab}{a+b}$$$. In the second equation, $$$c \leq x - a - b$$$. Since we want the $$$c$$$ to satisfy both inequalities, we must choose the stricter one. So, the number of possible $$$c$$$ is $$$\min(\frac{n-ab}{a+b},x-a-b)$$$.

The answer is the sum of number of possible $$$c$$$ over all possible $$$a$$$ and $$$b$$$.

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

int main(){
    int tc;
    cin >> tc;

    while (tc--){
        int n, x;
        cin >> n >> x;

        long long ans = 0;
        
        for (int a = 1; a <= min(n, x); a++){
            for (int b = 1; a * b <= n and a + b <= x; b++){
                int highestC = min((n - a * b) / (a + b), x - (a + b));
                ans += highestC;
            }
        }
        cout << ans << "\n";
    }
}

How can we efficiently check if a range contains the same amount of zeroes and ones? Let's create an array $$$a$$$ where $$$a_i = -1$$$ if $$$s_i = 0$$$ and $$$a_i = 1$$$ if $$$s_i = 1$$$. Let's denote $$$p$$$ as the prefix sum array of $$$a$$$. We want the contribution of $$$-1$$$ by the zeroes to cancel out with the ones, so if $$$p_r - p_{l-1} = 0$$$, then the range $$$[l, r]$$$ contain equal amounts of zeroes and ones. We can rephrase the problem as the following: for each subrange $$$[l, r]$$$, count the number of pairs $$$(x,y)$$$ such that $$$p_{x-1} = p_y$$$.

Let's fix $$$p_{x-1}$$$ and keep track of all potential $$$y$$$ such that $$$y \gt x$$$ and $$$p_{x-1} = p_{y}$$$. How many subarrays will cover $$$[x, y]$$$? Well, we have $$$x+1$$$ options as $$$l$$$ and $$$n-y+1$$$ options as $$$r$$$, so the range $$$[x,y]$$$ contributes to $$$(x+1) \cdot (n-y+1)$$$ subarrays. We just need to calculate this expression for all potential $$$y$$$ now. Let's denote the all possible $$$y$$$ as $$$y_1, y_2, ... y_k$$$. We are asked to find the sum of $$$(x+1) \cdot (n-y_1+1) + (x+1) \cdot (n-y_2+1) + \dots + (x+1) \cdot (n-y_k+1)$$$. Let's factor $$$(x+1)$$$ out, and we have $$$(x+1) \cdot ((n-y_1+1)+(n-y_2+1)+\dots+(n-y_k+1))$$$. Since, the second part of the expression is just the sum of all $$$(n-y_i+1)$$$, we can first precalculate that sum and since $$$y \gt x$$$, subtract as we sweep from left to right.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
 
template<ll M>
struct modint {
 
    static ll _pow(ll n, ll k) {
        ll r = 1;
        for (; k > 0; k >>= 1, n = (n*n)%M)
            if (k&1) r = (r*n)%M;
        return r;
    }
 
    ll v; modint(ll n = 0) : v(n%M) { v += (M&(0-(v<0))); }
    
    friend string to_string(const modint n) { return to_string(n.v); }
    friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
    friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
    template<typename T> explicit operator T() { return T(v); }
 
    friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
    friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
    friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
    friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
    friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
    friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }
 
    modint& operator+=(const modint n) { v += n.v; v -= (M&(0-(v>=M))); return *this; }
    modint& operator-=(const modint n) { v -= n.v; v += (M&(0-(v<0))); return *this; }
    modint& operator*=(const modint n) { v = (v*n.v)%M; return *this; }
    modint& operator/=(const modint n) { v = (v*_pow(n.v, M-2))%M; return *this; }
    friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
    friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
    friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
    friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
    modint& operator++() { return *this += 1; }
    modint& operator--() { return *this -= 1; }
    modint operator++(int) { modint t = *this; return *this += 1, t; }
    modint operator--(int) { modint t = *this; return *this -= 1, t; }
    modint operator+() { return *this; }
    modint operator-() { return modint(0) -= *this; }
 
    modint pow(const ll k) const {
        return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
    }
    modint inv() const { return _pow(v, M-2); }
};
 
using mint = modint<int(MOD)>;
 
 
int main(){
	int t; cin >> t;
	while(t--){
		string s; cin >> s;
		int n = s.size();
		vector<int> p(n+1);
		for(int i = 1; i <= n; i++){
			p[i] = p[i-1] + (s[i-1] == '0' ? -1 : 1);
		}
		vector<vector<ll>> sums(2 * n + 1);
		for(int i = 0; i <= n; i++){
			sums[p[i] + n].push_back(i);
		}
		mint ans = 0;
		for(auto& v: sums){
			int N = v.size();
			vector<ll> j_sum(N+1);
			for(int i = N - 1; i >= 0; i--){
				j_sum[i] = j_sum[i+1] + v[i];
			}
			for(int i = 0; i < N - 1; i++){
				ll left = N - i - 1;
				ans += v[i] * n * left;
				ans -= v[i] * j_sum[i+1];
				ans += v[i] * left;
				ans += n * left;
				ans -= j_sum[i+1];
				ans += left;
			}
		}
		cout << ans << "\n";
	}
}

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

#define ll long long

const int MOD = 1e9 + 7;

void solve(){
    string S;
    cin >> S;

    int n = S.size();
    S = " " + S;

    vector<int> P(n + 1, 0);

    for (int i = 1; i <= n; i++){
        P[i] = (S[i] == '1' ? 1 : -1) + P[i - 1];
    }

    map<int, ll> cnt;
    ll ans = 0;

    for (int i = 0; i <= n; i++){
        ans = (ans + (n - i + 1) * cnt[P[i]]) % MOD;
        cnt[P[i]] = (cnt[P[i]] + (i + 1)) % MOD;
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Let's first solve the problem in $$$\mathcal{O}(k)$$$. One possible solution is to loop through each operation and take the largest $$$a_i$$$ each time, and set $$$a_i = \max(0, a_i - b_i)$$$. This can be done with a set or a priority queue.

With that in mind, let's binary search for the largest $$$x$$$ such that every value we add to our score has been greater or equal to $$$x$$$ for all $$$k$$$ operations. Define $$$f(x)$$$ as the number of operations required for every $$$a_i$$$ to be less than $$$x$$$. Specifically, $$$f(x) = \sum_{i=1}^n \lceil \frac{a_i-x}{b_i} \rceil$$$. We are searching for the smallest $$$x$$$ such that $$$f(x) \leq k$$$. Once we've found $$$x$$$, we can subtract $$$f(x)$$$ from $$$k$$$. Note that now, $$$k$$$ must be less than to $$$n$$$ (otherwise we can another operation on all $$$a_i$$$). So, it suffices to run the slow solution for these remaining operations (as long as $$$a_i \gt 0$$$). Alternatively, we can notice that the remaining operations will all add $$$x-1$$$ to our answer (assuming $$$x \gt 0$$$).

To obtain the sum of all $$$a_i$$$ we collected when calculating $$$f(x)$$$, we can use the arithmetic sequence sum formula. For each $$$i$$$, the number of terms in the sequence is $$$t = \lceil \frac{a_i-x}{b_i} \rceil$$$. The first term of the sequence is $$$f = a_i - b_i \cdot (t-1)$$$. The last term is $$$a_i$$$. Using the formula, we can add $$$\frac{t}{2}(f+a_i)$$$ to the answer.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];

        int ok = 0, ng = 1e9+1;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;

            long long sum = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] >= mid)
                    sum += (a[i] - mid) / b[i] + 1;
            }

            if (sum >= k) ok = mid;
            else ng = mid;
        }

        long long ans = 0;
        int s = 0;

        for (int i = 0; i < n; i++) {
            if (a[i] >= ok) {
                int m = (a[i] - ok) / b[i] + 1;
                ans += 1LL * m * a[i] - 1LL * m * (m - 1) / 2 * b[i];
                s += m;
            }
        }

        ans -= 1LL * ok * (s - k);

        cout << ans << "\n";
    }

    return 0;
}

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

#define ll long long

void solve(){
    int n, k;
    cin >> n >> k;

    vector<int> A(n), B(n);
    
    for (int &i : A)
        cin >> i;
    for (int &i : B)
        cin >> i;

    auto getInfo = [&](int cutoff){
        ll ops = 0;
        ll sum = 0;

        for (int i = 0; i < n; i++){
            ll a = A[i];
            ll b = B[i];

            if (cutoff > a)
                continue;

            // a - uses * b >= cutoff
            ll uses = (a - cutoff) / b;
            sum += (uses + 1) * a - b * uses * (uses + 1) / 2; 
            ops += uses + 1;

            sum = min(sum, 2 * (ll)1e18);
        }
        return make_pair(sum, ops);
    };

    int L = 0, H = 1e9 + 5;

    while (L < H){
        int M = (L + H) / 2;
        getInfo(M).second <= k ? H = M : L = M + 1;
    }

    auto [ans, opsUse] = getInfo(L);
    cout << ans + (k - opsUse) * max(L - 1, 0) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

There are two configurations to satisfy every friendship $$$(a, b)$$$: activate all the roads from $$$a \rightarrow a+1 \rightarrow \dots \rightarrow b$$$ or $$$b \leftarrow \dots \leftarrow n \leftarrow 1 \leftarrow \dots \leftarrow a$$$. Let's fix a road we deactivate. Say it goes from $$$i \rightarrow i+1$$$. Observe that the configuration for all friendships is fixed to one of the two cases. For example, if $$$a \leq i \lt b$$$, then we must use the second configuration.

We can try fixing every road and taking the minimum of number of roads. This can be done with sweep line. Once we reach $$$i = a$$$ for any friendship, we toggle to the second configuration. Once we reach $$$b$$$, we toggle back to the first. We can track maintained roads by performing a range addition on a lazy propagated segment tree for each point covered by the current configuration. The number of roads required is $$$n$$$ minus the number of occurrences of zeroes in the segment tree, which can be tracked with Counting Minimums in a Segment Tree.

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

class LazySegmentTree {
    struct Node {
        int min_val;
        int count;
        int lazy;
    };

    std::vector<Node> tree;
    int n;

    void buildTree(int v, int tl, int tr) {
        if (tl == tr) {
            tree[v] = {0, 1, 0};
        } else {
            int tm = (tl + tr) / 2;
            buildTree(v*2, tl, tm);
            buildTree(v*2+1, tm+1, tr);
            merge(v);
        }
    }

    void apply(int v, int tl, int tr, int val) {
        tree[v].min_val += val;
        tree[v].lazy += val;
    }

    void push(int v, int tl, int tr) {
        if (tree[v].lazy != 0) {
            int tm = (tl + tr) / 2;
            apply(v*2, tl, tm, tree[v].lazy);
            apply(v*2+1, tm+1, tr, tree[v].lazy);
            tree[v].lazy = 0;
        }
    }

    void merge(int v) {
        if (tree[v*2].min_val < tree[v*2+1].min_val) {
            tree[v].min_val = tree[v*2].min_val;
            tree[v].count = tree[v*2].count;
        } else if (tree[v*2].min_val > tree[v*2+1].min_val) {
            tree[v].min_val = tree[v*2+1].min_val;
            tree[v].count = tree[v*2+1].count;
        } else {
            tree[v].min_val = tree[v*2].min_val;
            tree[v].count = tree[v*2].count + tree[v*2+1].count;
        }
    }

    void updateRange(int v, int tl, int tr, int l, int r, int addend) {
        if (l > r) return;
        if (l == tl && r == tr) {
            apply(v, tl, tr, addend);
        } else {
            push(v, tl, tr);
            int tm = (tl + tr) / 2;
            updateRange(v*2, tl, tm, l, std::min(r, tm), addend);
            updateRange(v*2+1, tm+1, tr, std::max(l, tm+1), r, addend);
            merge(v);
        }
    }

    std::pair<int, int> queryRange(int v, int tl, int tr, int l, int r) {
        if (l > r) return {INT_MAX, 0};
        if (l <= tl && tr <= r) {
            return {tree[v].min_val, tree[v].count};
        }
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        auto left = queryRange(v*2, tl, tm, l, std::min(r, tm));
        auto right = queryRange(v*2+1, tm+1, tr, std::max(l, tm+1), r);
        if (left.first < right.first) {
            return left;
        } else if (left.first > right.first) {
            return right;
        } else {
            return {left.first, left.second + right.second};
        }
    }

public:
    LazySegmentTree(int _n) {
    	n = _n;
        tree.resize(4*n);
        buildTree(1, 0, n-1);
    }

    void updateRange(int l, int r, int addend) {
        updateRange(1, 0, n-1, l, r, addend);
    }

    std::pair<int, int> queryRange(int l, int r) {
        return queryRange(1, 0, n-1, l, r);
    }
    
    int get_maintained(){
    	pair<int, int> res = queryRange(0, n-1);
    	assert(res.first == 0);
    	return n - res.second;
    };
};


void solve() {
	int n, m; cin >> n >> m;
	vector<pair<int, int>> p(m);
	for(int i = 0; i < m; i++){
		cin >> p[i].first >> p[i].second;
		p[i].first--; p[i].second--;
	}
	LazySegmentTree st(n);
	for(pair<int, int> i: p){
		st.updateRange(i.first, i.second - 1, 1);
	}
	int ans = st.get_maintained();
	vector<vector<int>> start(n), end(n);
	for(int i = 0; i < m; i++){
		start[p[i].first].push_back(i);
		end[p[i].second].push_back(i);
	}
	for(int i = 0; i < n; i++){
		for(int j: start[i]){
			st.updateRange(p[j].first, p[j].second - 1, -1);
			st.updateRange(p[j].second, n - 1, 1);
			st.updateRange(0, p[j].first - 1, 1);
		}
		for(int j: end[i]){
			st.updateRange(p[j].second, n - 1, -1);
			st.updateRange(0, p[j].first - 1, -1);
			st.updateRange(p[j].first, p[j].second - 1, 1);
		}
		ans = min(ans, st.get_maintained());
	}
	cout << ans << "\n";
}

signed main() {
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

Consider the $$$n$$$-gon formed by the houses, with each road becoming an edge of the polygon. We draw diagonals between houses if they are friends. Let each diagonal arbitrarily "cover" one side of the polygon, where every road contained within one section split by the diagonal is covered by the diagonal.

We claim that two roads can both be deleted if and only if they are covered by the same set of diagonals. First, this is equivalent to saying that when we draw a line between these two roads, they do not intersect any of our drawn diagonals. (This is since if any diagonal covers one road and not another, then they must be on opposite sides of the diagonal, so drawing a line between the two roads must intersect that diagonal. The converse also holds.)

Now note that if two roads are on opposite sides of a diagonal, they cannot both be deleted, as then there is no path along maintained roads that connects the two endpoints of the diagonals, or the two houses that are friends.

So it suffices to count the most frequent set of covered diagonals over all roads.

We can represent a diagonal cover for some road using a xor hashing, where each diagonal is assigned a random number, and the roads that are covered by that diagonal are xor'd by this number.

By using $$$64$$$-bit integers, the probability of collision is negligible, as each 64-bit integer has equal probability of representing a unique set of diagonals, and we have at most $$$n$$$ represented sets.

For each pair of friends, we want to xor all values in a range by some random number. This can be done with a prefix xor array in $$$\mathcal{O}(1)$$$ per pair of friends. Counting the most frequent value at the end will take $$$\mathcal{O}(n \log n)$$$ time if a map is used or $$$\mathcal{O}(n)$$$ if an unordered map is used. In all, this solution runs in $$$\mathcal{O}(n \log n + m)$$$ or $$$\mathcal{O}(n + m)$$$ time.

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

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

int n,m,a,b,k,t; 

void solve() {
	cin >> n >> m;
	vector<int> v(n); 
	while (m--) {
		k=rng(); cin >> a >> b;
		v[a-1]^=k;
		v[b-1]^=k;
	}
	map<int,int> c;
	for (int r:v) m=max(m,c[a^=r]++); 
	cout << n-m-1 << "\n"; 
}

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

We can construct a solution by fixing all $$$x_i$$$ as $$$x_c$$$ or all $$$y_i$$$ as $$$y_c$$$. For example, if we fix all $$$y_i$$$ as $$$y_c$$$, then we can output pairs $$$(x_c-1, y_c), (x_c+1, y_c), (x_c-2, y_c), (x_c+2, y_c), ... , (x_c- \lfloor \frac{k}{2} \rfloor, y_c), (x_c + \lfloor \frac{k}{2} \rfloor, y_c)$$$. If the $$$k$$$ is odd, we need one more pair, so just output $$$(x_c, y_c)$$$.

#include <iostream>
using namespace std;

int main() {
	int t; cin >> t;
	while(t--){
		int x, y, k; cin >> x >> y >> k;
		for(int i = 0; i < k - k % 2; i++){
			cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
		} 
		if(k & 1){
			cout << x << " " << y << "\n";
		}
	}
}

We can always construct a solution such that the number of pairs $$$(i, j)$$$ is $$$1$$$ where the only pair is $$$(1, n)$$$. There exists several constructions, such as rotating $$$p$$$ once or increment all $$$p_i$$$ (and $$$p_i = n$$$ turns into $$$p_i = 1$$$).

Consider the former construction, where $$$q = [p_2, p_3, ..., p_n, p_1]$$$. For an arbitrarily interval $$$[i, j]$$$, $$$p[i..j]$$$ and $$$q[i..j]$$$ will have exactly $$$1$$$ element that's different, disregarding ordering. Since we have a permutation and all elements are distinct, the sum in the range will never be the same. The only exception is the entire array, of course.

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

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		vector<int> p(n);
		for(int& i: p) cin >> i;
		rotate(p.begin(), p.begin() + 1, p.end());
		for(int i: p) cout << i << " ";
		cout << "\n";
	}
}

First, solve for $$$k = 0$$$. Find some nice characterization about $$$med(c_i)$$$ and thus the maximum score.

Divide into $$$2$$$ cases where we either increment the max element or the median.

Apply binary search

Let's forget about the operations of adding $$$1$$$ to $$$a_i$$$ and figure out how to find an array's score. Assume the array $$$a$$$ is sorted in increasing order as the order doesnt change the problem.

First observe how $$$med(c_i)$$$ changes with respect to $$$i$$$. $$$med(c_i)$$$ is always either $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ or $$$a_{\lfloor \frac{n + 2}{2} \rfloor}$$$. You can prove this formally by considering different positions of $$$i$$$ with respect to the initial median position. Specifically, for all $$$i \le \lfloor \frac{n}{2} \rfloor$$$, $$$med(c_i) = a_{\lfloor \frac{n + 2}{2} \rfloor}$$$, and for other $$$i$$$, $$$med(c_i) = a_{\lfloor \frac{n}{2} \rfloor}$$$.

Claim 1 : The score of the final array (after sorting in increasing order) is $$$a_n + med(c_n)$$$

Hence, our score can be nicely characterized by "max + median of the others".

Claim 2 : Either we will use all $$$k$$$ operations on the element which eventually becomes max element in our array, or we will use all operations trying to improve $$$med(c_n)$$$ and keep max element constant.

Thus, we are in $$$2$$$ cases now, either increase max, or increase median of the rest. We will solve the problem considering both cases separately.

Case $$$1$$$ : We do operations on the element which becomes max eventually.

Case 2 : We do operations to increase the median of the others.

Thus, the problem is solved in $$$O(N \cdot log (MAX))$$$. The code is nicely written and commented, you may want to check it out.

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

int main(){
    int t; cin >> t;
    
    while (t--){
        int n, k; cin >> n >> k;
        
        vector <pair<int, int>> a(n);
        for (auto &x : a) cin >> x.first;
        for (auto &x : a) cin >> x.second;
        sort(a.begin(), a.end());
        
        long long ans = 0;
        // case 1 : increment max 
        for (int i = 0; i < n; i++) if (a[i].second == 1){
            // find med(c_i) 
            int mc;
            if (i < n / 2) mc = a[n / 2].first;
            else mc = a[(n - 2) / 2].first;
            
            ans = max(ans, 0LL + a[i].first + k + mc);
        }
        
        // case 2 : increment median
        int lo = 0, hi = 2e9;
        while (lo != hi){
            int mid = (1LL + lo + hi) / 2;
            
            int z = 0;
            vector <int> smaller_list;
            for (int i = 0; i < n - 1; i++){
                if (a[i].first >= mid){
                    z++;
                } else if (a[i].second == 1){
                    smaller_list.push_back(mid - a[i].first); // list of numbers smaller than x but b[i] = 1 
                }
            }
            
            reverse(smaller_list.begin(), smaller_list.end()); // list will be sorted in ascending, but we want sorted in descending, as greedily changing largest elements 
            int kk = k;
            for (auto x : smaller_list) if (kk >= x){
                kk -= x;
                z++;
            }
            
            if (z >= (n + 1) / 2) lo = mid;
            else hi = mid - 1;
        }
        
        ans = max(ans, 0LL + a[n - 1].first + lo);
        
        cout << ans << "\n";
    }
    return 0;
}

First, let's consider if there was no alternative bridges. Then obviously, if Bessie starts at island $$$i$$$ and keeps moving forwards, it is impossible for Elsie to move past island $$$i$$$ since the bridge would have already collapsed. From this, we can deduce that Bessie cannot let Elsie use these alternative bridges to overtake the island Bessie is on, or else Elsie will always reach the end first.

Therefore, Bessie will keep moving right in hopes of breaking enough bridges so that it is impossible to for Elsie to overtake Bessie. This can be simplified to: consider we are at island $$$i$$$ and $$$t$$$ units of time has passed, for all alternative bridges that Elsie can take with an endpoint $$$v \gt i + t$$$, we have to reach $$$v$$$ before her.

Let $$$d_i$$$ denote the minimum amount of time Elsie takes to reach island $$$i$$$. For the first case, consider all bridges with endpoints $$$v \gt S$$$, then $$$d_v \geq v - S - 1$$$ must hold true since we want to reach $$$v$$$ before Elsie does when we keep going right. We can rearrange the equation as $$$S \geq v - d_v - 1$$$. To make sure this holds true for all bridges, we just have to make sure this is true for the maximum value of $$$v - d_v$$$.

All $$$d_i$$$ can be calculated using a linear sweep to the right, and we can track all $$$v - d_v$$$ with a sweep to the left. Note that we cannot take a bridge if it starts past $$$S$$$, so we need to track the maximum with a multiset and erasing as we sweep.

Time Complexity is $$$\mathcal{O}(n \log n)$$$. There exists other solutions using prefix sums in $$$\mathcal{O}(n)$$$ and segment tree in $$$\mathcal{O}(n \log n)$$$

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)

void solve() {
	int n, m; cin >> n >> m;
	vector<vector<int>> g(n), rg(n);
	FOR(i,0,m){
		int u, v; cin >> u >> v;
		--u; --v;
		g[u].pb(v);
		rg[v].pb(u);
	}
	FOR(i,0,n-1) g[i].pb(i+1);
	vector<int> dist(n, -1);
	queue<int> q;
	dist[0] = 0;
	q.push(0);
	while(!q.empty()){
		int f = q.front();
		q.pop();
		trav(i, g[f]){
			if(dist[i] == -1){
				dist[i] = dist[f] + 1;
				q.push(i);
			}
		}
	}
	multiset<int> max_good_rights;
	vector<vector<int>> to_erase(n);
	string ans = string(n - 1, '0');
	ROF(i,n-1,0){
		trav(j, rg[i]){
			int max_right = i - dist[j];
			max_good_rights.insert(max_right);
			to_erase[j].pb(max_right);
		}
		trav(j, to_erase[i]){
			max_good_rights.erase(max_good_rights.find(j));
		}
		if(i < n - 1){
			int max_good_right = max_good_rights.empty() ? -1 : *prev(max_good_rights.end());
			if(i >= max_good_right - 1){
				ans[i] = '1';
			}
		}
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

Consider the ball with the maximum number. Let this ball be $$$m$$$. That ball can clearly be the last ball remaining. And if we are able to merge some ball $$$i$$$ with ball $$$m$$$ (whilst removing $$$m$$$), then ball $$$i$$$ can also be the last ball remaining.

We can do a divide and conquer solution. For some range $$$[l,r]$$$, let $$$m$$$ be the ball with the maximum value. Clearly, $$$m$$$ can be the last ball remaining if we only consider the range $$$[l, r]$$$.

Let's first recurse on $$$[l,m)$$$ and $$$(m,r]$$$. Let $$$s_l=a_l+a_{l+1}+\cdots+a_{m-1}$$$ (i.e. the sum of the left half). If $$$s_l \lt a_m$$$ then no ball in the left half can be the last one remaining. Otherwise, the results (i.e. whether each ball can be the last one standing) for range $$$[l,r]$$$ for balls in $$$[l,m)$$$ is the results we computer when recursing onto $$$[l,m)$$$. The same reasoning holds for the right half.

We can use a sparse table to find the maximum ball in any range. This leads to a $$$\mathcal{O}(n\log n)$$$ solution.

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

#define ll long long
#define pll pair<ll, ll>

const int MAX = 2e5 + 5;

int n, x, ans; ll A[MAX], bad[MAX], P[MAX]; pll rmq[MAX][18];

void dnq(int l, int r){
    if (l >= r)
        return;
    
    int lg = 31 - __builtin_clz(r - l + 1);
    int mid = max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]).second;
    
    dnq(l, mid - 1);
    dnq(mid + 1, r);

    ll sum1 = P[mid - 1] - P[l - 1];
    ll sum2 = P[r] - P[mid];

    // Left half bad
    if (A[mid] > sum1){
        bad[l] += 1;
        bad[mid] += -1;
    }
    // Right half bad
    if (A[mid] > sum2){
        bad[mid + 1] += 1;
        bad[r + 1] += -1;
    }
}

void solve(){
    cin >> n >> x;

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
        bad[i] = 0;
        rmq[i][0] = {A[i], i};
    }
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    
    dnq(1, n);

    ans = 0;

    for (int i = 1; i <= n; i++){
        bad[i] += bad[i - 1];
        ans += !bad[i];
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

For some ball $$$i$$$, let $$$l_i$$$ and $$$r_i$$$ be the first balls on the left and right that have a value greater than $$$a_i$$$.

Proccess the balls from largest $$$a_i$$$ to smallest $$$a_i$$$. For each ball $$$i$$$, let $$$\text{ans}_i$$$ denote whether it can be the last ball remaining. We know that if we merge ball $$$i$$$ with some ball $$$j$$$ (while discarding $$$j$$$) and $$$\text{ans}_j=1$$$, then $$$\text{ans}_i=1$$$. Furthermore, we know that balls $$$l_i$$$ and $$$r_i$$$ can freely merge with balls $$$j$$$ where $$$j$$$ is in interval $$$[l_i+1 \ldots r_i-1]$$$ while discarding $$$j$$$ (i.e. $$$\text{ans}_{l_i}$$$ and $$$\text{ans}_{r_i}$$$ would have taken this into account).

This motivates the following idea. Let $$$s$$$ be the sum of values in $$$[l_i+1 \ldots r_i-1]$$$. If $$$s \geq a_{l_i}$$$ then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{l_i}$$$. Similarly, if $$$s \geq a_{r_i}$$$, then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{r_i}$$$. This solution runs in $$$\mathcal{O}(n \log n)$$$ due to sorting.

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

#define ll long long

void solve(){
    int n, x;
    cin >> n >> x;

    vector<int> A(n + 5);
    vector<ll> P(n + 5);
    vector<int> ans(n + 5, 0);
    vector<int> ord(n);
    set<int> S{0, n + 1};

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
        ord.push_back(i);
    }
    sort(ord.begin(), ord.end(), [&](int a, int b){
        return A[a] > A[b];
    });
    for (int i : ord){
        int l = *(--S.lower_bound(i));
        int r = *S.lower_bound(i);
        ll sum = P[r - 1] - P[l];

        if (i == ord[0])
            ans[i] = true;
        if (sum >= A[l])
            ans[i] |= ans[l];
        if (sum >= A[r])
            ans[i] |= ans[r];
        
        S.insert(i);
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Consider the naive greedy solution. We continuously merge with the balls on the left and right without removing our ball until we can't anymore or our ball is the final remaining one.

Suppose at some point in this greedy approach, we can not merge with the balls on our left and right anymore without discarding our ball. Let our ball be $$$i$$$. Then we have the following cases.

1. There is a ball $$$l$$$ on the left of $$$i$$$ and ball $$$r$$$ on the right of $$$i$$$. Then: $$$\min(a_l,a_r) \gt a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$.
2. There is a ball $$$l$$$ on the left of $$$i$$$ but no ball on the right of $$$i$$$. Then: $$$a_l \gt a_{l+1}+a_{l+2}+\cdots+a_{\text{last}}$$$.
3. There exists no ball on the left of $$$i$$$ but a ball $$$r$$$ on the right of $$$i$$$. Then: $$$a_r \gt a_1+a_2+\cdots+a_{r-1}$$$.

For some ball $$$i$$$, if there exists some $$$l$$$ and/or some $$$r$$$ such that one of the above is true, then there exists no way for our ball to be the last one remaining. Otherwise, the ball can be the last one remaining.

Let $$$p$$$ be the prefix sum array of $$$a$$$ (i.e. $$$p_i=a_1+a_2+\cdots+a_i$$$).

For some ball $$$i$$$, we want to do the following.

1. Find the smallest $$$r_1$$$ such that there exists some $$$l$$$ such that ($$$l, r_1$$$) is a pair (i.e. $$$\min(a_l,a_{r_1}) \gt a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$). Finding this is more difficult than the other cases and will be focused on later.
2. Find the smallest $$$r_2$$$ such that $$$a_{r_2} \gt a_1+a_2+\cdots+a_{{r_r}-1}$$$. We can rewrite it as as $$$a_{r_2} \gt p_{r_2-1}$$$ and it can easily be found.
3. Find the smallest $$$r_l$$$ such that there exists no $$$l$$$ on the left of $$$i$$$ such that $$$a_l \gt a_{l+1}+a_{l+2}+\cdots+a_{r_l}$$$. We can rewrite the inequality as finding the first $$$r_l$$$ such that $$$p_{r_l} \geq a_l + p_l$$$ which can be done with binary search.

Suppose at some $$$i$$$, we know its $$$r_l$$$, $$$r_1$$$, and $$$r_{2}$$$. Then we know ball $$$i$$$ can be the last one remaining for prefixes spanning from $$$r_l$$$ to $$$\min(r_1-1, r_{2}-1)$$$ so we can do a range add with prefix sums.

The only thing we have not resolved yet is how to find the smallest $$$r_1$$$ for some $$$i$$$ such that $$$\min(a_l,a_{r_1}) \gt a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$.

Let's iterate over $$$r$$$. For each $$$r$$$ we want to find the leftmost $$$l$$$ such that $$$\min(a_l,a_{r}) \gt a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$

A key observation is that we can write the following inequality as $$$a_l \gt a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ and $$$a_r \gt a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ (both have to be true).

Using prefix sums, the equations can be rewritten as $$$a_l + p_l \gt p_{r-1}$$$ and $$$p_l \gt p_{r-1} - a_r$$$.

So some $$$(l,r)$$$ works if the equation above is satisfied. Consider the second part $$$p_l \gt p_{r-1} - a_r$$$. We can binary search to find the range of available $$$l$$$ that satisfy this. Specifically, let $$$l_b$$$ be the lower bound of the range. Then, any $$$l$$$ in $$$[l_b...i)$$$ satisfies this.

Now, let's try to satisfy $$$a_l + p_l \gt p_{r-1}$$$. Unfortunately, $$$a_l + p_l$$$ is not monotonic so the method above will not work. Instead, we can create a sparse table over all $$$a_i + p_i$$$. Then we can binary search to find the first $$$l_{opt}$$$ such that the maximum in range $$$[l_b,l_{opt}]$$$ (which can be found with the sparse table) is greater than $$$p_{r-1}$$$.

Circling back, $$$r_1$$$ is the minimum $$$r$$$ of an interval covering $$$i$$$ which can be found with things such as sweepline. In all, this solution runs in $$$\mathcal{O}(n \log n)$$$ time.

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

#define ll long long

void solve(){
    int n, x;
    cin >> n >> x;

    vector<ll> A(n + 5, 0);
    vector<ll> P(n + 5, 0);
    vector<vector<ll>> rmq(n + 5, vector<ll>(18, 0));

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];        
        rmq[i][0] = A[i] + P[i];
    }
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);

    vector<vector<int>> add(n + 5), rem(n + 5);

    auto ins = [&](int l, int r, int v){
        l = max(l, 1);

        if (l > r)
            return;

        add[l].push_back(v);
        rem[r + 1].push_back(v);
    };
    for (int r = 1; r <= n; r++){
        // r is a roadblock
        if (A[r] > P[r - 1])
            ins(1, r - 1, r);

        // Find leftmost l possible
        int lowerB = upper_bound(P.begin() + 1, P.begin() + n + 1, P[r - 1] - A[r]) - P.begin();
        int lo = lowerB, hi = r - 1;

        while (lo < hi){
            int mid = (lo + hi) / 2;

            // Query lowerB...mid
            int lg = 31 - __builtin_clz(mid - lowerB + 1);
            ll val = max(rmq[lowerB][lg], rmq[mid - (1 << lg) + 1][lg]);

            val > P[r - 1] ? hi = mid : lo = mid + 1;
        }
        ins(lo + 1, r - 1, r);
    }

    multiset<int> badR{n + 1};
    vector<int> ans(n + 5, 0);
    ll worst = 0; 

    for (int i = 1; i <= n; i++){
        for (int v : add[i])
            badR.insert(v);
        for (int v : rem[i])
            badR.erase(badR.find(v));

        int l = lower_bound(P.begin() + i, P.begin() + n + 1, worst) - P.begin();
        int r = *badR.begin();

        // Active for interval [l...r)
        if (l <= r){
            ans[l]++;
            ans[r]--;
        }
        worst = max(worst, A[i] + P[i]);
    }
    
    for (int i = x; i <= n; i++){
        ans[i] += ans[i - 1];
        cout << ans[i] << " \n"[i == n];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

To swap the first character of the strings, you can use the built-in method std::swap in C++, or for each string, separate the first character from the rest of the string and concatenate it with the other string.

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

int main(){
	int t; cin >> t;
	while(t--){
		string a, b; cin >> a >> b;
		swap(a[0], b[0]);
		cout << a << " " << b << endl;
	}
}

To maximize the number of multiples of $$$x$$$ less than $$$n$$$, it optimal to choose a small $$$x$$$, in this case, $$$2$$$. The only exception is $$$n = 3$$$, where it is optimal to choose $$$3$$$ instead, since both $$$2$$$ and $$$3$$$ have only one multiple less than $$$3$$$.

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

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		cout << (n == 3 ? 3 : 2) << endl;
 	}
}

The only element that can be the sum of all other elements is the maximum element, since all elements are positive. Therefore, for each prefix $$$i$$$ from $$$1$$$ to $$$n$$$, check if $$$sum(a_1, a_2, ..., a_i) - max(a_1, a_2, ..., a_i) = max(a_1, a_2, ..., a_i)$$$. The sum and max of prefixes can be tracked with variables outside the loop.

#include <iostream>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		int a[n];
		for(int i = 0; i < n; i++)
			cin >> a[i];
		long long sum = 0;
		int mx = 0, ans = 0;;
		for(int i = 0; i < n; i++){
			sum += a[i];
			mx = max(mx, a[i]);
			if(sum - mx == mx) 
				ans++;
		}
		cout << ans << endl;
	}
}

Note that the manhattan circle is always in a diamond shape, symmetric from the center. Let's take notice of some special characteristics that can help us. One way is to find the top and bottom points of the circle. Note that these points will have columns at the center of the circle, so here we can acquire the value of $$$k$$$. To find $$$h$$$, since the circle is symmetric, it is just the middle of the rows of the top and bottom points.

Note that we never needed to find the value of $$$r$$$.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int main(){
	int t; cin >> t;
	while(t--){
		int n, m; cin >> n >> m;
		vector<vector<char>> g(n, vector<char>(m));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> g[i][j];
			}
		}
		pair<int, int> top = {INF, INF}, bottom = {-INF, -INF};
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(g[i][j] == '#'){
					top = min(top, {i, j});
					bottom = max(bottom, {i, j});
				}
			}
		}
		assert(top.second == bottom.second);
		cout << (top.first + bottom.first) / 2 + 1 << " " << top.second + 1 << endl;
	}
}

Since the side lengths of $$$S$$$ has to multiply to $$$k$$$, all three side lengths of $$$S$$$ has to be divisors of $$$k$$$. Let's denote the side lengths of $$$S$$$ along the $$$x$$$, $$$y$$$, and $$$z$$$ axes as $$$a$$$, $$$b$$$, and $$$c$$$ respectively. For $$$S$$$ to fit in $$$B$$$ , $$$a \leq x$$$, $$$b \leq y$$$, and $$$c \leq z$$$ must hold. Because of the low constraints, we can afford to loop through all possible values of $$$a$$$ and $$$b$$$, and deduce that $$$c=\frac{k}{a \cdot b}$$$ (make sure $$$c \leq z$$$ and $$$c$$$ is an integer). To get the amount of ways we can place $$$S$$$, we can just multiply the amount of shifting space along each axes, and that just comes down to $$$(x−a+1) \cdot (y−b+1) \cdot (z−c+1)$$$. The answer is the maximum among all possible values of $$$a$$$, $$$b$$$, and $$$c$$$ .

The time complexity is $$$\mathcal{O}(n^2)$$$ where $$$n$$$ is at most $$$2000$$$.

#include <iostream>
using namespace std;
using ll = long long;

int main(){
	int t; cin >> t;
	while(t--){
		ll x, y, z, k; cin >> x >> y >> z >> k;
		ll ans = 0;
		for(int a = 1; a <= x; a++){
			for(int b = 1; b <= y; b++){
				if(k % (a * b)) continue;
				ll c = k / (a * b);
				if(c > z) continue;
				ll ways = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1);
				ans = max(ans, ways);
			}
		}
		cout << ans << "\n";
	}
}

Unfortunately, there was a lot of hacks on this problem, and we're sorry for it. Since our intended solution is not binary search, we didn't really take overflow using binary search seriously. I (cry) prepared this problem and I only took into account about overflow with big cooldown, but I forgot overflow can happen on attacks as well. I apologize and we will do better next time!

Since the sum of $$$h$$$ is bounded by $$$2 \cdot 10^5$$$, and each attack deals at least $$$1$$$ damage. If we assume every turn we can make at least one attack, the sum of turns to kill the boss in every test case is bounded by $$$2 \cdot 10^5$$$. This means that we can afford to simulate each turn where we make at least one attack.

But what if we cannot make an attack on this turn? Since the cooldown for each attack can be big, we cannot increment turns one by one. We must jump to the next turn we can make an attack. This can be done by retrieving the first element of a sorted set, where the set stores pairs {$$$t$$$, $$$i$$$} which means {next available turn you can use this attack, index of this attack} for all $$$i$$$. Here, we can set the current turn to $$$t$$$ and use all attacks in the set with first element in the pair equal to $$$t$$$. Remember to insert the pair to {$$$c_i + t$$$, $$$i$$$} back into the set after processing the attacks.

The time complexity is $$$\mathcal{O}(h \log n)$$$.

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

int main(){
	int t; cin >> t;
	while(t--){
		int h, n; cin >> h >> n;
		vector<int> a(n), c(n);
		for(int& i: a) cin >> i;
		for(int& i: c) cin >> i;
		set<pair<long long, int>> S;
		for(int i = 0; i < n; i++){
			S.insert({1, i});
		}
		long long last_turn = 1;
		while(h > 0){
			auto [turn, i] = *S.begin();
			S.erase(S.begin());
			last_turn = turn;
			h -= a[i];
			S.insert({turn + c[i], i});
		}
		cout << last_turn << "\n";
	}
}

// comment "tomato" if you see this comment

Try to solve this if $$$1 \le h \le 10^9$$$.

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

#define ll long long

void solve(){
    ll h, n;
    cin >> h >> n;

    vector<ll> A(n), C(n);

    for (ll &i : A)
        cin >> i;
    for (ll &i : C)
        cin >> i;
    
    auto chk = [&](ll t){
        ll dmg = 0;
        for (int i = 0; i < n and dmg < h; i++){
            ll cnt = (t - 1) / C[i] + 1;

            if (cnt >= h)
                return true;

            dmg += cnt * A[i];
        }
        return dmg >= h;
    };

    ll L = 1, H = 1e12;

    while (L < H){
        ll M = (L + H) / 2;
        chk(M) ? H = M : L = M + 1;
    }
    cout << L << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

To satisfy $$$D(k \cdot n) = k \cdot D(n)$$$, each digit $$$d$$$ in $$$n$$$ must become $$$k \cdot d$$$ after multiplying $$$n$$$ by $$$k$$$. In other words, none of $$$n$$$'s digits can carry over to the next digit upon multiplication. From this, we can deduce that each digit in $$$n$$$ must be less than or equal to $$$\lfloor \frac{9}{k} \rfloor$$$. Only thing left is to count all such numbers in the range of $$$10^l$$$ inclusive and $$$10^r$$$ exclusive.

Every number below $$${10}^r$$$ has $$$r$$$ or less digits. For numbers with less than $$$r$$$ digits, let's pad the beginning with zeroes until it becomes a $$$r$$$ digit number (for example, if $$$r = 5$$$, then $$$69$$$ becomes $$$00069$$$). This allows us to consider numbers with less than $$$r$$$ digits the same way as numbers with exactly $$$r$$$ digits. For each digit, we have $$$\lfloor \frac{9}{k} \rfloor + 1$$$ choices (including zero), and there are $$$r$$$ digits, so the total number of numbers that satisfies the constraint below $$${10}^r$$$ is $$$(\lfloor \frac{9}{k} \rfloor + 1)^r$$$.

To get the count of numbers in range, it suffices to subtract all valid numbers less than $$$10^l$$$. Therefore, the answer is $$$(\lfloor \frac{9}{k} \rfloor + 1)^r - (\lfloor \frac{9}{k} \rfloor + 1)^l$$$. To exponentiate fast, we can use modular exponentiation.

MOD = int(1e9+7)
t = int(input())
for _ in range(t):
    l, r, k = map(int, input().split())
    print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD)

Let's first solve the problem if we can only select and fill rows. Columns can be handled in the exact same way.

For each row $$$r$$$, we need to find the size of the component formed by filling row $$$r$$$ (i.e. the size of the component containing row $$$r$$$ if we set all cells in row $$$r$$$ to be $$$\texttt{#}$$$).

The size of the component containing row $$$r$$$ if we set all cells in row $$$r$$$ to be $$$\texttt{#}$$$ will be the sum of:

1. The number of $$$\texttt{.}$$$ in row $$$r$$$ since these cells will be set to $$$\texttt{#}$$$. Let $$$F_r$$$ denote this value for some row $$$r$$$.
2. The sum of sizes of components containing a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ (i.e. components that are touching row $$$r$$$). This is since these components will be part of the component containing row $$$r$$$. Let $$$R_r$$$ denote this value for some row $$$r$$$.

The challenge is computing the second term quickly. For some component, let $$$s$$$ be the size of the component and let $$$r_{min}$$$ and $$$r_{max}$$$ denote the minimum and maximum row of a cell in the component. This means that the component will contain cells with rows $$$r_{min},r_{min+1},...,r_{max}$$$. Note that we can find these values with a dfs. Since the component will contribute $$$s$$$ to rows in $$$[r_{min}-1,r_{min},\ldots r_{max}+1]$$$, we add $$$s$$$ to $$$R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$$$. This can be done naively or with prefix sums.

We find the maximum $$$F_r+R_r$$$ and then handle columns in the same way. This solution runs in $$$\mathcal{O}(nm)$$$ time.

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

int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 
vector<vector<bool>> vis; vector<vector<char>> A;

void dfs(int i, int j){
    if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
        return;
    
    vis[i][j] = true;

    sz++;
    minR = min(minR, i);
    maxR = max(maxR, i);
    minC = min(minC, j);
    maxC = max(maxC, j);

    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
}

void solve(){
    cin >> n >> m;

    R.assign(n + 5, 0);
    C.assign(m + 5, 0);
    freeR.assign(n + 5, 0);
    freeC.assign(m + 5, 0);
    vis.assign(n + 5, vector<bool>(m + 5, false));
    A.assign(n + 5, vector<char>(m + 5, ' '));

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> A[i][j];

            if (A[i][j] == '.'){
                freeR[i]++;
                freeC[j]++;
            }
        }
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (vis[i][j] or A[i][j] == '.')
                continue;

            // Reset
            sz = 0;
            minR = 1e9;
            maxR = -1e9;
            minC = 1e9;
            maxC = -1e9;

            dfs(i, j);

            // Expand by 1 since adjacent cells also connect
            minR = max(minR - 1, 1);
            maxR = min(maxR + 1, n);
            minC = max(minC - 1, 1);
            maxC = min(maxC + 1, m);
            
            // Update prefix sums
            R[minR] += sz;
            R[maxR + 1] -= sz;

            C[minC] += sz;
            C[maxC + 1] -= sz;
        }
    }

    ans = 0;

    for (int i = 1; i <= n; i++){
        R[i] += R[i - 1];
        ans = max(ans, freeR[i] + R[i]);
    }
    for (int i = 1; i <= m; i++){
        C[i] += C[i - 1];
        ans = max(ans, freeC[i] + C[i]);
    }

    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

For each row $$$r$$$ and column $$$c$$$, we need to find the size of the component formed by filling both row $$$r$$$ and column $$$c$$$ (i.e. the size of the component containing row $$$r$$$ and column $$$c$$$ if we set all cells in both row $$$r$$$ and column $$$c$$$ to be $$$\texttt{#}$$$).

Extending the reasoning in H1, for some row $$$r$$$ and column $$$c$$$, consider the sum of:

1. The number of $$$\texttt{.}$$$ in row $$$r$$$ or column $$$c$$$ since these cells will be set to $$$\texttt{#}$$$. Let $$$F_{r,c}$$$ denote this value for some row $$$r$$$ and column $$$c$$$.
2. The sum of sizes of components containing a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ (i.e. components that are touching row $$$r$$$). This is since these components will be part of the component containing row $$$r$$$ and column $$$c$$$. Let $$$R_r$$$ denote this value for some row $$$r$$$.
3. The sum of sizes of components containing a cell in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$ (i.e. components that are touching column $$$c$$$). This is since these components will be part of the component containing row $$$r$$$ and column $$$c$$$. Let $$$C_c$$$ denote this value for some column $$$c$$$.

However, components that contain a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ as well as in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$ will be overcounted (since it will be counted in both terms $$$2$$$ and $$$3$$$) (you can think of it as components touching both row $$$r$$$ and column $$$c$$$). Thus, we need to subtract the sum of sizes of components that contain a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ as well as in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$. Let $$$B_{r,c}$$$ denote this for some row $$$r$$$ and column $$$c$$$.

Then the size of the component formed by filling both row $$$r$$$ and column $$$c$$$ will be $$$F_{r,c}+R_r+C_c-B_{r,c}$$$ and we want to find the maximum value of this.

Let's try to calculate these values efficiently. Consider some component.

1. Let $$$s$$$ be its size.
2. Let $$$r_{min}$$$ and $$$r_{max}$$$ denote the minimum and maximum row of a cell in the component. This means that the component contains cells with rows $$$r_{min},r_{min+1},...,r_{max}$$$.
3. Let $$$c_{min}$$$ and $$$c_{max}$$$ denote the minimum and maximum column of a cell in the component. This means that the component contains cells with columns $$$c_{min},c_{min+1},...,c_{max}$$$.

All these values can be found with a dfs. We then do the following updates:

1. Add $$$s$$$ to $$$R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$$$. This can be done naively or with prefix sums.
2. Add $$$s$$$ to $$$C_{c_{min}-1},C_{c_{min}},\ldots,C_{c_{max}+1}$$$. This can be done naively or with prefix sums.
3. Add $$$s$$$ to the subrectangle of $$$B$$$ with top left at ($$$r_{min}-1,c_{min}-1$$$) and bottom right at ($$$r_{max}+1,c_{max}+1$$$). This can be done with 2D prefix sums. (Note that doing this naively will pass because of low constant factor and the fact that we could not cut this solution without cutting slow correct solutions.)

We do this for each component. Also, calculating $$$F_{r,c}$$$ can be done by looking at the number of $$$\texttt{.}$$$ in row $$$r$$$, column $$$c$$$, and checking whether we overcounted a $$$\texttt{.}$$$ at ($$$r,c$$$). In all, this solution runs in $$$\mathcal{O}(nm)$$$ time.

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

int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 
vector<vector<int>> RC; vector<vector<bool>> vis; vector<vector<char>> A;

void dfs(int i, int j){
    if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
        return;
    
    vis[i][j] = true;

    sz++;
    minR = min(minR, i);
    maxR = max(maxR, i);
    minC = min(minC, j);
    maxC = max(maxC, j);

    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
}

void solve(){
    cin >> n >> m;

    R.assign(n + 5, 0);
    C.assign(m + 5, 0);
    freeR.assign(n + 5, 0);
    freeC.assign(m + 5, 0);
    RC.assign(n + 5, vector<int>(m + 5, 0));
    vis.assign(n + 5, vector<bool>(m + 5, false));
    A.assign(n + 5, vector<char>(m + 5, ' '));

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> A[i][j];

            if (A[i][j] == '.'){
                freeR[i]++;
                freeC[j]++;
            }
        }
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (vis[i][j] or A[i][j] == '.')
                continue;

            // Reset
            sz = 0;
            minR = 1e9;
            maxR = -1e9;
            minC = 1e9;
            maxC = -1e9;

            dfs(i, j);

            // Expand by 1 since adjacent cells also connect
            minR = max(minR - 1, 1);
            maxR = min(maxR + 1, n);
            minC = max(minC - 1, 1);
            maxC = min(maxC + 1, m);
            
            // Update prefix sums
            R[minR] += sz;
            R[maxR + 1] -= sz;

            C[minC] += sz;
            C[maxC + 1] -= sz;

            RC[minR][minC] += sz;
            RC[maxR + 1][minC] -= sz;
            RC[minR][maxC + 1] -= sz;
            RC[maxR + 1][maxC + 1] += sz;
        }
    }

    for (int i = 1; i <= n; i++)
        R[i] += R[i - 1];

    for (int i = 1; i <= m; i++)
        C[i] += C[i - 1];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            RC[i][j] += RC[i - 1][j] + RC[i][j - 1] - RC[i - 1][j - 1];
    
    ans = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, (R[i] + C[j] - RC[i][j]) + (freeR[i] + freeC[j] - (A[i][j] == '.')));
    
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}