• Great:
• Good:
• Average:
• Bad:
• Trash:

• A:
• B:
• C:
• D:
• E:
• F:

• A:
• B:
• C:
• D:
• E:
• F:

It's always possible to make Kamilka's pleasure at least $$$|x - y|$$$ for any $$$x, y \in a$$$.

First of all, it can be observed that for any two sheep with beauty levels $$$x \lt y$$$, the maximum possible pleasure cannot exceed $$$y - x$$$, since $$$\gcd(x, y) = \gcd(x, y - x)$$$.

Secondly, we can choose $$$x = \min(a)$$$, $$$y = \max(a)$$$, and $$$d = -x \bmod (y - x)$$$, achieving a pleasure of $$$\max(a) - \min(a)$$$.

Thus, the answer is $$$\max(a) - \min(a)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    cout << a[n - 1] - a[0] << endl;
}
 
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tt; cin >> tt;
    while (tt--) {
        solve();
    }
}

t = int(input())
 
for test in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    print(max(a) - min(a))

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Note that you can split strings $$$a$$$ and $$$b$$$ into two "zig-zags": $$$a_0, b_1, a_2, b_3, \dots$$$ and $$$b_0, a_1, b_2, a_3, \dots$$$

What are the necessary and sufficient conditions for each of these zig-zags?

Note that you can split strings $$$a$$$ and $$$b$$$ into two "zig-zags": $$$a_0, b_1, a_2, b_3, \dots$$$ and $$$b_0, a_1, b_2, a_3, \dots$$$.

For each of these zig-zags, you can achieve any sequence of 0s and 1s, provided that their quantities within the zig-zag are preserved. Therefore, the answer is Yes if and only if the number of 0 is at least $$$\lceil \frac{n}{2} \rceil$$$ in the first zig-zag and at least $$$\lfloor \frac{n}{2} \rfloor$$$ in the second one.

#include <iostream>
 
using namespace std;
 
void solve() {
    int n; cin >> n;
    string a, b; cin >> a >> b;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; ++i) {
        if (i & 1) {
            cnt2 += a[i] == '0';
            cnt1 += b[i] == '0';
        } else {
            cnt1 += a[i] == '0';
            cnt2 += b[i] == '0';
        }
    }
    cout << (cnt1 >= (n + 1) / 2 && cnt2 >= n / 2 ? "Yes" : "No") << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
}

t = int(input())
 
for test in range(t):
    n = int(input())
    a = input()
    b = input()
    cnt1, cnt2 = 0, 0
    for i in range(n):
        if i % 2:
            cnt2 += (a[i] == '0')
            cnt1 += (b[i] == '0')
        else:
            cnt1 += (a[i] == '0')
            cnt2 += (b[i] == '0')
 
    if cnt1 >= (n + 1) // 2 and cnt2 >= n // 2:
        print("Yes")
    else:
        print("No")

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

Consider two cases: first, when all numbers have the same parity; and second, when there is at least one even and one odd number.

Let $$$S$$$ be the sum of all numbers, and $$$k$$$ be the number of odd numbers in the array. Then, in the second case, the answer is $$$S - k + 1$$$.

Case 1. All numbers in $$$a$$$ have the same parity. In this case, it is impossible to perform any operation, so the answer is $$$\max(a)$$$.

Case 2. There is at least one even and one odd number. Let $$$S$$$ be the sum of all numbers, and $$$k$$$ be the number of odd numbers in the array. We will now prove that the answer is $$$S - k + 1$$$.

First of all, the answer cannot exceed $$$S - k + 1$$$, since the number of odd elements in the array remains unchanged after performing the operation.

Secondly, we will show that $$$S - k + 1$$$ is always achievable. Consider an arbitrary odd number $$$A \in a$$$. We can then merge all even numbers into $$$A$$$ $$$\left( \text{i.e.} \ (A, 2k) \to (A + 2k, 0) \right)$$$, resulting in an array consisting of the number $$$A + 2m$$$, $$$k-1$$$ odd numbers, and zeros for the remaining elements (here $$$2m$$$ denotes the sum of all even numbers in the initial array).

After this step, for each remaining odd number, we can sacrifice one unit by transferring it to any zero element in the array and then merge the resulting even number into $$$A$$$. It's easy to see that there will always be at least one zero available in the array before merging each odd number. Eventually, we will obtain an array consisting of one element equal to $$$S - k + 1$$$, $$$k - 1$$$ elements equal to one, and zeros filling the remaining positions.

Therefore, the answer in this case will be $$$S-k+1$$$.

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
void solve() {
    int n; cin >> n;
    vector <int> a(n);
    long long ans = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ans += a[i]; cnt += (a[i] & 1);
    }
    if (!cnt || cnt == n) {
        cout << *max_element(a.begin(), a.end()) << '\n';
    } else {
        cout << ans - cnt + 1 << '\n';
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
}

