PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : HARD
PREREQUISITES:
Matrix, Divide and Conquer, Recursion
PROBLEM:
Ali likes to play with wonderful matrices. To him, a matrix is wonderful if
Contains only digits from ‘0’ to ‘9’
When we arrange the digits of each Row, we should get a prime number.
The matrix should be symmetrical
Ali was playing, and while playing, he got a random number. He wants to make wonderful matrices, keeping this number as the first row. How many matrices can he make?
#QUICK EXPLANATION:
#EXPLANATION:
We need to count the number of symmetric matrices with a given first row, where each row is a prime number.
Since the matrix is symmetric, it is determined by its cells above or on the main diagonal. Let’s examine all possible values of digits above the main diagonal (at most 106 cases). Now the values of the remaining unknown digits (on the main diagonal) are independent of each other because each of them affects exactly one row of the matrix. Therefore, it is enough to count independently the number of possible values for each of the digits on the diagonal, multiply them and add the received number to the answer.
Moreover, it’s possible to pre-calculate such numbers for each position of an unknown digit and for each collection of known digits.
These observations are enough to pass all the tests.
One could go further, examining each next digit above the main diagonal only if it’s row and column can be extended to prime numbers by some digits, unknown at moment of this digit placing. Such a solution allows to find answers for all possible tests in the allowed time, but it wasn’t required.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define endl “\n”
#define IOS cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
const int N = 1e6;
int p[N+100]; //primes
int dp[N+100]; //next biger prime
int m[7][7]; //matix
int ten[7]; //index stands as power to ten. ex. ten[4]=10**4
int ans;
int n; //n=log10(num)
void getprimes(){
p[0]=1;p[1]=1;
for(ll i=2;i<=N;i++)
if(!p[i])
for(ll j=i*i;j<=N;j+=i) p[j]=1;
}
void dfs(int x){
if(x>n){
ans++;
return;
}
int val=0;//value of line
for(int i=1;i<x;i++){
val+=m[i][x]*ten[n-i];//matrix on diagonal mirrornig
}
int l=dp[val]; //prime with property >= val
int r=val+ten[n-x+1]; //right limit adds to last mirrored deciaml number +1
while(l<r){
int t=l;
for(int i=n;i>x;i--){ //fill matrix row
m[x][i]=t%10;
t/=10;
}
dfs(x+1);
l=dp[l+1]; //jump to next bigger prime
}
}
int t;
int main(){
IOS;
getprimes();
ten[0]=1;
dp[N+1]=N+1;
for(int i=N;i>=0;i--){
if(!p[i]) dp[i]=i; //if prime
else dp[i]=dp[i+1]; //if not prime
}
for(int i=1;i<7;i++){
ten[i]=ten[i-1]*10;
}
cin>>t;
while(t--){
int num;cin>>num;
n=0;
for(int i=num;i!=0;i/=10) n++; //n=log10(num)
for(int pos=n;pos>=0;pos--){ //filling first row
m[1][pos]=num%10;
num/=10;
}
ans=0;
dfs(2);
cout<<ans<<endl;
}
return 0;
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person