• Excellent contest
• Good contest
• Average contest
• Bad contest
• Horrible contest

• Easy contest
• Normal contest
• Hard contest

Without short steps, we can only visit coordinates where $$$x$$$ and $$$y$$$ are both even.

Using only long steps, we can only visit coordinates where $$$x \equiv 0 \pmod 2$$$ and $$$y \equiv 0 \pmod 2$$$. The extra short step allows us to change either $$$x$$$ or $$$y$$$ to become odd (i.e. $$$x \equiv 1 \pmod 2$$$ or $$$y \equiv 1 \pmod 2$$$), but not both.

Thus, we can say that all coordinates are reachable except for ones where both $$$x$$$ and $$$y$$$ are odd, since that would require more than one short step.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int x, y;
        cin >> x >> y;
        cout << (x % 2 == 0 || y % 2 == 0 ? "YES" : "NO") << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

It can never be harmful to choose the entire string as the substring.

As mentioned in the hint, choosing the entire string to be the substring, that we perform the operation on, is always optimal. Let's assume a smaller substring yields a valid RBS, we can just choose the entire string, and only move around the characters which are in the smaller substring. Thus, choosing the entire string is always optimal.

Now, the problem reduces to checking if we can rearrange a bracket sequence to become an RBS. We want each '$$$\texttt{(}$$$' to pair with a '$$$\texttt{)}$$$', leaving no unpaired brackets. This is equivalent to checking whether the number of occurrences of '$$$\texttt{(}$$$' is equal to the number of occurrences of '$$$\texttt{)}$$$' in the string.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
 
        int cnt = 0;
        for(int i = 0; i < n; i++) cnt += s[i] == '(';
 
        cout << (2 * cnt == n ? "YES" : "NO") << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

A subarray should have both $$$2$$$ and $$$3$$$ as prime factors of the product to be divisible by $$$6$$$. Each element can either contribute $$$2$$$, or $$$3$$$, or both.

From the previous hint, we can split the elements into $$$4$$$ groups.

A subarray has product divisible by $$$6$$$ if it contains both $$$2$$$ and $$$3$$$ as prime factors. Therefore, every element falls into one of $$$4$$$ groups:

• $$$S_6$$$: Elements divisible by $$$6$$$
• $$$S_2$$$: Elements divisible by $$$2$$$ but not $$$3$$$
• $$$S_3$$$: Elements divisible by $$$3$$$ but not $$$2$$$
• $$$S_1$$$: Elements neither divisible by $$$2$$$ nor $$$3$$$

Elements in $$$S_6$$$ already make any subarray divisible by $$$6$$$, so we want them packed together at an end to minimize the number of subarrays they are included in. For the next 2 paragraphs, let's forget about $$$S_6$$$.

For the remaining elements, if we place all $$$S_2$$$ before all $$$S_3$$$, then the only divisible subarrays are the ones that start in $$$S_2$$$ and end in $$$S_3$$$. Any other order would only create more such subarrays.

What do we do with elements of $$$S_1$$$? Inserting them anywhere can never decrease the number of divisible subarrays, but we can avoid increasing by placing them between $$$S_2$$$ and $$$S_3$$$. Subarrays divisible by $$$6$$$ would still be ones that start in $$$S_2$$$ and end in $$$S_3$$$, so the number of divisible subarrays is still as minimal as possible.

Therefore, an optimal construction is:

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a, b, c, d;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if(x % 6 == 0) a.push_back(x);
            else if(x % 2 == 0) b.push_back(x);
            else if(x % 3 == 0) c.push_back(x);
            else d.push_back(x);
        }

        vector<int> ans;
        for(auto it : a) ans.push_back(it);
        for(auto it : b) ans.push_back(it);
        for(auto it : d) ans.push_back(it);
        for(auto it : c) ans.push_back(it);
        
        for(int i = 0; i < n; i++) cout << ans[i] <<  " \n"[i == n - 1];
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

