ikbal's blog

CCC 2013, Day 2 Problem 3, Repetitivity
By ikbal, 10 years ago, In English

There is a string with length n ≤ 104.

Let us denote fi as number of occurrences of the i'th unique sub sequence.

We need to calculate . Sub sequence does not have to be consective.

I have no idea about the solution so far. So any help would be appreciated.

Here is the source of the problem : link

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to count amount of different subsequences of a string?..

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: For each distinct sub sequence count it when its lexicographically minimal by index values.

    → Reply
»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Some magic: http://www.everfall.com/paste/id.php?tuo8fxsbhlx0.

The main idea is that desired sum may be obtained in the following way: let's iterate over all pairs of subsequences in the string S and do ans += 1 iff they are equal.

→ Reply