Practice

Contest

Cakewalk

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:

1. Mahbub’s
``````
2. Sergey's

``````

# Editorialist’s Solution:

Can be found here

1 Like

All links to the solutions broken.

//