PROBLEM LINK:
Setter: Kirill Gulin
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium-hard
PREREQUISITES:
Tries and Binary Search.
PROBLEM:
Given an array of N integers, You have to find the K-th smallest value of f over all N*(N+1) sub-arrays.
For a sub-array [l, r], f(l,r) = min(l,r)*xor(l,r).
Here, min(l,r) = min(A[l], A[l+1] ..... A[r-1], A[r]) and xor(l, r) = A[l] xor A[l+1] xor .....A[r-1] xor A[r].
QUICK EXPLANATION
- Run a binary search for ans. For every and, we need to check how many sub-arrays have f(l,r) <= ans.
- Use divide and Conquer. If we are solving problem, for (l,r) and p denote position of minimum element in sub-array (l,r), then solve for f(l,p-1) and f(p+1,r) recursively.
- Now, if sub-array [l,p] is smaller than sub-array [p,r], Count Number of indices j from P to R inclusive For every index i from L to P, such that xor(i, j)*A[p]<=ans. Same way if sub-array [l,p] is greater than sub-array [p,r].
- For a fixed L, Query for Number of indices from [P, R] such that xor(L,P)*A[P] <= ans can be handled by Simple as well as persistent tries.
EXPLANATION
Let’s denote func(L,R, ans) as Number of sub-arrays of (L,R) inclusive, such that min(L,R)*xor(L,R) <= ans. Now, Find the minimum of range (L,R), let’s say P. Now, There can be three type of sub-arrays.
- Sub-arrays lying starting and ending in (L,P-1). Make a recursive call to func(L,P-1,ans).
- Sub-arrays lying starting and ending in (P+1,R). Make a recursive call to func(P+1,R,ans).
- Sub-arrays starting in (L,P), say l and ending in (P, R), say r.
Let’s focus on Third type of sub-arrays.
Take count(pos, Xo , ans) = Number of positions p up-to position pos, such that prefXor[p] xor Xo <= ans.
We know that min(l,r) will be A[p]. Now, if P is near L ie (P-L<= R-P), we will iterate from L to P and try counting Number of positions in (P,R) such that for position j, prefXor[j] xor prefXor[i-1] <= ans/A[p].=
Above queries can be represented as: count(R, prefXor[i-1], ans/A[P]) - count(P-1, prefXor[i-1], ans/A[P])
The problem reduces to finding$ count(P, value, ans)$ efficiently.
Now we can either use simple or persistent Tries for this. Read this Tutorial, Try this, this, or this problems for practicing Tries.
Now, Offline Solution using Simple Trie.
We run the binary search for ans as usual, Store all calls to count function in a query table, along with sign, build the trie on prefix xor array and whenever we encounter a query with current position P, Count the number of elements in trie such that element xor value <= ans.
Solution using persistent Trie
If this is your first ever implementation of a persistent Data structure, Read this blog on persistence.
In above solution, we are building trie for every iteration of outer binary search, so as to answer queries easily. We can build a single persistent trie with each insertion as a new update as explained in above blog, thus building this trie beforehand and then answering queries on the go.
Now remains the following problem,
We have a trie and two values X and ans, we need to count number of elements having value^X <= ans.
Suppose we are at root node of trie. Maintain a value newValue = 0, count = 0.
Run a loop j from L-1 to 1, L being the max number of bits in MAX(A).
If newValue|(1 lsh j) <= ans, we can add into count, Number of nodes in sub-tree of child of current node with same bit as jth bit of X. Set root = child with different bit.
else root = child with same bit.
**Note:**Lsh denote left shift.
Complexity: O(N * log N * log A * (log(A) + log(N)))
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution