saint_coder's blog

Why is everyone so unsupportive?
By saint_coder, 5 years ago, In English

I tried this problem on Hackerearth :

Link

The editorial is not provided, just the code is there. I cannot understand how the author did it.

Please try this problem and please explain the approach. Can this also be done using combinatorics?

Edit 1: I spent my whole day waiting for the solution from CF community. I don't know why anyone doesn't want to help a struggling coder. :(

Edit 2: I would request people that if they cannot help then atleast don't downvote someone's blog.

Edit 3: I was wrong about the CF community. You all are kind and helpful people. :D

  • Vote: I like it
  • -24
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting! I also stuck in this problem before

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

How do you know that it is an interview problem?

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

EDIT: itachi0012 pointed out below that e.g. a good string $$$caaac$$$ doesn't come from a good string shorter by $$$2$$$, so my idea is incorrect.

I would try extending a special string by adding a new character to the beginning and to the end at the same time. If we make some long palindrome-prefix, there was already some. So we should watch out only for palindrome-prefixes of length 2 or 3. I think the solution should be something like $$$dp[n] = dp[n-2] \cdot (k-2)$$$ unless $$$n$$$ is small. Does it make sense?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    "If we make some long palindrome-prefix, there was already some. So we should watch out only for palindrome-prefixes of length 2 or 3" — Couldn't get this part

    The recurrence in author's solution is this:

    if ( i%2 )

    dp[i] = ( K * dp[i-1] ) - dp[ ( i + 1 ) / 2 ]

    else

    dp[i] = dp[i-1] ;
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      I read both two comments and thought about it for ~15 minutes and still have no idea what is going on. Please, help!

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        Let's say $$$S$$$ was a good string and now we append a character $$$c$$$ to both sides. We get $$$cSc$$$. If it is for example $$$cabacxrzy...$$$ then we get a bad prefix. But hey, $$$aba$$$ was already a bad prefix in string $$$S = abacxrzy...$$$

        So, lemma: if string $$$cSc$$$ has a bad prefix of length $$$L \geq 4$$$ then $$$S$$$ wasn't a good string because it had a bad prefix of length $$$L - 2$$$.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    what about cases like "caaac". Are we accounting this case with this recurrence.

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

      It isn't a good string and neither is "aaa".

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        but i guess for n=5 this is a valid case how we are going to account for this!!

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

          Oh, you are right. There are good strings such that its interior isn't a good string. I don't know how to count that though :D

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            ok.. your logic was good and easy to understand.. i didn't get the recurrence mentioned by author The recurrence in author's solution is this:

            if ( i%2 )

            dp[i] = ( K * dp[i-1] ) — dp[ ( i + 1 ) / 2 ] else

            dp[i] = dp[i-1] ; can u explain this

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

              Somebody already pasted it. If I could explain it, I would already do that ;p

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

                oops!! my mistake.. thanks though.

                → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it -36 Vote: I do not like it

300iq Um_nik Radewoosh rng_58 majk Swistakk Xellos antontrygubO_o Lewin neal

please,if anyone of you could solve

Stuck on it since days.

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

    I figured it out!

    Take all palindromes with length $$$N$$$ and subtract the number of palindromes that have a palindromic prefix. When the smallest palindromic prefix of our palindrome has length $$$k$$$, we just need to take that and append $$$N-k$$$ characters. The last $$$k$$$ characters are uniquely defined and the rest can be chosen in any (palindromic) way, so we have 2 cases:

    • if $$$2k \le N$$$, there are exactly $$$K^{N-2k}$$$ ways to append $$$N-k$$$ characters
    • if $$$2k \gt N$$$, there's at most one way to do that

    Notice that in the latter case, if the last $$$2k-N$$$ characters of our prefix don't form a palindrome, we can't make a palindrome with length $$$N$$$, so it seems like we need to count something different — palindromes that don't have a non-trivial palindromic prefix but have a palindromic suffix. Fortuniately, if a palindrome has a palindromic suffix with length $$$l$$$, it obviously also has a palindromic prefix with length $$$l$$$, so the only option for $$$2k > N$$$ is $$$2k = N+1$$$.

    Now it's obvious how to solve this with $$$O(N^2)$$$ DP. To speed up to $$$O(N + \log mod)$$$, use multiplicative inverse and remember sums of $$$c_k K^{-2k}$$$.

    → Reply