#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            ans = max(ans, a[i]);
        }
    }
    
    cout << ans << nl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    ll sum_a = 0, cnt_1 = 0;
    for (int x: a) {
        sum_a += x;
        if (x == 1) cnt_1++;
    }
    
    if (sum_a >= cnt_1 + n && n > 1) {
        cout << "YES" << nl;
    } else {
        cout << "NO" << nl;
    }
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

void solve() {
    ll n, k;
    cin >> n >> k;
    
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    ll lb = 0, ub = *max_element(all(a)) + k, ans = 0;
    while (lb <= ub) {
        ll tm = (lb + ub) / 2;
        bool good = false;
        
        for (int i = 0; i < n; i++) {
            vector<ll> min_needed(n);
            min_needed[i] = tm;
            
            ll c_used = 0;
            for (int j = i; j < n; j++) {
                if (min_needed[j] <= a[j]) continue;
                
                if (j + 1 >= n) {
                    c_used = k + 1;
                    break;
                }
                
                c_used += min_needed[j] - a[j];
                min_needed[j + 1] = max(min_needed[j + 1], min_needed[j] - 1);
            }
            
            if (c_used <= k) good = true;
        }
        
        if (good) {
            ans = tm;
            lb = tm + 1;
        } else {
            ub = tm - 1;
        }
    }
    
    cout << ans << nl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int T;
	cin >> T;
	while (T--) solve();
}

• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

int query(int l, int r) {
    if (l == r) return 0;
    cout << "? " << l << ' ' << r << endl;
    
    int res;
    cin >> res;
    return res;
}

// Finds max on p[l; r]
int solve(int l, int r) {
    if (l == r) return l;
    
    int m = (l + r) / 2;
    int a = solve(l, m);
    int b = solve(m + 1, r);
    
    int r1, r2;
    r1 = query(a, b - 1);
    r2 = query(a, b);
    
    if (r1 == r2) {
        return b;
    } else {
        return a;
    }
}

void solve() {
    int n;
    cin >> n;
    
    int ans = solve(1, n);
    cout << "! " << ans << endl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

const int maxn = 1000000;

vector<int> g[maxn];
int s[maxn];
ll ans = 0;

void dfs(int v, int p = -1) {
    vector<ll> a;
    s[v] = 1;
    
    for (int u: g[v]) {
        if (u == p) continue;
        dfs(u, v);
        s[v] += s[u];
        
        a.push_back(s[u]);
    }
    
    vector<ll> dp(s[v]);
    ll cs = 0;
    for (int x: a) {
        for (ll i = cs + x; i >= 0; i--) {
            for (ll pr = min(cs, i); pr >= max(0LL, i - x); pr--) {
                ll j = i - pr;
                dp[i] = max(dp[i], dp[pr] + j * (cs - pr) + pr * (x - j));
            }
        } 
        cs += x;
    }
    
    ans += *max_element(all(dp));
    dp.clear();
    a.clear();
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        g[x - 1].push_back(i);
    }
    
    dfs(0);
    
    cout << ans << nl;
}

• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

const char nl = '\n';
typedef long long ll;
typedef long double ld;

using namespace std;

const int maxn = 1000000;

vector<int> g[maxn];
int s[maxn];
ll ans = 0;
vector<ll> b;
ll closest;

template <int len = 1>
void subset_sum(int n) {
    if (n >= len) {
        subset_sum<std::min(len*2, maxn)>(n);
        return;
    }
    
    bitset<len> dp;
    
    dp[0] = 1;
    for (ll x: b) {
        dp = dp | (dp << x);
    }
    
    ll cv = n;
    closest = 0;
    for (int i = 0; i <= n; i++) {
        if (dp[i] && abs(i - (n - i)) < cv) {
            closest = i;
            cv = abs(i - (n - i));
        }
    }
}

ll solve(vector<ll> &a) {
    if (a.empty()) return 0;
    
    sort(allr(a));
    ll cs = 0;
    for (ll x: a) cs += x;
    
    if (a[0] * 2 >= cs) {
        return a[0];
    }
    
    int n = gsize(a);
    a.push_back(0);
    
    b.clear();
    int pi = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[i - 1]) {
            ll cnt = i - pi;
            ll x = a[i - 1];
            
            ll j = 1;
            while (j < cnt) {
                b.push_back(x * j);
                cnt -= j;
                j *= 2;
            }            
            b.push_back(x * cnt);

            pi = i;
        }
    }
    
    subset_sum(cs);
    return closest;
}

void dfs(int v, int p = -1) {
    vector<ll> a;
    s[v] = 1;
    
    for (int u: g[v]) {
        if (u == p) continue;
        dfs(u, v);
        s[v] += s[u];
        
        a.push_back(s[u]);
    }
    
    ll x = solve(a);
    ans += x * (s[v] - 1 - x);
    a.clear();
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        g[x - 1].push_back(i);
    }
    
    dfs(0);
    
    cout << ans << nl;
}

• Good problem
• Average problem
• Bad problem