Hope you liked the problems!

**(from thanhchauns2) Before the round starts**

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!

**Testers' predictions**

Tester | A | B | C | D | E | F |
---|---|---|---|---|---|---|

xiaoziya | 900 | 1000 | 1400 | 1800 | 2100 | 3000 |

feecle6418 | 900 | 1200 | 1400 | 1700 | 2200 | 2900 |

valeriu | 800 | 1100 | 1550 | 1900 | 2200 | - |

6aren | 800 | 1200 | - | 2000 | 2200 | - |

neko_nyaaaaaaaaaaaaaaaaa | 800 | - | - | 2100 | 2400 | 3000 |

tibinyte | 800 | 1100 | 1550 | 1800 | 2100 | 2550 |

**Some moments in the rating section**

**From neko_nyaaaaaaaaaaaaaaaaa**

**From hoangquan05112002**

**From _Astraea_**

**From Valenz**

**From TrendBattles**

**Some comments from testers and authors**

**From hoangquan05112002**

**From cadmiumky**

**From shiwei**

**From DMCS and DeMen100ns**

**tfg discussing problem F**

**From feecle6418**

**tibinyte and fextivity about problem A**

**neko_nyaa and errorgorn about problem A**

**From hoangquan05112002 again**

**From darkkcyan**

**From QuangBuiCP**

**From tibinyte, the Russian sentence is `use English please`**

**From errorgorn**

**From SPyofgame**

Author: thanhchauns2

**Hints**

**Hint 1**

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

**Hint 2**

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

**Tutorial**

### 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)$$$

**Solution**

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

Author: Vladithur Preparation: Vladithur and Alexdat2000

**Hints**

**Hint 1**

Try to have the last $$$k + 1$$$ numbers sorted.

**Hint 2**

Fix some set of numbers (not necessary sorted) of size $$$w$$$ and don't choose them in the operation. Try to have the last $$$n - w$$$ numbers sorted.

**Hint 3**

Fix the set of numbers $$$1,2,3,\ldots$$$

**Tutorial**

**Solution**

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

Author: thanhchauns2

**Hints**

**Hint 1**

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

**Hint 2**

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

**Hint 3**

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

**Hint 4**

Which element should you construct first?

**Tutorial**

### 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).

**Proof**

Consider there is some index that $$$a[i] <i$$$, then both $$$p[i] < i$$$ and $$$q[i] < i$$$ must satisfy. This is also true for the first $$$i - 1$$$ index, so the numbers that are smaller than $$$i$$$ in both $$$p$$$ and $$$q$$$ are $$$(i - 1) \times 2 + 2 = i * 2$$$. This is a contradiction.

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))$$$

**Solution**

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

**Yet another better solution**

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

**Fresh meme from SPyofgame to the intended solution of the author**

**Step 1**

If there are at least $$$k > 3$$$ positions $$$i_1, i_2, \ldots, i_k$$$ that $$$a[i_1] = a[i_2] = \ldots = a[i_k]$$$ then there is no solution.

**Proof**

Since we need the condition $$$a[i] = max(p[i], q[i])$$$, hence $$$p[i] = a[i]$$$ or/and $$$q[i] = a[i]$$$.

If there are already $$$p[i_1] = a[i_1]$$$ and $$$q[i_2] = a[i_2]$$$ then we don't have another number equal to $$$a[i_k]$$$ because $$$p[]$$$ and $$$q[]$$$ are two permutations (each number must appear exactly **once**).

**Approach**

```
/// 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;
}
}
```

**Step 2**

Since we have the $$$max()$$$ function, we need to use the larger value firsts.

**Proof**

If we iterate from the smallest value to the top, there will be scenarios where all the remaining positions $$$i$$$ will result in $$$max(p[i], q[i]) \geq a[i]$$$ because you don't have enough smaller integers.

**Approach**

So for each $$$x = n \rightarrow 1$$$ (iterating from the largest element to the smallest element), we check for each position $$$i$$$ that $$$a_i = x$$$, then assign $$$p[i] := a[i]$$$ if $$$a[i]$$$ didn't appear in permutation $$$p[]$$$, otherwise assign $$$q[i] := a[i]$$$.

```
/// 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;
}
}
```

**Step 3**

We fill the remaining integers that wasn't used, from the largest to the smallest.

**Approach**

We use $$$vp$$$ as the largest integer not used in permutation $$$p[1..n]$$$.

We use $$$vq$$$ as the largest integer not used in permutation $$$q[1..n]$$$.

Then for each of the value $$$x = n \rightarrow 1$$$, we assign to $$$p[i], q[i]$$$ that was not used.

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

**Step 4**

Check if the permutation $$$p[]$$$ and $$$q[]$$$ satisfied the solution, if it didnt then output "NO", otherwise output "YES" and the two permutations: $$$p[1..n]$$$ and $$$q[1..n]$$$.

**Approach**

Just iterate through each element as normal.

```
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";
```

**Bonus**

There is also another way that you can skip testing if $$$max(p[i], q[i]) = a[i])$$$ is correct.

