BISHOP - Editorial

PROBLEM LINK:

Practice

Contest

Author: Chinmay Rakshit

Tester: Chinmay Rakshit

Editorialist: Chinmay Rakshit

DIFFICULTY:

MEDIUM

PREREQUISITES:

HASHING

PROBLEM:

given the positions of the bishop on the chess board you have to find how many of them are in the attacking position

attacking positions is defined as if both bishops are in same diagonal irrespective if any bishop is in between or not.

QUICK EXPLANATION:

to solve this brute force will be to calculate for a single bishop how many bishops lies in its diagonal and repeat this for all this will be O(N^2) and will barely pass 3 subtasks

now another way can be to store the data.
We can notice that the bishops lie in the same diagonal if:

  • there sum of x and y-axis are same.

  • there difference of x and y-axis are same.

so we make a map and just store the frequence for each

map[x+y]++

map[x-y]++

and after that looping over the map and count the number of ways a pair can be chosen from a set of pairs,
suppose the number of pairs is n so nC2 is the number of ways a pair can be chosen thus count+=n*(n-1)/2

print count

But using map will only provide 80 points and will not allow passing the last subtask, as map uses logn time to store value so total time complexity turns to nlogn

for O(N) solution, suppose instead of using map we use an array for hashing thus same procedure and the question is solved and 100 points is achieved.

AUTHOR’S SOLUTIONS:

Tester’s solution can be found here

Why do we need to maintain separate arrays for addition and subtracted values?