Hasnaine_'s blog

By Hasnaine_, history, 6 weeks ago, In English,


Recently I came across the problem SPOJ-Maxmatch While doing a marathon on FFT. After being unable to solve this, I went to search for the editorial of this problem. Found a blog explaining this.

But cannot actually visualize what is going on here. Why does matching function respond to that polynomial or why does it work? And how we represent the polynomial in the form: $$$(x^{-1} + x^{-3} + x^{-4})$$$? Can anyone please explain?

Thank you so much!

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

6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

The main idea for this problem is to compute the maximum number of pairs of identical elements which have the same "shift" value (e.g. $$$s[4]$$$ and $$$s[1]$$$ is an example of such a pair with shift $$$4 - 1 = 3$$$, since $$$s[4] = s[1]$$$). With this in mind, the trick is:

For each distinct character $$$c$$$, we will represent the set of that character's positions with a polynomial $$$f(x)$$$, where term $$$x^i$$$ exists if and only if $$$s[i] = c$$$. Then, we can imagine a second string with the same indices but negative represented by $$$g(x)$$$, since the indices of the second string are effectively "cancelling" that of the first. Once we multiply these 2 polynomials together, it will effectively produce a frequency array for each shift value. For example, in the pair mentioned above, we notice that $$$f(x)$$$ will contain term $$$x^4$$$ and $$$g(x)$$$ will contain term $$$x^{-1}$$$. From this specific pair, the resulting polynomial $$$f(x) \times g(x)$$$ will have the coefficient of term $$$x^4 \times x^{-1} = x^3$$$ increased by $$$1$$$.

Hopefully from the example above you see why the resulting polynomial $$$f(x) \times g(x)$$$ represents the frequency array of each shift value. Once you have the frequency array for each distinct character, you can simply add them up and find the terms with a positive degree having the largest coefficient.

The final complexity of this approach will be $$$O(3 \times N\log N)$$$ with FFT.

  • »
    6 weeks ago, # ^ |
    Rev. 5   Vote: I like it +8 Vote: I do not like it

    Thanks a lot. I can't tell you how much I struggled to understand before you explained here:

    From this specific pair, the resulting polynomial $$$f(x)×g(x)$$$ will have the coefficient of term $$$x^4×x^{-1}=x^3$$$ increased by $$$1$$$.

    I am sure your comment will help those also who will be struct next time while solving this particular problem.

    I have another question can you please explain how do I represent a negative indexed polynomial? (Never mind, got it :D)