CAOS1 - Editorial

cakewalk
caos1
editorial
sept13

#1

Problem Link:

Practice

Contest

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*[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*[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

(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


#2

All links to the solutions broken.