An alternative solution to IOI 2012 Day1 Q3 using Persistent Segment Tree

Revision en14, by heavylightdecomp, 2022-04-09 18:04:52

Hello Codeforces,

Recently I was solving some problems and came across IOI 2012, Crayfish Scrivener. It is quite an interesting problem. I think my solution for 100 points is pretty cool so I decided to post it here. Hopefully it has not been mentioned before :)

For this solution we will be using 1-based indexing.

Firstly, I noticed that actually adding characters to the end of the string seems a little annoying to optimize. So I tried converting it to a more static problem. First we must notice that this dynamic string can be represented using a static char array. Also notice that for all subtasks, the number of queries is at most $$$1,000,000$$$ ($$$10^6$$$). Thus, the maximum size of our string is $$$10^6$$$. So if we have a char array of size $$$10^6$$$, initialized to some default value, and keep track of the actual "size" of the represented string in an integer, in order to "type a letter", we can just update the index ($$$size + 1$$$) with the desired letter (this is a point update) without affecting the correctness of our algorithm.

Actually, this reduction allows us to reframe the problem in a way that is very intuitive to solve. Observe that the $$$Undo$$$ operation just requires us to "copy" some arbitrary previous revision of the char array, and make a new revision from it. The $$$TypeLetter$$$ operation just requires us to do a make a new revision that does a point update on the current revision. The $$$GetLetter$$$ operation just requires us to get the value at a specified index, which is a point query. So we need a persistent data structure (to access any previous revision quickly) which can also do point updates and point queries quickly.

What data structure supports all this? Persistent segment trees! Thus, the solution is to build a persistent segment tree on the aforementioned char array.

Its space complexity is $$$O(QlogN)$$$ where $$$Q$$$ is the number of queries and $$$N$$$ is the size of our char array ($$$10^6$$$ in this case, the number of queries) which is $$$O(QlogQ)$$$. "Copying" a previous revision $$$O(1)$$$. Point updates and point queries are $$$O(logN)$$$, which is $$$O(logQ)$$$. Our final time complexity is $$$O(QlogQ)$$$. This is good enough to score 100 points.

Note: We do not use the full power of segment tree for this problem as all the char information is stored in the leaf nodes, which represent a single index.

Implementation note: Don't forget to convert 0-based indexing given in input to 1-based indexing, or implement your solution in 0-based indexing (idea stays the same, just a few minor changes).

PS: I hope you enjoyed reading through my first Codeforces blog. I spent a lot of time on it and if you have any suggestions or tips for improvement please post them in the comments. Though maybe this is not the most elegant way to solve the problem, this is the first idea I came up with and I feel like I understand it a lot more than the other solution which uses binary jumping (though I think it is pretty cool as well, you can view it here).


My implementation
Tags ioi, segtree, persistent segment trees, ioi2012, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English heavylightdecomp 2022-04-09 18:06:40 3268 Reverted to en14
en15 English heavylightdecomp 2022-04-09 18:06:30 3268 Reverted to en1
en14 English heavylightdecomp 2022-04-09 18:04:52 5 (published)
en13 English heavylightdecomp 2022-04-09 18:01:14 4
en12 English heavylightdecomp 2022-04-09 18:00:24 12
en11 English heavylightdecomp 2022-04-09 17:55:38 12 Tiny change: 'etty cool and concise so I deci' -> 'etty cool so I deci'
en10 English heavylightdecomp 2022-04-09 17:55:16 37 Tiny change: 'ng problem with many different methods to solve. I think ' -> 'ng problem. I think '
en9 English heavylightdecomp 2022-04-09 17:51:40 6
en8 English heavylightdecomp 2022-04-09 17:51:03 2 Tiny change: 'revision $$O(1)$$. Point u' -> 'revision $O(1)$. Point u'
en7 English heavylightdecomp 2022-04-09 17:50:14 2974
en6 English heavylightdecomp 2022-04-09 17:48:56 46
en5 English heavylightdecomp 2022-04-09 17:39:39 15 Tiny change: 'pdf)).\n\n<spoil' -> 'pdf)).\n\n\n\n\n<spoil'
en4 English heavylightdecomp 2022-04-09 17:38:54 78
en3 English heavylightdecomp 2022-04-09 17:37:52 627
en2 English heavylightdecomp 2022-04-09 17:28:27 2610
en1 English heavylightdecomp 2022-04-09 16:41:29 1947 Initial revision (saved to drafts)