#include <bits/stdc++.h>

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

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

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    cout << 1 + (n - 1) * k << 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()

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 pref_max = 0, s = 0, mx = 0;
    for (int i = 0; i < n; i++) {
        pref_max = max(pref_max, (ll) a[i]);
        
        ll d = pref_max - a[i];
        s += d;
        mx = max(mx, d);
    }
    
    cout << s + mx << 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()

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> h(n);
    for (auto &x: h) cin >> x;
    
    int ans = h[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        ans = max(ans + 1, h[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()

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

using namespace std;

const int inf = 1e9;

void solve() {
    vector<int> a;
    {
        int n;
        cin >> n;
        
        map<int, int> cnt;
        while (n--) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        
        for (auto const &[k, v]: cnt) {
            a.push_back(v);
        }
    }
    
    int n = a.size();
    vector<int> dp(n + 1, inf);
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        vector<int> ndp = dp;
        
        for (int k = 1; k <= n; k++) {
            int nv = dp[k - 1] + a[i - 1];
            
            if (nv <= i - k) {
                ndp[k] = min(ndp[k], nv);
            }
        }
        
        dp = ndp;
    }
    
    int ans = n;
    while (dp[ans] >= inf) ans--;
    cout << n - 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()

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

using namespace std;

const ll inf = 1e15;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    
    vector<int> d(n);
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        p--;
        
        g[p].push_back(i);
        d[i] = d[p] + 1;
    }
    
    vector<ll> b(n); // b[v] = sum(a[u]) - a[v]
    for (int v = 0; v < n; v++) {
        if (g[v].empty()) {
            b[v] = inf;
        } else {
            b[v] = -a[v];
        
            for (int u: g[v]) {
                b[v] += a[u];
            }
        }
    }
    
    ll ans = 0;
    for (int v = n - 1; v >= 0; v--) {
        queue<int> q;
        
        q.push(v);
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            
            for (int u: g[i]) {
                ll delta = min(-b[v], b[u]);
                
                if (delta > 0) {
                    b[v] += delta;
                    b[u] -= delta;
                    ans += delta * (d[u] - d[v]);
                }
                
                q.push(u);
            }
        }
    }
    
    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()

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

using namespace std;

const int inf = 1e9;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    
    vector<vector<int>> dp(n + 1, vector<int> (n + 1, inf));
    
    for (int i = 0; i <= n; i++) {
        dp[i][i] = 0;
    }
    
    for (int le = 1; le <= n; le++) {
        for (int l = 0; l + le <= n; l++) {
            if (a[l] % 2 != (l + 1) % 2) continue;
            if (a[l] > l + 1) continue;
            int v = (l + 1 - a[l]) / 2;
            
            int r = l + le;
            for (int m = l + 1; m < r; m += 2) { // index of the closing bracket
                if (dp[l + 1][m] <= v) {
                    int new_val = max(v, dp[m + 1][r] - (m - l + 1) / 2);
                    dp[l][r] = min(dp[l][r], new_val);
                }
            }
        }
    }
    
    vector<int> dp2(n + 1);
    for (int i = 0; i < n; i++) {
        dp2[i + 1] = dp2[i];
        
        for (int j = 0; j < i; j++) {
            if (dp[j][i + 1] <= dp2[j]) {
                dp2[i + 1] = max(dp2[i + 1], dp2[j] + (i - j + 1) / 2);
            }
        }
    }
    
    cout << dp2[n] << nl;
}

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

• Good problem
• Average problem
• Bad problem

• Good problem
• Average problem
• Bad problem

Meow? (Waiting for something to happen?)

Consider that the edges are directed from $$$i \to l_i$$$ or $$$i \to r_i$$$ respectively. So that edges point from vertices with smaller values to vertices with larger values. That is $$$a \to b$$$ implies that $$$p_a < p_b$$$.

Notice that by definition, every vertex must have only $$$1$$$ edge that is going out of it. Therefore, if we consider the diameter to be something like $$$v_1 \to v_2 \to v_3 \to \ldots \to v_k \leftarrow \ldots \leftarrow v_{d-1} \leftarrow v_{d}$$$, since it is impossible for there to be some $$$\leftarrow v_i \to$$$ since each vertex has exactly one edge going out of it.

Therefore, it makes that we can split the path into 2 distinct parts: - $$$v_1 \to v_2 \to v_3 \to \ldots \to v_k$$$ - $$$v_d \to v_{d-1} \to \ldots \to v_{k}$$$

I claim that I can choose some $$$m$$$ such that the path $$$v_1 \to v_2 \to v_3 \to \ldots \to v_{k-1}$$$ and $$$v_d \to v_{d-1} \to \ldots \to v_{k+1}$$$ are in the range $$$[1,m]$$$ and $$$[m+1,n]$$$ or vice versa. That we are able to cut the array into half and each path will stay on their side.

The red line shown above is the cutting line, as described. Proof is at the bottom under Proof 1 for completeness.

Now, we want to use this idea to make a meet in the middle solutions where we merge max stacks from both sides. Specifically: - maintain a max stack of elements as we are sweeping from $$$i=1\ldots n$$$. - for each element on the max stack, maintain the maximum size of a path that is rooted on that element.

Here is an example with $$$p=[4,1,5,3,2,6]$$$

• $$$i=1$$$: $$$s=[(4,1)]$$$
• $$$i=2$$$: $$$s=[(4,2),(1,1)]$$$
• $$$i=3$$$: $$$s=[(5,3)]$$$
• $$$i=4$$$: $$$s=[(5,3),(3,1)]$$$
• $$$i=5$$$: $$$s=[(5,3),(3,2),(2,1)]$$$
• $$$i=6$$$: $$$s=[(6,4)]$$$

When we insert a new element $$$x$$$, we pop all $$$(p_i,val)$$$ with $$$p_i < p_x$$$ and add in $$$(x,\max(val)+1)$$$ into the stack. Now, all elements of the stack has to updated with $$$s_{i,1} := \max(s_{i,1},s_{i+1,1}+1)$$$, which is really updating a suffix of $$$s_{*,1}$$$ with $$$val+k,\ldots,val+1,val$$$.

