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.
- 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.
Auto comment: topic has been updated by Nachia (previous revision, new revision, compare).
Beautiful algorithm
Nice. It reminds me of the suffix array algorithm
You could also use (persistent) Merkel trees to solve this problem. And you can also avoid hashes: just set unique identifiers to nodes and keep a global hashmap that assigns a pair $$$(label_l, label_r)$$$ to the label of the root node.
This approach, however, has a worse constant than what you’re describing, but at the same time feels like it could be applied in a little bit more general scenarios.
Thank you! I didn't noticed that aspect (and approach).
I also created a problem in such settings: Baby Seokhwan. It was used in a CSAcademy Round.
Thank you for information!
Auto comment: topic has been updated by Nachia (previous revision, new revision, compare).
How to solve this problem using randomized hash?
Let $$$(w_0, \ldots, w_{n-1})$$$ be a randomly generated sequence. By hash of a subsegment $$$[l, r]$$$ of array $$$a$$$ we will denote the value of $$$w_la_l + \ldots + w_ra_r$$$. If we build a persistent segment tree that stores the hashes, we can compare two versions of the array by finding the length of the minimal prefix with different hashes in these versions, then somehow compare the corresponding elements. However, I couldn't meet the memory limit with this approach