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!

Try to brute force for $$$k \lt 50$$$. Do you see anything suspicious?

Now try to brute force from $$$k - 1$$$ to $$$0$$$ for large numbers.

1768A- Greatest Convex

Does

Unable to parse markup [type=CF_MATHJAX]

The answer is yes, as

Unable to parse markup [type=CF_MATHJAX]

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

Time complexity: $$$O(1)$$$

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

• Good problem
• Average problem
• Bad problem

Will be added later

• Good problem
• Average problem
• Bad problem

How many times an unique number can appear in the array $$$a$$$?

Can there be two numbers $$$1$$$ in $$$a$$$? What is the conclusion?

If you sort the array, which rules should the new array satisfies? Given an array $$$1$$$ $$$2$$$ $$$2$$$, is there any answer for this case?

Which element should you construct first?

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] \lt i$$$ ($$$1$$$-indexed).

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

Unable to parse markup [type=CF_MATHJAX]

• 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

  Unable to parse markup [type=CF_MATHJAX]

  .

• 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

  Unable to parse markup [type=CF_MATHJAX]

  and attach to

  Unable to parse markup [type=CF_MATHJAX]

  , vice versa.

A naive solution requires the

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Time complexity:

Unable to parse markup [type=CF_MATHJAX]

#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

Will be added later

• Good problem
• Average problem
• Bad problem

Given a fixed permutation, how many operations do we need to sort it?

Keep in mind there is one already sorted permutation that doesn't need to be sorted.

What if there is exactly $$$1$$$ number in the range

Unable to parse markup [type=CF_MATHJAX]

This is not really a hint, fft solutions exist, but we made sure most of them cannot pass.

1768E- Partial Sorting

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

• For

  Unable to parse markup [type=CF_MATHJAX]

  , there is only one case: the initially sorted permutation.

• For

  Unable to parse markup [type=CF_MATHJAX]

  , 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

  Unable to parse markup [type=CF_MATHJAX]

  , or the largest $$$n$$$ numbers' positions are in range $$$[n + 1, 3n]$$$.

• For

  Unable to parse markup [type=CF_MATHJAX]

  , it will be the count of all valid permutations.

Time complexity: $$$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

~~~~~

~~~~~

• Good problem
• Average problem
• Bad problem