#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!

Every problem has a hidden reference in it, you are welcome to try and guess them all!

And don't forget to rate the problems in the editorial after the contest! Also, some problems will have bonus versions that you can try to solve.

Only a few strings have the answer "YES".

For $$$n \ge 3$$$, the answer is "NO".

Let $$$n \ge 3$$$ and the resulting string be $$$a$$$. For there to be no palindromes of length greater than $$$1$$$, at least all of these inequalities must be true: $$$a_1 \neq a_2$$$, $$$a_2 \neq a_3$$$, and $$$a_1 \neq a_3$$$. Since our string is binary, this is impossible, so the answer is "NO".

For $$$n \le 2$$$, there are 4 strings that have the answer "YES": $$$0$$$, $$$1$$$, $$$01$$$, and $$$10$$$; as well as 2 strings that have the answer "NO": $$$00$$$ and $$$11$$$.

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

• C++ code.
• Python code.

The cost of construction is a power of two.

The cost of construction is $$$2 ^ k$$$, where $$$k$$$ is the highest set bit in $$$n - 1$$$.

Let $$$k$$$ be the highest set bit in $$$n - 1$$$. There will always be a pair of adjacent elements where one of them has the $$$k$$$-th bit set and the other one doesn't, so the cost is at least $$$2^k$$$. A simple construction that reaches it is $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.

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

Bonus: count the number of permutations with the minimum cost.

• C++ code.
• Python code.

It is optimal to apply the third operation at most once.

It is optimal to apply the third operation at most once, because is does not decrease $$$a$$$ and always makes $$$b \le a$$$. This means that after we use it, we can only apply the second operation.

If we don't apply the third operation, the answer is $$$b - a$$$.

