PROBLEM LINK:
Author: Tasnim Imran Sunny
Tester: Istvan Nagy
Editorialist: Lalit Kundu
DIFFICULTY:
Hard
PREREQUISITES:
maths, backtracking
PROBLEM:
A number is called a Dual Palindrome if it’s representation in bases B1 and B2 are both palindromes. Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 2^{60}. If there are more than 1000 Dual Palindromes, then output the first 1000 only(these numbers should be in base 10).
EXPLANATION:
================
The cases where B1 and B2 are powers of same number then we have lots of Dual Palindromes, but since only the first 1000 palindromes are of interest the search will be finished quickly. The Dual Palindromes for other cases are very rare. The solution idea is backtracking with pruning.
Let’s say we want to build a Dual Palindrome with L digits(in base B1). For that, first we split the digits of base B1 palindromes in 4 groups of lengths approximately \frac{L}{4}. Now, consider two sets of numbers A and B(in base B1). Set A contains all the numbers possible by considering the first quarter digits(i.e. first \frac{L}{4} digits). Now, fixing first \frac{L}{4} digits fixes the digits in last quarter also. Assume, digits are all 0 in both middle quarters. This is the set of numbers called A.
Set B contains the possible numbers by considering the first and fourth quarter as all 0 s and we define all possible ways to fill 2^{nd} quarter, so this fixed the 3^{rd} quarter too.
Adding any element from A with any element of B, will always make a palindrome in B1. The problem is reduced to getting the pairs from A and B where their sum is palindrome in B2.
If you note, sets A and B have 2^{15} elements roughly in worst case.
Now, we have to construct the palindromes in B2. We use bactracking by placing digits from left to middle in our palindrome. At each node in the backtracking tree, we build two prefixes(say x and y) from sets A and B such that current palindrome is x … y … \textrm{rev}(y) … \textrm{rev}(x). Now, if there exists a pair of digits a and b such that x \textrm{concat} a is present in set A, and y \textrm{concat} b is present in set B(for implementing this setter has use Trie), and the new palindrome being formed in base B1 is a palindrome in B2, then we go ahead into the recursion tree with the new prefixes. Note, we are not exploring the exponential number of states in the backtracking recursion tree, because at each step we are pruning the subtrees by not going into unrequired nodes.
See setter’s code for the implementation.