USACO Gold P1 Find and Replace

#1

I’m currently reading the official editorial for the 2023 january gold p1 find and replace.

I pretty much understand all of it, except the one part when they state:

Note that its very important that leaf nodes only contain individual letters and not empty strings. Changing the one line
   Node* result = nullptr;
    to
   Node* result = new Node();
results in an O(NM) solution instead because the empty string gets repeated many times in S but doesnt count toward its length.

I recently switched from java to c++, and am not familiar with why this would make a difference(I’ve tried searching online). Can someone please clarify this?
Thanks in advance

1 Like
#2

It’s not specific to C++. Consider what happens if all updates replace one character with another character. Then for each update, the official analysis does not create any new nodes (which makes sense; the final string will consist of just a single character). However, if you use Node* result = new Node(); instead, then every update will create new nodes, and current[0] can potentially be a very large tree with a single leaf node containing a character and the rest of the leaf nodes being empty.

1 Like