codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1768.md (24885B)


      1 Source: https://codeforces.com/blog/entry/110901
      2 
      3 Hope you liked the problems!
      4 
      5 **(from thanhchauns2) Before the round starts**
      6 
      7 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!
      8 
      9 **Testers' predictions**
     10 
     11 | Tester | A | B | C | D | E | F |
     12 | --- | --- | --- | --- | --- | --- | --- |
     13 | [xiaoziya](/profile/xiaoziya "International Grandmaster xiaoziya") | 900 | 1000 | 1400 | 1800 | 2100 | 3000 |
     14 | [feecle6418](/profile/feecle6418 "Grandmaster feecle6418") | 900 | 1200 | 1400 | 1700 | 2200 | 2900 |
     15 | [cadmiumky](/profile/cadmiumky "Candidate Master cadmiumky") | 800 | 1100 | 1550 | 1900 | 2200 | - |
     16 | [6aren](/profile/6aren "Grandmaster 6aren") | 800 | 1200 | - | 2000 | 2200 | - |
     17 | [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Grandmaster neko_nyaaaaaaaaaaaaaaaaa") | 800 | - | - | 2100 | 2400 | 3000 |
     18 | [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") | 800 | 1100 | 1550 | 1800 | 2100 | 2550 |
     19 
     20 **Some moments in the rating section**
     21 
     22 **From neko_nyaaaaaaaaaaaaaaaaa**
     23 
     24 ![ ](/predownloaded/5d/65/5d65c276208c9b2e569d380bbda93f4e83082348.png)
     25 
     26 **From hoangquan05112002**
     27 
     28 ![ ](/predownloaded/b4/82/b482aaa9bc39c7816bd88d248e5be48fd4ff615c.png)
     29 
     30 **From _Astraea_**
     31 
     32 ![ ](/predownloaded/da/62/da62050a988b056c1fac742ab729cb2ddd5c52ea.png)
     33 
     34 **From Valenz**
     35 
     36 ![ ](/predownloaded/93/37/9337cc5f610116785d347bc54b3e8972531f32f4.png)
     37 
     38 **From TrendBattles**
     39 
     40 ![ ](/predownloaded/9f/94/9f94f05c0c6ec75e565749bb0c546ee3bb729e68.png)
     41 
     42 **Some comments from testers and authors**
     43 
     44 **From hoangquan05112002**
     45 
     46 ![ ](/predownloaded/af/c1/afc129222ef1a134ce1c5c014f6351c83d478f98.png)
     47 
     48 **From cadmiumky**
     49 
     50 ![ ](/predownloaded/6b/25/6b259efa427f11769c3cc091688706eab355af1b.png)
     51 
     52 **From shiwei**
     53 
     54 ![ ](/predownloaded/b9/c2/b9c24434ff6ff1ac26421589c98a3fa08f79f11b.png)
     55 
     56 **From DMCS and DeMen100ns**
     57 
     58 ![ ](/predownloaded/cc/ef/ccef503546d451c672a3386c6778f04202d6f8ba.png)
     59 
     60 **tfg discussing problem F**
     61 
     62 ![ ](/predownloaded/6c/b9/6cb9b75fe7067ad625ea036ef3d6481836bf32db.png) ![ ](/predownloaded/71/06/7106f493d4955fa32fea8e41ecf9a4f4fa6c4449.png) ![ ](/predownloaded/ec/28/ec2825dbe2cd5de8ea55c7c15cd78e433e90a328.png)
     63 
     64 **From feecle6418**
     65 
     66 ![ ](/predownloaded/35/fa/35fab8fe5ff2a35eb23215b8ebfa595e1961db8f.png)
     67 
     68 **tibinyte and fextivity about problem A**
     69 
     70 ![ ](/predownloaded/38/6a/386afa83a33d9b906596610ed420a2ae16809b0d.png)
     71 
     72 **neko_nyaa and errorgorn about problem A**
     73 
     74 ![ ](/predownloaded/54/74/54748e1ab9e34c6da9f3179ad6b50fc1a0d6d8f8.png)
     75 
     76 **From hoangquan05112002 again**
     77 
     78 ![ ](/predownloaded/fb/07/fb078facc7dc287e25b43269476d35a02f29451f.png)
     79 
     80 **From darkkcyan**
     81 
     82 ![ ](/predownloaded/e0/f0/e0f08913064830fca47bc67665c4754d4263b1f0.png)
     83 
     84 **From QuangBuiCP**
     85 
     86 ![ ](/predownloaded/ec/69/ec69f8aca25c0fd4703e8bb293374ff43e862573.png)
     87 
     88 **From tibinyte, the Russian sentence is `use English please`**
     89 
     90 ![ ](/predownloaded/55/11/5511d014254297ea923162403d5b01c05ee3842e.png)
     91 
     92 **From errorgorn**
     93 
     94 ![ ](/predownloaded/8c/1a/8c1a659185adef908106540e22bb5ce4f50a047f.png)
     95 
     96 **From SPyofgame**
     97 
     98 ![ ](/predownloaded/00/11/00116ee666748b67607e9aef12fd701c3ef93f40.png)
     99 
    100 [1768A - Greatest Convex](/contest/1768/problem/A "Codeforces Round 842 (Div. 2)")
    101 
    102 Author: [thanhchauns2](/profile/thanhchauns2 "Candidate Master thanhchauns2")
    103 
    104 **Hints**
    105 
    106 **Hint 1**
    107 
    108 Try to brute force for $k \lt 50$. Do you see anything suspicious?
    109 
    110 **Hint 2**
    111 
    112 Now try to brute force from $k - 1$ to $0$ for large numbers.
    113 
    114 **Tutorial**
    115 
    116 ### [1768A- Greatest Convex](https://codeforces.com/contest/1768/problem/A)
    117 
    118 Is $x = k - 1$ always suitable?
    119 
    120 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$.
    121 
    122 Therefore, $x = k - 1$ is the answer.
    123 
    124 Time complexity: $\mathcal{O}(1)$
    125 
    126 **Solution**
    127 
    128 ```
    129 answer = [print(int(input()) - 1) for testcase in range(int(input()))]
    130 ```
    131 
    132 **Feedback**
    133 
    134 * Good problem
    135 * Average problem
    136 * Bad problem
    137 
    138 [1768B - Quick Sort](/contest/1768/problem/B "Codeforces Round 842 (Div. 2)")
    139 
    140 Author: [Vladithur](/profile/Vladithur "Master Vladithur") Preparation: [Vladithur](/profile/Vladithur "Master Vladithur") and [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
    141 
    142 **Hints**
    143 
    144 **Hint 1**
    145 
    146 Try to have the last $k + 1$ numbers sorted.
    147 
    148 **Hint 2**
    149 
    150 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.
    151 
    152 **Hint 3**
    153 
    154 Fix the set of numbers $1,2,3,\ldots$
    155 
    156 **Tutorial**
    157 
    158 Tutorial is loading...
    159 
    160 **Solution**
    161 
    162 ```
    163 #include <bits/stdc++.h>
    164 
    165 #define all(x) (x).begin(), (x).end()
    166 #define allr(x) (x).rbegin(), (x).rend()
    167 #define gsize(x) (int)((x).size())
    168 
    169 const char nl = '\n';
    170 typedef long long ll;
    171 typedef long double ld;
    172 
    173 using namespace std;
    174 
    175 void solve() {
    176     int n, k;
    177     cin >> n >> k;
    178     vector<int> p(n);
    179     for (int i = 0; i < n; i++) cin >> p[i];
    180     
    181     int c_v = 1;
    182     for (int i = 0; i < n; i++) {
    183         if (p[i] == c_v) c_v++;
    184     }
    185     
    186     cout << (n  - c_v + k) / k  << nl;
    187 }
    188 
    189 int main() {
    190 	ios::sync_with_stdio(0); cin.tie(0);
    191 	
    192 	int T;
    193 	cin >> T;
    194 	while (T--) solve();
    195 }
    196 ```
    197 
    198 **Feedback**
    199 
    200 * Good problem
    201 * Average problem
    202 * Bad problem
    203 
    204 [1768C - Elemental Decompress](/contest/1768/problem/C "Codeforces Round 842 (Div. 2)")
    205 
    206 Author: [thanhchauns2](/profile/thanhchauns2 "Candidate Master thanhchauns2")
    207 
    208 **Hints**
    209 
    210 **Hint 1**
    211 
    212 How many times a unique number can appear in the array $a$?
    213 
    214 **Hint 2**
    215 
    216 Can there be two numbers $1$ in $a$? What is the conclusion?
    217 
    218 **Hint 3**
    219 
    220 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?
    221 
    222 **Hint 4**
    223 
    224 Which element should you construct first?
    225 
    226 **Tutorial**
    227 
    228 ### [1768C- Elemental Decompress](https://codeforces.com/contest/1768/problem/C)
    229 
    230 Two cases produce no answers:
    231 
    232 * One element appears more than twice in $a$.
    233 * After sorting, there is some index that $a[i] \lt i$ ($1$-indexed).
    234 
    235 **Proof**
    236 
    237 Consider there is some index that $a[i] \lt i$, then both $p[i] \lt i$ and $q[i] \lt 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.
    238 
    239 Otherwise, solutions always exist. One method is to constructively attach each element in $a$ to $p$ or $q$:
    240 
    241 * 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$.
    242 * 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.
    243 
    244 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>`.
    245 
    246 Time complexity: $\mathcal{O}(n \log(n))$
    247 
    248 **Solution**
    249 
    250 ```
    251 #include <bits/stdc++.h>
    252 
    253 using namespace std;
    254 
    255 const int N = 200005;
    256 int n;
    257 int a[N], b[N], c[N], ra[N], rb[N];
    258 
    259 void out()
    260 {
    261 	for (int i = 0; i < n; i++)
    262 	{
    263 		cout << a[i] << ' ';
    264 	}
    265 	cout << '\n';
    266 	
    267 	for (int i = 0; i < n; i++)
    268 	{
    269 		cout << b[i] << ' ';
    270 	}
    271 	cout << '\n';
    272 }
    273 
    274 void solve()
    275 {
    276 	cin >> n;
    277 	vector<pair<int, int> > V;
    278 	for (int i = 0; i < n; i++)
    279 	{
    280 		cin >> c[i];
    281 		a[i] = b[i] = 0;
    282 		ra[i + 1] = rb[i + 1] = 1;
    283 		V.push_back(make_pair(c[i], i));
    284 	}
    285 	sort(V.rbegin(), V.rend());
    286 	
    287 	for (int i = 0; i < n; i++)
    288 	{
    289 		int k = V[i].second;
    290 		if (ra[c[k]] == 1) a[k] = c[k], ra[c[k]]--;
    291 		else b[k] = c[k], rb[c[k]]--;
    292 	}
    293 	
    294 	int r1 = n, r2 = n;
    295 	for (int i = 0; i < n; i++)
    296 	{
    297 		int k = V[i].second;
    298 		if (a[k] == 0)
    299 		{
    300 			while (ra[r1] == 0) r1--;
    301 			ra[r1]--;
    302 			if (r1 > b[k])
    303 			{
    304 			    cout << "NO" << '\n';
    305 			    return;
    306 			}
    307 			a[k] = r1--;
    308 		}
    309 		else
    310 		{
    311 			while (rb[r2] == 0) r2--;
    312 			rb[r2]--;
    313 			if (r2 > a[k])
    314 			{
    315 			    cout << "NO" << '\n';
    316 			    return;
    317 			}
    318 			b[k] = r2--;
    319 		}
    320 	}
    321 	for (int i = 1; i <= n; i++)
    322 	{
    323 		if (ra[i] != 0 || rb[i] != 0)
    324 		{
    325 			cout << "NO" << '\n';
    326 			return;
    327 		}
    328 	}
    329 	cout << "YES" << '\n';
    330 	out();
    331 }
    332 
    333 int main(int argc, char* argv[])
    334 {
    335 	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    336 	int t;
    337 	cin >> t;
    338 	while(t--)
    339 		solve();
    340 }
    341 ```
    342 
    343 **Yet another better solution**
    344 
    345 There is actually a $O(n)$ solution to this problem.
    346 
    347 **Fresh meme from SPyofgame to the intended solution of the author**
    348 
    349 ![ ](/predownloaded/00/11/00116ee666748b67607e9aef12fd701c3ef93f40.png)
    350 
    351 **Step 1**
    352 
    353 If there are at least $k \gt 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.
    354 
    355 **Proof**
    356 
    357 Since we need the condition $a[i] = max(p[i], q[i])$, hence $p[i] = a[i]$ or/and $q[i] = a[i]$.
    358 
    359 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**).
    360 
    361 **Approach**
    362 
    363 ```
    364     /// Storing position of each a[i]
    365     vector<vector<int> > b(n + 1);
    366     for (int i = 1; i <= n; ++i) {
    367         b[a[i]].push_back(i);
    368 
    369         /// max(p[i], q[i]) = a[i] so either p[i] = a[i] or/and q[i] = a[i]
    370         /// so if the number appear the third time or more, then "NO"
    371         if (b[a[i]].size() >= 3) {
    372             cout << "NO\n";
    373             return 0;
    374         }
    375     }
    376 ```
    377 
    378 **Step 2**
    379 
    380 Since we have the
    381 
    382 Unable to parse markup [type=CF_MATHJAX]
    383 
    384 function, we need to use the larger value firsts.
    385 
    386 **Proof**
    387 
    388 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.
    389 
    390 **Approach**
    391 
    392 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]$.
    393 
    394 ```
    395     /// Initialize permutation p[1..n], q[1..n]
    396     vector<int> p(n + 1, -1), q(n + 1, -1);
    397 
    398     /// Initialize permutation position, fp[p[i]] = i, fq[q[i]] = i
    399     vector<int> fp(n + 1, -1), fq(n + 1, -1);
    400     for (int x = n; x >= 1; --x) {
    401         for (int i : b[x]) {
    402             /// Because of max(), we must save up the smaller value
    403             /// So we assign p[i] or q[i] by x, one by one from x large -> small
    404                  if (fp[x] == -1) p[fp[x] = i] = x;
    405             else if (fq[x] == -1) q[fq[x] = i] = x;
    406         }
    407     }
    408 ```
    409 
    410 **Step 3**
    411 
    412 We fill the remaining integers that wasn't used, from the largest to the smallest.
    413 
    414 **Approach**
    415 
    416 We use $vp$ as the largest integer not used in permutation $p[1..n]$.
    417 
    418 We use $vq$ as the largest integer not used in permutation $q[1..n]$.
    419 
    420 Then for each of the value $x = n \rightarrow 1$, we assign to $p[i], q[i]$ that was not used.
    421 
    422 ```
    423     for (int x = n, vp = n, vq = n; x >= 1; --x) {
    424         for (int i : b[x]) {
    425             /// Assign the remaining integers
    426             while (fp[vp] != -1) --vp;
    427             while (fq[vq] != -1) --vq;
    428             if (p[i] == -1 && vp > 0) p[fp[vp] = i] = vp;
    429             if (q[i] == -1 && vq > 0) q[fq[vq] = i] = vq;
    430         }
    431     }
    432 ```
    433 
    434 **Step 4**
    435 
    436 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]$.
    437 
    438 **Approach**
    439 
    440 Just iterate through each element as normal.
    441 
    442 ```
    443     for (int i = 1; i <= n; ++i) {
    444         if (max(p[i], q[i]) != a[i]) {
    445             /// Statement condition is not satisfied
    446             cout << "NO\n";
    447             return 0;
    448         }
    449     }
    450 
    451     /// Output the answer
    452     cout << "YES\n";
    453     for (int i = 1; i <= n; ++i) cout << p[i] << " "; cout << "\n";
    454     for (int i = 1; i <= n; ++i) cout << q[i] << " "; cout << "\n";
    455 ```
    456 
    457 **Bonus**
    458 
    459 There is also another way that you can skip testing if $max(p[i], q[i]) = a[i])$ is correct.
    460 
    461 But the proof is a bit harder to understand, so I prefer using this code instead.
    462 
    463 **Full Code**
    464 
    465 ```
    466 #include <iostream>
    467 #include <vector>
    468 
    469 using namespace std;
    470 
    471 int query()
    472 {
    473     /// Input number of element
    474     int n;
    475     cin >> n;
    476 
    477     /// Input the array a[1..n]
    478     vector<int> a(n + 1);
    479     for (int i = 1; i <= n; ++i)
    480         cin >> a[i];
    481 
    482     /// Storing position of each a[i]
    483     vector<vector<int> > b(n + 1);
    484     for (int i = 1; i <= n; ++i) {
    485         b[a[i]].push_back(i);
    486 
    487         /// max(p[i], q[i]) = a[i] so either p[i] = a[i] or/and q[i] = a[i]
    488         /// so if the number appear the third time or more, then "NO"
    489         if (b[a[i]].size() >= 3) {
    490             cout << "NO\n";
    491             return 0;
    492         }
    493     }
    494 
    495     /// Initialize permutation p[1..n], q[1..n]
    496     vector<int> p(n + 1, -1), q(n + 1, -1);
    497 
    498     /// Initialize permutation position, fp[p[i]] = i, fq[q[i]] = i
    499     vector<int> fp(n + 1, -1), fq(n + 1, -1);
    500     for (int x = n; x >= 1; --x) {
    501         for (int i : b[x]) {
    502             /// Because of max(), we must save up the larger value
    503             /// So we assign p[i] or q[i] by x, one by one from x large -> small
    504                  if (fp[x] == -1) p[fp[x] = i] = x;
    505             else if (fq[x] == -1) q[fq[x] = i] = x;
    506         }
    507     }
    508 
    509     for (int x = n, vp = n, vq = n; x >= 1; --x) {
    510         for (int i : b[x]) {
    511             /// Assign the remaining integers
    512             while (fp[vp] != -1) --vp;
    513             while (fq[vq] != -1) --vq;
    514             if (p[i] == -1 && vp > 0) p[fp[vp] = i] = vp;
    515             if (q[i] == -1 && vq > 0) q[fq[vq] = i] = vq;
    516         }
    517     }
    518 
    519     for (int i = 1; i <= n; ++i) {
    520         if (max(p[i], q[i]) != a[i]) {
    521             /// Statement condition is not satisfied
    522             cout << "NO\n";
    523             return 0;
    524         }
    525     }
    526 
    527     /// Output the answer
    528     cout << "YES\n";
    529     for (int i = 1; i <= n; ++i) cout << p[i] << " "; cout << "\n";
    530     for (int i = 1; i <= n; ++i) cout << q[i] << " "; cout << "\n";
    531     return 0;
    532 }
    533 
    534 signed main()
    535 {
    536     ios::sync_with_stdio(NULL);
    537     cin.tie(NULL);
    538 
    539     int q = 1; /// If there is no multiquery
    540     cin >> q;  /// then comment this
    541 
    542     while (q-->0)
    543     {
    544         /// For each query
    545         query();
    546 
    547     }
    548 
    549     return 0;
    550 }
    551 ```
    552 
    553 **Feedback**
    554 
    555 * I reached $O(n \log n)$ solution.
    556 * I reached $O(n)$ solution.
    557 
    558 **Feedback**
    559 
    560 * Good problem
    561 * Average problem
    562 * Bad problem
    563 
    564 [1768D - Lucky Permutation](/contest/1768/problem/D "Codeforces Round 842 (Div. 2)")
    565 
    566 Author: [Vladithur](/profile/Vladithur "Master Vladithur") Preparation: [Vladithur](/profile/Vladithur "Master Vladithur") and [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
    567 
    568 **Hints**
    569 
    570 **Hint 1**
    571 
    572 There are $n - 1$ permutations of length $n$ that have exactly one inversion in them.
    573 
    574 **Hint 2**
    575 
    576 This problem is similar to finding the minimum number of swaps needed to sort a permutation.
    577 
    578 **Hint 3**
    579 
    580 Try looking at the permutation like a graph.
    581 
    582 **Hint 4**
    583 
    584 Try to find the number of cycles in each of the $n - 1$ graphs.
    585 
    586 **Tutorial**
    587 
    588 Tutorial is loading...
    589 
    590 **Solution**
    591 
    592 ```
    593 #include <bits/stdc++.h>
    594 
    595 #define all(x) (x).begin(), (x).end()
    596 #define allr(x) (x).rbegin(), (x).rend()
    597 #define gsize(x) (int)((x).size())
    598 
    599 const char nl = '\n';
    600 typedef long long ll;
    601 typedef long double ld;
    602 
    603 using namespace std;
    604 
    605 void solve() {
    606 	int n;
    607 	cin >> n;
    608 	vector<int> p(n);
    609 	for (int i = 0; i < n; i++) {
    610 		cin >> p[i]; p[i]--;
    611 	}
    612 	
    613 	int ind = 1, ans = 0;
    614 	vector<int> comp(n, 0);
    615 	for (int i = 0; i < n; i++) {
    616 		if (comp[i]) continue;
    617 		{
    618 			int v = i;
    619 			while (comp[v] == 0) {
    620 				comp[v] = ind;
    621 				v = p[v];
    622 				ans++;
    623 			}
    624 			
    625 			ind++; ans--;
    626 		}
    627 	}
    628 	
    629 	for (int i = 0; i < n - 1; i++) {
    630 		if (comp[i] == comp[i + 1]) {
    631 			cout << ans - 1 << nl;
    632 			return;
    633 		}
    634 	}
    635 	cout << ans + 1 << nl;
    636 }
    637 
    638 int main() {
    639 	ios::sync_with_stdio(0); cin.tie(0);
    640 	
    641 	int T;
    642 	cin >> T;
    643 	while (T--) solve();
    644 }
    645 ```
    646 
    647 **Feedback**
    648 
    649 * Good problem
    650 * Average problem
    651 * Bad problem
    652 
    653 [1768E - Partial Sorting](/contest/1768/problem/E "Codeforces Round 842 (Div. 2)")
    654 
    655 Author: [thanhchauns2](/profile/thanhchauns2 "Candidate Master thanhchauns2")
    656 
    657 **Hints**
    658 
    659 **Hint 1**
    660 
    661 Given a fixed permutation, how many operations do we need to sort it?
    662 
    663 **Hint 2**
    664 
    665 Keep in mind there is one already sorted permutation that doesn't need to be sorted.
    666 
    667 **Hint 3**
    668 
    669 What if there is exactly $1$ number in the range $[n + 1, 2n]$ that appears in the first $n$ numbers?
    670 
    671 **Hint 4**
    672 
    673 This is not really a hint, fft solutions exist, but we made sure most of them cannot pass.
    674 
    675 **Tutorial**
    676 
    677 ### [1768E- Partial Sorting](https://codeforces.com/contest/1768/problem/E)
    678 
    679 We need at most $3$ operations to sort the permutation: $1 - \gt 2 - \gt 1$
    680 
    681 * For $f(p) = 0$, there is only one case: the initially sorted permutation.
    682 
    683 **Calculate**
    684 
    685 `return (38912738912739811 & 1)`
    686 
    687 * For $f(p) \leq 1$, this scenario appears when the first $n$ numbers or the last $n$ numbers are in the right places.
    688 
    689 **Calculate**
    690 
    691 Both cases have $n$ fixed positions, so there will be $(2n!)$ permutations in each case.
    692 
    693 Intersection: since both cases share the $n$ middle elements, $(n!)$ permutation will appear in both cases.
    694 
    695 So there will be $2 \times (2n!) - (n!)$ such permutations.
    696 
    697 * 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]$.
    698 
    699 **Calculate**
    700 
    701 If the smallest $n$ elements are all in position from $1$ to $2n$, then:
    702 
    703 * There are $C_{2n}^{n}$ ways to choose $n$ positions for these numbers.
    704 * 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.
    705 * The total number of valid permuations are: $C_{2n}^{n} \times n! \times 2n!$
    706 
    707 If the largest $n$ elements are all in position from $n + 1$ to $3n$, we do the same calculation.
    708 
    709 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]$.
    710 
    711 Let `intersection = 0`
    712 
    713 **Sketch and calculation in details**
    714 
    715 Let's talk about the numbers in range $[n + 1, 2n]$. There are $n$ such numbers.
    716 
    717 . Imagine there are EXACTLY $i = 0$ numbers in this range that appear in the first $n$ numbers. So:
    718 
    719 * In the first $n$ numbers there are $n$ numbers in range $[1, n]$. There are $C_{n}^{n - 0} \times n!$ cases.
    720 * In the first $n$ numbers there are $0$ numbers in range $[n + 1, 2n]$. There are $C_{n}^{0} \times n!$ cases.
    721 * 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.
    722 
    723 Then we have: `intersection +=` $C_{n}^{n - 0} \times C_{n}^{0} \times C_{2n - 0}^{n} \times n! \times n! \times n!$
    724 
    725 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!$
    726 
    727 How about there is EXACTLY $i = 1$ number in range $[n + 1, 2n]$ appearing in the first $n$ numbers?
    728 
    729 * In the first $n$ numbers there are $n - 1$ numbers in range $[1, n]$. There are $C_{n}^{n - 1} \times n!$ cases.
    730 * In the first $n$ numbers there are $1$ numbers in range $[n + 1, 2n]$. There are $C_{n}^{1} \times n!$ cases.
    731 * 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.
    732 
    733 Then we have: `intersection +=` $C_{n}^{n - 1} \times C_{n}^{1} \times C_{2n - 1}^{n} \times n! \times n! \times n!$
    734 
    735 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!$
    736 
    737 We do the same thing with remaining cases, all the way up to $i = n$.
    738 
    739 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! $
    740 
    741 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!$
    742 
    743 * For $f(p) \leq 3$, it will be the count of all valid permutations.
    744 
    745 **Calculate**
    746 
    747 `return __factorial(n * __number_of_sides_of_a_triangle)`
    748 
    749 Time complexity: $\mathcal{O}(n)$
    750 
    751 **Solution**
    752 
    753 ```
    754 #include <bits/stdc++.h>
    755 
    756 using namespace std;
    757 
    758 long long n, M;
    759 
    760 long long frac[3000005], inv[3000005];
    761 
    762 long long powermod(long long a, long long b, long long m)
    763 {
    764 	if (b == 0) return 1;
    765 	unsigned long long k = powermod(a, b / 2, m);
    766 	k = k * k;
    767 	k %= m;
    768 	if (b & 1) k = (k * a) % m;
    769 	return k;
    770 }
    771 
    772 void Ready()
    773 {
    774 	frac[0] = 1;
    775 	inv[0] = 1;
    776 	for (int i = 1; i <= 3000000; i++)
    777 	{
    778 		frac[i] = (frac[i - 1] * i) % M;
    779 	}
    780 	
    781 	inv[3000000] = powermod(frac[3000000], M - 2, M);
    782 	
    783 	for (int i = 3000000; i > 0; i--)
    784 	{
    785 		inv[i - 1] = (inv[i] * i) % M;
    786 	}
    787 }
    788 
    789 long long C(long long n, long long k)
    790 {
    791 	return ((frac[n] * inv[k]) % M * inv[n - k]) % M;
    792 }
    793 
    794 int main()
    795 {
    796 	cin >> n >> M;
    797 	Ready();
    798 	long long ans[4]{};
    799 	
    800 	// X = 0
    801 	
    802 	ans[0] = 1;
    803 	
    804 	// X = 1
    805 	
    806 	ans[1] = 2 * frac[2 * n] - frac[n] - ans[0] + M + M;
    807 	ans[1] %= M;
    808 	
    809 	// X = 2
    810 	
    811 	ans[2] = frac[2 * n];
    812 	ans[2] = ans[2] * C(2 *n, n) % M;
    813 	ans[2] = ans[2] * frac[n] % M;
    814 	ans[2] = ans[2] * 2 % M;
    815 	
    816 	for (int i = 0; i <= n; i++)
    817 	{
    818 		int sub = C(n, i);
    819 		sub = sub * C(n, n - i) % M;
    820 		sub = sub * C(2 * n - i, n) % M;
    821 		sub = sub * frac[n] % M;
    822 		sub = sub * frac[n] % M;
    823 		sub = sub * frac[n] % M;
    824 		ans[2] = (ans[2] - sub + M) % M;
    825 	}
    826 	ans[2] = (ans[2] - ans[1] + M) % M;
    827 	ans[2] = (ans[2] - ans[0] + M) % M;
    828 	
    829 	// X = 3
    830 	
    831 	ans[3] = frac[3 * n];
    832 	ans[3] = (ans[3] - ans[2] + M) % M;
    833 	ans[3] = (ans[3] - ans[1] + M) % M;
    834 	ans[3] = (ans[3] - ans[0] + M) % M;
    835 	
    836 	long long answer = ans[1] + 2 * ans[2] + 3 * ans[3];
    837 	answer %= M;
    838 	
    839 	cout << answer << endl;
    840 }
    841 ```
    842 
    843 **Feedback**
    844 
    845 * Good problem
    846 * Average problem
    847 * Bad problem
    848 
    849 [1768F - Wonderful Jump](/contest/1768/problem/F "Codeforces Round 842 (Div. 2)")
    850 
    851 Author: [Vladithur](/profile/Vladithur "Master Vladithur") Preparation: [Vladithur](/profile/Vladithur "Master Vladithur") and [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
    852 
    853 **Hints**
    854 
    855 **Hint 0**
    856 
    857 Use dynamic programming.
    858 
    859 **Hint 1**
    860 
    861 $a_i \le n$
    862 
    863 **Hint 2**
    864 
    865 Compare $\min(a_i \ldots a_j) \cdot (j - i)^2$ with $n \cdot (j - i)$.
    866 
    867 **Hint 3**
    868 
    869 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 \lt k \lt j$.
    870 
    871 **Hint 4**
    872 
    873 Two cases: $\min(a_i \ldots a_j) \ge \sqrt{n}$ and $\min(a_i \ldots a_j) \lt \sqrt{n}$.
    874 
    875 **Hint 5**
    876 
    877 Split $\min(a_i \ldots a_j) \lt \sqrt{n}$ into two more cases: $\min(a_i \ldots a_j) = a_i$ and $\min(a_i \ldots a_j) = a_j$.
    878 
    879 **Tutorial**
    880 
    881 Tutorial is loading...
    882 
    883 **Solution**
    884 
    885 ```
    886 #include <bits/stdc++.h>
    887 
    888 #define all(x) (x).begin(), (x).end()
    889 #define allr(x) (x).rbegin(), (x).rend()
    890 #define gsize(x) (int)((x).size())
    891 
    892 const char nl = '\n';
    893 typedef long long ll;
    894 typedef long double ld;
    895 
    896 using namespace std;
    897 
    898 const int K = 650;
    899 
    900 int main() {
    901 	ios::sync_with_stdio(0); cin.tie(0);
    902 	
    903 	int n;
    904 	cin >> n;
    905 	vector<ll> a(n);
    906 	for (int i = 0; i < n; i++) cin >> a[i];
    907 	
    908 	vector<ll> dp(n, 1e18);
    909 	dp[0] = 0;
    910 	
    911 	vector<int> st = {0};
    912 	for (int i = 1; i < n; i++) {
    913 		// Case 1
    914 		{
    915 			ll mi = a[i];
    916 			for (int j = i - 1; j >= max(0, i - K); j--) {
    917 				mi = min(mi, a[j]);
    918 				dp[i] = min(dp[i], dp[j] + mi * (i - j) * (i - j));
    919 			}
    920 		}
    921 		
    922 		// Case 2
    923 		if (a[i] <= K) {	
    924 			for (int j = i - 1; j >= 0; j--) {
    925 				dp[i] = min(dp[i], dp[j] + a[i] * (i - j) * (i - j));
    926 				if (a[j] <= a[i]) break;
    927 			}
    928 		}
    929 		
    930 		// Case 3 
    931 		{
    932 			for (int j: st) {
    933 				dp[i] = min(dp[i], dp[j] + a[j] * (i - j) * (i - j));
    934 			}
    935 			
    936 			if (a[i] <= K) {
    937 				while (!st.empty() && a[st.back()] >= a[i]) {
    938 					st.pop_back();
    939 				}
    940 				st.push_back(i);
    941 			}
    942 		}
    943 	}
    944 	
    945 	for (int i = 0; i < n; i++) cout << dp[i] << ' ';
    946 	cout << endl;
    947 }
    948 ```
    949 
    950 **Shorter solution (tfg)**
    951 
    952 ```
    953 #include <iostream>
    954 #include <vector>
    955 #include <chrono>
    956 #include <random>
    957 #include <cassert>
    958  
    959 std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
    960  
    961 int main() {
    962     std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    963     int n;
    964     std::cin >> n;
    965     std::vector<int> a(n);
    966     for(int i = 0; i < n; i++) {
    967         std::cin >> a[i];
    968     }
    969     std::vector<long long> dp(n, 1e18);
    970     dp[0] = 0;
    971     for(int i = 0; i < n; i++) {
    972         int dist = n / a[i] + 1;
    973         // take from behind
    974         for(int j = i-1; j >= 0 && i-j <= dist; j--) {
    975             dp[i] = std::min(dp[i], dp[j] + (long long) a[i] * (i - j) * (i - j));
    976             if(a[j] <= a[i]) break;
    977         }
    978         // propagate forward
    979         for(int j = i+1; j < n && j-i <= dist; j++) {
    980             dp[j] = std::min(dp[j], dp[i] + (long long) a[i] * (i - j) * (i - j));
    981             if(a[j] <= a[i]) break;
    982         }
    983         std::cout << dp[i] << (i + 1 == n ? '\n' : ' ');
    984     }
    985 }
    986 ```
    987 
    988 **Feedback**
    989 
    990 * Good problem
    991 * Average problem
    992 * Bad problem