Some days ago, I tried to solve Binary Palindrome. The problem seemed difficult at first and I had no idea how to approach it. As a start, I wrote a simple program to calculate the result for small inputs, and ... I saw a pattern! I guessed what the result could be, and after some tries I could get it Accepted!
I don't know if other people also solve problems by guessing or not. But this wasn't my first. Some others were:
I don't know if other people also solve problems by guessing or not. But this wasn't my first. Some others were:
- Difficult Choice: I wrote an O(N^3) DP locally, and looking at dp table I found a pattern, and invented an O(N^2) algorithm without knowing the logic,
- Cartoon: I wrote an O(N^2 * K) solution which didn't pass the time limit. Then I guessed an optimization like Knuth's optimization, and happily it worked!
Exercises 15.5-4:
Knuth has shown that there are always roots of optimal subtrees such that root[i, j - 1] ≤ root[i, j] ≤ root[i + 1, j] for all 1 ≤ i < j ≤ n. Use this fact to modify the OPTIMAL-BST procedure to run in Θ(n2) time.
I meant this optimization.
The solution for this problem is simple: modified Z-algorithm.