t = int(input())
 
for test in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    ans, cnt = 0, 0
    for i in a:
        ans += i
        cnt += i % 2
        
    if not cnt or cnt == n:
        print(max(a))
    else:
        print(ans - cnt + 1)

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

It is impossible to balance the string if and only if all its letters are the same.

It is clear that there is no solution if all the letters in $$$s$$$ are the same. Let us now prove that a solution always exists in all other cases.

While the string remains unbalanced, let us assume that $$$\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$$$, where $$$a, b, c \in \lbrace \tt{L}, \tt{I}, \tt{T} \rbrace$$$, and $$$\text{cnt}(l)$$$ denotes the number of occurrences of the letter $$$l$$$ in $$$s$$$. Consider two cases:

1. The string $$$s$$$ contains the substring bc or cb. In this case, we can perform the operation on it to obtain bac or cab.

2. Otherwise, the string $$$s$$$ must contain the substring ca or ac. Without loss of generality, assume that $$$s$$$ contains ca. Then we can perform the following sequence of operations: ca $$$\to$$$ cba $$$\to$$$ cbca $$$\to$$$ cbaca $$$\to$$$ cabaca.

It can be observed that after each operation, the value of $$$2 \cdot \text{cnt}(c) - \text{cnt}(b) - \text{cnt}(a)$$$ decreases by one. Here, $$$a$$$, $$$b$$$, and $$$c$$$ are always chosen such that $$$\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$$$. Therefore, the algorithm is guaranteed to terminate, and it does so when $$$2 \cdot \text{cnt}(c) - \text{cnt}(b) - \text{cnt}(a) = 0$$$, which implies $$$\text{cnt}(a) = \text{cnt}(b) = \text{cnt}(c)$$$.

It remains to prove that the number of operations performed by the proposed algorithm does not exceed $$$2n$$$.

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string base = "LIT";
    int t; cin >> t;
    while (t--) {
        int n; string s;
        cin >> n >> s;
        if (count(s.begin(), s.end(), s[0]) == n) {
            cout << -1 << '\n';
        } else {
            vector <int> ans;
            while (true) {
                vector <pair<int, char>> cnt;
                for (auto i : base) cnt.push_back(make_pair(count(s.begin(), s.end(), i), i));
                sort(cnt.begin(), cnt.end());
                if (cnt[0].first == cnt[1].first && cnt[1].first == cnt[2].first) break;
 
                auto op = [&] (int i) -> void {
                    string z = base; z.erase(find(z.begin(), z.end(), s[i])); z.erase(find(z.begin(), z.end(), s[i + 1]));
                    ans.push_back(i);
                    s = s.substr(0, i + 1) + z[0] + s.substr(i + 1);
                };
 
                bool done = false;
                for (int i = 0; i < s.size() - 1; ++i) {
                    if (s[i] == s[i + 1]) continue;
                    if (s[i] != cnt[0].second && s[i + 1] != cnt[0].second) {
                        op(i); 
                        done = true;
                        break;
                    }
                }
                
                if (done) continue;
                
                for (int i = 0; i < s.size() - 1; ++i) {
                    if (s[i] == s[i + 1]) continue;
                    if (s[i] == cnt[2].second) {
                        op(i); op(i + 1); op(i); op(i + 2); break;
                    } else if (s[i + 1] == cnt[2].second) {
                        op(i); op(i); op(i + 1); op(i + 3); break;
                    }
                }
            }
            
            cout << ans.size() << '\n';
            for (auto i : ans) cout << i + 1 << '\n';
        }
    }
}

We assume that a solution exists (refer to the beginning of the first solution). Now, at each step, let's greedily find the first position where the rarest letter can be inserted and place it there. If no such position exists during a given iteration, we insert the most frequent letter instead. The algorithm terminates when all letters occur the same number of times. We claim that this greedy strategy performs no more than $$$2n$$$ operations.

Assume that initially $$$x = \text{cnt}(a), y = \text{cnt}(b), z = \text{cnt}(c)$$$, where $$$\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$$$. Then $$$x + y + z = n$$$. Here, $$$\text{cnt}(l)$$$ denotes the number of occurrences of the letter $$$l$$$ in $$$s$$$.

Claim 1. If the rarest letter cannot be inserted, there always exists a position where the most frequent letter can be inserted.

Claim 2. If $$$x = y$$$, the solution can always be obtained in exactly $$$(z - x) + (z - y) = 2z - x - y$$$ operations.

Now consider the case when $$$x \lt y$$$. Observe that in two operations, the algorithm increases the count of the rarest letter by one and increases the count of the most frequent letter by at most one. This is true because, after inserting the most frequent letter, we obtain a substring like bc. It is easy to see that a can be inserted into it, and the algorithm, being greedy, will do exactly that.

