Problem Link:
Difficulty:
Cakewalk
Pre-requisites:
None
Problem:
Given a matrix whose each entry is either ‘^’ or ‘#’, find the number of 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).
Explanation:
It is easy to see that since 2 is the smallest Prime, for a cell to be CPC, it is necessary and sufficient that
2 ≤ min(L, R, T, B)
Therefore, all you were supposed to do was to check the number of consecutive '^'s on each of its four sides is at least 2.
bool check-CPC(int i, int j) // 1 ≤ i ≤ n, 1 ≤ j ≤ m
if mat[i][j] != '^'
return false
if i-2 < 1 or j-2 < 1 or i+2 > n or j+2 > m
return false
for (int x=-2; x<=2; x++)
if mat[i+x][j] != '^' or mat[i][j+x] != '^'
return false
return true
We could also calculate the exact values of L, R, T, B and then check if its minimum is at least 2, but that will be covered in CAOS2 editorial.
Setter’s Solution:
Can be found here
Tester’s Solution:
- Mahbub’s
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/CAOS1.cpp)
2. Sergey's
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/CAOS1.cpp)
Editorialist’s Solution:
Can be found here