Mutate Array and Sort All Obtained Arrays in Lexicographic Order

Revision en7, by Nachia, 2023-10-23 14:56:55

I got AC on Codeforces Round 905 (Div. 1) C. Minimum Array with my prewritten code sorting all arrays obtained (in lexicographic order) in $$$\mathcal{O}(n\log n + q\log q)$$$ time.

https://codeforces.net/contest/1887/submission/229244614

How is the processing time achieved? I made a tutorial (in Japanese) before. (https://www.mathenachia.blog/sortseqs/ and https://nachiavivias.github.io/cp-library/cpp/array/point-update-lex-sort.html) This time I make a brief explanation in English.

Problem

First you are given an array $$$(A _ 0[0],A _ 0[1],\ldots ,A _ 0[N-1])$$$ of length $$$N$$$ . You will construct other $$$Q$$$ arrays $$$A _ 1, A _ 2, \ldots , A _ Q$$$ as follows :

  • For $$$k=1,2,\ldots ,Q$$$ (in order) , you are given an integer $$$p _ k$$$ $$$( 0 \leq p _ k \leq N - 1 )$$$ and a value $$$x _ k$$$ . Overwrite $$$A _ k$$$ with the copy of $$$A _ {k-1}$$$ and change the value of $$$A _ {k}[p _ k]$$$ to $$$x _ k$$$ .

Find an array $$$(F _ 0,F _ 1,F _ 2,\ldots ,F _ Q)$$$ of nonnegative integers such that :

  • $$$F _ i \lt F _ j \iff A _ i\lt A _ j$$$ (in lexicographic order) holds for $$$0 \leq i \leq Q$$$ , $$$0 \leq j \leq Q$$$ .
  • Maximum value of $$$(F _ 0,F _ 1,F _ 2,\ldots ,F _ Q)$$$ is minimized.

In other words, sort all $$$Q+1$$$ arrays in lexicographic order.

Algorithm

Above I wrote like $$$A _ a[b]$$$ , so I call $$$a$$$ as time index and $$$b$$$ as array index .

Divide and Conquer array index . After we could sort every half, we can get full answer in linear time with radix sort (sort by second digit, then stable sort by first digit) .

When we divide array index, changing points are also divided in two groups. So we can compress time index . We can bound the sum of number of time index as $$$\mathcal{O}(N+Q)$$$ in any layer of dividing. Of cource the number of the layers is $$$\mathcal{O}(\log N)$$$ . Therefore the entire process takes $$$\mathcal{O}((N+Q) \log (N+Q))$$$ time ( the term $$$Q\log Q$$$ is for sorting given values ).

Main Usage

We can sometimes use this deterministic algorithm instead of randomized hash.

Supplement Based on Comments

Thank you for your helpful comments.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Nachia 2023-10-23 14:56:55 527 accrate text and add supplement based on comments
en6 English Nachia 2023-10-22 19:58:11 0 (published)
en5 English Nachia 2023-10-22 19:52:01 4 Tiny change: '+Q) \log (n+q))$ overal' -> '+Q) \log (N+Q))$ overal'
en4 English Nachia 2023-10-22 19:51:47 14
en3 English Nachia 2023-10-22 19:47:15 6
en2 English Nachia 2023-10-22 19:37:11 18
en1 English Nachia 2023-10-22 19:36:30 2135 Initial revision (saved to drafts)