Firstly, it is clear that the $$$2$$$ vertices we merge, should have the biggest $$$p_i$$$ value, since a bigger $$$p_i$$$ value implies a bigger path size.

What we care about is the biggest path size possible only using vertices on $$$[1,i]$$$, which we denote array $$$best$$$. In the above example, $$$best = [1,2,3,3,4]$$$. We really only care about obtaining the array $$$best$$$ and not $$$s$$$. We can find this array in $$$O(n \log n)$$$ using segment trees or even in $$$O(n)$$$.

However, we cannot directly take the biggest values on each side. Consider $$$p=[2,1\mid,3,4]$$$. On the left and right side, the max stacks are $$$[2,1]$$$ and $$$[4,3]$$$ respectively, but we cannot connect $$$2$$$ with $$$4$$$ since the $$$3$$$ is blocking the $$$2$$$.

Suppose $$$a_1,a_2,\ldots,a_s$$$ are the prefix maximums while $$$b_1,b_2,\ldots,b_t$$$ are the suffix maximums.

Then, if the dividing line is at $$$a_i \leq m < a_{i+1}$$$, we will merge $$$a_i$$$ on the left side with $$$a_{i+1}$$$ on the right side. Similarly, if the dividing line is at $$$b_i \leq m < b_{i+1}$$$, we will merge $$$b_i$$$ on the left side with $$$b_{i+1}$$$ on the right side.

So, if $$$a_i \leq m < a_{i+1}$$$, it is equivalent to merging the best path on $$$[1,m]$$$ and $$$(m,a_{i+1})$$$ since then $$$a_{i+1}$$$ will be the root of the best path on the right side. It is similar for $$$b_i \leq m < b_{i+1}$$$.

Actually, we can prove that instead of $$$(m,a_{i+1})$$$, $$$(m,a_{i})$$$ is enough, and the proof is left as an exercise.

The total complexity becomes $$$O(n \log n)$$$ or $$$O(n)$$$ depending on how quickly array $$$best$$$ is found for subarrays.

Proof 1

Suppose that there are 2 paths $$$a_1 \to a_2 \to \ldots \to a_s$$$ and $$$b_1 \to b_2 \to \ldots \to b_t$$$, $$$a_1 < b_1$$$, and $$$a_s = b_t$$$ but they do not intersect at any vertices other vertices. Then we will prove that there is no such case where $$$a_s' > b_t'$$$.

Suppose that it is true that we can find some $$$a_{s'} > b_{t'}$$$.

Let $$$(s',t')$$$ be the minimum counterexample so that $$$a_{s'} > b_{t'}$$$ but $$$a_{s'-1}<b_{t}$$$. Therefore, we have $$$a_{s'-1} < b_t < a_{s'}$$$. By definition, that $$$r_{a_{s'-1}} = a_{s'}$$$, we have $$$p_{b_t} < p_{a_{s'-1}}$$$.

Then, $$$a_s$$$ cannot be in between $$$a_{s'-1}$$$ and $$$a_{s'}$$$ or else $$$r_{a_{s'-1}} = a_{s} \neq a_{s'}$$$. But, then we need to find a path from $$$b_{t'}$$$ to $$$b_{t}=a_{s}$$$ which does not touch either $$$a_{s'-1}$$$ or $$$a_{s'}$$$ which is impossible.

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

#define ii pair<int,int>
#define fi first
#define se second

#define pub push_back
#define pob pop_back

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define sz(x) (int)(x).size()

int n;
int arr[400005];
string s;

int ans[2][400005];
int t[400005];
vector<int> stk[2];

vector<ii> process(int l,int r,int val[]){
	vector<ii> v;
	int curr=0;
	
	rep(x,l,r+1){
		ii res={x,0};
		while (!v.empty() && arr[v.back().fi]<arr[x]){
			int t=v.back().se; v.pob();
			if (!v.empty()) v.back().se=max(v.back().se,t+1);
			res.se=max(res.se,t+1);
		}
		v.pub(res);
		
		curr=max(curr,res.se+sz(v));
		val[x]=curr;
	}
	
	return v;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,1,n+1) cin>>arr[x];
		cin>>s;
		
		rep(z,0,2){
			auto v=process(1,n,ans[z]);
			stk[z].clear();
			for (auto [a,b]:v) stk[z].pub(a);
			reverse(arr+1,arr+n+1);
		}
		
		int mx=ans[0][stk[0][0]]+ans[1][n-stk[0][0]+1]-1;
		
		rep(z,0,2){
			rep(x,0,sz(stk[z])-1){
				process(stk[z][x],stk[z][x+1],t);
				rep(y,stk[z][x],stk[z][x+1]) mx=max(mx,t[y]+ans[z^1][n-y]);
			}
			
			reverse(arr+1,arr+n+1);
		}
		
		cout<<mx-1<<endl;
	}
}

• Good problem
• Average problem
• Bad problem

#include <bits/stdc++.h>

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

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

using namespace std;

array<vector<int>, 2> get_l_and_r(vector<int> &p) {
    int n = p.size();
    
    vector<int> l(n), r(n);
    
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && p[s.top()] < p[i]) s.pop();
        
        if (s.empty()) l[i] = -1;
        else l[i] = s.top();
        
        s.push(i);
    }
    
    s = {};
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && p[s.top()] < p[i]) s.pop();
        
        if (s.empty()) r[i] = n;
        else r[i] = s.top();
        
        s.push(i);
    }
    
    return {l, r};
}

int ans_l_edge(array<int, 2> d, array<int, 2> e) {
    return d[0] + 1 + max(d[1], e[0]);
}

int ans_r_edge(array<int, 2> d, array<int, 2> e) {
    return e[1] + 1 + max(d[1], e[0]);
}

array<int, 2> add_l_edge(array<int, 2> d, array<int, 2> e) {
    return {max({d[0], d[1] + 1, e[0] + 1}), e[1]};
}

array<int, 2> add_r_edge(array<int, 2> d, array<int, 2> e) {
    return {d[0], max({d[1] + 1, e[0] + 1, e[1]})};
}

