PROBLEM LINK:
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