After some number of iterations, $$$x$$$ becomes equal to $$$y$$$ (note that $$$y$$$ remains unchanged throughout the algorithm). Then, by the reasoning above, the final value of $$$z' = \text{cnt}(c)$$$ satisfies:

Applying Claim 2, we get that the total number of operations does not exceed

#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
using namespace std;
 
vector<char> a = {'L', 'I', 'T'};
 
int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        set<char> se;
        for (auto u : s) se.insert(u);
        if (se.size() == 1) {
            cout << -1 << endl;
            continue;
        }
        vector<int> ans;
        map<char, int> mp;
        for (auto u : s) {
            mp[u]++;
        }
        auto func = [&](int i) {
            for (auto u : a) {
                if (s[i] != u && s[i + 1] != u) return u;
            }
            return '$';
        };
        while (max({mp['L'], mp['I'], mp['T']}) != min({mp['L'], mp['I'], mp['T']})) {
            int mn = min({mp['L'], mp['I'], mp['T']});
            int mx = max({mp['L'], mp['I'], mp['T']});
            int ok = 0;
            for (int i = 0; i < s.size() - 1; i++) {
                char x = func(i);
                if (s[i] != s[i + 1] && mp[x] == mn) {
                    mp[x]++;
                    ok = 1;
                    s.insert(s.begin() + i + 1, x);
                    ans.push_back(i);
                    break;
                }
            }
            if (!ok) {
                for (int i = 0; i < s.size() - 1; i++) {
                    char x = func(i);
                    if (s[i] != s[i + 1] && mp[x] == mx) {
                        mp[x]++;
                        s.insert(s.begin() + i + 1, x);
                        ans.push_back(i);
                        ok = 1;
                        break;
                    }
                }
            }
        }
        cout << ans.size() << endl;
        for (auto u : ans) {
            cout << u + 1 << endl;
        }
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

If a cell has an even number of neighbours, does its color matter?

Let $$$S$$$ be the set of cells that have an odd number of neighbouring cells. It is easy to observe that $$$S$$$ consists of border cells, excluding the corner ones. More precisely,

Idea 1. I claim that the number of adjacent border cell pairs with different colors is even. Indeed, if we walk along the border—which essentially forms a cycle—starting and ending at $$$(1, 1)$$$, we must change color an even number of times.

Idea 2. It can be observed that the parity of $$$|A|$$$ does not change when flipping the color of any cell not in $$$S$$$, since such a cell has an even number of neighbouring cells. Therefore, if we fix the coloring of the border cells, the parity of $$$|A|$$$ remains unchanged if we imagine recoloring all non-border cells white. This implies that the parity of $$$|A|$$$ depends solely on the parity of the number of black (or white) cells in $$$S$$$. Moreover, it can be seen that these parities are actually equal.

Idea 3. Now, we are left with counting the number of colorings such that $$$|S|$$$ contains an even number of black cells. Let's consider two cases:

1. All cells in $$$S$$$ are initially colored. In this case, the answer is $$$2^{n \cdot m - k}$$$ if the number of black cells in $$$S$$$ is even, and $$$0$$$ otherwise, since the colors of the remaining cells do not affect the parity.

2. At least one cell in $$$S$$$ is uncolored. In this case, the answer is $$$2^{n \cdot m - k - 1}$$$. This follows from the basic identity of the binomial coefficients:

#include <iostream>
#include <vector>
 
using namespace std;
 
using ll = long long;
const ll mod = 1000000007;
 
ll binpow (ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) {
            res *= a; res %= mod;
        }
        a *= a; a %= mod; n >>= 1;
    }
    return res;
}
 