vector<array<int, 2>> process_dp(vector<array<int, 2>> &dp) {
    array<int, 2> max_a = {-1, -1}, max_b = {-1, -1}, max_s = {-1, -1};
    
    for (auto [a, b]: dp) {
        if (a > max_a[0] || (a == max_a[0] && b > max_a[1])) {
            max_a = {a, b};
        }
        
        if (b > max_b[1] || (b == max_b[1] && a > max_b[0])) {
            max_b = {a, b};
        }
        
        if (a + b > max_s[0] + max_s[1]) {
            max_s = {a, b};
        }
    }
    
    return {max_a, max_b, max_s};
}

void add_to_map(map<array<int, 2>, int> &dp_ind, int &len_dp, array<int, 2> a) {
    if (!dp_ind.count(a)) {
        dp_ind[a] = len_dp++;
    }
}

void solve() {
    int n;
    cin >> n;
    
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    
    string s;
    cin >> s;
    
    auto [l, r] = get_l_and_r(p);
    
    for (int i = 0; i < n; i++) {
        if (p[i] == n) continue;
        
        if (l[i] == -1 && s[i] == 'L') {
            cout << -1 << nl;
            return;
        }
        
        if (r[i] == n && s[i] == 'R') {
            cout << -1 << nl;
            return;
        }
    }
    
    int ans = 0;
    
    vector<int> q(n + 1);
    for (int i = 0; i < n; i++) {
        q[p[i]] = i;
    }
    
    int len_dp = 0;
    map<array<int, 2>, int> dp_ind;
    
    for (int x = 1; x <= n; x++) {
        int i = q[x];
        int tl = l[i], tr = r[i];
        
        add_to_map(dp_ind, len_dp, {tl, i});
        add_to_map(dp_ind, len_dp, {i, tr});
        add_to_map(dp_ind, len_dp, {tl, tr});
    }
    
    vector<vector<array<int, 2>>> dp(len_dp, {{0, 0}});
    for (int x = 1; x <= n; x++) {
        int i = q[x];
        int tl = l[i], tr = r[i];
        
        int ind_l = dp_ind[{tl, i}];
        int ind_r = dp_ind[{i, tr}];
        int ind_c = dp_ind[{tl, tr}];
        
        for (auto const &d: dp[ind_l]) {
            for (auto const &e: dp[ind_r]) {
                ans = max(ans, d[1] + e[0]);
                
                if (tl >= 0 && s[i] != 'R') {
                    ans = max(ans, ans_l_edge(d, e));
                    dp[ind_c].push_back(add_l_edge(d, e));
                }
                
                if (tr <= n - 1 && s[i] != 'L') {
                    ans = max(ans, ans_r_edge(d, e));
                    dp[ind_c].push_back(add_r_edge(d, e));
                }
            }
        }
        
        dp[ind_c] = process_dp(dp[ind_c]);
    }
    
    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()

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

using namespace std;

int ans_x = 0, ans_y = 0, cnt_q = 0;
// Coordinates are flipped
int query(int x, int y) {
    cnt_q++;

    int res = 0;
    cout << "? " << y << ' ' << x << endl;
    cout.flush();
    
    cin >> res;
    
    if (res < 0) {
        exit(0);
    }
    
    if (res == 0) {
        ans_x = x;
        ans_y = y;
    }
    
    return res;
}

/* Explanation:
 * Splits the stripe of three into |a-O-a-b-O-b-a-O-a|.
 * O are the three query points (all in the same column). 
 * Cons: hard to correctly account for errors in a non-bruteforce way.
 * Pros: gives a better constant factor (3 / 4 of the original length)
 * Number of queries: n + 3 * 21 + 25 * ceil(log(25, 2)) + eps 
 * Though the binary search part uses less queries than that */

void f(int lx, int rx, int ly, int ry) {
    int n = rx - lx + 1;
    
    // Bruteforce base case (uses binary search)
    if (n <= 25) { // can be n <= 22 or above
        for (int x = lx; x <= rx; x++) {
            int lb = ly, ub = ry;
            
            while (lb <= ub) {
                int res = query(x, lb);
                
                int low_y = ((res - 1) + 1) / 2, high_y = res;
                
                int new_lb = lb + max(1, low_y), new_ub = min(ub, lb + high_y);
                lb = new_lb;
                ub = new_ub;
            }
        }
        
        return;
    }
    
    
    // Here, (2a - 1) + (2b - 1) + (2a - 1) = n
    int a = 3 * (n + 3) / 16;
    int y = min(ry, ly + 1);
    
    int x1 = lx + a - 1;
    x1 = max(x1, lx);
    x1 = min(x1, rx);
    
    int x2 = (lx + rx) / 2;
    x2 = max(x2, x1 + 1);
    x2 = min(x2, rx);
    
    int x3 = rx - a + 1;
    x3 = max(x3, x2 + 1);
    x3 = min(x3, rx);


    int m = min(3, ry - ly + 1);
    vector<vector<bool>> good(n, vector<bool> (m, true));
    
    int new_lx = lx, new_rx = rx;
    int new_ly = ly, new_ry = ry;
    
    for (int x: {x1, x2, x3}) {
        int res = query(x, y);
        
        new_lx = max(new_lx, x - res);
        new_rx = min(new_rx, x + res);
        
        new_ly = max(new_ly, y - res);
        new_ry = min(new_ry, y + res);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int r_x = lx + i, r_y = ly + j;
                
                int dx = abs(r_x - x);
                int dy = abs(r_y - y);
                
                int d = dx + dy;
                int S = (dx + 1) * (dy + 1);
                
                // d <= res <= d + S must hold
                if (res < d || d + S < res) {
                    good[i][j] = false;
                }
            }
        }
    }
    
    bool has_good = false;
    for (auto vx: good) {
        for (auto vy: vx) {
            if (vy) {
                has_good = true;
            }
        }
    }
    good.clear();
    good.shrink_to_fit();
    
    if (has_good) {
        f(new_lx, new_rx, new_ly, new_ry);
    } else {
        f(lx, rx, ly + m, ry);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    ans_x = 0; ans_y = 0; cnt_q = 0;
    
    f(1, m, 1, n);
    
    cout << "! " << ans_y << ' ' << ans_x << endl;
    cout.flush();
    
    cerr << n << ' ' << cnt_q << " | " << n + 225 << 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;

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]) break;
                
                if (j + 1 >= n) {
                    c_used = k + 1;
                    break;
                }
                
                c_used += min_needed[j] - a[j];
                min_needed[j + 1] = max(0LL, 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

This is my second contest on Codeforces, inspiring coordination has been done for the last several months, cannot wait until the third round is released!

1768A- Greatest Convex

Is $$$x = k - 1$$$ always suitable?

The answer is yes, as $$$x! + (x - 1)! = (x - 1)! \times (x + 1) = ((k - 1) - 1)! \times ((k - 1) + 1) = (k - 2)! \times (k)$$$, which is clearly a multiple of $$$k$$$.

Therefore, $$$x = k - 1$$$ is the answer.

Time complexity: $$$\mathcal{O}(1)$$$

answer = [print(int(input()) - 1) for testcase in range(int(input()))]

• 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, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    
    int c_v = 1;
    for (int i = 0; i < n; i++) {
        if (p[i] == c_v) c_v++;
    }
    
    cout << (n  - c_v + k) / k  << nl;
}

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