But the proof is a bit harder to understand, so I prefer using this code instead.

**Full Code**

```
#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;
}
```

Author: Vladithur Preparation: Vladithur and Alexdat2000

**Hints**

**Hint 1**

There are $$$n - 1$$$ permutations of length $$$n$$$ that have exactly one inversion in them.

**Hint 2**

This problem is similar to finding the minimum number of swaps needed to sort a permutation.

**Hint 3**

Try looking at the permutation like a graph.

**Hint 4**

Try to find the number of cycles in each of the $$$n - 1$$$ graphs.

**Tutorial**

**Solution**

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

Author: thanhchauns2

**Hints**

**Hint 1**

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

**Hint 2**

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

**Hint 3**

What if there is exactly $$$1$$$ number in the range $$$[n + 1, 2n]$$$ that appears in the first $$$n$$$ numbers?

**Hint 4**

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

**Tutorial**

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

**Calculate**

`return (38912738912739811 & 1)`

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

**Calculate**

Both cases have $$$n$$$ fixed positions, so there will be $$$(2n!)$$$ permutations in each case.

Intersection: since both cases share the $$$n$$$ middle elements, $$$(n!)$$$ permutation will appear in both cases.

So there will be $$$2 \times (2n!) - (n!)$$$ such permutations.

- 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]$$$.

**Calculate**

If the smallest $$$n$$$ elements are all in position from $$$1$$$ to $$$2n$$$, then:

There are $$$C_{2n}^{n}$$$ ways to choose $$$n$$$ positions for these numbers.

For each way to choose these positions, there are $$$n!$$$ ways to choose the position for the smallest $$$n$$$ numbers, and $$$2n!$$$ ways for the rest.

The total number of valid permuations are: $$$C_{2n}^{n} \times n! \times 2n!$$$

If the largest $$$n$$$ elements are all in position from $$$n + 1$$$ to $$$3n$$$, we do the same calculation.

Intersection: intersection appears when the first $$$n$$$ numbers are all in range $$$[1, 2n]$$$ and the last $$$n$$$ numbers are all in range $$$[n + 1, 3n]$$$.

Let `intersection = 0`

**Sketch and calculation in details**

Let's talk about the numbers in range $$$[n + 1, 2n]$$$. There are $$$n$$$ such numbers.

. Imagine there are EXACTLY $$$i = 0$$$ numbers in this range that appear in the first $$$n$$$ numbers. So:

In the first $$$n$$$ numbers there are $$$n$$$ numbers in range $$$[1, n]$$$. There are $$$C_{n}^{n - 0} \times n!$$$ cases.

In the first $$$n$$$ numbers there are $$$0$$$ numbers in range $$$[n + 1, 2n]$$$. There are $$$C_{n}^{0} \times n!$$$ cases.

In the last $$$n$$$ numbers there are $$$n$$$ numbers in range $$$[n + 1, 3n]$$$, we have used $$$0$$$ numbers for the first n numbers. There are $$$C_{2n - 0}^{n} \times n!$$$ cases.

Then we have: `intersection +=`

$$$C_{n}^{n - 0} \times C_{n}^{0} \times C_{2n - 0}^{n} \times n! \times n! \times n!$$$

After convert $$$0$$$ to $$$i$$$, we have `intersection +=`

$$$C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$$$

How about there is EXACTLY $$$i = 1$$$ number in range $$$[n + 1, 2n]$$$ appearing in the first $$$n$$$ numbers?

In the first $$$n$$$ numbers there are $$$n - 1$$$ numbers in range $$$[1, n]$$$. There are $$$C_{n}^{n - 1} \times n!$$$ cases.

In the first $$$n$$$ numbers there are $$$1$$$ numbers in range $$$[n + 1, 2n]$$$. There are $$$C_{n}^{1} \times n!$$$ cases.

In the last $$$n$$$ numbers there are $$$n$$$ numbers in range $$$[n + 1, 3n]$$$, we have used $$$1$$$ numbers for the first $$$n$$$ numbers. There are $$$C_{2n - 1}^{n} \times n!$$$ cases.

Then we have: `intersection +=`

$$$C_{n}^{n - 1} \times C_{n}^{1} \times C_{2n - 1}^{n} \times n! \times n! \times n!$$$

After convert $$$1$$$ to $$$i$$$, we have `intersection +=`

$$$C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$$$

We do the same thing with remaining cases, all the way up to $$$i = n$$$.

The number of intersections will be equal to: $$$ \sum_{i = 0}^{n} C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n! $$$

So, the answer will be $$$2 \times C_{2n}^{n} \times n! \times 2n! - \sum_{i = 0}^{n} C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$$$

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

**Calculate**

`return __factorial(n * __number_of_sides_of_a_triangle)`

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

**Solution**

```
#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;
}
```

Author: Vladithur Preparation: Vladithur and Alexdat2000

**Hints**

**Hint 0**

Use dynamic programming.

**Hint 1**

$$$a_i \le n$$$

**Hint 2**

