Problem Link:
Author Roman Furko
Tester Balajiganpathi
Editorialist Utkarsh Lath
Difficulty:
Medium
Pre-requisites:
binary search
Problem:
Given an array A of N strings, answer M queries of the following type
- query**(l, v, k)** means concatenate strings at indexes l, l + v, l + 2v … and report the kth character of the concatenated string.
Explanation:
The most obvious approach for solving the problem is:
- For each query, construct the concatenated string, and report the kth character.
Since each string can be of length upto 10, and each each query may require upto N such strings, such a solution would need upto O(10 N) instructions per query. However, even for subtask 1, the solution would need 10000 instructions per query, therefore, 109 instructions for all queries, which should time out. However, on thinking a bit, you would realize that in order to get the kth character, you dont actually need to concatenate the strings. kth character of the concatenated string is going to to be the pth character of some qth string. These p and q can be obtained by summing the lengths of strings that need to be concatenated instead of actually concatenating them, and stop as soom as this sum reaches becomes k or more. The code below uses this idea. This would be good enough to get us through the first subtask, because complexity of answering a query is O(N).
answer-query(l, v, k)
p = k
q = l
while (q <= N and p > A[q].length)
p -= A[q].length
q += v
return A[q][p]
Now, lets focus on how to solve subtask 2, and may be we will get some insight about how to solve
subtask 3. Subtask 2 has constraint on v, that it is going to be small. Lets first assume that v will be 1 in all queries, and then can we answer the queries in better than O(N) time. In the above code for subtask 1, we are calculating the sum of lengths of A[i] till it exceeds k, and p is the last such index. How can we speed this up ? binary search should easily be able to help us. For each i, we could store the sum of lengths of all strings upto index i, and then do binary-search on this array to find the last position q such the sum of lengths of all strings with indices between l and q is at most k-1.
So, v=1 case does not look very hard to deal with. How about handling small v ?
Can we use the same idea ?
Since there are small number of v’s, we can handle each v individually. Lets say we want to handle a fixed v = v0. Like the case with v=1 where we constructed an array to store sum of lengths of all strings upto index i, we can build another array, to store sum of lengths of string upto index i, skipping v0 at a time. That means, I build an array
Bv0[i] = A[i] + A[i-v<sub>0</sub>] + A[i-v<sub>0</sub>] … A[i%v<sub>0</sub>].
My binary search for v=1 case can be modified accordingly as well, so that for a given pair (l, v0), it looks only at those indices i for which i v<sub>0</sub> = l v0, and finds the last index p such that Bv0[p] - Bv0[l-v0] is at most k-1.
How much time and space would it take ? If v ≤ vmax, we would build one array of size N for each v in the range. Each query can be answered in O(log N) time. So our overall complexity is O(N * vmax + M log N). This is sufficient to solve subtask 2.
For handling subtask 3, you need to realize that for large v, the naive solution would not take too much time. In fact, you will iterate through at most ⌊ N/v ⌋ array entries in the solution given for subtask 1. Therefore, for small enough v, we could use this trivial method.
Lets say for v ≤ v0, I construct the array Bv0. For answer a query (l, v, k), if **v ≤ v0, we use the arrays Bv constructed above, and for v > v0, we answer the queries by trivial method. The complexity of such a solution will be O(N * v0 + M * N / v0). For v0 = √M, this quantity is minimum, and equal to O( N * √M). This complexity is good enough to pass all subtasks.
Solutions:
Setter’s Solution
Tester’s Solution
Editorialist’s Solution
tags:
editorial, ltime04, chithh, medium, preprocessing, binary-search