• Good problem
• Average problem
• Bad problem

1768C- Elemental Decompress

Two cases produce no answers:

• One element appears more than twice in $$$a$$$.

• After sorting, there is some index that $$$a[i] < i$$$ ($$$1$$$-indexed).

Otherwise, solutions always exist. One method is to constructively attach each element in $$$a$$$ to $$$p$$$ or $$$q$$$:

• Traverse from the biggest element to the smallest in $$$a$$$, if that number haven't appeared in $$$p$$$ then attach it to $$$p$$$, otherwise attach it to $$$q$$$.

• Traverse from the biggest element to the smallest in $$$a$$$ again, if we attached it to $$$p$$$, find the biggest number that did not appear in $$$q$$$ and attach to $$$q$$$, vice versa.

A naive solution requires the $$$O(n^2)$$$ method to solve. We can reduce to $$$O(n \log n)$$$ by sorting elements in $$$a$$$ as pairs <element, index>.

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

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
int n;
int a[N], b[N], c[N], ra[N], rb[N];

void out()
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << ' ';
	}
	cout << '\n';
	
	for (int i = 0; i < n; i++)
	{
		cout << b[i] << ' ';
	}
	cout << '\n';
}

void solve()
{
	cin >> n;
	vector<pair<int, int> > V;
	for (int i = 0; i < n; i++)
	{
		cin >> c[i];
		a[i] = b[i] = 0;
		ra[i + 1] = rb[i + 1] = 1;
		V.push_back(make_pair(c[i], i));
	}
	sort(V.rbegin(), V.rend());
	
	for (int i = 0; i < n; i++)
	{
		int k = V[i].second;
		if (ra[c[k]] == 1) a[k] = c[k], ra[c[k]]--;
		else b[k] = c[k], rb[c[k]]--;
	}
	
	int r1 = n, r2 = n;
	for (int i = 0; i < n; i++)
	{
		int k = V[i].second;
		if (a[k] == 0)
		{
			while (ra[r1] == 0) r1--;
			ra[r1]--;
			if (r1 > b[k])
			{
			    cout << "NO" << '\n';
			    return;
			}
			a[k] = r1--;
		}
		else
		{
			while (rb[r2] == 0) r2--;
			rb[r2]--;
			if (r2 > a[k])
			{
			    cout << "NO" << '\n';
			    return;
			}
			b[k] = r2--;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (ra[i] != 0 || rb[i] != 0)
		{
			cout << "NO" << '\n';
			return;
		}
	}
	cout << "YES" << '\n';
	out();
}

int main(int argc, char* argv[])
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while(t--)
		solve();
}

There is actually a $$$O(n)$$$ solution to this problem.

    /// Storing position of each a[i]
    vector<vector<int> > b(n + 1);
    for (int i = 1; i <= n; ++i) {
        b[a[i]].push_back(i);

        /// max(p[i], q[i]) = a[i] so either p[i] = a[i] or/and q[i] = a[i]
        /// so if the number appear the third time or more, then "NO"
        if (b[a[i]].size() >= 3) {
            cout << "NO\n";
            return 0;
        }
    }

    /// Initialize permutation p[1..n], q[1..n]
    vector<int> p(n + 1, -1), q(n + 1, -1);

    /// Initialize permutation position, fp[p[i]] = i, fq[q[i]] = i
    vector<int> fp(n + 1, -1), fq(n + 1, -1);
    for (int x = n; x >= 1; --x) {
        for (int i : b[x]) {
            /// Because of max(), we must save up the smaller value
            /// So we assign p[i] or q[i] by x, one by one from x large -> small
                 if (fp[x] == -1) p[fp[x] = i] = x;
            else if (fq[x] == -1) q[fq[x] = i] = x;
        }
    }

    for (int x = n, vp = n, vq = n; x >= 1; --x) {
        for (int i : b[x]) {
            /// Assign the remaining integers
            while (fp[vp] != -1) --vp;
            while (fq[vq] != -1) --vq;
            if (p[i] == -1 && vp > 0) p[fp[vp] = i] = vp;
            if (q[i] == -1 && vq > 0) q[fq[vq] = i] = vq;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (max(p[i], q[i]) != a[i]) {
            /// Statement condition is not satisfied
            cout << "NO\n";
            return 0;
        }
    }

    /// Output the answer
    cout << "YES\n";
    for (int i = 1; i <= n; ++i) cout << p[i] << " "; cout << "\n";
    for (int i = 1; i <= n; ++i) cout << q[i] << " "; cout << "\n";

#include <iostream>
#include <vector>

using namespace std;

int query()
{
    /// Input number of element
    int n;
    cin >> n;

    /// Input the array a[1..n]
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    /// Storing position of each a[i]
    vector<vector<int> > b(n + 1);
    for (int i = 1; i <= n; ++i) {
        b[a[i]].push_back(i);

        /// max(p[i], q[i]) = a[i] so either p[i] = a[i] or/and q[i] = a[i]
        /// so if the number appear the third time or more, then "NO"
        if (b[a[i]].size() >= 3) {
            cout << "NO\n";
            return 0;
        }
    }

    /// Initialize permutation p[1..n], q[1..n]
    vector<int> p(n + 1, -1), q(n + 1, -1);

    /// Initialize permutation position, fp[p[i]] = i, fq[q[i]] = i
    vector<int> fp(n + 1, -1), fq(n + 1, -1);
    for (int x = n; x >= 1; --x) {
        for (int i : b[x]) {
            /// Because of max(), we must save up the larger value
            /// So we assign p[i] or q[i] by x, one by one from x large -> small
                 if (fp[x] == -1) p[fp[x] = i] = x;
            else if (fq[x] == -1) q[fq[x] = i] = x;
        }
    }

    for (int x = n, vp = n, vq = n; x >= 1; --x) {
        for (int i : b[x]) {
            /// Assign the remaining integers
            while (fp[vp] != -1) --vp;
            while (fq[vq] != -1) --vq;
            if (p[i] == -1 && vp > 0) p[fp[vp] = i] = vp;
            if (q[i] == -1 && vq > 0) q[fq[vq] = i] = vq;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (max(p[i], q[i]) != a[i]) {
            /// Statement condition is not satisfied
            cout << "NO\n";
            return 0;
        }
    }

    /// Output the answer
    cout << "YES\n";
    for (int i = 1; i <= n; ++i) cout << p[i] << " "; cout << "\n";
    for (int i = 1; i <= n; ++i) cout << q[i] << " "; cout << "\n";
    return 0;
}



signed main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);



    int q = 1; /// If there is no multiquery
    cin >> q;  /// then comment this

    while (q-->0)
    {
        /// For each query
        query();


    }



    return 0;
}

