123gjweq2's blog

Any idea on how to solve this challenging problem?
By 123gjweq2, history, 4 hours ago, In English

You are given an integer $$$n$$$. Let $$$S$$$ be the set of all strings of length $$$n$$$ that contain only lowercase Latin characters. So $$$S$$$ will have $$$26^n$$$ elements.

You pick a random string $$$s$$$ from set $$$S$$$, then you pick a random index $$$i$$$ from the range $$$[2, n]$$$. What is the expected value of $$$z_i$$$, where $$$z_i$$$ is the value of the $$$Z$$$-function of $$$s$$$ at index $$$i$$$?

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

»
4 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

Totally an IQ problem

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

    The solution might involve a lot of competitive-programming-specific knowledge, so I would be hesitant to call it an IQ problem.

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this argument works:

For a fixed $$$i$$$, we claim the answer is $$$\frac{1}{26} + \frac{1}{26^2} + \cdots + \frac{1}{26^{n-i+1}}$$$. This is because we must have $$$S[i] = S[1], S[i + 1] = S[2], \ldots$$$ so this is equivalent to computing the expectation of a truncated geometric.

Then, summing over all coordinates, this implies that the expected $$$Z$$$-function value is $$$\frac 1{n-1}\sum_{i=1}^{n - 1}\frac{n-i}{26^i}$$$. The rest is an exercise in algebra :)

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

    I think you are right. That is a cool way to think about it. I just brute forced it for n = 5 and it seems to work. Turns out that it was an IQ (ish) problem after all.

    → Reply