PROBLEM LINK:
Editorialist: Adithya Dsilva
DIFFICULTY:
EASY
PREREQUISITES:
Sorting, Arithmetic progression, Pair (its equivalent in your language), Dynamic array
PROBLEM:
You are given a grid of size N*M, where each element of the grid \in \{E,W,B\}. Note that E corresponds to ‘ . ‘ in the original question and has been changed for better readability.
You are given the location of all W and B cells. All other cells are E cells.
The raydistance of an E cell is defined as the distance traveled by a ray shot from this E cell towards the right of the grid, given that the ray
 passes through any E cell unaffected
 stops on reaching a B cell
 loses its power drastically on passing through a W cell and stops on reaching the next W or B cell
 stops on reaching a boundary cell, that is, cell (i,M)
More formally, if the starting cell is (i,j) and the ray stops at (i,k), the raydistance of this cell is kj+1, which is inclusive of both starting and ending cells.
Calculate the sum of the raydistance over all E cells in the grid.
EXPLANATION:
The first idea to strike our minds would be a simple brute force approach. For each E cell in the grid, we would stimulate the movement of the ray and find the raydistance of this cell.
However, this would \textcolor{green}{AC} only in the first subtask and would \textcolor{red}{TLE} in the rest due to the increased constraints, as the time complexity of this solution is O(N*M*M) = O(N*M^2).
How do we get an 100 pt solution?
This problem is a simple example of remodulation, or in layman terms, looking at the problem from another angle.
Notice that there are at max, 2*10^5 nonE cells in the entire grid. Could we try iterating through these to find the solution?
We start by making arrays for each of the N rows in the grid, and store locations of all W and B cells of a row, in its corresponding array. We could differentiate between the 2 types of cells (W and B) in the array(s) by assigning them a bool
value.
We shall assign W and B cells in the arrays with bool
values 0 and 1 respectively.
Now, we sort every array, in ascending order of the column indices.
What is the intuition behind reordering them based on their row appearance? A simple arrival to this would be as follows. Notice that a ray is restricted to the row from which it was shot  since it can only move to the right of the grid. Thus raydistance of a cell at (i, j) is influenced by nonE cells located in row i only. This is how we arrive at this logic!
The sorting intuition follows from the fact that a ray shot from cell (i,j) has to cross cell (i,j+k) before it can cross cell (i,j+k+1).
Thus arranging them in this order would help us to quickly find the next nonE cell after a particular E cell, thus enabling us to easily determine the cell where the ray would stop!
We get into further implementation details in the implementation section later!
However, for those of you who didn’t understand the above part clearly, I have added a sample C++
code implementing the above mentioned container.
C++ Code
vector<pair<int, bool>> A[N];
//Every B cell and W cell in row i (applies to all i)
//Is added into the array A[i]
Adding the input into the array A is as follows:
//If cell (i, j) is a W cell
A[i].push_back({j, 0});
//0 is used to show that cell (i, j) is a W cell
//How would we determine the kind of cell at (i, j) without the bool value?
//If cell (i, j) is a B cell
A[i].push_back({j, 1});
//1 is used to show that cell (i, j) is a B cell
Finally, sorting is achieved as follows:
//Sorting cells in every row based on order of appearance in the grid
//This sorting is done for all rows in the grid
sort(A[i].begin(), A[i].end());
//By default, it sorts the pairs in ascending order of the first element!
Now, lets get to the main part of the solution!
We start by defining an unprocessed cell as an E cell whose raydistance has not been computed and added to the final sum. This term shall be used throughout the editorial!
What we are going to do now is, iterate through all the nonE cells in every row, and for every nonE cell, we are going to process all the unprocessed cells before this cell at once.
More specifically, if we are currently processing a nonE cell at index (i,j), we compute the sum of the raydistance of all unprocessed (i,k) cells, where k<j.
How do we compute the raydistance of all unprocessed cells before a W or B cell?
Let firstUnp
be the first unprocessed index in a particular row whose raydistance we are currently computing.
Initially, firstUnp
is 0. Now there are two cases (the corner case, where there exists no nonE cell after firstUnp
is discussed later):
 The first nonE cell after
