abcdabcd987's blog

A simple&efficient solution to CF271D (D — Good Substrings) & some personal feeling
By abcdabcd987, 12 years ago, In English

Hello everybody. I took part in Codeforces Round 166 (Div. 2) last night. I'm a newbie, so I only solved Problem ABD.

Last night, I thought that enumerating substrings and using set<string> in C++ could solve this problem in O(n^2logn), and seems code length would be quite short. Then I coded it (only 32 lines) and submitted it. Unfortunately, I forgot to calculate the memory (needs 1G memory), and MLE: 3097364

Then I thought I should change map to hash, but actually, I don't know how to hash it. However, fortunately, I thought of a tiny&powerful data structure: Trie!

Using Trie to solve this problem is quite comfortable.

  1. Create a root node.
  2. Enumerate the start point of the substring in the string. Then enumerate the end of the substring. And at the same time, travel the Trie. If current node is valid and not marked in Trie, ++ans!

Quite easy to code (also 32 lines), and the memory cost is quite low, runs fast, too: 3098298 3105955 I've read the official tutorial & many other people's submissions. I found this problem could be solve by Suffix Array, RK Hash, ... I learnt a lot from all you guys, especially Robert's RK hash: 3106330

Thanks Codeforces for providing such a good place to learn from each other.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your first algo is having a hidden cost of O(n). Hence it is O((n^3) * log(n)) .

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Basically you are describing the author's solution. If you read carefully they state their structure as a trie. It's true your code is shorter, but some people will write with the same speed a little bit longer solution, but well structured. Anyways, this was a nice problem :)

→ Reply