.o.'s blog

By .o., history, 6 months ago, In English,

Last week, there was a preliminary ICPC contest in Korea, whose result is used to select teams from various universities to advance to the Seoul Regional (regional contest in Korea)

This is the problemset: http://icpckorea.org/2018/preliminary/problems.pdf

Most problems were solved, at least algorithmically, by people during the contest or after the contest. However, anyone, including some top-tier people in our country, couldn't solve problem C.

In the contest, problem C was solved, but it was just because the test data was super weak to allow solutions with complexity O(n2 / k) :p Since the description is short enough, I will not describe the problem here, just click the link to see the task.

I am really curious about the solution of this problem. Could I get some hints or entire solutions for this task? Thanks in advance :)

  • Vote: I like it  
  • +35
  • Vote: I do not like it  

6 months ago, # |
  Vote: I like it +47 Vote: I do not like it

I thought quite a long time with my previous teammates, but I couldn't figure out anything :(

I also searched for some papers, but I could only find the case where K = 2.

Can someone solve this problem? This seems to be quite interesting problem, and I would be pleased if I could know the solution :)

6 months ago, # |
  Vote: I like it -41 Vote: I do not like it

Ask the legends > @Petr @tourist

6 months ago, # |
Rev. 2   Vote: I like it +65 Vote: I do not like it

When k is large, it's easy to solve the problem with complexity .

When k = 2, let's count how many substrings are in the form of "AA". This is a classic problem: assume that the length is 2L , divide the string into several parts, where each part has a length L (maybe except the last one). For example, when L = 3, we will divide the string ababbabbaba like this:


For each two neighboring part we compute the LCP(longest common prefix) and the LCS(longest common suffix) of them. Every substring of length 2L will cover at most three parts, with LCP and LCS we can easily compute the answer.

Let's back to the original problem. We don't compute LCP and LCS of all neighboring parts; Just compute all parts i, j(i < j) when j - i ≤ k . And we'll get something like "substrings starts with [l, r] is not a k-LS": there are of them: with them we can find the number of k - LS substrings with length kL using sweep line. The total complexity is

When , we'll use the second algorithm, otherwise we'll use the first algorithm. The total complexity is .

Sorry for my poor English.

  • »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, this is an wonderful solution. I'm impressed by the idea using LCP and LCS to check the sameness. Thank you very much!