CAOS2 - Editorial

Problem Link:

Practice

Contest

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:

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

3 Likes

All links to the solutions broken

Whats wrong with my solution. Still ??

My solution for coa2

can any body comment on my algorithm…???
Algorithm is…

  1. First of all we can neglect first two rows and two columns as these cells can’t give us cpc
  2. then if cell is not a wall we will compute L,R,T,B but one at a time but we can move in all direction one by one till we get # or the end of map where ever the loop will stop gives d minimum of L,R,T,B
  3. CHECK with precomputed prime no…

can u tell me d complexity of my program …here i am submitting d program

http://www.codechef.com/viewsolution/2665933

Your code complexity is O(T*N^3), try your code execution time for empty map 500x500 with 100 same test cases…

COA 1 was accepted !! Shockingly

can anyone tell…where am i going wrong.
my algorithm is-

L[i][j] - number of continuous ‘^’ left to L[i][j] (excluding L[i][j])

U[i][j] - number of continuous ‘^’ up to L[i][j] (excluding L[i][j])

R[i][j] - number of continuous ‘^’ right to L[i][j] (excluding L[i][j])

D[i][j] - number of continuous ‘^’ down to L[i][j] (excluding L[i][j])

First initialize the boundary by zero (because at least one parameter would be zero)

for(i=0;i<r;++i){
		for(j=0;j<c;++j){
				if(i>=1 && a[i-1][j]=='^') U[i][j] =1+U[i-1][j];
				if(j>=1 && a[i][j-1]=='^') L[i][j] =1+L[i][j-1];
				if(c>=j+1 && a[i][c-j]=='^') R[i][c-1-j]=1+R[i][c-j];
				if(r>=i+1 && a[r-i][j]=='^') D[r-1-i][j]=1+D[r-i][j];
			
		}
	}
p[0]=0; s=0;
for(i=0;i<r;++i){
		for(j=0;j<c;++j){
			if(a[i][j]!='#')	
				m = min(L[i][j],U[i][j],R[i][j],D[i][j]);
			else m=0;
			s+=p[m];
		}

	}

you can access my full code at http://www.codechef.com/viewplaintext/2684034

Thanks!!

1.can anyone tell me what wrong with my technique of not processing certain cells due to its proximity to # by 2
2.coupled with using a default cell value of min(l,r,u,d) calculated from the boundary of grid and

adjusting based on a # on a row or column.

Notice that number of #'s and good cells are inversly proportional.

so running time is O(number of # * number of good cells)

You have used character arrays, which can store only upto 255. So, if left = 300, right=top=bottom=100,
min should be 100. but it will actually be 44, because left will become 44.

1 Like

I havent seen your solution, but if your solution is really of complexity you say it is, then it is too slow. Consider the case when the left half of grid is all ‘#’ and right half is all ‘^’. Then your code will take O(n^2 m^2) time.

You have used character arrays, which can store only upto 255. So, if left = 300, right=top=bottom=100,
min should be 100. but it will actually be 44, because left will become 44.

1 Like

@admin: i guess in following code there is missing j++; statement
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;
return K-1;

Actually it was K++ that was missing :slight_smile:

But thanks for pointing the mistake. I have corrected it now.

Can you please help? My code is correct as far as I know but it still shows ‘Wrong Answer’ when I submit. My code for CAOS1 worked perfectly and showed AC too.

Link : http://www.codechef.com/viewsolution/2688274

@sanjam_kumar Consider your function : calcmin(char a[][510], int x, int y).
I guess the problem lies in this line :

   while ( [x][k]=='^' && a[x][l]=='^' && a[i][y]=='^' && a[j][y]=='^')

You are not performing any checks on the bounds of the varibles i,j,k,l to check that they lie within the R*C grid. you should put checks to see that they are >=0 and less than R and C in their respective cases. Otherwise if one reaches the end of the grid, it will not see a ‘^’ and break from the loop. you are lucky you did not get a runtime error because of array index becoming negative.

@kcahdog I don’t think that’s the error.

I submitted the same exact code for CAOS1 with just the count++ implement of (z>=2). It worked fine there.

Guess you found the bug. always perform bounds checking in arrays.You were lucky your code got AC in CAOS 1!

simplest
http://www.codechef.com/viewsolution/2666152

@utkarsh_lath : I have made it integer to protect overflow, still it is wrong answer so is there any logical mistake i have made??
If yes, could you please provide me the test case?
here is the new submission link http://www.codechef.com/viewsolution/2710467

@y07uc118 does your p array contain only zeros?

p[0]=p[1]=0;
for(i=2;i<250;++i) p[i]+=p[i-1];