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.me/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.
- You can search Merkle tree for a broader perspective on this topic.
- Baekjoon Online Judge already has a judge for a similar problem at least as hard as this example.