The minimum answer is $$$1$$$, because a $$$0$$$ always exists, and we can take a $$$0$$$ individually as a palindromic subarray with $$$\operatorname{mex} = 1$$$.

Any valid subarray with a $$$\operatorname{mex} \gt 1$$$ will still contain at least one $$$0$$$. So we know the optimal subarray will always contain a $$$0$$$.

There are several valid approaches to this problem. Here, I will explain the intended approach.

We can claim that the optimal subarray will always contain the element $$$0$$$. This is because, if it did not contain $$$0$$$, then $$$\operatorname{mex} = 0$$$. But $$$\operatorname{mex} = 1$$$ can be achieved by considering a $$$0$$$ element as its own subarray (it is palindromic). So, the optimal subarray must always contain the element $$$0$$$.

This gives us only $$$3$$$ candidate centers to expand the palindrome from. Let $$$x$$$ be the position of the first $$$0$$$ in the array, and $$$y$$$ be the position of the second $$$0$$$:

• $$$x$$$ can be the center of the optimal palindrome.
• $$$y$$$ can be the center of the optimal palindrome.
• $$$x$$$ and $$$y$$$ can be on opposite corresponding sides of the palindrome. For instance, $$$[\dots, 0, \dots, j, k, j, \dots, 0, \dots]$$$ for odd palindromes, $$$[\dots, 0, \dots, j, k, k, j, \dots, 0, \dots]$$$ for even palindromes.

We can try each of these choices, and expand from the candidate center as long as the subarray is still palindromic, while keeping track of $$$\operatorname{mex}$$$. The answer is the maximum $$$\operatorname{mex}$$$ among all $$$3$$$ candidates.

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

int n;
vector<int> v;

int solve(int l, int r) {
    set<int> s;
    for(int i = 0; i <= n; i++) s.insert(i);

    while(l >= 0 && r < 2 * n && v[l] == v[r]) {
        s.erase(v[l]);
        l--, r++;
    }

    return *s.begin();
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        v = vector<int> (2 * n);
        for(auto &it : v) cin >> it;

        int x = -1, y;
        for(int i = 0; i < 2 * n; i++) {
            if(!v[i]) {
                if(~x) y = i;
                else x = i;
            }
        }

        cout << max({solve(x, x), solve(y, y), solve((x + y) / 2, (x + y + 1) / 2)}) << endl;
    }
}

Instead of only expanding from the $$$3$$$ possible candidates, we can brute force over all centers (even and odd palindrome centers) and only expand as long as the subarray will stay palindromic. Can you prove why this fits the time limit?

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Look at one height at a time. A cube stays only if every column to its right is tall enough for that height.

The number of cubes that stay in column $$$i$$$ is exactly the suffix minimum $$$s_i$$$.

Let $$$s_i = \min(a_i, a_{i+1}, \dots, a_n)$$$ be the suffix minimum of the array.

The key observation is that a cube at position $$$(i, h)$$$ stays in the same column after the gravity shift if every column to its right also has a cube on height $$$h$$$. In other words, the row $$$h$$$ is already a suffix of occupied cells. This happens exactly when $$$h = s_i$$$.

So, column $$$i$$$ contributes exactly $$$s_i$$$ cubes that do not move, and therefore it contributes $$$a_i - s_i$$$ cubes that do move. Without any operation, the total number of moving cubes is $$$\sum_{i=1}^{n} (a_i - s_i)$$$. Now we try the operation. If $$$a_i \gt s_i$$$, then this decrease does not change any suffix minimum at all, because there is already a smaller somewhere to the right. Such a choice is useless. The only useful positions are those where $$$a_i = s_i$$$, which are exactly the positions where the suffix minimum array changes (i.e., $$$s_i \neq s_{i+1}$$$).

Since suffix minima are non-decreasing from left to right, equal values form contiguous blocks. If we decrease the rightmost element of such a block, then the suffix minimum on the whole block drops by $$$1$$$. This means the number of cubes that stay in place decreases by the length of that block, while the total number of cubes decreases by only $$$1$$$. Consequently, the number of moving cubes increases by $$$\text{block length} - 1$$$.

