Difficulty : Medium
Pre-requisites : Strings, Segment Tree/BIT
You need to implement two kinds of query on a string S:
- Insert a string in a specific position.
- Print out a specific sub-string of S.
At first, let’s consider some partial solutions.
How to get 20/50 points
Just use the built-in library in you language. You will pass this sub-task with that. You might even pass the second subtask.
How to get 100 points
Firstly, we can simplify the problem by converting the queries so that we deal with the characters only.
- Inserting a string x = c_1,c_2,…,c_m after the i’th character of S is equivalent to m queries of inserting the character c_1 after the i’th character of S and then inserting the character c_2 after the (i+1)'th character of S and so on until c_m.
- Query about the sub-string of length m starts at position i of S means you have to know what character is in the position i, i + 1 and i + m - 1 of S.
So, we’ll process each query character by character. We break each update query in updation of various single characters and second query into retrieval of many single characters.
First we find out what will be the length of the final string, which is very easy. Let N be the length of the final string, so we have N positions, numbered from 1 to N. Consider all the query in the inverse order, for each query we will convert the given positions into the corresponding final value. It is pretty straight forward. For example you are given to update/query the k’th character. Position k means it is the k’th smallest position among the “available” positions. We use the word “available” here because after you visit an insert query, you must remove the position that that query used since it is not available for the previous insert queries.
An example will make it more clear. Let’s consider the sample input given in question.
5 + 0 ab + 1 c ? 1 3 + 2 dd ? 1 5
We break our queries first. Our queries are:
+ 0 a + 1 b + 1 c ? 1 ? 2 ? 3 + 2 d + 3 d ? 1 ? 2 ? 3 ? 4 ? 5
We know the final length of string is 5. Right now all positions from 1 to 5 are empty. We’ll start processing the queries in inverse order.
For, “? 5” the 5’th smallest position available is 5. So we know our answer will be the 5’th character. Similarily for the “? 4”, “? 3”, “? 2” and “? 1”.
Now, “+ 3 d”, what is the 4’th smallest available position? 4 is available. So we mark ANS=‘d’.
Now, “+ 2 d”, what is the 3’rd smallest available position? 2 is available. So we mark ANS=‘d’.
Now, “? 3”, what is the 3’rd smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS.
Now, “? 2”, what is the 2’nd smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS.
Now, “? 1”, what is the 1’st smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS1.
Now, “+ 1 c”, what is the 2’nd smallest available position? 2 is available. So we mark ANS=‘c’.
Now, “+ 1 b”, what is the 2’nd smallest available position? 5 is available. So we mark ANS=‘b’.
Now, “+ 0 a”, what is the 1’st smallest available position? 1 is available. So we mark ANS1=‘a’.
For all “?” queries we know what answer will be. After building the whole string we just have to process those queries in chronological order.
Now, the problem is how do we find the k’th smallest position available?
Suppose right now we have an array of 1’s and 0’s where arr[i]=1 if the i’th position is not available. How do we go about finding the k’th smallest position available?
SUM[arr[i], i=1 to j] is an non-decreasing function on j. So, we can apply binary search on j to find the answer.
But, once we mark and arr[i]=0, we’ll have to calculate the prefix sum again and again. Here comes into play the Binary Indexed Trees. Using them we can mark/unmark in log(N) complexity and find the prefix sum also in log(N). So complexity here would be O(log N * log N) since each query will take O(log N). This solution should pass.
Another method to achieve better complexity would be balanced binary search tree or splay trees. Here on an average, the complexity is O(log N) for searching the K’th smallest element. Also, add/remove in O(log N).
So, our problem is solved.
Clarification: It was realised during the contest that brute force solutions are getting accepted, even though testdata was strong. Tester/Setter’s brute force solutions during testing phase were not getting accepted. We apologise for this.