Problem Link:
Difficulty:
Simple
Pre-requisites:
None
Problem:
Given a matrix whose each entry is either ‘^’ or ‘#’, find the sum of weights of all CPCs. A cell is CPC if it is filled with ‘^’, and there exists a prime P such that there are P or more consecutive '^'s on each of its four sides(i.e. left, right, top bottom). The weight of CPC is number of distinct primes P which satisfy the above property.
Explanation:
You need to evaulate each of L, R, T, B for all cells in the matrix. This can be done trivially in O(n+m) time per cell, or O(m * n * (m+n)) time overall.
// computing L. Similarly for R, T, B.
int compute_L(int i, j):
while(i-L ≥ 0)
if mat[i-L][j] != '^'
break
return L-1
However, the above approach would need approximately 500 * 500 * 1000 = 2.5 * 108, which will time out.
How do we proceed then ?
Method 1
One way of going about is to try and optimize the above approach. Optimizations can be based on the fact that we want minimum of L, R, T, B. For a cell at (i, j),
- L can be at most i, R can be at most n-1-i, T can be at most j and B can be at most m-1-j. Therefore, min(L, R, T, B) ≤ min(i, j, m-1-j, n-1-i).
- If min(L, R, T, B) = K, then K can be computed in O(K) time.
int compute(int i, j):
int upper = min(i, j, n-1-i, m-1-j);
int K = 1;
while(K ≤ upper)
if mat[i+K][j] != '^' or mat[i-K][j] != '^' or mat[i][j-K] != '^' or mat[i][j+K] != '^'
break;
else
K++;
return K-1;
Complexity of this method is still O(n * m * (m+n)), but constants will be lower. To get an idea, for 500 x 500 grid, computing L, R, T, B separately for all cells will take upto 2.5 * 108(approx.) matrix lookups. However, the above method will need at most 8.3 * 107(approx.) matrix lookups, which is 3 times faster.
This approach is good enough to find out the value of K = min(L, R, T, B). To find no of primes upto K, we can compute offline and store all primes upto 500(actually upto 250) in an array, and then count the number of primes less than K.
K = compute(i, j)
I = 0
while(sorted-array-of-primes[I] ≤ K)
I ++;
// I is the number of monsters cell i,j can accommodate.
Method 2
We will confine ourselves to calculating L for all cells in O(n * m) time. R, T, B can be computed similarly.
We can compute L for a single cell in O(m) time.
Can we do better ? If we need to do this for a single cell, of course we cant do better because all relevant cells(that are O(m)) need to be checked.
So, is there some relation between the value of L for different cells, which can be used to compute L for all cells fast ?
If you think about it for a minute, the relation is obvious
L(i, j+1) = L(i, j) + 1 if mat[i][j] = ‘^’
= 0 otherwise
Therefore, we can compute the value of L for entire matrix as follows:
for i = 0 to n-1
L [i][0] = 0
for j = 1 to m-1
if L[i][j-1] == '^'
L[i][j] = L[i][j-1] + 1
else
L[i][j] = 0
The values of R, T and B can be computed for all cells similarly. The complexity of this method is clearly O(n * m).
Once K = min(L, R, T, B) has been computed, number of primes less than K can be read either from a precomputed lookup table, or by iterating through list of primes as in Method 1.
Setter’s Solution:
Can be found here
Tester’s Solution:
- Mahbub’s
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/CAOS2.cpp)
2. Sergey's
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/CAOS2.cpp)
Editorialist’s Solution:
Can be found here
