ZCO17002-Editorial

infinitepro · September 28, 2019, 12:58pm

PROBLEM LINK:

Practice

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 ray-distance 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 ray-distance of this cell is k-j+1, which is inclusive of both starting and ending cells.

Calculate the sum of the ray-distance 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 ray-distance 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 re-modulation, or in layman terms, looking at the problem from another angle.

Notice that there are at max, 2*10^5 non-E 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 re-ordering 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 ray-distance of a cell at (i, j) is influenced by non-E 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 non-E 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 ray-distance 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 non-E cells in every row, and for every non-E cell, we are going to process all the unprocessed cells before this cell at once.
More specifically, if we are currently processing a non-E cell at index (i,j), we compute the sum of the ray-distance of all unprocessed (i,k) cells, where k<j.

How do we compute the ray-distance of all unprocessed cells before a W or B cell?

Let firstUnp be the first unprocessed index in a particular row whose ray-distance we are currently computing.
Initially, firstUnp is 0. Now there are two cases (the corner case, where there exists no non-E cell after firstUnp is discussed later):

The first non-E cell after firstUnp is a B cell, and
The first non-E 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 non-E cell). Thus the ray-distance from x would be y-x+1.

Note that shooting a ray from index x,x+1,\dots,y-1 would all end at y (why?). Now, notice the ray-distance from x,x+1,\dots,y-1 to y:

y-x+1=(y-x+1)
y-(x+1)+1=(y-x)
\dots
y-(y-2)+1=3
y-(y-1)+1=2

This is equivalent to 2+3+\dots+(y-x+1). Notice that this is an arithmetic sequence. We use the formula for calculating the sum of an arithmetic progression

\frac{n}{2}(a_1+a_n)\tag{1}

Here,

n = (y-x+1)-2+1=y-x
a_1=2
a_n=y-x+1

Substituting values into (1) yields,

\frac{y-x}{2}(y-x+3)

which can be easily calculated in O(1).

The value of firstUnp would now be y+1, as the ray-distance 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 non-E cell after y be at index z. As said before, the case where there exists no non-E 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 non-E cell.

Recalling the quoted statement below, we are only going to compute the ray-distance of all unprocessed cells before index y.

What we are going to do now is, iterate through all the non-E cells in every row, and for every non-E cell, we are going to process all the unprocessed cells before this cell at once.

The ray-distance from x,x+1,\dots,y-1 is as follows:

z-x+1=(z-x+1)
z-(x+1)+1=(z-x)
z-(x+2)+1=(z-x-1)
\dots
z-(y-1)+1=(z-y+2)

The sum of all the above ray-distance’s can be computed again using arithmetic progression.

Here,

n=(z-x+1)-(z-y+2)+1=y-x
a_1=z-y+2
a_n=z-x+1

Thus the sum using (1) would now be

\frac{y-x}{2}(2z+3-x-y)

The value of firstUnp would now be y+1, as the ray-distance 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 non-E cells only. This refers to the grid!)

It is a non-E 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 ray-distance 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 non-E cell in the sequence. However, since this is the last cell in the sequence, the query would return an out-of-bounds 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 if-else to handle last cell), but this is more intuitive!

Case (2)

Notice we process all unprocessed cells before a particular non-E cell at once. However, if the last cell were to be an E cell, only the cells till the last non-E 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 non-E 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 non-E cell). Thus we have to add 1 to the final answer manually, as a ray can be shot from this E cell, with ray-distance 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 data-type, 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<> in C++ 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 non-E cell at location (i,j), we add the pair \{j,*\} into dynamic array at A[i], where * is bool 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 non-E 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 * to bool 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.
Next we start by iterating through each of the rows i in A. For each row, we calculate the ray-distance of the unprocessed cells before every non-E 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 non-E 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 ray-distance 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 Non-E 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 Out-of-Bounds
            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

O((w+b)+(w+b)\log(w+b)) \approx O((w+b)\log(w+b))

which fits within the time constraints!

SOLUTIONS:

Editorialist’s solution can be found here.