My learning note on AGC061C based on Little09's (Simplified) Chinese Blog

Revision en11, by CristianoPenaldo, 2023-02-15 14:41:38

I admit that AGC061C is too hard for me, and I don't even understand its official editorial. Today I see a Luogu blog with a very clear idea on this problem. I learn a lot from it, and I would like to share it to you. The writer of this blog is possibly Little09, but I am not quite sure.

Part1: Problem Statement and Constraints

There are $$$N$$$ customers named $$$1$$$, ..., $$$N$$$ visiting a shop. Customer $$$i$$$ arrives at time $$$A_i$$$ and leaves at time $$$B_i$$$ The queue order is first in first out, so $$$A_i$$$ and $$$B_i$$$ are both increasing. Additionally, all $$$A_i$$$ and $$$B_i$$$ are pairwise distinct.

At the entrance, there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo $$$998244353$$$.

Constraints:

$$$\cdot 1 \leq N \leq 500000$$$.

$$$\cdot 1 \leq A_i \leq B_i \leq 2N$$$.

$$$\cdot A_i < A_{i+1}\,(1 \leq i \leq N-1)$$$.

$$$\cdot B_i < B_{i+1}\,(1 \leq i \leq N-1)$$$.

$$$\cdot A_i \neq B_j \,(i \neq j)$$$

$$$\cdot \text{All values in the input are integers}$$$.

Part2: Idea in the blog

Consider two dynamic programming tables named $$$f$$$ and $$$g$$$ ($$$dp$$$ in the original blog). The blog computes $$$f,\,g$$$ in the reverse order. Formally,

$$$f(i) (1 \leq i \leq n)$$$: The number of permutations when we have already considered persons $$$i,\,i+1,\,...,\,n$$$.

$$$g(i) (1 \leq i \leq n)$$$: The number of permutations when we have already considered persons $$$i,\,i+1,\,...,\,n$$$, and the person $$$i$$$ is forced to sign her (or his) name on $$$B_i$$$.

The blog defines $$$c(i)$$$ as:

$$$c(i) := max\{j|a_j < b_i\}$$$. Obviously $$$i \in \{j|a_j < b_i\}$$$ and $$$c(i) \geq i$$$.