Compare $$$\min(a_i \ldots a_j) \cdot (j - i)^2$$$ with $$$n \cdot (j - i)$$$.

**Hint 3**

Compare $$$\min(a_i \ldots a_j) \cdot (j - i)^2$$$ with $$$\min(a_i \ldots a_k) \cdot (k - i)^2 + \min(a_k \ldots a_j) \cdot (j - k)^2$$$ for some $$$i < k < j$$$.

**Hint 4**

Two cases: $$$\min(a_i \ldots a_j) \ge \sqrt{n}$$$ and $$$\min(a_i \ldots a_j) < \sqrt{n}$$$.

**Hint 5**

Split $$$\min(a_i \ldots a_j) < \sqrt{n}$$$ into two more cases: $$$\min(a_i \ldots a_j) = a_i$$$ and $$$\min(a_i \ldots a_j) = a_j$$$.

**Tutorial**

**Solution**

```
#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;
}
```

**Shorter solution (tfg)**

```
#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' : ' ');
}
}
```

From SPyofgame during the contest:

yeah, bro

First time ranked top100 in div2. Hope for no FST!

Update: It's frustrating that I always get downvoted and don't know the reason

Why so many downvotes? This is bully!

maybe because the information is irrelevant to this blog? keep your achievements to yourself.

There are only $$$2$$$ hacks for problem C in today's contest. The pretest is really strong!

Permutation Forces !

Delivered so fast..2023 should not be a permutation

love the fast editorial

I got the idea for C but not able to implement it. :-)..

mee too

Can anybody help me to figure why this code is not accepted??? https://codeforces.com/contest/1768/submission/188117185

Do not paste the code in the comment.

ok thanks to indicate I have removed the code

Write codes in spoiler or only provide the link as you have provided here, as it becomes quite difficult to read this way

ok I will see to it from next time

Although pasting code directly is awful, I've checked your code in the link. In fact, the most part of your code is right except one point: when doing

you need to check if (*it1>*it2). If not, there's no solution because max(p[i],q[i]) will be *it2.

ok!!!!!!!! Right I will think harder next time to not miss something like this

You know what it feels like when you finish E when there're only 10 sec left but fail to submit the code before the last second?

dude same, i was literally about to finish it, rip 2250

Not my first time actually :3

Sorry, never solved D.:(

Amazing , was very curious for fast tutorial especially for Problem C.

Hi guys! although the editorial they've provided is great! still if you want a video format editorial you can find it here

PermutationForces?)

"it took me 2 minutes to actually prove the solution"

and it took me probably a minute and a half

^{(may be inaccurate)}to find out that $$$k! + (k-1)! = (k-1)!(k+1)$$$ and the rest of the proof is just factoradic blah blahi submitted 6 unsuccessful attempts so i lost 300 points in the contest? if there is a maximum amount u can lose, how much is it?

No matter how many times you submit for a problem, you get at least 30% of points if you solved it finally.

If you have wrong submission for problem $$$X$$$ you will get 50 points less then you usually would on that problem.

If you have few wrong submissions on a problem you didn't solve, you won't lose any points.

what the F... solution ?

Why so tight TL on E.

You can calculate the inverses of factorials more efficiently by calculating them from n to 0.

OK! thanks

Actually there's O(n) solution for C. We don't need to do any sorting. We can just count the occurence of 1-n and let occ[i]= the times i appeared in array a[]. if there's some occ[i]>2 there's no answer. Then we build two list more[] and less[]. We iterate for i from 1 to n, if occ[i]==0 we add it to less[], if occ[i]==2 we add it to more[]. since 0<=occ[i]<=2, the size of more[] and less[] will be equal. then we iterate for more[i] and less[i] reversely, if some more[i]<less[i] there's no answer. If there's no such i, we can construct p and q: for each pair of more[i] and less[i], let's call they M and L, and j = the smaller index where a[j]==M, k = the larger index where a[k]==M, we let p[j]=q[k]=M, q[j]=p[k]=L. For those j which a[j] appear only once, we just let p[j]=q[j]=a[j].

My submission:188076704

Yah nice solution :3

It's a well know fact that n — cycles is the minimum number of swaps to get 1, 2, ..., n.

Can someone explains me this ? and where is this well know ?

each cycle of length $$$l$$$ needs $$$l-1$$$ swaps to be sorted, you can try it yourself

Thank for the fast tutorial!

nice E...stuck in case f=2 too longgg...

codeforces!

I can’t understand the part of the proof(problem C) on why i*2 is contradiction. Can someone brief it and add some examples

I was confused, see the editorial

"after sorting"is mentioned then it is true.Proof:

if there is some index a[i]<i(1-indexed) then it is not possible because

consider a = [5,2,4,1,4,3]

after sorting, 1 2 3 4 4 5, here a[i]<i (1-indexed) for index 5 as 4<5.

Here afterwards I am talking about the sorted array, not the original array