firstUnp
is a B cell, and  The first nonE cell after
firstUnp
is a W cell.
CASE (1):
Let the value of firstUnp
be x. Let the first B cell after x be at index y.
Now, shooting a ray from x would definitely end at y (since this a B cell and the first nonE cell). Thus the raydistance from x would be yx+1.
Note that shooting a ray from index x,x+1,\dots,y1 would all end at y (why?). Now, notice the raydistance from x,x+1,\dots,y1 to y:

yx+1=(yx+1)

y(x+1)+1=(yx)

\dots

y(y2)+1=3

y(y1)+1=2
This is equivalent to 2+3+\dots+(yx+1). Notice that this is an arithmetic sequence. We use the formula for calculating the sum of an arithmetic progression
Here,
 n = (yx+1)2+1=yx
 a_1=2
 a_n=yx+1
Substituting values into (1) yields,
which can be easily calculated in O(1).
The value of firstUnp
would now be y+1, as the raydistance of all indices <y in this row has been processed!
CASE (2):
Let the value of firstUnp
be x. Let the first W cell after x be at index y. Let the first nonE cell after y be at index z. As said before, the case where there exists no nonE cell shall be discussed later!
Now, shooting a ray from x would definitely end at z. Why so? Because a ray shot from x would drastically lose its power after crossing y and would stop completely at z, irrespective of whether the value at z is W or B.
Note that it is not necessary for a ray shot from an index after y to stop at z, since if the value at z is W, it would pass through this index z and stop only at the next nonE cell.
Recalling the quoted statement below, we are only going to compute the raydistance of all unprocessed cells before index y.
What we are going to do now is, iterate through all the nonE cells in every row, and for every nonE cell, we are going to process all the unprocessed cells before this cell at once.
The raydistance from x,x+1,\dots,y1 is as follows:
 zx+1=(zx+1)
 z(x+1)+1=(zx)
 z(x+2)+1=(zx1)
 \dots
 z(y1)+1=(zy+2)
The sum of all the above raydistance’s can be computed again using arithmetic progression.
Here,
 n=(zx+1)(zy+2)+1=yx
 a_1=zy+2
 a_n=zx+1
Thus the sum using (1) would now be
The value of firstUnp
would now be y+1, as the raydistance of all indices <y in this row have been processed!
We are close to finishing the solution, but we have to manage the case when the ray reaches the end of the grid.
Let us start by discussing the two possible cases for the last cell in every row of the grid. Notice the term grid and not array (Recall that the array stores the nonE cells only. This refers to the grid!)
 It is a nonE cell
 It is an E cell
Case (1)
Notice that interchanging the value of this cell (W \rarr B or B \rarr W) doesn’t affect the raydistance of any cell in that row. Why? This is because, a ray is destined to stop at this cell (since it can’t cross the grid), whatever the value of the cell is.
We can use this property to convert this cell to a B cell (if it was a W cell, or leave it untouched otherwise). But why would we need to do this?
Notice that while processing a W cell, we query for the next nonE cell in the sequence. However, since this is the last cell in the sequence, the query would return an outofbounds
error as there exists no other cell in the current row after this cell.
However, processing a B cell isn’t dependent on the next cell in the sequence, which makes it ideal to convert the W cell to a B cell!
You could go about without implementing this (using ifelse
to handle last cell), but this is more intuitive!
Case (2)
Notice we process all unprocessed cells before a particular nonE cell at once. However, if the last cell were to be an E cell, only the cells till the last nonE cell would be processed, leaving all cells after it unprocessed.
To overcome this issue, we convert this last cell of the row to a B cell (not to a W cell for the reason mentioned in Case (1) above), as all the remaining rays will stop at this cell.
However, a ray can’t be shot from a nonE cell, and thus a ray shot from this originally E cell won’t get counted by the above formula’s (as the formula’s believe this is a nonE cell). Thus we have to add 1 to the final answer manually, as a ray can be shot from this E cell, with raydistance 1.
You can observe the order of execution in the implementation section below!
IMPLEMENTATION:
 Start by creating a variable
