TAEDITOR - Editorial

general
, , , ,
1

Problem link : contest practice

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. :slight_smile:

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.

5 Likes
2

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

3

It looks like I cheated a bit here. I just used the inbuilt StringBuilder functions of append() and insert()… :stuck_out_tongue:

http://www.codechef.com/viewsolution/4384023

4

I got 100 points and i didn’t use segment tree…

5

i did same in cpp :stuck_out_tongue: :smiley:

http://www.codechef.com/viewsolution/4387406

6

Problem is while printing the substring .
The second parameter is length not index … I did the same mistake …

1 Like
7

Mistake is in second type of query …

 cin>>i>>l;
 for(i--;i<l;i++)
 cout<<b[i];
 cout<<"\n";

Instead it should be

cin>>i>>l;
for( int f = i ; f < i + l; f++)
cout<<b[f];
cout<<"\n";
1 Like
8

Can someone tell me why I got WA? http://www.codechef.com/viewsolution/4392270

9

Oh No :frowning: :frowning: :(…
Ruined the contest!!
Thanks Now.

10

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.

11

I used rope. (For more information http://codeforces.com/blog/entry/10355)

// #includes ...
#include <ext/rope>
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');
}
7 Likes
12

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!!

4 Likes
13

This problem is the same as problem B from ACPC regional contest 2012

Link for the problem

2 Likes
14

that’s something new, but in the codeforces blog it uses rope , but you used crope. what’s the difference?

15

Can anyone tell me why brute force solutions are getting accepted?

1 Like
16

can someone tell me why my solution gives wa my submission id is http://www.codechef.com/viewsolution/4393776

17

I read the manual and found out that crope is just a wrapper for rope or similar.

18

I think this problem can also be solved with Treap(Balanced BST).

19

It can: http://www.codechef.com/viewsolution/4393525

20

Learned something new. Appreciate the fact that you called out your unique implementation in the comments, would have remained unware of Rope other wise :slight_smile:

Thanks
Lone Coder