Therefore, the best strategy is to pick the longest block of equal values in the suffix minimum array. The final formula for the maximum number of moving cubes is:

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

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<ll> v(n);
        ll sum = 0;
        for(auto &it : v) {
            cin >> it;
            sum += it;
        }

        vector<ll> suf_mn(n);
        suf_mn[n - 1] = v[n - 1];
        sum -= suf_mn[n - 1];
        for(int i = n - 2; i >= 0; i--) {
            suf_mn[i] = min(suf_mn[i + 1], v[i]);
            sum -= suf_mn[i];
        }

        ll mx = -1, cur = 1;
        for(int i = 1; i < n; i++) {
            if(suf_mn[i] == suf_mn[i - 1]) cur++;
            else {
                mx = max(mx, cur);
                cur = 1;
            }
        }

        mx = max(mx, cur);
        cout << sum + mx - 1 << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

Cubes on the same height never interact with other heights.

For a fixed height $$$h$$$, the cubes end up in the rightmost $$$\texttt{cnt}[h]$$$ columns, where $$$\texttt{cnt}[h]$$$ is the number of cubes at height $$$h$$$.

After decreasing one column by $$$1$$$, only one height level changes, so the gain value is easy to calculate locally.

Fix some height $$$h$$$. A cube at height $$$h$$$ exists in column $$$i$$$ exactly when $$$a_i \ge h$$$. When gravity shifts to the right, all cubes on the same height behave independently from the other heights, they just slide as far right as possible without overlapping. Therefore, on height $$$h$$$, all cubes occupy the rightmost $$$\texttt{cnt}[h]$$$ columns, where $$$\texttt{cnt}[h]$$$ is the number of columns with $$$a_i \ge h$$$. So the whole problem can be reduced to counting, for each height, how many cubes start there and where they end up.

Let

Then the sum of final column indices of the cubes on height $$$h$$$ is simply the sum of an arithmetic progression:

The sum of initial column indices of the cubes on height $$$h$$$ is the sum of all indices $$$i$$$ such that $$$a_i \ge h$$$. If we sum this over all heights, we get the total movement distance of all cubes. An easy way to compute the initial sum is column-wise instead of height-wise. A cube in column $$$i$$$ contributes $$$i$$$ to the initial column-sum for every height from $$$1$$$ to $$$a_i$$$. So the total initial sum is $$$\sum_{i=1}^n i \cdot a_i$$$. For the final sum, we use the $$$\texttt{cnt}[h]$$$ values above. So if no operation is performed, the answer is $$$\text{final} - \text{initial}$$$.

Now consider the allowed operation. Suppose $$$a_i = x$$$, then the initial sum decreases by exactly $$$i$$$, because one cube from column $$$i$$$ disappears. What happens to the final sum? Only height $$$x$$$ changes, because the column still contributes to all heights $$$1, 2, \dots, x-1$$$, but no longer contributes to height $$$x$$$. So $$$\texttt{cnt}[x]$$$ decreases by $$$1$$$, and all other heights stay unchanged.

For height $$$x$$$, the final sum of occupied columns changes from the rightmost $$$\texttt{cnt}[x]$$$ columns to the rightmost $$$\texttt{cnt}[x]-1$$$ columns. The difference is exactly $$$n - \texttt{cnt}[x] + 1$$$. So the total gain from decreasing $$$a_i$$$ is:

That means we should compute this value for every index $$$i$$$ and take the maximum.

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

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> v(n + 1), cnt(n + 1);
        for(int i = 1; i <= n; i++) {
            cin >> v[i];
            cnt[v[i]]++;
        }

        vector<int> have(n + 1);
        have[n] = cnt[n];
        for(int i = n - 1; i >= 1; i--) have[i] = have[i + 1] + cnt[i];

        int init = 0, aft = 0;
        for(int i = 1; i <= n; i++) {
            init += i * v[i];
            aft += have[i] * (2 * n - have[i] + 1) / 2;
        }

        int cur = aft - init, mx = 0;
        for(int i = 1; i <= n; i++) mx = max(mx, i - n + have[v[i]] - 1);

        cout << cur + mx << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

