You are not logged in. Please login at www.codechef.com to post your questions!

×

TAEDITOR - Editorial

5
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. :)

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".

asked 27 Jul '14, 14:47

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%

edited 30 Jul '14, 18:26

admin's gravatar image

0★admin ♦♦
19.6k349497539


10

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');
}
link

answered 27 Jul '14, 15:29

gdisastery1's gravatar image

4★gdisastery1
1.9k41317
accept rate: 11%

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

(27 Jul '14, 18:30) tamimcsedu193★

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

(27 Jul '14, 19:10) gdisastery14★

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) lonecodertaken2★

@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) gdisastery14★

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

link

answered 27 Jul '14, 15:31

rsaha77's gravatar image

4★rsaha77
9663815
accept rate: 17%

edited 27 Jul '14, 15:55

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) upendra12342★

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

Link for the problem

link

answered 27 Jul '14, 18:22

ahmed1ossama13's gravatar image

4★ahmed1ossama13
21218
accept rate: 0%

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

link

answered 27 Jul '14, 18:42

code_overlord's gravatar image

3★code_overlord
2236
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) ayush102944★

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

link

answered 27 Jul '14, 14:56

yash_15's gravatar image

5★yash_15
5181716
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) alphaparticle4★
1

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";
(27 Jul '14, 15:03) alphaparticle4★

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

(27 Jul '14, 15:10) yash_155★

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

link

answered 27 Jul '14, 14:58

gkcs's gravatar image

4★gkcs
2.6k11127
accept rate: 9%

(27 Jul '14, 15:01) ravi02134★

I got 100 points and i didn't use segment tree..

link

answered 27 Jul '14, 15:00

kullumanali99's gravatar image

2★kullumanali99
1
accept rate: 0%

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

link

answered 27 Jul '14, 15:06

manraj's gravatar image

1★manraj
-2
accept rate: 0%

edited 27 Jul '14, 15:21

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.

link

answered 27 Jul '14, 15:19

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61747
accept rate: 10%

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

link

answered 27 Jul '14, 21:23

rijul_csedu's gravatar image

3★rijul_csedu
1
accept rate: 0%

I am getting SIGSEGV for all test cases..I am using linked list can anyone help me?

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

link

answered 30 Jul '14, 20:58

mtbar131's gravatar image

2★mtbar131
163
accept rate: 0%

I am getting SIGABRT for all test cases, here is my solution : http://www.codechef.com/viewsolution/4474050 can anyone help me?

link

answered 04 Aug '14, 20:13

beakon1's gravatar image

3★beakon1
1
accept rate: 0%

I Didn't Understand The Editorial , Can Someone Please Explain it to me ??

link

answered 23 Dec '14, 13:09

siddharths067's gravatar image

1★siddharths067
7927
accept rate: 4%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,664
×1,188
×371
×348
×12

question asked: 27 Jul '14, 14:47

question was seen: 6,162 times

last updated: 23 Dec '14, 13:09