• 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();
}