• Horrible contest
• Bad contest
• Average contest
• Good contest
• Peak contest

• Extreme contest
• Hard contest
• Normal contest
• Easy contest
• Trivial contest

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    
    int mx = 0, ans = 0;
    for (int i : a) mx = max(i, mx);
    for (int i : a) ans += i == mx;
    cout << ans << '\n';
}

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

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

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

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

    if (is_sorted(a.begin(), a.end())) cout << n << '\n';
    else cout << "1\n";
}

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

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

What if you delete characters instead of replacing them with $$$*$$$?

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

void solve() {
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; 2*i < n; i++) {
        for (int j = 1; j < size(s); j++) {
            if (s[j] == s[j-1]) {
                s.erase(j-1, 2);
            }
        }
    }
    cout << (s.empty() ? "YES\n" : "NO\n");
}

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

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

void solve() {
    int n;
    string s;
    cin >> n >> s;
    stack<int> st;
    for (char c : s) {
        if (st.size() && c == st.top()) st.pop();
        else st.push(c);
    }
    cout << (st.empty() ? "YES\n" : "NO\n");
}

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

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

What invariants does $$$p$$$ have?

Consider the elements in between the portals and the elements outside of them.

What invariant does each of these two regions have?

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

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    x--, y--;
    vector<int> a, b;
    for (int i = 0; i < n; i++) {
        int j;
        cin >> j;
        if (i <= x || i > y) a.push_back(j);
        else b.push_back(j);
    }

    // solve
    if (!b.empty()) rotate(b.begin(), min_element(b.begin(), b.end()), b.end());
    int m = b.empty() ? -1 : b[0];
    auto it = a.begin();
    while (it != a.end() && *it < m) it++;
    a.insert(it, b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n-1];
    }
}

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

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

What elements can the operation not be used on?

What first moves ensure that Alice will win?

If Alice can win, then she can ensure victory on her first move.

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

#define all(x) begin(x), end(x)

int primebase(int x) {
    set<int> s;
    for (int i = 2; i*i <= x; i++) {
        while (x % i == 0) {
            s.insert(i);
            x /= i;
        }
    }
    if (x > 1) s.insert(x);
    if (s.size() > 1) return -1;
    if (s.size() == 0) return 1;
    return *s.begin();
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    
    // solve
    vector<int> b(n);
    for (int i = 0; i < n; i++) b[i] = primebase(a[i]);
    if (is_sorted(all(a))) {
        cout << "Bob\n";
    } else if (*min_element(all(b)) == -1) {
        cout << "Alice\n";
    } else if (is_sorted(all(b))) {
        cout << "Bob\n";
    } else {
        cout << "Alice\n";
    }
}

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

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

Try to solve the problem without shop particles.

If Bessie has to use a shop particle, which of her own particles should she replace with it?

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

template<class T> bool smin(T &a, const T b) { return b < a ? a = b, 1 : 0;}
template<class T> bool smax(T &a, const T b) { return a < b ? a = b, 1 : 0;}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<array<int, 2>> a(n);
    for (auto &i : a) cin >> i[1] >> i[0];

    // solve
    sort(a.rbegin(), a.rend());
    int ptr = 0;
    multiset<int> s;
    ll mx = 0, cur = 0;
    vector<ll> pref(n+1);
    for (int k = n; k >= 0; k--) {
        while (ptr < n && a[ptr][0] >= k) {
            cur += a[ptr][1];
            s.insert(a[ptr][1]);
            ptr++;
        }
        while (s.size() > k + 1) {
            cur -= *s.begin();
            s.erase(s.begin());
        }
        smax(mx, cur);
        pref[k] = (s.size() <= k) ? cur : cur - *s.begin();
    }
    for (int k = 1; k <= n; k++) smax(pref[k], pref[k-1]);

    // queries
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << max(mx, pref[y] + x) << '\n';
    }
}

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

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

Convert each - operation to + and / operation to x.

Fix the permutation. For each +y operation, by how much would the answer change if it was removed?

How can you calculate the expected value of the product x operations that come after +y over all permutations?

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

const int mod = 1e9+7;

ll mpow(ll a, ll b) {
    ll r = 1;
    while (b) {
        if (b & 1) {
            r *= a;
            r %= mod;
        }
        b >>= 1;
        a *= a;
        a %= mod;
    }
    return r;
}

ll inv(ll a) {
    return mpow(a, mod-2);
}

const int maxn = 5000;
ll facts[maxn+1] = {1};