Suppose we do apply it. Before that, we used the first and second operations some number of times, let the resulting values of $$$a$$$ and $$$b$$$ be $$$a'$$$ and $$$b'$$$ respectively $$$(a \le a', b \le b')$$$. The answer in this case will be $$$(a' - a) + (b' - b) + ((a' \ | \ b') - b') + 1$$$ $$$=$$$ $$$a' + (a' \ | \ b') + (1 - a - b)$$$. This is equivalent to minimizing $$$a' + (a' \ | \ b')$$$, since $$$(1 - a - b)$$$ is constant.

To do that, we can iterate $$$a'$$$ from $$$a$$$ to $$$b$$$. For a fixed $$$a'$$$, we have to minimize $$$a' \ | \ b'$$$, the optimal $$$b'$$$ can be constructed like this:

Set $$$b'$$$ to zero and iterate over bits from highest to lowest. There are 4 cases:

• If current bit of $$$a'$$$ is $$$0$$$ and $$$b$$$ is $$$1$$$, set the current bit of $$$b'$$$ to $$$1$$$.
• If current bit of $$$a'$$$ is $$$0$$$ and $$$b$$$ is $$$0$$$, set the current bit of $$$b'$$$ to $$$0$$$.
• If current bit of $$$a'$$$ is $$$1$$$ and $$$b$$$ is $$$1$$$, set the current bit of $$$b'$$$ to $$$1$$$.
• If current bit of $$$a'$$$ is $$$1$$$ and $$$b$$$ is $$$0$$$, set the current bit of $$$b'$$$ to $$$1$$$ and stop.

This works in $$$O(\log b)$$$ and can also be sped up to $$$O(1)$$$ using bit manipulation.

Time complexity: $$$O(b)$$$ or $$$O(b \log b)$$$

Bonus 1: solve the problem in $$$O(\log b)$$$ or faster.

Bonus 2: prove that is optimal to have either $$$a' = a$$$ or $$$b' = b$$$.

• C++ code with complexity $$$O(b \log b)$$$.
• C++ code with complexity $$$O(b)$$$.
• Python code with complexity $$$O(b \log b)$$$.

Let's call a segment $$$[l, r]$$$ bad if $$$\gcd(a_l \ldots a_r) = r - l + 1$$$. There at most $$$n$$$ bad segments.

For a fixed $$$l$$$, as $$$r$$$ increases, $$$\gcd(a_l \ldots a_r)$$$ does not increase.

Suppose you change $$$a_i$$$ into a big prime. How does this affect the bad segments?

Read the hints above.

Let's find all of the bad segments. For a fixed $$$l$$$, let's find the largest $$$r$$$ that has $$$\gcd(a_l \ldots a_r) \ge r - l + 1$$$. This can be done with binary search and a sparse table / segment tree. If $$$\gcd(a_l \ldots a_r) = r - l + 1$$$, then the segment $$$[l, r]$$$ is bad.

If we change $$$a_i$$$ into a big prime, no new bad segments will appear. And all bad segments that have $$$i$$$ inside of them will disappear. So we have to find the minimum number of points to cover all of them. This is a standard problem, which can be solved greedily: choose the segment with the smallest $$$r$$$, delete all segments that have $$$r$$$ in them, and repeat. In our case, this is easy to do because our segments are not nested.

Time complexity: $$$O(n \log n \log A)$$$ with a sparse table, where $$$A$$$ is the maximum value of $$$a_i$$$.

Notes:

There are many different modifications to the previous solution, some of them use two pointers (since segments are not nested) and some of them update the answer on the fly while searching for the bad segments. Using a segment tree and two pointers you can get the complexity $$$O(n (\log n + \log A))$$$.

You can also use the fact that for a prefix, there at most $$$O(\log A)$$$ different suffix $$$\gcd$$$ values. This leads to another way to find the bad segments.

• C++ code with segment tree and binary search with complexity $$$O(n \log n (\log n + \log A))$$$.
• C++ code with sparse table and two pointers with complexity $$$O(n \log n \log A)$$$.
• Python code with segment tree and two pointers with complexity $$$O(n (\log n + \log A))$$$.

It is optimal to add edges of type $$$(1, v)$$$.

Try to check if for a fixed $$$x$$$ the answer is at most $$$ans$$$.

For a fixed $$$x$$$ and answer $$$ans$$$, find the distance between nodes that have $$$depth_v > ans$$$.

For each node, find two children with the deepest subtrees.

Read the hints above.

Let $$$f_{ans}$$$ be the maximum distance between two nodes that have $$$depth_v > ans$$$. If for some $$$x$$$ the answer is at most $$$ans$$$, then either $$$ans \ge depth$$$ or $$$\lceil \frac{f_{ans}}{2} \rceil + x \le ans$$$, since we can add an edge $$$(1, u)$$$ where $$$u$$$ is in the middle of the path connecting the two farthest apart nodes with $$$depth_v > ans$$$. Since $$$f_{ans}$$$ decreases as $$$ans$$$ increases, we can use binary search. Also note that we can use two pointers and increase $$$ans$$$ as we increase $$$x$$$.

How to calculate $$$f_{ans}$$$? Let's find for each node its two children with the deepest subtrees. Let $$$a_v$$$ and $$$b_v$$$ be the depths of their subtrees ($$$a_v \ge b_v$$$). If there are not enough children, set this values to $$$depth_v$$$. If $$$b_v > 0$$$, do $$$f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v)$$$. After this, iterate $$$i$$$ from $$$n - 2$$$ to $$$0$$$ and do $$$f_i = \max(f_i, f_{i + 1})$$$.

Time complexity: $$$O(n)$$$ or $$$O(n \log n)$$$ with binary search.

Note: To solve E1, it is enough to calculate $$$f_{ans}$$$ in $$$O(n)$$$ or $$$O(n \log n)$$$ for each $$$ans$$$. One way to do that is to find the diameter of the resulting tree after repeatedly deleting any leaf that has $$$depth_v \le ans$$$ ($$$1$$$ is also considered a leaf).

• C++ code for E1 with complexity $$$O(n ^ 2)$$$.
• Python code for E1 with complexity $$$O(n ^ 2)$$$.
• C++ code for E2 with complexity $$$O(n)$$$.
• Python code for E2 with complexity $$$O(n)$$$.