Problem Link:Author Roman Furko Difficulty:Medium Prerequisites:binary search Problem:Given an array A of N strings, answer M queries of the following type Explanation:The most obvious approach for solving the problem is: 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, 10^{9} instructions for all queries, which should time out. However, on thinking a bit, you would realize that in order to get the k^{th} character, you dont actually need to concatenate the strings. k^{th} character of the concatenated string is going to to be the p^{th} character of some q^{th} 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).
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 binarysearch 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 k1. So, v=1 case does not look very hard to deal with. How about handling small v ? Since there are small number of v's, we can handle each v individually. Lets say we want to handle a fixed v = v_{0}. 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 v_{0} at a time. That means, I build an array How much time and space would it take ? If v ≤ v_{max}, 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 * v_{max} + 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 ≤ v_{0}, I construct the array B_{v0}. For answer a query (l, v, k), if v ≤ v_{0}, we use the arrays B_{v} constructed above, and for v > v_{0}, we answer the queries by trivial method. The complexity of such a solution will be O(N * v_{0} + M * N / v_{0}). For v_{0} = √M, this quantity is minimum, and equal to O( N * √M)**. This complexity is good enough to pass all subtasks. Solutions:Setter's Solution tags: editorial, ltime04, chithh, medium, preprocessing, binarysearch
This question is marked "community wiki".
asked 29 Sep '13, 14:55

I think there is a little problem with the testcases  http://www.codechef.com/viewsolution/2733311 here I have done a pretty fast solution that takes O(n) for a query and all the testcases pass. answered 30 Sep '13, 14:31
