(Contest problem) Count the number of squares that are not attacked by bishops

Question

My solution is in below.

The bishop in chess is a piece that attacks all squares on the same diagonal (on both diagonals).

Shakhriyar placed m bishops on a chessboard of size n * n. Now he wants to count the number of squares that are not attacked by bishops. Help Shahriyar in this matter.

Input data First line contains two integers: the size n (1 ≤ n ≤ 10^6) of a chessboard and the number of bishops m (1 ≤ m ≤ 10^5). Each of the next m lines contains pair of integers: r[i] и c[i] (1 ≤ r[i], c[i] ≤ n) - the numbers of row and column where the bishop number i is located. The bishops are numbered from 1 to m. All bishops are located on different squares.

Output data Print the number of squares not attacked by the bishops.

https://www.eolymp.com/en/problems/9630

Input example #1

10 6

4 7

8 5

8 7

6 2

9 7

8 4

Output example #1

33

I solved up to here:

(sorry for the messy picture)

diagonals=2n-1

d-diagonals number

(i;j)-coordinats of points(y,x)

From picture 1:

1:(6;1)

2:(5;1); (6;2)

3:(4;1); (5;2); (6;3)

4:(3;1); (4;2); (5;3); (6;4)

...

10:(1;5); (2;6)

11:(1;6)

d=n-(i-j);

From picture 2:

1:(1;1)

2:(1;2); (2;1)

3:(1;3); (3;1); (2;2)

4:(1;4) (4;1) (2;3) (3;2)

...

d=i+j-1;

Intersections of diagonals:

Diagonals from picture 1(2)	Diagonals from picture 2(1)
1, 11	6
2, 10	5, 6, 7
3, 9	4,5,6,7,8
4, 8	3,4,5,6,7,8,9
5, 7	2,3,4,5,6,7,8,9,10
6	1,2,3,4,5,6,7,8,9,10,11

While finding the number of points, Intersections are preventing me . How can I fix this?

My code(C++):

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> hit_diagonals1,hit_diagonals2;
    int n,m;
    cin>>n>>m;
    for(int k=0,i,j; k<m; k++){///O(m)-->1e5
        cin>>i>>j;
        hit_diagonals1.insert(n-(i-j));
        hit_diagonals2.insert(i+j-1);
    }
    int cnt=0;//hit_points_number
    
    //.....
    
    cout<<n*n-cnt<<'\n';
    return 0;
}

Answer 1

You can solve this in O(m log m) time using a diagonal sweep-line algorithm.

First, let's call the diagonals where x+y is constant the "backslash diagonals" and the "slash" diagonals will be the ones where x-y is constant.

Now we can consider the backslash diagonals in order from 0 to 2m+1 (the maximum x+y).

First, make a list of "events". For each bishop position (x,y), record:

• (x+y, 'cover'): This indicates the backslash diagonal the the bishop completely covers;
• (abs(x-y), 'enter'): The first backslash diagonal at which the bishop starts covering its slash diagonal:
• (m+m-1-abs(x,y), ' exit'): The first backslash diagonal at which the bishop no longer covers its slash diagonal.

Make an initially empty dictionary slashes to keep track of the number of bishops covering each slash diagonal. While modifying this map, you will also make sure that you can keep track of the number of non-zero entries.

Now, sort the events by backslash diagonal, and process them in order, grouping by backslash diagonal.

For each backslash group <= (m-1)+(m-1): - accumulate the number of unattacked squares since the last backslash group with events. Since there were no events in these backslashes, that means that you can calculate the number of unattacked squares with a simple formula. - process the 'enter' and 'exit' events to update the slashes map. - if there is a 'cover' event, then just go to the next group, because there are no unattacked squares in the backslash. - otherwise, use the number of non-zero entries in slashes to calculate the number of unattacked squares in the backslash. It's the length of the backslash diagonal minus the number of non-zero entries.

Finally, if you didn't process backslash 2(m-1), the last one, then use the add the number of squares in all the unprocessed backslashes -- they aren't attacked.

Note that the constraints in the problems suggest that an O(m²), O(m + n), or O(m + n log n) algorithm is expected. This is O(m log m), which is then better than they expect.

Answer 2

As the diagonals have identifying numbers that are in a small range, you can use a vector for this instead of a set. The index is the diagonal number, and the corresponding value indicates whether the diagonal is attacked or not (0 or 1).

The algorithm could first iteration the forward diagonals (/) and only when it finds that diagonal is not attacked, it could iterate the relevant crossing diagonals to count those that are also not attacked. Note that the number of crossing diagonals depends on which forward diagonal is under consideration, and the numbers of these crossing diagonals are always 2 steps apart (they are either all odd or all even for a given forward diagonal).

Here is how it could be coded:

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> diagonals(4*n, 1); // initialise with all 1
    
    for (int bishop = 0, row, col; bishop < m; bishop++) {
        std::cin >> row >> col;
        // Mark the two diagonals that this biship covers with 0
        diagonals[row+col] = diagonals[3*n+(row-col)] = 0;
    }
    
    int freeCount = 0;
    for (int forwIdx = 2, lowIdx = 3*n, highIdx = lowIdx; forwIdx <= 2*n; forwIdx++) {
        if (diagonals[forwIdx]) { // Non-attacked diagonal (/)
            // The crossing diagonals (\) always have same parity (+2)
            for (int crossIdx = lowIdx; crossIdx <= highIdx; crossIdx += 2) {
                freeCount += diagonals[crossIdx];
            }
        }
        int grow = forwIdx <= n ? 1 : -1; 
        lowIdx -= grow;
        highIdx+= grow;
    }
    std::cout << freeCount << '\n';
    return 0;
}