Codeforces Round #804 (Div. 2) Editorial reupload

Revision en6, by tibinyte, 2022-10-31 00:15:29

Hints

Hint 1

Let $$$p[x]$$$ be the position of $$$x$$$ in permutation $$$a$$$.

Since $$$MEX([a_{p[0]}])=1$$$, the only possible position of $$$0$$$ in permutation $$$b$$$ is exactly $$$p[0]$$$.

Hint 2

Continuing this line of thought, where can $$$1$$$ be placed in permutation $$$b$$$?

Hint 3

Without loss of generality, we will assume that $$$p[0] \lt p[1]$$$.

If $$$p[2] \lt p[0]$$$, then how many possible positions can $$$2$$$ have in permutation $$$b$$$?

If $$$p[0] \lt p[2] \lt p[1]$$$, then how many possible positions can $$$2$$$ have in permutation $$$b$$$?

If $$$p[2] \gt p[1]$$$, then how many possible positions can $$$2$$$ have in permutation $$$b$$$?

Solution

Let $$$p[x]$$$ be the position of $$$x$$$ in permutation $$$a$$$.

Since $$$MEX([a_{p[0]}])=1$$$, the only possible position of $$$0$$$ in permutation $$$b$$$ is exactly $$$p[0]$$$.

Without loss of generality, we will assume that $$$p[0] \lt p[1]$$$. For every interval $$$[l,r]$$$ ($$$l \le p[0] \lt p[1]\le r$$$), $$$MEX([b_l,\ldots,b_r])$$$ must be at least $$$2$$$. For every other interval, $$$MEX([b_l,\ldots,b_r])$$$ cannot exceed $$$2$$$. The only position for $$$1$$$ which satisfies both of these constraints is exactly $$$p[1]$$$.

Let's consider the current interval $$$[l,r]$$$ as being $$$[p[0],p[1]]$$$.

If $$$p[2] \in [l,r]$$$, we can say that, for every interval $$$[x,y]$$$ ($$$x \le l \lt r \le y$$$), $$$MEX([b_x,\ldots,b_y])$$$ must be at least $$$3$$$. Similarly, for every other interval, $$$MEX([b_x,\ldots,b_y])$$$ cannot exceed $$$3$$$. Both of these constraints are only met if $$$2$$$ occurs in permutation $$$b$$$ on some position $$$p \in [l,r]$$$. Since only $$$2$$$ positions are currently occupied in $$$[l,r]$$$, the total number of similar permutations will be multiplied by $$$(r-l+1)-2$$$.

Otherwise, $$$2$$$ can be placed in permutation $$$b$$$ only on $$$p[2]$$$. Additionally, the current interval will be "extended" to include $$$p[2]$$$, resuting in either $$$[p[2],r]$$$ or $$$[l,p[2]]$$$.

After processing $$$0,1, \ldots, k-2$$$ and $$$k-1$$$, the algorithm for processing $$$k$$$ is very similar to the one presented earlier. If $$$p[k] \in [l,r]$$$, the answer gets multiplied by $$$(r-l+1)-k$$$. Otherwise, the current interval is extended to include $$$p[k]$$$.

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en42 English tibinyte 2022-11-06 21:29:15 0 (published)
en41 English tibinyte 2022-11-06 19:15:16 0 (saved to drafts)
en40 English Gheal 2022-10-31 22:14:25 0 (published)
en39 English Gheal 2022-10-31 22:12:04 16
en38 English Gheal 2022-10-31 22:11:13 13 Tiny change: 'er authors of round 804. We are v' -> 'er authors. We are v'
en37 English Gheal 2022-10-31 22:10:53 211
en36 English Gheal 2022-10-31 22:04:25 26
en35 English Gheal 2022-10-31 22:03:40 39
en34 English Gheal 2022-10-31 22:01:52 74
en33 English Gheal 2022-10-31 21:57:17 200
en32 English Gheal 2022-10-31 21:57:01 747
en31 English Gheal 2022-10-31 21:48:53 629
en30 English tibinyte 2022-10-31 21:41:38 7
en29 English tibinyte 2022-10-31 21:41:03 38
en28 English Gheal 2022-10-31 21:38:59 40
en27 English tibinyte 2022-10-31 21:37:09 17
en26 English Gheal 2022-10-31 21:34:15 81
en25 English Gheal 2022-10-31 21:33:19 2311
en24 English tibinyte 2022-10-31 21:33:02 34
en23 English tibinyte 2022-10-31 21:32:50 340
en22 English tibinyte 2022-10-31 21:31:52 3999
en21 English tibinyte 2022-10-31 21:29:21 303
en20 English tibinyte 2022-10-31 21:29:00 18 Tiny change: 'anks to \ncadmiumky\n ):\n\nT' -> 'anks to \n[user:cadmiumky]\n ):\n\nT'
en19 English tibinyte 2022-10-31 21:28:31 4797
en18 English Gheal 2022-10-31 21:27:42 924
en17 English Gheal 2022-10-31 21:18:46 409
en16 English Gheal 2022-10-31 21:16:45 519
en15 English Gheal 2022-10-31 21:13:59 46
en14 English Gheal 2022-10-31 21:12:58 48
en13 English Gheal 2022-10-31 21:11:37 1405
en12 English tibinyte 2022-10-31 00:18:26 7
en11 English tibinyte 2022-10-31 00:18:18 79
en10 English tibinyte 2022-10-31 00:18:10 73
en9 English tibinyte 2022-10-31 00:18:00 3259
en8 English tibinyte 2022-10-31 00:16:45 3531
en7 English tibinyte 2022-10-31 00:15:55 2754
en6 English tibinyte 2022-10-31 00:15:29 2047
en5 English tibinyte 2022-10-31 00:14:20 1085
en4 English tibinyte 2022-10-31 00:12:33 2468
en3 English tibinyte 2022-10-31 00:08:20 10
en2 English tibinyte 2022-10-31 00:07:58 2606
en1 English Gheal 2022-10-30 23:34:08 50 Initial revision (saved to drafts)