rayDist
, which will hold the final answer. Remember to use a 64 bit datatype, as the overall sum can exceed 10^9(why?)  We first start by storing the input in an array of size N, consisting of dynamic arrays (
vector<>
inC++
is an example for dynamic array), arranged according to the rows in which they are located.  We differentiate between W and B cells by assigning them
bool
values 0 and 1 respectively. More formally, for a nonE cell at location (i,j), we add the pair \{j,*\} into dynamic array at A[i], where * isbool
value 0 if it is a W cell or 1 otherwise.  Then, for every row i\space(1 \le i \le N), we sort the dynamic array A[i] according to the order of appearance of the first value in the pair (sort according to the value of j).
 Next, for every row i in A, we check for the last value in the dynamic array at A[i] (since the array is sorted, the last element corresponds to the last nonE cell in this row).
Now, one of the 2 things can happen: The last term in A[i] has value \{M,*\}, where * can be any of the
bool
values. We convert this * tobool
value 1(we make it a B cell).  The last term (the array might even be empty!) is not of value \{M,*\}. Here, we add pair \{M,1\} to the end of the dynamic array at A[i] and add 1 to
rayDist
.
 The last term in A[i] has value \{M,*\}, where * can be any of the
 Next we start by iterating through each of the rows i in A. For each row, we calculate the raydistance of the unprocessed cells before every nonE cell (which is stored in A[i]) using the methods mentioned above. You can have a look at the code snippet below for a understanding on how to execute this.
 Finally, we output the value of
rayDist
!
SOLUTION SNIPPET:
ll APSum(int n, int a1, int an){
return ((ll)n * (a1 + an)) / (ll)2;
//AP Sum formula!
}
//0 based indexing is being used in this code!
//{*, 0} > W cell, {*, 1} > B cell
ll rayDist = 0; //The sum of all ray distances
for(auto &i : A){
sort(i.begin(), i.end()); //Sort based on order of appearance
if(i.empty() or i.back().first != M  1){
//If last nonE cell in this row is not at index M  1
i.push_back({M  1, 1}); //Push a B cell to the last column
rayDist++; //A ray can be sent from this cell (the cell we have made B)
//and it has raydistance of 1. So add it to the sum!
}else{ //Last column of this row has a W or B cell
i.back().second = 1; //Make this a B cell
}
}
for(auto i : A){
int firstUnp = 0; //First index on this row whose raydist is not calculated
for(int j = 0; j < i.size(); j++){
int &y = i[j].first; //y as in the editorial
//y is the location of the current NonE cell being processed
if(i[j].second == 1){ //B cell being processed
//AP Sum calculation for Case (1)
rayDist += APSum(y  firstUnp, 2, y  firstUnp + 1);
}else{ //W cell being processed
int &z = i[j + 1].first; //z follows from the editorial
//This will never go OutofBounds
rayDist += APSum(y  firstUnp, z  y + 2, z  firstUnp + 1);
//AP Sum calculation for Case (2)
}
firstUnp = y + 1; //Update firstUnp!
}
}
cout << rayDist << endl; //The final answer
TIME COMPLEXITY:
Sorting all the w+b cells would take worst case, O((w+b)\log(w+b)).
Since only 1 iteration is done through all these w+b cells, the time complexity of this task if O(w+b).
Thus the overall complexity is
which fits within the time constraints!
SOLUTIONS:
Editorialist’s solution can be found here.
SIMILAR PROBLEMS:
As I’ve been unable to find good similar problems of this kind, please suggest some problems (if you know any) in the comments section below, and I’ll try to add it here!
Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!
Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 15, where 5 represents an awesome editorial)
 1
 2
 3
 4
 5
0 voters
Also don’t forget to upvote this post if you liked it !