• 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> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i]; p[i]--;
	}
	
	int ind = 1, ans = 0;
	vector<int> comp(n, 0);
	for (int i = 0; i < n; i++) {
		if (comp[i]) continue;
		{
			int v = i;
			while (comp[v] == 0) {
				comp[v] = ind;
				v = p[v];
				ans++;
			}
			
			ind++; ans--;
		}
	}
	
	for (int i = 0; i < n - 1; i++) {
		if (comp[i] == comp[i + 1]) {
			cout << ans - 1 << nl;
			return;
		}
	}
	cout << ans + 1 << nl;
}

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

• Good problem
• Average problem
• Bad problem

1768E- Partial Sorting

We need at most $$$3$$$ operations to sort the permutation: $$$1 -> 2 -> 1$$$

• For $$$f(p) = 0$$$, there is only one case: the initially sorted permutation.

• For $$$f(p) \leq 1$$$, this scenario appears when the first $$$n$$$ numbers or the last $$$n$$$ numbers are in the right places.

• For $$$f(p) \leq 2$$$, this scenario appears when the smallest $$$n$$$ elements' positions are in range $$$[1, 2n]$$$, or the largest $$$n$$$ numbers' positions are in range $$$[n + 1, 3n]$$$.

• For $$$f(p) \leq 3$$$, it will be the count of all valid permutations.

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

#include <bits/stdc++.h>

using namespace std;

long long n, M;

long long frac[3000005], inv[3000005];

long long powermod(long long a, long long b, long long m)
{
	if (b == 0) return 1;
	unsigned long long k = powermod(a, b / 2, m);
	k = k * k;
	k %= m;
	if (b & 1) k = (k * a) % m;
	return k;
}

void Ready()
{
	frac[0] = 1;
	inv[0] = 1;
	for (int i = 1; i <= 3000000; i++)
	{
		frac[i] = (frac[i - 1] * i) % M;
	}
	
	inv[3000000] = powermod(frac[3000000], M - 2, M);
	
	for (int i = 3000000; i > 0; i--)
	{
		inv[i - 1] = (inv[i] * i) % M;
	}
}

long long C(long long n, long long k)
{
	return ((frac[n] * inv[k]) % M * inv[n - k]) % M;
}

int main()
{
	cin >> n >> M;
	Ready();
	long long ans[4]{};
	
	// X = 0
	
	ans[0] = 1;
	
	// X = 1
	
	ans[1] = 2 * frac[2 * n] - frac[n] - ans[0] + M + M;
	ans[1] %= M;
	
	// X = 2
	
	ans[2] = frac[2 * n];
	ans[2] = ans[2] * C(2 *n, n) % M;
	ans[2] = ans[2] * frac[n] % M;
	ans[2] = ans[2] * 2 % M;
	
	for (int i = 0; i <= n; i++)
	{
		int sub = C(n, i);
		sub = sub * C(n, n - i) % M;
		sub = sub * C(2 * n - i, n) % M;
		sub = sub * frac[n] % M;
		sub = sub * frac[n] % M;
		sub = sub * frac[n] % M;
		ans[2] = (ans[2] - sub + M) % M;
	}
	ans[2] = (ans[2] - ans[1] + M) % M;
	ans[2] = (ans[2] - ans[0] + M) % M;
	
	// X = 3
	
	ans[3] = frac[3 * n];
	ans[3] = (ans[3] - ans[2] + M) % M;
	ans[3] = (ans[3] - ans[1] + M) % M;
	ans[3] = (ans[3] - ans[0] + M) % M;
	
	long long answer = ans[1] + 2 * ans[2] + 3 * ans[3];
	answer %= M;
	
	cout << answer << endl;
}

• 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 K = 650;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n;
	cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	vector<ll> dp(n, 1e18);
	dp[0] = 0;
	
	vector<int> st = {0};
	for (int i = 1; i < n; i++) {
		// Case 1
		{
			ll mi = a[i];
			for (int j = i - 1; j >= max(0, i - K); j--) {
				mi = min(mi, a[j]);
				dp[i] = min(dp[i], dp[j] + mi * (i - j) * (i - j));
			}
		}
		
		// Case 2
		if (a[i] <= K) {	
			for (int j = i - 1; j >= 0; j--) {
				dp[i] = min(dp[i], dp[j] + a[i] * (i - j) * (i - j));
				if (a[j] <= a[i]) break;
			}
		}
		
		// Case 3 
		{
			for (int j: st) {
				dp[i] = min(dp[i], dp[j] + a[j] * (i - j) * (i - j));
			}
			
			if (a[i] <= K) {
				while (!st.empty() && a[st.back()] >= a[i]) {
					st.pop_back();
				}
				st.push_back(i);
			}
		}
	}
	
	for (int i = 0; i < n; i++) cout << dp[i] << ' ';
	cout << endl;
}

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
 
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
 
