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

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

• Good problem
• Average problem
• Bad problem