×

TAEDITOR - Editorial

Difficulty : Medium

Pre-requisites : Strings, Segment Tree/BIT

Problem :

You need to implement two kinds of query on a string S:

1. Insert a string in a specific position.
2. Print out a specific sub-string of S.

Explanation

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.

1. 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.
2. 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[4]='d'.
Now, "+ 2 d", what is the 3'rd smallest available position? 2 is available. So we mark ANS[3]='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[5].
Now, "? 2", what is the 2'nd smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS[2].
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[2]='c'.
Now, "+ 1 b", what is the 2'nd smallest available position? 5 is available. So we mark ANS[5]='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. :)

Solutions : setter tester

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.

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

19.8k350498541

 10 I used rope. (For more information http://codeforces.com/blog/entry/10355) // #includes ... #include using namespace __gnu_cxx; using namespace std; crope S; char x[MAX_N]; // inserting x into i void insert(int i){ S.insert(S.mutable_begin() + i, x); } void query(int i, int len){ for(int j = 0; j < len; j++){ putchar(S[i + j - 1]); } putchar('\n'); }  answered 27 Jul '14, 15:29 1.9k●4●13●17 accept rate: 11% that's something new, but in the codeforces blog it uses rope , but you used crope. what's the difference? (27 Jul '14, 18:30) I read the manual and found out that crope is just a wrapper for rope or similar. (27 Jul '14, 19:10) Learned something new. Appreciate the fact that you called out your unique implementation in the comments, would have remained unware of Rope other wise :) Thanks Lone Coder (29 Jul '14, 18:02) @gdisastery1 What i found is "rope" is taking more time(approx double) than simple std::string insert/substr based implementation. why?? String based @ http://www.codechef.com/viewsolution/4404035 , rope based @ http://www.codechef.com/viewsolution/4390862 (31 Jul '14, 00:09) rajeshb4★ 1 Use this to generate a test case: http://ideone.com/X1kXHB with Python 2.7 On my computer, the std::string version is taking about ~2.5 seconds and the rope version only ~0.3 seconds. (31 Jul '14, 14:01)
 7 Using the built-in functions for string, str.insert for inserting and str.substr for printing the substring gave me 100 points! Here is the AC solution. Weak Test Cases....?? If not then i am more interested in knowing their built-in implementations!! answered 27 Jul '14, 15:31 4★rsaha77 966●3●8●15 accept rate: 17% I think you are lucky .. :) My solution with same approach is not getting 100 and even I used same approach during contest, I got 50 only. My Solution http://www.codechef.com/viewsolution/4404727 (30 Jul '14, 14:23)
 2 This problem is the same as problem B from ACPC regional contest 2012 Link for the problem answered 27 Jul '14, 18:22 212●1●8 accept rate: 0%
 1 Can anyone tell me why brute force solutions are getting accepted? answered 27 Jul '14, 18:42 223●6 accept rate: 0% can someone tell me why my solution gives wa my submission id is http://www.codechef.com/viewsolution/4393776 (27 Jul '14, 18:45)
 0 Please tell me that why am I getting WA for all but first test case ? I can understand TLE but why WA? Please see the code here answered 27 Jul '14, 14:56 5★yash_15 518●1●7●16 accept rate: 2% 1 Problem is while printing the substring . The second parameter is length not index ... I did the same mistake .. (27 Jul '14, 15:02) 1 Mistake is in second type of query ...  cin>>i>>l; for(i--;i>i>>l; for( int f = i ; f < i + l; f++) cout<
 0 It looks like I cheated a bit here. I just used the inbuilt StringBuilder functions of append() and insert()... :-P http://www.codechef.com/viewsolution/4384023 answered 27 Jul '14, 14:58 4★gkcs 2.6k●1●11●28 accept rate: 9% i did same in cpp :P :D http://www.codechef.com/viewsolution/4387406 (27 Jul '14, 15:01) ravi02134★
 0 I got 100 points and i didn't use segment tree.. answered 27 Jul '14, 15:00 1 accept rate: 0%
 0 Can someone tell me why I got WA? http://www.codechef.com/viewsolution/4392270 answered 27 Jul '14, 15:06 1★manraj -2 accept rate: 0%
 0 Can any one point out mistake in my code(I know my code gives TLE but it say's WA mainly): http://www.codechef.com/viewsolution/4391311. answered 27 Jul '14, 15:19 2.2k●6●17●48 accept rate: 10%
 0 I think this problem can also be solved with Treap(Balanced BST). answered 27 Jul '14, 21:23 1 accept rate: 0% (27 Jul '14, 23:49)
 0 I am getting SIGSEGV for all test cases..I am using linked list can anyone help me? http://www.codechef.com/viewsolution/4406111 answered 30 Jul '14, 20:58 2★mtbar131 16●3 accept rate: 0%
 0 I am getting SIGABRT for all test cases, here is my solution : http://www.codechef.com/viewsolution/4474050 can anyone help me? answered 04 Aug '14, 20:13 3★beakon1 1 accept rate: 0%
 0 I Didn't Understand The Editorial , Can Someone Please Explain it to me ?? answered 23 Dec '14, 13:09 79●2●7 accept rate: 4%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,755
×1,250
×371
×349
×12

question asked: 27 Jul '14, 14:47

question was seen: 6,252 times

last updated: 23 Dec '14, 13:09