# 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**k**character of the concatenated string.^{th}

# 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, **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**character, you dont actually need to concatenate the strings.

^{th}**k**character of the concatenated string is going to to be the

^{th}**p**character of some

^{th}**q**string. These

^{th}**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 = 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**at a time. That means, I build an array

_{0}**B**.

_{v0}[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, v**, it looks only at those indices

_{0})**i**for which

**i v<sub>0</sub> = l v**, and finds the last index

_{0}**p**such that

**B**is at most

_{v0}[p] - B_{v0}[l-v_{0}]**k-1**.

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**. This is sufficient to solve subtask 2.

_{max}+ M log N)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**. For answer a query

_{v0}**(l, v, k)**, if **v ≤ v

_{0}, we use the arrays

**B**constructed above, and for

_{v}**v > v**, we answer the queries by trivial method. The complexity of such a solution will be

_{0}**O(N * v**. For

_{0}+ M * N / v_{0})**v**, this quantity is minimum, and equal to

_{0}= √M**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