ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2061. OEIS A216264

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
Posted by Vit Demidenko 20 Nov 2018 17:16
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
Posted by Levon Oganesyan 3 Mar 2020 03:05
How could you bruteforce 2^61 strings of length 61?
Re: Some Deductions on the Problem
Posted by Virus TI 27 Jun 2020 01:37
imagine a binary tree of these strings, use DFS with eertree