so note that all elements before this element 4(present in index 5(1-indexed) ) should have both p and q less than or equal to element 4, otherwise it is not possible, because consider you place element 5 for any previous index in a sorted array then maximum will be 5 so you have to place only element x (x<=4) for all previous index. So you would have placed till 4th index, the elements <=4, so in that case both 4's will be included already. So for this index 5 you wont have elements that are <=4 , you need atleast 10 numbers for index 5 which is not possible.

If you still have doubt ask. Would be happy to help

Can you explain the approach?..I am a newbie.

There is Two conditions for answer to not exist. First is if an element is present more than 2 times. Note: an element should appear exactly 2 times in final answer. Suppose if there is an element in array A that is present 3 times, then already we would placed two elements and there wont be 3rd element to place here. And the second condition is mentioned by me in above comment.

So if neither of the condition satisfy, then there is answer so "YES".

Now how to construct the answer is the question.

We will take 2nd test case mentioned in the problem for example i.e.

5

5 3 4 2 5

So make 2 arrays p and q and place a element in p if the same element is already not present p as you cant place 2 same elements in p or q which wont be a permutation

so

p: 5 3 4 2 _

q: _ _ _ _ 5

so in both array p and q, all 1 to 5 should be present

so you will have each element of count 2. i.e. there will be two 1's, two 2's, two 3's and so on.... . [5 3 4 2 5] these element are already present so you would have remaining is [1,1,2,3,4]

Now you have placed some elements in p and q, now traverse from highest to lowest element in p and place next biggest number that is not placed yet in q.

So, for 5 in p, place 4. for 4 in p, place 3. for 3 in p, place 2. for 2 in p, place 1, similarly do the same for q. So for 5 in q, place 1.

p 5 3 4 2 1

q 4 2 3 1 5

So this is the answer. Hope I have helped. This problem actually a lot more implementation specific.

Can you pls explain me how greedy aproach is working after filling array P and Q P 5 3 4 2 _ Q _ _ _ _ 5

and then iterating from 0 to n if p[i] is empty then put the missing maximum element of P in P[i] or if Q[i] is empty then put the missing maximum element of Q in Q[i].

Thank you I got it now.

Here is my explaination. Why we put the maximum missing element in p or q.

suppose array a = [4, 2, 7, 10, 10, 1, 6, 6, 9, 9]. if there is a permutation of n numbers then if one number got repeated then it will replace 1 number in order to get repeated. Here in this example 10, 9, 6 replaced 3, 5, 8 in order to get repeated.

After sorting the array vector<pair<int,int>> V in decreasing order V = 1 -> 5, 2 -> 1, 4 -> 0, 6 -> 8, 6 -> 9, 7 -> 2, 9 -> 6, 9 -> 7, 10 -> 3, 10 -> 4.

then filling the array P and Q as a = 4 2 7 10 10 1 9 9 6 6

p = 4 2 7 10 __ 1 9 _ 6 _

q = _ _ _ __ 10 _ _ 9 _ 6

In second step Traversing in V from i = 0 to n-1, if we attached V[i].first it to p, find the biggest number that did not appear in q and attach to q, vice versa.

Here is the reason why the biggest number that did not appear in p or q if a number got repeated so to make a valid permutation a smaller number must be replaced. Here repeated numbers are 10, 9, 6 or to fill the empty space by a small number which is 8, 5, 3. so it will make the valid permutations. biggest repeated number got replaced by biggest number which did not appear.

F is so fantastic! It's hard to solve, but not hard to understand the solution.

Can we see pretest after the contest. This submission failed pretest 2: Link

Take a look at Ticket 16674 from

CF Stressfor a counter example.Pretest 2 is every combination possible for $$$n \leq 5$$$, you can write a code then generate pretest 2 yourself.

I'm looking for problem like today problem D and C. Specially problems on arrays that can be transformed into problems on graph.

Example 1 : You want to obtains array b from array a with some specific operation

Example 2 : You want to obtains array a and b from array c with some specific operation

Example 3 : optimizing or computing something on an array after some operation (This turns out to be somewhat related to paths on a graph ...)

In almost all the solutions we need to build some graph with specific edges. I don't know how to tackle that kind of problems.

F let me feel :F

D let me feel :D

Problem C : Video Editorial Solution : link : https://youtu.be/d7Mb6pB4WKU

I got o(n) for C lolol. 188093045

nvm its o(nlogn)

sort(putP.rbegin(), putP.rend()) It is minimum O(n logn)

No comments

Since I didn't implement, please point out if I did anything wrong on F, or if my approach would TLE.

After the monotonic stack observation, it should be possible to use a kinetic tournament on quadratics to handle cases with $$$min(a_i,\ldots, a_j)=a_i$$$ and li-chao tree or another kinetic tournament otherwise. The time complexity would be $$$O(n2^{\alpha(n)}\log^2(n))$$$.

I cannot understand the editorial of Problem C, which says there are (i — 2)*2 + 2 numbers. (there can be a repetition of numbers in p and q) also, why is this a contradiction?

What do you mean by

