Some Deductions on the Problem

Posted by

orzczt 3 Apr 2016 12:54

If you search for the id "A216264" on oeis.org, you would find a table of a(n), n=1..60.

One interesting thing is that the site said that it was Mikhail Rubinchik who calculated a(26) to a(60), which happened to be out of the brute-force range. What is really disappointing is that in this problem, n may be 61, I think it's that guys's trick to play with us. Another interesting fact is that this guy also invented and introduced the Palindromic Tree. So, I deduce that the solution to this problem is somehow related to this data structure.

*Edited by author 03.04.2016 12:56*

Re: Some Deductions on the Problem

Yes, with eertree you can bruteforce all answers

My solution runs ~20 hours to generate result, it can be theoretically speed up 2 times by bruteforcing only strings such s<=reverse(s)

Re: Some Deductions on the Problem

How could you bruteforce 2^61 strings of length 61?

Re: Some Deductions on the Problem

imagine a binary tree of these strings, use DFS with eertree