MD_RIEV - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: evanraisul
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

1253

PREREQUISITES:

None

PROBLEM:

Consider the first N palindromic prime numbers.
How many of them have an even number of digits, and how many of them have an odd number of digits?

EXPLANATION:

This might seem daunting at first, but there’s a rather simple observation: 11 is the only palindromic prime with an even number of digits!

That’s because any even length palindrome must be a multiple of 11, and so clearly cannot be prime (unless it’s 11 itself).
It’s easy to see why: the well-known divisibility test for 11 is to check if the sum of even-indexed digits equals the sum of odd-indexed digits; and for an even-length palindrome, this is obviously true since each digit appears once in an even index and once in an odd index.

11 is the fifth palindromic prime (with 2, 3, 5, 7 coming before it).
So, the solution is:

  • If N \leq 4, there are 0 even-length palindromic primes and N odd ones.
  • Otherwise, there’s 1 even-length palindromic prime and N-1 odd ones.

TIME COMPLEXITY

\mathcal{O}(1) per testcase.

CODE

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    if n <= 4: print(0, n)
    else: print(1, n-1)
2 Likes
2

One can also see that the answer is always 1, n-1 for n >= 4 with sieve algorithm.

Sample Code:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>

#define all(v) v.begin(),v.end()
#define ep emplace_back
#define int long long
#define $AzH_TxdmN$ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;

const int MAX_N = 1e7;
const int __SQRT_MAX_N = 3163;
int t,n;
bool isPrime[MAX_N+1];
string s;
vector<string>primes;

bool check(const string &s)
{
    string tmp = s;
    reverse(all(tmp));
    return s == tmp;
}

void sieve()
{
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 1; i <= __SQRT_MAX_N; i++)
    {
        if (isPrime[i])
        {
            for (int j = i*i; j <= MAX_N; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= MAX_N; i++)
    {
        if (isPrime[i])
        {
            s = to_string(i);
            if (check(s))
            {
                primes.ep(s);
            }
        }
    }
}

signed main()
{
    $AzH_TxdmN$
    sieve();
    int odd = 0,even = 0;
    for (int i = 0; i < primes.size(); i++)
    {
        cout<<i<<"-th prime | Even Count: "<<even<<" | Odd Count: "<<odd<<'\n';
        primes[i].size() & 1 ? odd++ : even++;
    }
}
3

Unfortunately this isn’t really a proof.
What guarantee do you have that the 48374-th palindromic prime satisfies this property, for example? (it’s large enough that your code won’t compute it)

You observed a pattern and made a guess based on it, which turned out to be correct; but in general it’s good to try and prove your guesses, otherwise you might get WA on a more complicated problem and yet have no idea why.

4 Likes
4

this was such a troll question, i actually wrote a precomputation code for it and it still showed TLE. Any tips, on when to know, your code needs an overhaul in logic?

1 Like
5

As a rule of thumb, you can perform around 10^8 operations in one second.
If your algorithm needs significantly more than that, you definitely need something better.

In the case of this problem, the 10^5-th palindromic prime is around 13 digits long; so iterating across all the numbers, and checking if each one is a prime and/or a palindrome is obviously going to be way too slow - iterating till 13-digit numbers is already 10^{13}, then you have additional checks (primality testing is another \approx 10^6 operations per prime, for instance).

In almost every case, you should be able to tell whether your algorithm is fast enough before you even start coding.
If it’s not, you need to think more.

2 Likes
6

Hi @iceknight1093

I have go through both text and video editorial , but still i did not get it why there we get only one number with even no of digits when n>4 , can you please help .

7

Do you know the divisibility test for 11?
A number N = d_1d_2d_3\ldots d_k is divisible by 11 if and only if d_1+d_3+d_5+\ldots = d_2+d_4+d_6 + \ldots — that is, the sum of digits at odd positions equals the sum of digits of even positions.
For example, N = 1056 is divisible by 11, because 1+5 = 0+6, but N = 121212 is not, because 1+1+1\neq 2+2+2.

What happens if you have an even-length number that’s a palindrome?
The first and last digits are equal, but one of them is on an even position and one is on an odd position.
The second and second-last digits are equal, but again: one is at an even position and the other isn’t.
Similarly you can see the exact same thing happens to every digit: one equal pair will be at both even and odd indices.
So obviously, the sum of even-index digits and odd-index digits has to be equal, right?

This means that any even-length palindrome will be a multiple of 11, because it satisfies the divisibility test.
If a number is a multiple of 11, can it be a prime?

8

Hi @iceknight1093 ,

Thanks for help got it now