"there can be a repetition of numbers in p and q"? $$$p$$$ and $$$q$$$ are permutations, they can't have any repeated numbers (although the same numbers that appear in $$$p$$$ also appear in $$$q$$$ since they are both permutations from $$$1$$$ to $$$n$$$).I was also confused, see the editorial

"after sorting"is mentioned then it is true. Completely forget the proof that is in editorial. I will explain it.Proof:

if there is some index a[i]<i(1-indexed) then it is not possible because

consider a = [5,2,4,1,4,3]

after sorting, 1 2 3 4 4 5, here a[i]<i (1-indexed) for index 5 as 4<5.

Here afterwards I am talking about the sorted array, not the original array

so note that all elements before this element 4(present in index 5(1-indexed) ) should have both p and q less than or equal to element 4, otherwise it is not possible, because consider you place element 5 for any previous index in a sorted array then maximum will be 5 so you have to place only element x (x<=4) for all previous index. So you would have placed till 4th index, the elements <=4, so in that case both 4's will be included already. So for this index 5 you wont have elements that are <=4 , you need atleast 10 numbers for index 5 which is not possible.

If you still have doubt ask. Would be happy to help

In the editorial of problem E, when calculating the intersection for f(p)<=2, the sum should be sum(i=0...n) instead of sum(i=1...n). Please fix it

Yes it is, I fixed the editorial.

I had a slightly different $$$O(n)$$$ 188071468 from the one given for Problem C.

No CHT solution for F? That's very interesting.

It is possible to use it to solve the second case, but you'll have to squeeze it into the tight ML.

It is a well know fact that n−cycles is the minimum number of swaps needed to get the permutation 1,2,3,…,n from our initial one (in other words, to sort it).

Can anyone Please provide me the material where i can see this tutorial and learn . Thank You!!.

Someone mentioned it. Each cycle of length $$$l$$$ needs $$$l - 1$$$ swaps to sort.

Thanks, i got it now .

Can anyone explain E in a simpler way ? I am having a hard time understanding the editorial..

I modified it a little bit, maybe you'll find it easier to read.

Ugh my solution to C FST'd due to TLE can someone tell me why :(( https://codeforces.com/contest/1768/submission/188118022

Here is the reason -> https://codeforces.com/blog/entry/48793