int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::vector<long long> dp(n, 1e18);
    dp[0] = 0;
    for(int i = 0; i < n; i++) {
        int dist = n / a[i] + 1;
        // take from behind
        for(int j = i-1; j >= 0 && i-j <= dist; j--) {
            dp[i] = std::min(dp[i], dp[j] + (long long) a[i] * (i - j) * (i - j));
            if(a[j] <= a[i]) break;
        }
        // propagate forward
        for(int j = i+1; j < n && j-i <= dist; j++) {
            dp[j] = std::min(dp[j], dp[i] + (long long) a[i] * (i - j) * (i - j));
            if(a[j] <= a[i]) break;
        }
        std::cout << dp[i] << (i + 1 == n ? '\n' : ' ');
    }
}

• Good problem
• Average problem
• Bad problem

The smallest possible sum is $$$1 + 2 + \ldots + k$$$.

#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 main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (int i = 0; i < n; i++) cin >> a[i];
		
		vector<int> b = a;
		sort(all(b));
		int x = b[k - 1];
		
		int ans = 0;
		for (int i = 0; i < k; i++) {
			if (a[i] > x) ans++;
		}
		cout << ans << nl;
	}
}

#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 main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		if (n % 2 == 0) {
			for (int i = 1; i <= n; i += 2) {
				cout << i + 1 << ' ' << i << ' ';
			}
			cout << nl;
		} else {
			cout << 1 << ' ';
			for (int i = 2; i <= n; i += 2) {
				cout << i + 1 << ' ' << i << ' ';
			}
			cout << nl;
		}
	}
}

#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 main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		
		vector<int> a(n);
		map<int, vector<int>> p;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			p[a[i]].push_back(i);
		}
		
		int ans = 0;
		set<int> ts;
		for (int i = 0; i < n - 1; i++) {
			if (a[i] > a[i + 1]) ts.insert(i);
		}
		
		while (!ts.empty()) {
			int i = *ts.begin();
			int x;
			if (a[i] > 0) {
				x = a[i];
			} else {
				x = a[i + 1];
			}
			
			for (int j: p[x]) {
				a[j] = 0;
				ts.erase(j - 1);
				ts.erase(j);
				if (j > 0 && a[j - 1] > a[j]) ts.insert(j - 1);
				if (j + 1 < n && a[j] > a[j + 1]) ts.insert(j);
			}
			ans++;
		}
		
		cout << ans << nl;
	}
}

#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 inf = 1000000000;

bool f(vector<int> a, int k, int ans) {
	int n = gsize(a);
	int dk = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] * 2 < ans) {
			a[i] = inf;
			k--;
			dk++;
		}
	}
	
	if (k < 0) return false;
	if ((k > 0 && dk > 0) || k >= 2) return true;
	
	if (k == 1 && dk == 0) {
		return *max_element(all(a)) >= ans;
	}
	
	for (int i = 0; i < n - 1; i++) {
		if (min(a[i], a[i + 1]) >= ans) return true;
	}
	
	return false;
}

void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	int lb = 0, ub = inf, tans = 0;
	while (lb <= ub) {
		int tm = (lb + ub) / 2;
		if (f(a, k, tm)) {
			tans = tm;
			lb = tm + 1;
		} else {
			ub = tm - 1;
		}
	}
	
	cout << tans << nl;
}

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

#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 = 200000; 

int t[(maxn + 1) * 4];

void update(int v, int tl, int tr, int i, int x) {
	t[v] += x;
	if (tl != tr - 1) {
		int tm = (tl + tr) / 2;
		if (i < tm) update(2*v + 1, tl, tm, i, x);
		else update(2*v + 2, tm, tr, i, x);
	}
}

int query(int v, int tl, int tr, int l, int r) {
	if (l >= r) return 0;
	if (tl == l && tr == r) return t[v];
	else {
		int tm = (tl + tr) / 2;
		int r1 = query(2*v + 1, tl, tm, l, min(r, tm));
		int r2 = query(2*v + 2, tm, tr, max(l, tm), r);
		return r1 + r2;
	}
}
 
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	vector<vector<int>> d(2*maxn + 1);
	
	for (int i = 1; i <= maxn; i++) {
		for (int j = i; j <= 2*maxn; j += i) {
			d[j].push_back(i);
		}
	}
	
	vector<vector<pair<int, int>>> segs(maxn + 1);
	
	for (int k = 1; k <= maxn; k++) {
		for (int ti = 0; ti < gsize(d[2*k]); ti++) {
			int i = d[2*k][ti], ct = 0;
			
			for (int tj = ti + 1; tj < gsize(d[2*k]); tj++) {
				int j = d[2*k][tj];
				if (j >= k) break;
				if (i + j > k || (k % i == 0 && k % j == 0)) ct++;
			}
			
			if (ct > 0)	{
				segs[i].emplace_back(k, ct);
			}
		}
	}
	
	
	
	int T;
	cin >> T;
	
	vector<ll> ans(T);
	vector<array<int, 3>> queries;
	
	for (int i = 0; i < T; i++) {
		ll l, r;
		cin >> l >> r;
		queries.push_back({l, r, i});
		ans[i] = (r - l + 1) * (r - l) * (r - l - 1) / 6;
	}
	
	sort(all(queries));
	
	int ti = T - 1;
	for (int i = maxn; i >= 1; i--) {
		
		// Update ST
		for (auto [r, ct]: segs[i]) {
			update(0, 0, maxn + 1, r, ct);
		}
		
		// Get Answers
		while (ti >= 0 && queries[ti][0] == i) {
			ans[queries[ti][2]] -= query(0, 0, maxn + 1, i, queries[ti][1] + 1);
			ti--;
		}
	}
	for (int i = 0; i < T; i++) cout << ans[i] << nl;
}