The length of the array decreases by $$$2$$$ after each operation, so only odd-length subarrays are possibly good.

Think about alternating sum. What can you notice about it after applying some operations?

Alternating sum is invariant. A good subarray must be a positive single element at the end, so the alternating sum must be positive. Is this a sufficient condition?

Let's define:

which is the alternating sum of an array $$$c$$$.

First, every operation keeps the parity of the length unchanged, because the length only decreases by $$$2$$$. Therefore, if an array can be reduced to length $$$1$$$, then its length must be odd.

Now, let's look at the operation. Suppose we choose an index $$$i$$$ and perform the replacement:

In the alternating sum $$$S(c)$$$, the signs of these three positions are either $$$(+, -, +)$$$ or $$$(-, +, -)$$$, depending on the parity of $$$i-1$$$. Their contribution to the total sum is:

This is exactly the contribution of the new element $$$x$$$ at that position. Therefore, the alternating sum is invariant under the operation.

Since the final array has length $$$1$$$, its alternating sum is just that single remaining number, which is positive. Therefore, every good array must have positive alternating sum. So far we have proved a necessary condition: a good array must have odd length and positive alternating sum.

It turns out, the condition is actually sufficient.

Now the problem is reduced to counting subarrays with odd-length and positive alternating sum. Let:

For a subarray $$$[l, r]$$$, if $$$r − l + 1$$$ is odd, then $$$l$$$ and $$$r$$$ have the same parity, and the subarray is good exactly when the corresponding prefix values satisfy:

• If $$$l$$$ is odd, the subarray sum is $$$\texttt{pref}[r] - \texttt{pref}[l-1]$$$. We need $$$\texttt{pref}[r] \gt \texttt{pref}[l-1]$$$.
• If $$$l$$$ is even, the subarray sum is $$$\texttt{pref}[l-1] - \texttt{pref}[r]$$$. We need $$$\texttt{pref}[r] \lt \texttt{pref}[l-1]$$$.

So while scanning $$$r$$$ from left to right, we only need to count previous prefix indices of the opposite type with a smaller or larger prefix value. This is a standard task, which can be done using Fenwick Tree and coordinate compression, or using an ordered set with order statistics.

// written by omsincoconut

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<pair<ll, int>, null_type,less<pair<ll, int>>, rb_tree_tag,tree_order_statistics_node_update>

const bool HAVE_CASE = true;

void test_case_run() {
    ll n;
    cin >> n;

    ll a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    ll qc[n+1];
    qc[0] = 0;
    ordered_set oset[2];
    oset[0].insert({0LL, 0});

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        qc[i] = a[i] - qc[i-1];

        ans += oset[(i+1)%2].order_of_key({qc[i], -1});
        oset[i%2].insert({-qc[i], i});
    }

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

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

    int t = 1;
    if (HAVE_CASE) cin >> t;
    while (t--) test_case_run();
 
    return 0;
}

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

struct FenwickTree {
    int n;
    vector<int> bit;
    FenwickTree(int n) : n(n + 1), bit(n + 1) {}
    int query(int r) {
        int ret = 0;
        while(r > 0) {
            ret += bit[r];
            r -= (r & -r);    
        }

        return ret;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    void update(int idx, int delta) {
        while(idx < n) {
            bit[idx] += delta;
            idx += (idx & -idx);
        }
    }
};

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> v(n);
        for(auto &it : v) cin >> it;

        vector<int> pre(n + 1);
        for(int i = 1; i <= n; i++) {
            if(i & 1) pre[i] = pre[i - 1] + v[i - 1];
            else pre[i] = pre[i - 1] - v[i - 1];
        }

        vector<int> h = pre;
        sort(h.begin(), h.end());
        h.erase(unique(h.begin(), h.end()), h.end());
        auto get = [&](int x) { return lower_bound(h.begin(), h.end(), x) - h.begin() + 1; };