:((((( oh no I didn't know

Well, U know it now.

Is it possible for you to make a report on the channels that download solutions on YouTube during the contest? Very thanks.<3

Maybe I missed something, but why there is O(n*sqrt(n)) with [n, n-1, n-2, ..., 1] array? Or any similar.

In this subcase, $$$a_j < \sqrt{A}$$$.

I think this time aj is smaller than sqrtA, consider all the cases of such j, the total compexity of the j with same value will not exceed n, so the overall complexity will not exceed..nsqrtA sorry my poor english

What will be the expected rating of the first 3 questions?

⌊n−w+k−1⌋/k

could you please eplain me why we add K-1 with n-w ? .

so as to do the ceil operation otherwise it's by default floor operation as the integer division truncates anything after the decimal point

I'm having a hard time trying to understand the intersection formula for $$$f(p) \le 2$$$ from E's editorial. Can you please proofread the 'sketch and calculation' spoiler and fix some mistakes/typos?

I modified it a little bit, maybe you'll find it easier to read.

I mean I read for example this sentence:

In the last $$$n$$$ numbers there are $$$n$$$ numbers in range $$$[n+1,2n]$$$, we have used $$$1$$$ numbers for the first $$$n$$$ numbers. There are $$$C^n_{2n-1} \cdot n!$$$ cases.

I think you wanted to write:

In the last $$$2n$$$ numbers there are $$$n-1$$$ numbers in range $$$[n+1,2n]$$$, we have used $$$1$$$ numbers for the first $$$n$$$ numbers.

And if this is the case, then I don't really understand the $$$C^n_{2n-1} \cdot n!$$$ formula.

No, there are $$$n$$$ numbers, not $$$n - 1$$$. Since we used $$$1$$$ number to fill in the first $$$n$$$ numbers, there are only $$$2n-1$$$ options to choose for the last $$$n$$$ numbers, since they must be in range $$$[n + 1, 3n]$$$. I think the $$$n!$$$ part is easy to understand.

Edit: okay I think I spotted the wrong thing, it is fixed.

Ok, I see the interval in the third case was fixed. Now I get it. Thanks!

I still want to add something, maybe someone finds it helpful. I don't find the $$$n!$$$ parts easy to understand as they are right now in the editorial, I find them a bit unnatural if not just 'wrongly' explained. The third case actually counts the number of ways to fill the last $$$n$$$ positions. What are the other two cases counting exactly, including the $$$n!$$$ 's, explained with words?

This is how I would split it, each part counting one third of the positions:

This is much clearer, thanks a lot.

Kudo for lbm364dl, great explanation that help me a lot, take a long time to understand the editorial before found your comment.

Sorry for late reply, suppose we have $$$n$$$ fixed indexes for the numbers in range $$$[1, n]$$$, then there are $$$n!$$$ cases for these numbers switching places with each other, the second and third $$$n!$$$ are exactly the same.

In conclusion:

The combinatorics is how we choose indexes for number in a range.

The factorial is the number of cases after having fixed indexes.

The third one is $$$n!$$$ because we already chose indexes for $$$n$$$ numbers out of $$$2n$$$.

Anyway thank you for providing a much clearer explanation for this problem!

Problem C was a simple implementation problem I couldn't submit during the contest due to debugging issue, unlucky me but the contest was really great.

Here's my submission for problem C — 188127408

Hi guys I have made editorial videos on A,B,C,D and uploaded on the channel — https://www.youtube.com/@GrindCoding, you can have a look and let me know if you like the explanation or please provide your valuable feedbacks.

[D is currently being processed by youtube so might take a few mins to upload]

There's no reason to make the mod not fixed as something like 1e9 + 7 in problem E. Any fft solution that passes that mod will pass for any other mod that you might ask for.

Can someone figure out the reason of runtime error in my code ? https://codeforces.com/contest/1768/submission/188111711

Take a look at Ticket 16675 from

CF Stressfor a counter example.Any idea why I got Wrong Answer instead of Runtime?

During the contest in problem C I was getting WA so I tried to modify my solutions but now that the we can see the test cases it says "wrong output format Unexpected end of file — int32 expected"

The thing is that I used an array of size $$$10^5$$$ instead of $$$2 \times 10^5$$$

WA code

AC code

So sad, with this modification I got AC with my first attempt :(

In problem D,

Turns out that we can easily calculate cycles′ if we know cycles:

cycles′=cycles+1 if the vertices k and k+1 were in the same cycle in the initial graph, cycles′=cycles−1 otherwise.

Can someone explain this???

Here is the explanation

You can understand it with

Group Theory: explanation + codeI had a slightly different solution for C. Instead of sorting, you can use the upper_bound function to find the biggest number that hasnt appeared yet.

Submission: https://codeforces.com/contest/1768/submission/188130191

thanks for the great round <3

finally become pupil after 82 contest !!

Somebody please help me with my submission of problem C . https://codeforces.com/contest/1768/submission/188118465 Can't able to detect error.

Take a look at Ticket 16676 from

CF Stressfor a counter example.Can someone explain for problem Lucky Permutation:

Turns out that we can easily calculate cycles′ if we know cycles:cycles′=cycles+1 if the vertices k and k+1 were in the same cycle in the initial graph,cycles′=cycles−1 otherwise.It's not easy to explain. I noticed this by using brute force on some small cases, but I can't prove it until the end of contest.

Cycles are for sort the array, we want 1 inversion. Let's say $$$i$$$ is connected with $$$x$$$ and ($$$i$$$+1) is connected with $$$y$$$.for inversion, we break the link from $$$i$$$ to $$$x$$$ and ($$$i$$$+1) to $$$y$$$ and make a new link from $$$i$$$ to $$$y$$$ and ($$$i$$$+1) to $$$x$$$. That's it, now if we analyse breaking and making link for $$$i$$$ and $$$i$$$+1 ,

we can see if $$$i$$$ and $$$i$$$+1 are from the same cycle they will brake the cycle and we have 2 cycles from the 1 cycle.

If $$$i$$$ and $$$i$$$+1 in different cycle they will join together and make 1 cycle from joining 2 cycles.

i hope it is understandable.

graphNice explanation

Thanks

"If we iterate from the smallest value to the top, there will be scenarios where all the remaining positions i will result in max(p[i],q[i])≥a[i] because you don't have enough smaller integers." This is written in the tutorial of problem C. Can anyone pls provide me a testcase where this scenario happens?

5 5 2 2 1

In this case, there are no enough place for 3,4,5 to put in.

But this test case anyways has no solution, provide a test case in which iterating from the smallest value give wrong answer.

can anyone pls tell me my mistake in problem C 188133899

Take a look at Ticket 16677 from

CF Stressfor a counter example.Why does my submission for C give TLE although it looks nLog(n).

Spoilerhttps://codeforces.com/contest/1768/submission/188114920

You are using the function upper_bound(something). Instead, use setname.upper_bound(int). The one you ar eusing can run O(n) sometimes and is bad. The one I mentioned uses binary search on sets and is much faster

can anyone please help me in figuring out why is this code of mine giving runtime error on test 7? tried enough not able to figure out.188129954

F is cool!

Is "1. min(ai...aj)>=A and 2. min(ai...aj)<A" (in F's Tutorial) typo ?

I think they should be sqrt(A).

Thanks! It's a typo, should be fixed now.

Got the idea for D after the contest lol

Video Solutions for A-E

Nlog(n) code giving Tle for problem C please help! here is the code 188134958

You are using the function upper_bound(something). Instead, use setname.upper_bound(int). The one you ar eusing can run O(n) sometimes and is bad. The one I mentioned uses binary search on sets and is much faster

In vector upper-bound is log(n) right? So why not in sets?

It is not. The normal upper_bound() function works differently and at worst cases might iterate over the entire vector/set. But there is a special upper_bound() function for sets. Use setname.upper_bound(x). This is actual logn

Thanks a lot!

A approach to Problem D using Group theory ,

Link To solution : 188139688

If Permutation is not sorted, then it will contain some cycles, using Cycle Decomposition, we can break the Cycle of length

kinto** k – 1 Transpose** (Two Length cycles). If Identity transpose ex (1 3) is multiplied to itself ( 1 3 ) => it will cancel the effect , i.e. Elements have been placed to their correct respective location . So to make the permutation sorted, if there are k transpose, we can multiple k identity transpose, thus canceling out the effect and make them sit on their place.Note : sorted permutation means zero Inversion.And at last, do multiple any transpose of adjacent elements ( 3 4 ) or (1 2 ) or ( 5 6 ) , etc. to get One Extra Inversion .So, using DFS one can check for Cycles, find the length of cycles, cycle length – 1 is the transpose.

So

`answer = total no of transpose from all cycles + 1 [ General case ]`

(for last extra One Inversion that is been added on top of sorted permutation).There is an edge case, what if one adjacent transpose is already present in one of the cycles, For example (1,2) is already present, and this contributes to only one Inversion, so we can take help of already present good transpose for this case

`note: we only need any One good transpose (adject transpose) .`

Let’s say good transpose is T , so first , in general case , we will multiply T with T to cancel out T and make permutation sorted, then again multiply T to add extra one inversion . So we can skip multiplication of T two(x2 ) times , because at last we want to use T as good transpose .`T x T x T = T`

( extra multiplication of T two times ) so we can subtract 2 operation from the general case answer .

`Ans = ( transpose + 1 ) – 2 [ when good transpose is already present in any of the cycles`

Fucking shit I have been associated with a psychopath

Can somehelp me find the bug in my code.

It's giving a wrong output on 7345th test case in test2.

Here the link of my code-https://codeforces.com/contest/1768/submission/188142179

Isn't a case possible in D where number of cycles will remain same?

Why does my solution for C work when using

`stack`

but not`unordered_map`

? Solution using`unordered_map`

: Solution Solution using`stack`

: Solution I am doing the same thing in both of them, except it works when I use`stack`

instead of`unordered_map`

. I see it gives wrong answer on test case 2, but I can't see the test case. Can someone give a test case that doesn't work for`unordered_map`

? Thanks.When you do it=extra.begin() when extra is an unordered_map, It's not guaranteed which element you will get, so probably it->second==true for both it you get for a certain i, which cause i appear 2 times in q.

But I'm taking the iterator, then erasing it before I get the next element. Shouldn't it delete the one I just used?

It's not "getting the one just used". It's "There might be multiple entries where it->second==true and you get 2 such entries for one x, then you put two x in q"

Can you give me an example of when this would happen? Thanks.

It depends on the implementation of the iterator of unordered_map, so there's no determinate example.

But why would it work when I use a stack? Couldn't this also happen with a stack???

Stack is an ordered data structure, you always get what you just put into it

So the two elements I get are guaranteed to be one in p, and one in q, right?

Yes

Thanks!!!

i am not improving._. may be i will improving

The problemset should should have a tag for permutations, to practice for these kinds of problems.

Can someone explain why there is a +k in the final result of problem B, and not just (n-w)/k??

The reason is because we want to using ceiling division. If we used (n — w) / k, we would round down.

Permforces

C took me over an hour to implement...

Yet another $$$O(n)$$$ solution for C, but can be implemented more easily. Without the headers, it's only 700 B long with two

`for`

loops.solutionIterate from the smallest element to the largest. If a number $$$x$$$ appears only once at index $$$i$$$, then $$$p[i]=q[i]=x$$$. If it never appears, push it into a set. If it appears twice at indices $$$i$$$ and $$$j$$$, then remove any element $$$y$$$ from the set (I use a stack to implement). If the set is empty, then it's impossible; otherwise, $$$p[i]=q[j]=x$$$ and $$$p[j]=q[i]=y.$$$ If it appears more times, it's impossible. Iterating from the largest to the smallest is ok, too.

Is $$$O(n)$$$ solution for C too hard to think? Why not hack $$$O(n \log n)$$$ solutions?

How to prove in C that a[i]>I for all i ?

Consider this case:

The missing number here is 4, but the the 2nd element is 1, we cannot possibly construct this because if we put the missing element in the position, we'll get

Which is: 4 4 2 3 5

However, if our array was like this: 1 3 3 4 5

The missing element is 2, and we can construct an array like this:

Which results in the correct array!

Okay thanks for the help.

Hello

Can anyone help why my code is giving wrong answer . Although it is not optimal ,but I am not getting where I am wrong . Pls help My submission ... Thanyou

Take a look at Ticket 16678 from

CF Stressfor a counter example.Can someone help explaining why in the editorial for F part 2.2 $$$min(a_i…a_j)=a_j$$$, iterating $$$i$$$ the way mentioned results in a total complexity of $$$O(N\sqrt{A})$$$ amortized ? Thanks in advance.

for aj with the same value which is smaller than sqrtA, the total complexity will not exceed n.

Very frustrated to say I was able to solve C during the contest but due to the silly mistake of not printing extra space at the end of the first two outputs it gave the wrong answer. I left the solution unchecked, woke up in the morning, saw the test case failing, checked the code, found the silly mistake, and got AC.

I am not able to digest this fact .

Consider there is some index that a[i]<i, then both p[i]<i and q[i]<i must satisfy. This is also true for the first i−1 index, so the numbers that are smaller than i in both p and q are (i−1)×2+2=i∗2. This is a contradiction.Pls help me out

Thank you

B is more difficult for me than C..

Can someone help me to find the reason for TLE in Problem C for the submission 188102874

But an AC for the submission 188105380

use set.lower_bound(value) instead of set.lower_bound(start,end,value). The latter costs much more time.

Thanks!! Got Accepted now

lower_bound on set is linear time, use set.lower_bound instead

Thanks

At Line 157 use auto it = s.lower_bound(-q[i]); O(n^2)->O(nlogn)

ok thanks

The Submission 188119572 is Successfully Hacked but the Participant got points for the problem. How is This possible?

It's hacked after contest ends

Problem C Eternal Decompress Video Editorial : Link: https://youtu.be/d7Mb6pB4WKU

Concise solution for D:

~~~~~

I'm still curious about that "the minimum number of swaps" theory in problem D, is there any prove of that theory (blog or something)?

the minimum number of swaps to sort is the classic problem, here is link

Thx :)

Explanation : Link to comment Group theory has prove for this

About D, How they know the way to solve this problem during the contest? I mean is this a classical question ? Or they just figure out?

i'm interesting of how could they just know whatever what is swaping in a cycle it will only minus 1,and whatever what is swaping between two cycle ,it must cost one movement to change it to the answer Do they prove it or just consider it should work

If someone had knowledge of Group Theory , then it is a clasical problem for them . Here is a explanation which might help : Link

can anyone tell what is wrong in my code I have used visited array for solving problem c https://codeforces.com/contest/1768/submission/188190772

Take a look at Ticket 16679 from

CF Stressfor a counter example.Though my rating falls drastically in this contest. I love both the contest and the editorial. Keep organizing such contests Vladithur ❤️.

Loved the contest, amazing problems, amazing editorial!!

By the way,

for problem C: 1768C — Elemental Decompress

Another Way HereHow can i improve the time so i dont get TLE https://codeforces.com/contest/1768/submission/188205457

Can anyone explain or tell about resources where i can learn about

counting the number of cycles in a directed graph. as a can't find it online. thanksI am just really glad this contest happened and would like to thank the authors of this round, as finally I could reach expert after this round.

can any one plzzz suggest a roadmap to be good at compeitive programming

At first ,i cnt not believe a so easily

Problem C Please someone help me with my code of Problem C I am not able to understand why there is a out of range error Help will be highly appreciated

I can share you how I solved the problem. so basically I just kept the indexes of all the elements of the a with count of how much is number is occurring . since with some casework we can find that the number can occur only once or twice or none at all. so its just pairing the numbers that occur 2 times with the ones with 0 times. and place on the both arrays with what occurred one time at same place. since

Code hereTake a look at Ticket 16680 from

CF Stressfor a counter example.Can anyone tell why it is giving TLE (Div2 C) : https://codeforces.com/contest/1768/submission/188232190

I love F!I think it is a quite good problem!

In F tutorial,Is the "Just maintain the leftmost occurences" for the 2.1 cases a typo?Seems that it needs to maintain the rightmost occurences<j from 1 to √A

Should be fixed now.

In problem D, Can we solve it by using cyclic sort technique? I am not able to figure it out that-> say by cyclic sort, we get n cycles as ans. Then how we will decide ans to be n+1 or n-1. What I know, by cyclic sort method, we get the minimum swaps to sort the array. Anyone please help

The front problem is too easy but the later problem is too difficult.

Problem F is awesome. Couldn't solve it during the contest. After the contest, I looked at the "$$$a_i \le n$$$" hint from the editorial and solved it from there :) Sometimes just stressing a part of the statement can help you solve a problem :)

On problem D, cycles' = cycles + 1 if there are no adjacent connected components, not the opposite right?

F is a really good problem, I thought $$$O(n\sqrt n)$$$ solution for a long time during the contest but still did not know how to solve it. But later I was amazed by the tutorial of problem F :)

The facts to solve this problem are easy to understand and easy to prove, but it's really hard to find them :)

why we need to Compare min(ai…aj)⋅(j−i)2 with n⋅(j−i)?

Video solutions for A,B,C

https://youtu.be/erOqAwknRJU

Need some help with a failed test case in problem C. 193152726

Take a look at Ticket 16729 from

CF Stressfor a counter example.Consider there is some index that a[i]<i , then both p[i]<i and q[i]<i must satisfy. This is also true for the first i−1 index, so the numbers that are smaller than i in both p and q are (i−1)×2+2=i∗2 . This is a contradiction.

what does this mean can anyone explain this with an example please