Tags combinatorics, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en55 English CristianoPenaldo 2023-02-18 13:01:26 4 Tiny change: ' and $c(i)<i$. They c' -> ' and $c(i) > i$. They c'
en54 English CristianoPenaldo 2023-02-15 19:06:57 5 Tiny change: '{c(i)+1,\,j+2\,...,\,' -> '{c(i)+1,\,c(i)+2\,...,\,'
en53 English CristianoPenaldo 2023-02-15 19:06:01 1 Tiny change: 'fix: $[i+1\,i+2\,...' -> 'fix: $[i+1,\,i+2\,...'
en52 English CristianoPenaldo 2023-02-15 19:00:40 9
en51 English CristianoPenaldo 2023-02-15 18:26:48 58
en50 English CristianoPenaldo 2023-02-15 18:06:47 4 Tiny change: 'rt2: Idea in the blog*' -> 'rt2: Idea of the blog*'
en49 English CristianoPenaldo 2023-02-15 17:36:32 14 Tiny change: '3), i.e., there is actually not neces' -> '3), i.e., it is not neces'
en48 English CristianoPenaldo 2023-02-15 17:31:03 1 Tiny change: 'their name, $i$ is a' -> 'their names, $i$ is a'
en47 English CristianoPenaldo 2023-02-15 17:19:57 150
en46 English CristianoPenaldo 2023-02-15 17:11:30 2 Tiny change: '\n\n**Part4: The last' -> '\n\n**Part5: The last'
en45 English CristianoPenaldo 2023-02-15 17:09:23 62
en44 English CristianoPenaldo 2023-02-15 17:05:53 32 Tiny change: 'he first**, otherwis' -> 'he first** among $\\{i,\,i+1,\,...,\,n\\}$, otherwis'
en43 English CristianoPenaldo 2023-02-15 17:04:42 4 Tiny change: 'dd $i$ in front of ' -> 'dd $i$ in the front of '
en42 English CristianoPenaldo 2023-02-15 17:03:34 6
en41 English CristianoPenaldo 2023-02-15 17:02:11 11 Tiny change: 'e $A$.\n\nFinally, although we' -> 'e $A$.\n\nAlthough we'
en40 English CristianoPenaldo 2023-02-15 17:01:24 11 Tiny change: 'th a very clear ide' -> 'th a very genius and clear ide'
en39 English CristianoPenaldo 2023-02-15 17:00:40 178
en38 English CristianoPenaldo 2023-02-15 16:52:57 216
en37 English CristianoPenaldo 2023-02-15 16:48:30 1 Tiny change: 'i \neq j)$\n\n$\cdot' -> 'i \neq j)$.\n\n$\cdot'
en36 English CristianoPenaldo 2023-02-15 16:48:07 6
en35 English CristianoPenaldo 2023-02-15 16:47:40 272 (published)
en34 English CristianoPenaldo 2023-02-15 16:44:14 651
en33 English CristianoPenaldo 2023-02-15 16:32:35 2 Tiny change: 'j=i+1}^{c(j)} g(j) + ' -> 'j=i+1}^{c(i)} g(j) + '
en32 English CristianoPenaldo 2023-02-15 16:25:16 4
en31 English CristianoPenaldo 2023-02-15 16:06:22 74 Tiny change: '\geq i$.\n\n![ ](htt' -> '\geq i$.\n![ ](htt'
en30 English CristianoPenaldo 2023-02-15 16:05:39 64
en29 English CristianoPenaldo 2023-02-15 16:03:18 60
en28 English CristianoPenaldo 2023-02-15 16:01:46 149
en27 English CristianoPenaldo 2023-02-15 15:51:47 56
en26 English CristianoPenaldo 2023-02-15 15:50:00 2 Tiny change: 's_{j=i+1}^c(j) g(j) + f(' -> 's_{j=i+1}^{c(j)} g(j) + f('
en25 English CristianoPenaldo 2023-02-15 15:48:45 191
en24 English CristianoPenaldo 2023-02-15 15:45:44 542
en23 English CristianoPenaldo 2023-02-15 15:36:54 6
en22 English CristianoPenaldo 2023-02-15 15:36:08 44
en21 English CristianoPenaldo 2023-02-15 15:34:44 139
en20 English CristianoPenaldo 2023-02-15 15:30:07 742
en19 English CristianoPenaldo 2023-02-15 15:22:23 8
en18 English CristianoPenaldo 2023-02-15 15:20:53 327
en17 English CristianoPenaldo 2023-02-15 15:17:02 241
en16 English CristianoPenaldo 2023-02-15 15:12:05 355
en15 English CristianoPenaldo 2023-02-15 15:05:27 708
en14 English CristianoPenaldo 2023-02-15 14:57:22 153
en13 English CristianoPenaldo 2023-02-15 14:55:41 359
en12 English CristianoPenaldo 2023-02-15 14:52:52 75 Tiny change: 'eq i$.\n\n\n' -> 'eq i$.\n\n![ ](https://codeforces.net/633ccf/blog.png)\n\n\n'
en11 English CristianoPenaldo 2023-02-15 14:41:38 55
en10 English CristianoPenaldo 2023-02-15 14:33:54 279
en9 English CristianoPenaldo 2023-02-15 14:28:39 696
en8 English CristianoPenaldo 2023-02-15 14:20:37 15 Tiny change: '\text{All inputs are integ' -> '\text{All values in the input are integ'
en7 English CristianoPenaldo 2023-02-15 14:19:48 214
en6 English CristianoPenaldo 2023-02-15 14:16:46 46 Tiny change: '98244353$.' -> '98244353$.\n\nConstraints:\n$\cdot 1 \leq N \leq 500000$'
en5 English CristianoPenaldo 2023-02-15 14:16:07 30
en4 English CristianoPenaldo 2023-02-15 14:14:35 565
en3 English CristianoPenaldo 2023-02-15 14:11:37 116
en2 English CristianoPenaldo 2023-02-15 14:10:18 278
en1 English CristianoPenaldo 2023-02-15 13:31:51 165 Initial revision (saved to drafts)