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