void solve() {
    ll n, m, k; cin >> n >> m >> k;
    int good = 0, sum = 0;
    for (int i = 0; i < k; ++i) {
        int x, y, c; cin >> x >> y >> c;
        if ((x == 1 && y == 1) || (x == 1 && y == m) || (x == n && y == 1) || (x == n && y == m)) continue;
        if (x == 1 || y == 1 || x == n || y == m) {
            ++good; sum += c;
        }
    }
    if (good == 2 * (n + m - 4)) {
        cout << (sum % 2 ? 0 : binpow(2, n * m - k)) << '\n';
    } else {
        cout << binpow(2, n * m - k - 1) << '\n';
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve:

It is sufficient to consider only two types of blocks of consecutive 0s and 1s: those of size $$$1$$$ and those of size greater than $$$1$$$.

For a fixed beauty value $$$m$$$ of a substring, there are $$$O\left(\frac{sz}{m}\right)$$$ possible values of $$$k$$$, where $$$sz$$$ is the number of blocks of consecutive 0s and 1s.

For a fixed pair $$$(m, k)$$$, let $$$S$$$ be the set of indices $$$i$$$ such that it is possible to divide the prefix $$$[1, i]$$$ of the string into $$$k$$$ substrings of beauty $$$m$$$. It is claimed that $$$S$$$ forms a continuous segment $$$[l, r]$$$ for some $$$1 \le l \le r \le sz$$$.

First, note that it is sufficient to consider only two types of blocks of consecutive 0s and 1s: those of size $$$1$$$ and those of size greater than $$$1$$$. Based on this, we construct a new string of length $$$sz$$$, consisting of characters 1 and 2, representing the types of blocks. For example, for the original string 00101110, the new string is 21121.

Let’s fix a value of $$$m$$$—the desired beauty of the substrings we are dividing the string into. It is easy to see that there are $$$O\left(\frac{sz}{m}\right)$$$ possible values of $$$k$$$ (the number of substrings).

Now, for a fixed pair $$$(m, k)$$$, let $$$S_k$$$ be the set of indices $$$i$$$ such that it is possible to divide the prefix $$$[1, i]$$$ of the new string (representing block types) into $$$k$$$ substrings of beauty $$$m$$$. It is claimed that $$$S_k$$$ forms a continuous segment $$$[l, r]$$$ for some $$$1 \le l \le r \le sz$$$. Let’s prove this by induction.

Base case ($$$k = 1$$$). We set $$$l = m$$$, $$$r = m$$$ (0-based indexing).

Inductive step ($$$k \rightarrow k + 1$$$). Suppose that for every index $$$i \in [l, r]$$$, the first $$$i$$$ blocks can be divided into $$$k$$$ substrings of beauty $$$m$$$. Then we can construct a valid division into $$$k+1$$$ substrings by:

• Simply appending a new substring of length $$$m+1$$$ starting at block $$$i+1$$$, giving us a new upper bound at $$$i + m + 1$$$.

• Additionally, if block $$$i$$$ is of type $$$2$$$, we can split it between the $$$k$$$-th and $$$(k+1)$$$-th substrings, allowing us to finish the $$$k$$$-th substring earlier and start the $$$(k+1)$$$-th within the same block. This enables us to reach $$$i + m$$$ as well.

Thus, we conclude:

• $$$S_{k+1} = [l + m, r + m + 1]$$$ if the $$$l$$$-th block is of type 2.

• Otherwise, $$$S_{k+1} = [l + m + 1, r + m + 1]$$$.

To compute the full solution, we iterate over all values of $$$m$$$ from $$$1$$$ to $$$sz - 1$$$. For each $$$m$$$, we iterate over $$$k$$$ until the left bound $$$l$$$ of the corresponding segment exceeds $$$sz$$$. The special case $$$m=0$$$ should be handled separately.

For each $$$k$$$, we need to increment the answer for all positions from $$$l$$$ to $$$r$$$ by one. This can be efficiently done by recording the operations $$$(l, +1)$$$ and $$$(r + 1, -1)$$$ and then applying a scanline technique to process the accumulated changes.

Since there are $$$O\left(\frac{sz}{m}\right)$$$ possible values of $$$k$$$ for each $$$m$$$, the total complexity of this solution is $$$O(n \log n)$$$.

#include <iostream>
#include <vector>
 
using namespace std;
 
using ll = long long;
 
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector <int> a;
    int curr = 0;
    for (int i = 0; i < n; ++i) {
        if (i && s[i] != s[i - 1]) {
            if (curr) a.push_back(curr);
            curr = 1;
        }
        else ++curr;
    }
    a.push_back(curr);
    int sz = a.size();
 
    vector <int> ans(n, 0), left(sz, 0), right(sz, 0);
    for (int i = 0; i < sz; ++i) {
        if (!i) {
            left[i] = 0; right[i] = a[i] - 1;
        } else {
            left[i] = right[i - 1] + 1;
            right[i] = left[i] + a[i] - 1;
        }
    }
    for (int i = 0; i < sz; ++i) {
        for (int j = left[i]; j <= right[i]; ++j) {
            ans[j] += j - i + 1;
        }
    }
    vector <int> add(sz, 0);
    for (int m = 1; m < sz; ++m) {
        ll l = m, r = m, k = 1;
        while (l < sz) {
            ++add[l];
            if (r + 1 < sz) --add[r + 1];
 
            if (a[l] == 1) {
                l += m + 1;
            } else {
                l += m;
            }
 
            r += m + 1;
            ++k;
        }
    }
    int pref = 0;
    for (int i = 0; i < sz; ++i) {
        pref += add[i];
        for (int j = left[i]; j <= right[i]; ++j) {
            ans[j] += pref;
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i];
        if (i != n - 1) cout << ' ';
    }
    cout << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Didn't solve: