Mutate Array and Sort All Obtained Arrays in Lexicographic Order

Правка en1, от Nachia, 2023-10-22 19:36:30

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 integers $$$p _ k$$$ $$$(0 \leq p \leq N-1)$$$ and a value $$$x _ k$$$ . Overwrite $$$A _ i$$$ with the copy of $$$A _ {i-1}$$$ and change the value of $$$A _ {i}[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 array index and $$$b$$$ as time 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 time complexity is $$$\mathcal{O}((n+q) \log (n+q))$$$ overall ( the term $$$q\log q$$$ is for sorting given values ).

Main Usage

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Nachia 2023-10-23 14:56:55 527 accrate text and add supplement based on comments
en6 Английский Nachia 2023-10-22 19:58:11 0 (published)
en5 Английский Nachia 2023-10-22 19:52:01 4 Tiny change: '+Q) \log (n+q))$ overal' -> '+Q) \log (N+Q))$ overal'
en4 Английский Nachia 2023-10-22 19:51:47 14
en3 Английский Nachia 2023-10-22 19:47:15 6
en2 Английский Nachia 2023-10-22 19:37:11 18
en1 Английский Nachia 2023-10-22 19:36:30 2135 Initial revision (saved to drafts)