You are not logged in. Please login at www.codechef.com to post your questions!

×

DUALPAL - Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR'S, TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 28 Aug '15, 18:08

darkshadows's gravatar image

5★darkshadows ♦
3.0k91161186
accept rate: 12%

edited 09 Feb '16, 19:13

admin's gravatar image

0★admin ♦♦
17.4k347487515

why does the time limit for this question is so high 8 sec I haven't seen such high limit in any questions...?

(26 Sep '15, 00:49) jain_mj3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,272
×913
×872
×103
×72
×1

question asked: 28 Aug '15, 18:08

question was seen: 2,240 times

last updated: 09 Feb '16, 19:13