FINDID - Editorial

editorial
, , , , , ,
1

PROBLEM LINK :

Contest

Setter: Aditya Kumar Shaw
Tester: Reet Roy
Editorialist: Sitam Sardar

DIFFICULTY :

MEDIUM

PREREQUISITES :

Array
String
Prime Number Theorem

PROBLEM :

Chef is a secret agent for the Government of Chef Land. Chef has found a gang planning to attack Chef Land. The gang is going to bombard few cities in Chef Land. The names of the cities in Chef Land are always 7 digits numbers .

The gang leader, Almoodi, is fond of mathematics and has devised a unique and perfect method of selecting the cities to be bombarded. He has concatenated all prime numbers to create a big string: “23571113171923293137…”. He asks each of his bombers to provide a number ( which is not provided by previous bombers, to prevent collision). This number is that starting index in the string of primes, and the city name will be the next 7 digits in the string. E.g., if the bomber chooses 8, the city name will be 1719232. Note that the index of string starts from 0.

Chef has a spy in the gang. The spy has provided Chef all the numbers chosen by the bombers. However, Chef isn’t that comfortable with prime numbers and doesn’t have time to learn it. So, Chef has requested you to assist him in finding the city names before it is too late.

SHORT EXPLANATION OF THE QUESTION :

Here basically all prime numbers are concatenated in a string.

  • At first, you have to give input the number of the test cases (lets the input be n)
  • Thereafter we have to give n number of inputs which are basically different indices ( i ) of the string.
  • Now after getting each index we get the substring of the 7 characters from the i-th index ( subString[i,i+7] ).

QUICK APPROACH :

  1. Take Input the number of the test case (t) and corresponding indices (n).
  2. Now make a string that contains n th index and subSting[n,n+7].
  3. Then print the corresponding substrings of different indices.

EXPLANATION :

  • At first let’s take a max number 33000000 though 32000000 is sufficient for this problem
  • Then make an array needed for sieve (primeArr) of bool type of size max which contains 0 (false) or 1 (true) if its i^th index is non-prime or prime simultaniously.
  • Then create the desired string of prime numbers by using the primeArr.
  • Then take input the number of test cases (t) and maximum possible input (n) for each test case.

Time Complexity :

O(m * log log m)

Space Complexity :

O(m)

Here m = O(n log n) which is the size of the array primeArr, array needed for sieve.

֍ Now question is, how to find the value of m?

  • Let’s Find the value of m :
    We know (approximately) from the prime number theorem that
  1. Numbers of prime numbers till n, \pi (n) = n / log n
  2. n-th prime number p(n) = n * (log n + log log n)
    But we don’t need the nth prime number. Each prime number has some length. Most prime numbers will have length 6 for the given constraint for n ( 1.5 * 10^7 ). We can cross-check this fact by putting n = 4, 5, and 6 in Eqn(3) for primes of length 4, 5, and 6 respectively.
  3. Numbers of primes each having length x, Y(x) = π(10^(x+1)) -π(10^x)
    Hence, we can divide p(n) by 6 to get an approximation of m.
    We have got approx value of m = n * (log n + log log n) / 6. For n = 10^7, m is approximately 4.8 * 10^7.

We now try different values of m and print the length of the string of primes. We see that for m = 3.2 * 10*7, length of string > n while for m = 3.1 * 10^7, length of string < n. So, we shall use m = 3.2 * 10^7.

SOLUTION

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
int NextPrime(bool *arr, int n, int p);
void sieve(bool *arr, int n);
string stringOfPrimes(bool *arr, int n);
int main(void)
{
int max = 33000000; // though 32000000 is sufficient for this problem
bool *primeArr = (bool *)malloc(max * sizeof(bool));
sieve(primeArr, max);
string primes = stringOfPrimes(primeArr, max);
// cout << “size of prime string is " << primes.length() << endl;
int t, n;
cin >> t;
while(t–) {
cin >> n;
cout << primes.substr(n, 7) << endl;
}
return 0;
}
string stringOfPrimes(bool *arr, int n) {
stringstream st(”");
for(int i=2; i<n; ++i) {
if(arr[i]==1)
st << i;
}
return st.str();
}
void sieve(bool *arr, int n)
{
// initialize array with 1
// 1 means prime
// all non-primes will be changed to 0
for(int i=0; i<n; ++i) {
arr[i] = 1;
}
arr[0] = 0; //0 is not prime
arr[1] = 0; //1 is neither prime nor composite
int p = 2; //will start finding composites nos with 2
int n_sqrt = sqrt(n);
while(p <= n_sqrt) {
int index = pow(p,2);
for(; index<n; index+=p) {
arr[index] = 0;
}
//cout << "last " << p;
p = NextPrime(arr,n,p);
//cout << " next " << p << endl;
}
}

int NextPrime(bool *arr, int n, int p) {
int i;
for(i = p+1; i<n; ++i) {
if(arr[i]!=0)
break;
}
return i;
}

Tester's Solution

import math
max_val = 33000000
def sieve():
tr = [True] * max_val
s = ‘’ #string of primes generation
for i in range(2, max_val):
if(tr[i]):
s += str(i) #append if true
for j in range(i*i, len(tr), i):
tr[j] = False
return s
t = int(input())
s = sieve()
while(t > 0):
n = int(input())
print(s[n:n+7])#city id taking 7 digits starting from n
t -= 1