CAOS1 - Editorial

Problem Link:








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).


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.