## Editorial for DMOPC '20 Contest 5 P6 - Top Row

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

We note that the problem asks for the sum of the number of distinct substrings and the total length of all distinct substrings for each specified range.

For this subtask, any reasonable brute force algorithm (such as maintaining a set of hash values for each round) should pass.

Time Complexity:

For this subtask, it is sufficient to solve the problem for each of the given rounds independently using any suffix string data structure. One such data structure which provides a straightforward solution to this subtask is the suffix automaton (SAM), which will also be used in later subtasks.

Time Complexity:

Time Complexity: , where is the expected height of the suffix link tree.

For full marks, we notice that the operation of updating all states from the current state to the root is extremely similar to the Access operation of a link/cut tree. If we maintain the suffix link tree using an LCT, we can support suffix link jumping to the root in the amortized complexity of the LCT, and that is sufficient for full marks. It is also possible to achieve the same time complexity using small to large merging heuristics on the set of end positions for each state of the suffix link tree. Special care should be taken to avoid excessive memory usage.

Time Complexity:

• commented on April 28, 2021, 7:57 a.m.

P6 have appeared long ago, and I even find an editorial for similar problem in contest from another OJ, but I failed because of memory exceed. The problem is easy, but the memory limit is crazy. In my opinion, the reasonable limits are supposed to be 4 x spense of author's solution if the code is written by C++ or C, 2 times for other language.

• commented on April 28, 2021, 10:17 a.m.

Hi, could you tell me where P6 has appeared before? I spent a long time searching for it on the internet but I couldn't find the same problem, so I was pretty confident that the problem itself is unique. As for similar problems, I was aware that similar problems exist from past contests (for example you can see the main problem mentioned here), but the idea of backing a suffix automaton with an LCT to support suffix updates at any index was so brilliant and new for me that I decided there was a place for it on the DMOPC this time. Regarding your submissions, I believe they failed more so do the time limit than the memory limit, looking at the verdicts of your in contest submissions. That's quite unfortunate, since we intentionally kept the time limit relatively tight (2.5x reference solution in C++) to minimize the probability of constant optimized quadratic (or faster, like sqrt) solutions passing. I'll keep that in mind for future problems though, and if we are able to get enough Java testing then perhaps we can set custom limits for Java. Thanks for reaching out.

• commented on April 29, 2021, 5:31 a.m. edit 4

Of course, it's similar rather than same problem. I first knew such problem in https://codeforces.com/blog/entry/62331 long ago, and in contest, I found a similar problem without persistent trick in Chinese OJ https://www.luogu.com.cn/problem/P6292. There is a Chinese blog talked about how to solve the online version, I learned the trick here.

Thanks for your cool problem, at first glance I didn't care about such problem until I met a hard version in your contest, as a consequence I learned a new skill.