        FenwickTree fen_ev(h.size()), fen_od(h.size());
        int ans = 0;

        fen_ev.update(get(0), 1);

        for(int i = 1; i <= n; i++) {
            int x = get(pre[i]);
            if(i & 1) {
                ans += fen_ev.query(x - 1);
                fen_od.update(x, 1);
            }
            else {
                ans += fen_od.query(x + 1, h.size());
                fen_ev.update(x, 1);
            }
        }

        cout << ans << endl;
    }
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem

For a fixed edge, when does it contribute $$$1$$$ to the answer?

Root the tree anywhere. Let $$$\texttt{cnt}[u]$$$ be the number of leaves in the subtree of $$$u$$$, and $$$u \neq \texttt{root}$$$. The edge $$$\texttt{parent}_u \to u$$$ is used if $$$\texttt{cnt}[u]$$$ is odd.

There can be an unchosen leaf. How to choose which leaf to ignore?

Let's pick any vertex as the root. For every edge connecting a parent to a child $$$u$$$, let $$$\texttt{cnt}[u]$$$ be the total number of leaves in the subtree rooted at $$$u$$$.

Consider this edge alone:

• If $$$\texttt{cnt}[u]$$$ is even, all leaves inside this subtree can be paired with each other internally. This edge does not need to be crossed by any path.
• If $$$\texttt{cnt}[u]$$$ is odd, after pairing as many leaves as possible within the subtree, exactly one leaf will be left over. This leaf must cross the edge to find a pair outside the subtree. Therefore, this edge must be used exactly once.

If the total leaf count is even, every leaf must be paired. An edge is used if and only if its child's subtree contains an odd number of leaves. Hence:

But what if the total leaf count was odd? Exactly one leaf will remain unchosen. Leaving a leaf $$$x$$$ unchosen allows us to save or lose the cost of some edges. Specifically, for every edge on the path from the root to $$$x$$$, the parity of the number of leaves in the corresponding child subtree changes:

• If the subtree had an odd number of leaves, it becomes even, so that edge is no longer needed;
• If the subtree had an even number of leaves, it becomes odd, so that edge becomes needed.

Therefore, if the total number of leaves is odd, we want to choose a leaf $$$x$$$ such that the value

is maximized.

Let's define $$$\texttt{mx}[u]$$$ as:

Thus, the answer for the odd leaves case is:

We can compute $$$\texttt{cnt}[u]$$$ for every vertex using a DFS. Then, in the same DFS or in a separate one, we compute $$$\texttt{mx}[u]$$$. The transition is:

and for a leaf, $$$\texttt{mx}[u] = 0$$$.

Therefore,

• If $$$\texttt{cnt}[\texttt{root}]$$$ is even, the answer is just the number of edges whose child subtree has odd $$$\texttt{cnt}[u]$$$;
• If $$$\texttt{cnt}[\texttt{root}]$$$ is odd, subtract $$$\texttt{mx}[\texttt{root}]$$$ from that answer.

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

const int N = 2e5 + 10;

int n;
vector<int> adj[N];
int mx[N], cnt[N];

void dfs(int u, int par) {
    cnt[u] = (adj[u].size() == 1);

    for(int v : adj[u]) {
        if(v == par) continue;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
    
    int cur = 0;
    for(int v : adj[u]) {
        if(v == par) continue;
        int w = (cnt[v] & 1) ? 1 : -1;
        cur = max(cur, mx[v] + w);
    }

    mx[u] = cur;
}

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

    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) adj[i].clear();

        for(int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        dfs(1, 0);

        int ans = 0;
        for(int u = 2; u <= n; u++) {
            if(cnt[u] & 1) ans++;
        }

        if(!(cnt[1] & 1)) cout << ans << endl;
        else cout << ans - mx[1] << endl;
    }

    return 0;
}

• Excellent problem
• Good problem
• Average problem
• Bad problem
• Horrible problem