void precomp() {
    for (int i = 1; i <= maxn; i++) {
        facts[i] = facts[i-1] * i % mod;
    }
}

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

    vector<ll> mults;
    ll adds = 0;
    for (int i = 0; i < n; i++) {
        char c;
        ll v;
        cin >> c >> v;
        if (c == '-') adds += mod - v;
        else if (c == '+') adds += v;
        else if (c == '/') mults.push_back(inv(v));
        else mults.push_back(v);
    }
    adds %= mod;

    // solve
    int m = mults.size();
    vector<ll> dp(m+1);
    dp[0] = 1;
    for (auto &b : mults) {
        x *= b;
        x %= mod;
        for (int i = m; i >= 1; i--) {
            dp[i] += dp[i-1] * b;
            dp[i] %= mod;
        }
    }

    ll S = 0;
    for (int i = 0; i <= m; i++) {
        S += dp[i] * facts[i] % mod * facts[m-i] % mod * inv(facts[m]) % mod;
        S %= mod;
    }
    S *= inv(m+1);
    S %= mod;

    // answer
    ll ans = x + adds * S;
    ans %= mod;
    cout << ans << "\n";
}

signed main() {
    precomp();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

Solve for $$$n \leq 2\cdot 10^5$$$.

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Peak problem
• Did not solve

Find a recursive definition for special numbers.

When can $$$x \bmod{42}$$$ tell us if $$$x$$$ is special?

If $$$42\mid x$$$, how can we determine if $$$x$$$ is special?

Iterate on the number of operations $$$\bmod{42}$$$.

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

using ll = long long;
const ll inf = LLONG_MAX / 2;

ll f(const vector<ll>& a) {
    if (a.empty()) return 0;
    if (a.back() == 1) return 5;
    int n = a.size();
    int mod6 = a[0] % 6;
    vector<ll> groups[7];
    for (ll x : a) {
        if (x % 6 != mod6) return inf;
        groups[(x - mod6) / 6 % 7].push_back(x);
    }
    ll ans = inf;
    for (int r = 0; r < 7; r++) {
        ll k = (42 - 6*r - mod6) % 42;
        vector<ll> next;
        for (ll x : groups[r]) next.push_back((x + k) / 42);
        ll rec = f(next);
        if (rec >= inf) continue;
        ans = min(ans, k + 42 * rec);
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    ll res = f(a);
    if (res >= inf) cout << "-1\n";
    else cout << res << '\n';
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

It is only impossible if the number of k is 0 and r is not universal, or if r consists of only one distinct character.

Time complexity: $$$O(n)$$$

For the MEX to be 0, we must remove all 0s from the array and then apply the operation on the whole array. We can remove all zeroes in one operation (with endpoints on the leftmost and rightmost zeroes) unless both the first and last element are 0, in which case it takes two operations. Once all zeros are removed, we can MEX the whole array resulting in 0.

Time complexity: $$$O(n)$$$

It is always possible if x != y. WLOG, assume x>y. Note that a+b=a^b (^ is xor) if and only if the bitwise and of a and b is 0. Let M be the least power of 2 greater than or equal to x. Using k = M-x will set all bits in x+k to zero except one, and since x>y, the bitwise and of x+k and y+k will be 0.

Time complexity: $$$O(1)$$$ (with bitwise operations)

Consider reversing time: we iterate over the dishes backwards, and at each move we can increase r by one or take the current dish and decrease it by k. We must end with r >= 0. We greedily eat a dish every time we can. If we ate a dish earlier but the current dish has a greater value of d[i] than it, we can replace the older dish with the current one to maximize the answer (since we can save the k for the current dish instead of using it earlier). To do this, we maintain a sorted multiset of all dishes we have taken so far. The answer is simply the sum of all elements in the multiset.

Time complexity: $$$O(n\log{n})$$$

Let A be the sum of all elements in a and B be sum of all elements in B. Note that k must divide B-A. We can iterate over all divisors of this value and check each of them. This will run in time since the maximum number of divisors of B-A is less than 3000.

Time complexty: $$$O(3000n\log{n})$$$

Consider the middle index of the final subarray. We can iterate over this index, keeping track of the closest occurrences to the left and right for each index using sets. For each middle index, we iterate over all values 1 to k (except the value of the middle index) and choose the closest index (either to the left or right) to the middle index, or mark it as equal distance to both sides. If the number of values on both sides is equal (or differs by 1), we can update the answer with the number of required moves in this case.

Time complexity: $$$O(n^2)$$$

We optimize the solution for F1 above. Note that a candidate answer depends only on the sum of the distances from each value to the current middle index (because the number of nodes on each side is equal). Additionally, only $$$O(1)$$$ will change from the left side to the right side each time we increment the middle index. Thus, we can maintain the sum of the distances to the middle node. When we increment the the middle index, the distance to all values on the left increases by $$$1$$$, and the distance to all nodes on the right decreases by $$$1$$$. We can store counts of the numbers on the left and right sides of the middle node to update the total distance in $$$O(1)$$$ time.

Time complexity: $$$O(n\log{n})$$$