ironman7453's blog

Chef and the Dual Palindromes
By ironman7453, history, 9 years ago, In English

This problem was given at https://www.codechef.com/COOK61.

Problem link: DUALPAL

Problem statement:

A number is called a Dual Palindrome if it's representation in bases B1 and B2 are both palindromes. e.g. Let B1 = 3, B2 = 4, then number 130 (in base 10) will be called a Dual Palindrome, as it is palindrome in base 3 (11211) as well as in base 4 (2002). However, it is not a Dual Palindrome for B1 = 3 and B2 = 5 as it's not a palindrome in base 5(1010). Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 260. If there are more than 1000 Dual Palindromes, then output the first 1000 only (these numbers should be in base 10).

Input:

The fine line of the input contains an integer T denoting the number of test cases. Each test case consists of a single line containing two space separated integers: B1 and B2, respectively.

Output:

For each test case, output a list of space separated integers which are Dual Palindromes less than 2^60 for the input bases. If there are more than 1000 Dual Palindromes, then output the first 1000 only. The numbers should be printed in an ascending order.

Constraints:

1 ≤ T ≤ 5

2 ≤ B1 < B2 ≤ 16

Any idea how to approach the problem?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 260.
Maybe : Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 2^60.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I was looking at the post for like good 5min wondering why is that easy problem troubling everyone. Then I realised it's supposed to be 2^60 :D

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just thinking. The number of n-ary palindromes from 0 to 2^60 is roughly n^(1/2*log2^60/logn)=n^30log2/logn=2^30 ~ 10^9

We could generate all B2-nary palindromes till 2^60 and check if each one is also a B1-ary palindrome.

C++ can do as much as 10^8 operations per second. If we can implement palindrome generation and checking quick enough, we can potentially fit this calculation loop into 10 seconds.

Also note that the number of possible B1, B2 combinations is very small (about 100). We could try calculating all combinations on a local machine and try storing some of the results in an array. But I'm not sure if the solution size limitation (8000 bytes) allow us to do that.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are roughly 2^30 binary palindromes, but for any base other than 2, the number of palindromes fall quickly, note that there are about 2^19 ~ 5*10^5 palindromes in base 3 (using your formula). So, generating all B2-ary palindromes till 2^60 and then check for those that are B1-ary palindromes too would be fast enough, and the number of operations is below 10^8

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My formula shows that the number of palindromes for any n is almost the same. How many 10-ary palindromes are there from 0 to 2^60 ~ 10^18? about 10^9, right?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oops, I think you are right. It should be 3^19 instead of 2^19, that is about 10^9 as you said. And your formula works very well, I wasn't looking close enough.

        → Reply