#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;
int f[maxn], d[maxn];
vector<int> g[maxn], g2[maxn], val[maxn];
int n, q;

vector<int> ans, x;

void solve() {
	
	for (int v = n - 1; v >= 0; v--) {
		for (int u: g[v]) {
			if (gsize(val[u]) > gsize(val[v])) swap(val[u], val[v]);
			for (int fu = 0; fu < gsize(val[u]); fu++) {
				for (int qi = 0; qi < q; qi++) {
					while (true) {
						int fv = max(0, ans[qi] - fu - x[qi]);
						if (fv < gsize(val[v]) && 
							val[v][fv] + val[u][fu] - 2*d[v] >= ans[qi]) ans[qi]++;
						else break;
					}
				}
			}
			for (int fu = 0; fu < gsize(val[u]); fu++) {
				val[v][fu] = max(val[v][fu], val[u][fu]);
			}
			val[u].clear();
			val[u].shrink_to_fit();
		}
		{
			int fu = f[v];
			for (int qi = 0; qi < q; qi++) {
				while (true) {
					int fv = max(0, ans[qi] - fu - x[qi]);			
					if (fv < gsize(val[v]) && 
						val[v][fv] - d[v] >= ans[qi]) ans[qi]++;
					else break;
				}
			}
			if (fu == gsize(val[v])) {
				val[v].push_back(d[v]);
			}
		}
	}
	
	for (int i = 0; i < q; i++) {
		ans[i]--;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	
	vector<int> deg(n);
	for (int i = 1; i < n; i++) {
		int p;
		cin >> p;
		d[i] = d[p - 1] + 1;
		g[p - 1].push_back(i);
		g2[i].push_back(p - 1);
	}
	
	{
		queue<int> qe;
		vector<bool> used(n, false);
		for (int i = 0; i < n; i++) {
			if (gsize(g2[i]) + gsize(g[i]) == 1) {
				qe.push(i);
				used[i] = true;
			}
		}
		
		while (!qe.empty()) {
			int v = qe.front();
			qe.pop();
			for (int u: g[v]) {
				if (used[u]) continue;
				f[u] = f[v] + 1;
				qe.push(u);
				used[u] = true;
			}
			
			for (int u: g2[v]) {
				if (used[u]) continue;
				f[u] = f[v] + 1;
				qe.push(u);
				used[u] = true;
			}
		}
	}
	
	cin >> q;
	for (int i = 0; i < q; i++) {
		int tx;
		cin >> tx;
		x.push_back(tx);
		ans.push_back(0);
	}
	
	solve();
	
	for (int tans: ans) cout << tans << ' ';
	cout << nl;
}

Hope you liked them!

В каждой задаче скрыта отсылка, можете попробовать их отгадать!

И не забудьте оценить все задачи в разборе после контеста! Также, у некоторых задач будут бонусные версии, которые вы можете попробовать решить.

Ответ "YES" только для малого количества строк.

Для $$$n \ge 3$$$, ответ "NO".

Пусть $$$n \ge 3$$$ и результирующая строка будет $$$a$$$. Чтобы в ней не было палиндромов длины больше чем 1, должны выполняться как минимум вот эти неравенства: $$$a_1 \neq a_2$$$, $$$a_2 \neq a_3$$$ и $$$a_1 \neq a_3$$$. Но так как у нас бинарная строка, это невозможно, поэтому ответ "NO".

Для $$$n \le 2$$$, есть 4 строки с ответом "YES": $$$0$$$, $$$1$$$, $$$01$$$, и $$$10$$$; а также 2 строки с ответом "NO": $$$00$$$ и $$$11$$$.

Временная сложность: $$$O(n)$$$

• Код на C++.
• Код на Python.

Минимальная стоимость постройки опор — степень двойки.

Минимальная стоимость постройки опор — $$$2 ^ k$$$, где $$$k$$$ — старший бит числа $$$n - 1$$$.

Пусть $$$k$$$ — старший бит числа $$$n - 1$$$. Очевидно, что в массиве высот опор точно будет два соседних элемента, у одного из которых $$$k$$$-ый бит будет равен $$$1$$$, а у второго — $$$0$$$. Из этого следует, что минимальная стоимость постройки опор не меньше $$$2 ^ k$$$. Простая конструкция, в которой эта минимальная стоимость достигается — $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.

Временная сложность: $$$O(n)$$$

Бонус: посчитайте количество перестановок с минимальной стоимостью

• Код на C++.
• Код на Python.

В оптимальном решении третья операция применяется не больше одного раза.

В оптимальном решении третья операция применяется не больше одного раза, так как применение данной операции не уменьшает $$$a$$$ и всегда делает $$$b \le a$$$. Это означает, что после применения третьей операции выгодно выполнять только вторую операцию до тех пор, пока $$$a$$$ не станет равно $$$b$$$.

Если мы не применяем третью операцию ни разу, ответ $$$b - a$$$.

Предположим, что мы применили третью операцию. Перед этим мы какое-то количество раз применили первую и вторую операцию, пусть итоговые значения $$$a$$$ и $$$b$$$ непосредственно перед применением третьей операции будут $$$a'$$$ и $$$b'$$$ соответственно $$$(a \le a', b \le b')$$$. В этом случае ответ будет равен $$$(a' - a) + (b' - b) + ((a' \ | \ b') - b') + 1$$$ $$$=$$$ $$$a' + (a' \ | \ b') + (1 - a - b)$$$. Это эквивалентно минимизации $$$a' + (a' \ | \ b')$$$, так как $$$(1 - a - b)$$$ — константа.

Для решения этой задачи будем итерироваться по $$$a'$$$ от $$$a$$$ до $$$b$$$. Для фиксированного $$$a'$$$, нам необходимо минимизировать $$$a' \ | \ b'$$$, оптимальный $$$b'$$$ может быть найден следующим образом:

Сначала положим $$$b' = 0$$$. Будем итерироваться по битам от старших к младшим. Тогда есть 4 случая:

• Если текущий бит $$$a'$$$ — $$$0$$$ и $$$b$$$ — $$$1$$$, то выставляем текущий бит $$$b'$$$ в $$$1$$$.
• Если текущий бит $$$a'$$$ — $$$0$$$ и $$$b$$$ — $$$0$$$, то выставляем текущий бит $$$b'$$$ в $$$0$$$.
• Если текущий бит $$$a'$$$ — $$$1$$$ и $$$b$$$ — $$$1$$$, то выставляем текущий бит $$$b'$$$ в $$$1$$$.
• Если текущий бит $$$a'$$$ — $$$1$$$ и $$$b$$$ — $$$0$$$, то выставляем текущий бит $$$b'$$$ в $$$1$$$ и останавливаемся.

Данный алгоритм работает за $$$O(\log b)$$$ и может быть ускорен до $$$O(1)$$$ с помощью использования битовых операций.

Временная сложность: $$$O(b)$$$ или $$$O(b \log b)$$$

Бонус 1: решите задачу за $$$O(\log b)$$$ или быстрее.

Бонус 2: докажите что оптимально сделать $$$a' = a$$$ или $$$b' = b$$$.

• Код на C++ с временной сложностью $$$O(b \log b)$$$.
• Код на C++ с временной сложностью $$$O(b)$$$.
• Код на Python с временной сложностью $$$O(b \log b)$$$.

Назовем отрезок $$$[l, r]$$$ плохим, если $$$\gcd(a_l \ldots a_r) = r - l + 1$$$. Есть не больше $$$n$$$ плохих отрезков.

Для фиксированного $$$l$$$, с возрастанием $$$r$$$, $$$\gcd(a_l \ldots a_r)$$$ не возрастает.

Предположим, вы изменили $$$a_i$$$ на большое простое число. Как это повлияет на плохие отрезки?

Для начала, прочитайте подсказки выше.

Найдем все плохие отрезки. Для фиксированного $$$l$$$, давайте найдем наибольшее $$$r$$$, такое, что $$$\gcd(a_l \ldots a_r) \ge r - l + 1$$$. Это можно сделать бинарным поиском и спарз таблицей / деревом отрезков. Если $$$\gcd(a_l \ldots a_r) = r - l + 1$$$, то отрезок $$$[l, r]$$$ плохой.

Если мы заменим $$$a_i$$$ на большое простое число, то все плохие отрезки, включающие $$$i$$$-ый элемент перестанут быть плохими, а новых плохих отрезков не появится.

Теперь задача свелась к стандартной: даны отрезки и нужно выбрать минимальное количество точек так, чтобы на каждом отрезке лежала хотя бы одна точка. Только в данном случае задача еще упрощена тем, что среди отрезков нет вложенных. Эта задача может быть решена жадным алгоритмом: в ответ возьмем правую границу самого левого отрезка, удалим все отрезки, покрытые данной точкой, и повторим операцию, пока есть хоть один отрезок.

Временная сложность: $$$O(n \log n \log A)$$$ со спарз таблицей, где $$$A$$$ — максимальное значение $$$a_i$$$.

Примечание:

Есть множество модификаций предыдущего решения, некоторые из которых используют метод двух указателей и обновляют ответ по ходу поиска плохих отрезков. Используя дерево отрезков и метод двух указателей, можно добиться временной сложности $$$O(n (\log n + \log A))$$$.

Также вы можете использовать тот факт, что для любого префикса существует максимум $$$O(\log A)$$$ различных суффиксных $$$\gcd$$$-значений. Это наблюдение также может использоваться для поиска плохих отрезков.

• Код на C++, использующий дерево отрезков и бинарный поиск с временной сложностью $$$O(n \log n (\log n + \log A))$$$.
• Код на C++, использующий спарс таблицу и метод двух указателей с временной сложностью $$$O(n \log n \log A))$$$.
• Код на Python, использующий дерево отрезков и метод двух указателей с временной сложностью $$$O(n (\log n + \log A))$$$.

Оптимально добавлять рёбра типа $$$(1, v)$$$.

Для фиксированного $$$x$$$, как проверить, что ответ не больше $$$ans$$$?

Для фиксированного $$$x$$$ и $$$ans$$$, найдите максимальное расстояние между двумя вершинами для которых верно $$$depth_v > ans$$$.

Для каждой вершины, найдите два ребёнка с максимальной глубиной поддеревьев.

Для начала, прочитайте подсказки выше.

Пусть $$$f_{ans}$$$ будет максимальным расстоянием между вершинами с $$$depth_v > ans$$$. Если для какого-то $$$x$$$ ответ не больше $$$ans$$$, то $$$ans \ge depth$$$ или $$$\lceil \frac{f_{ans}}{2} \rceil + x \le ans$$$, так как мы можем добавить ребро $$$(1, u)$$$, где $$$u$$$ будет на середине пути между двумя дальнейшими вершинами с $$$depth_v > ans$$$. Так как с возрастанием $$$ans$$$, $$$f_{ans}$$$ убывает, мы можем использовать бинпоиск или два указателя.

Как посчитать $$$f_{ans}$$$? Найдём для каждой вершины два ребёнка с глубочайшими поддеревьями. Пусть $$$a_v$$$ и $$$b_v$$$ — глубины их поддеревьев ($$$a_v \ge b_v$$$). Если детей не хватает, то присвоим этим значениям $$$depth_v$$$. Если $$$b_v > 0$$$, то делаем $$$f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v)$$$. А после этого переберём $$$i$$$ от $$$n - 2$$$ до $$$0$$$ и сделаем $$$f_i = \max(f_i, f_{i + 1})$$$.

Временная сложность: $$$O(n)$$$ или $$$O(n \log n)$$$ с бинпоиском.

Примечание: чтобы решить E1, достаточно найти $$$f_{ans}$$$ за $$$O(n)$$$ или $$$O(n \log n)$$$ для каждого $$$ans$$$. Один способ это сделать — найти диаметр дерева после того, как были удалены все листы с $$$depth_v \le ans$$$ ($$$1$$$ тоже лист).

• Код на C++ для E1 с временной сложностью $$$O(n ^ 2)$$$.
• Код на Python для E1 с временной сложностью $$$O(n ^ 2)$$$.
• Код на C++ для E2 с временной сложностью $$$O(n)$$$.
• Код на Python для E2 с временной сложностью $$$O(n)$$$.