Editorial for Mock CCC '18 Contest 1 S5 - A Palindrome Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: xiaowuc1

The intended solution is a linear-time DP where the relevant state includes the string of digits to consider and whether the leftmost digit is allowed to shift from nine to zero. Obviously, you never want to shift from nine to zero more than once.

The base case is a string of length zero or one, these strings are obviously palindromes.

The DP transition involves matching the first and last characters, and then solving the subproblem of making the string removing the first and last characters a palindrome. If the inner string is allowed to have its leftmost digit shift from nine to zero, then that forces an increment of the current leftmost digit. If the inner string is not allowed to have its leftmost digit shift from nine to zero, then all the increments must be accounted for immediately.

Comments


  • 0
    lonerz  commented on Feb. 12, 2018, 4:03 a.m. ← edited

    Can someone elaborate more on this editorial? Thanks! I'm not sure how to consider the shifting from nine to zero and carrying over to the next digits. EDIT: One example that I'm struggling with is "0999." How do we deal with increasing the last "9"?