### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### PREREQUISITES

Ad Hoc, Sweep Line

### PROBLEM

You are given a chess board with several bishops, and several **obstacles**. Considering that the movement of the Bishops is blocked by these obstacles, you wish to find the **number of cells that are under threat from one or more Bishops**.

Note that if a cell is under threat from multiple Bishops, we must count it only once.

### QUICK EXPLANATION

We can imagine each Bishop to be at the center of an **X shaped region**. The region is terminated by either the **boundary of the chess-board** or some **obstacle**.

We can find the number of cells within this X shaped region.

Now, for all the Bishops together, we can find the **sum of of number of cells within their regions of attack**. The regions of attack of different bishops may **intersect** (we can easily handle overlaps, as we will see below). These **intersection points** have been double counted!

Finding the number of **intersection points** by use of a **sweep line algorithm**, we can count and then eliminate them.

The implementation of this approach, can use several simplifications as described below.

### EXPLANATION

**Consider bishops and obstacles in white cells and black cells separately**

We know that bishops in black cells do not share regions of attack with bishops in white cells. Thus, we can consider them as two separate cases for simplicity.

The real benefit of introducing this differentiation is in the following simplification.

**Tilt the board by 45 degrees**

Now, each region of attack is a simple **plus** shaped region, built from a **horizontal segment**, and a **vertical segment**. We consider white and black on different boards, hence do not have to worry about how to **not consider the intersection of segments from bishops which are rooted on cells of two separate colors**.

Consider a board of size **5 by 5**. The alternate boards that should be considered are shown below

Original Board.

1 | 2 | 3 | 4 | 5

1 | 2 | 3 | 4 | 5

## 6 | 7 | 8 | 9 | 10

## 11 | 12 | 13 | 14 | 15

## 16 | 17 | 18 | 19 | 20

21 | 22 | 23 | 24 | 25

Assuming that the top left cell is colored black, let us look at the arrangement of all the black cells tilted by 45 degrees. We preserve the labels of the cells as showed above to make the mapping obvious.

| | 1 | |

| | 1 | |

## | 11 | 7 | 3 |

## 21 | 17 | 13 | 9 | 5

## | 23 | 19 | 15 |

| | 25 | |

Let us look at the arrangement of all the white cells tilted by 45 degrees.

| 6 | 2 |

| 6 | 2 |

## 16 | 12 | 8 | 4

## 22 | 18 | 14 | 10

| 24 | 20 |

Note how the **black** board is built from cells numbered odd, and the **white** board from cells numbered even.

**Consider horizontal segments and vertical segments**

Now, in each one of the **sub-boards** separately (**black** and **white**), we can consider the line segments that are attacked by bishops. We know that the segments will be vertical and horizontal.

**We can count the number of cells in each one of the segments**. Next, we must find the **number of intersection points** caused by these segments. **Reducing this** from the **sum of number of cells in all the segments** leads us to the answer.

**Finding the number of intersections**

We have **N** horizontal and **N** vertical line segments (potentially fewer, because overlapping line segments from different bishops can be **merged** and considered as single line segment).

We wish to find the number of points at which these line segments **intersect**. We already know that two line segments that overlap (touch each other sideways) can always be merged and considered as a single segment. Thus, each intersection can only happen between one horizontal segment, and one vertical segment.

Let **T**, be an augmented binary tree that is aware of the **dynamic order index** of its members. This can be done in several ways, for example

- Use a Binary Index Tree (or Fenwick’s Tree)
- add 1 at the value that is inserted
- subtract 1 at the value that is deleted
- Now, sum until each value represents the order index of the value

- Use a Binary Tree with number of descendants stored at each node
- update this number with each insert / delete
- add the number of descendants for each left sub-child that is skipped in the traversal from root to the node. This represents the order index of the value.

Both the techniques above support each operation (add, delete and check-index) in **O(log N)** time, where we may add at most **N** items.

In the case of Fenwick’s Tree, because the number of values that are added is much smaller than the range of values, we must **relabel** the values to a smaller range [1 … number of values].

Let **E** represent the set of events for a **Sweep Line algorithm**. We will consider the following events

- Vertical segment start
- Vertical segment end
- Horizontal segment encountered

We can iterate through the list of events **sorted by the x-coordinate**. We handle the events as follows

- Vertical segment start
**Insert y coordinate of the segment in T**

- Vertical segment end
**Delete y coordinate of the segment in T**

- Horizontal segment encountered
- Add to result, the number of values in T between the start and end of the horizontal segment.
- The number of values can be calculated as
**T.OrderIndex(end) - T.OrderIndex(start) + 1**

Thus, we will know the number of intersection points.

The overall complexity of the algorithm would be **O(N log N)**, where **N is the number of bishops**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.