TABISHOP - Editorial

editorial
, , , , ,
1

PROBLEM LINKS

Practice
Contest

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

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

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

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.

1 Like
2

#include<stdio.h>
#include<conio.h>
main()
{
int N,K,M;
int i,counter,l,j;
counter=0;
printf(“enter n,k,m\n”);
scanf("%d %d %d",&N,&K,&M);
int arr[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};
int X,Y,U,V;
int u,v,t;
int bis[K][2];
int res[M][2];
printf(“enter pos of bishop\n”);
for(i=0;i<K;i++)
{
scanf("%d %d",&X,&Y);
bis[i][0]=X;
bis[i][1]=Y;
}
printf(“enter pos of other\n”);
for(i=0;i<M;i++)
{
scanf("%d %d",&U,&V);
res[i][0]=U;
res[i][1]=V;
}
for(i=0;i<K;i++)
{
for(j=0;j<4;j++)
{
t=1;
u=0;
v=0;
while(u!=N && v!=N && u!=1 && v!=1)
{
u=bis[i][0]+(arr[j][0]*t);
v=bis[i][1]+(arr[j][1]*t);
for(l=0;l<M;l++)
{
if(u==res[l][0] && v==res[l][1])
{
u=N;
}
}
t++;
counter++;
}

}
}
printf("%d",counter);
getch();
return 0;
}