PROBLEM LINK:
Author: Kornala Arun
Editorialist: Kornala Arun
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Maths
PROBLEM:
Given a (n+1) * (n+1) grid find the no of squares possible such that either the sides or the diagonals lie in the grid directions (i.e. x and y).
EXPLANATION:
It is a counting problem. First we will take into account the squares that have their sides in x and y directions. Assume that the distance between any two consecutive points on the grid is 1 unit. Thus we have:
No of squares of side length 1 = n^2
No of squares of side length 2 = (n-1)^2 (Note that 2 different alternatives can have a maximum of 2 vertices common)
:
:
No of squares of side length n-1 = 2^2
No of squares of side length n = 1^2
Therefore no of squares that have their sides along grid direction = 1^2 + 2^2 + ……+ n^2 = n*(n+1)(2*n+1)/6
Now let us take the squares where diagonals are along grid directions. An important observation here is that diagonal lengths must be even (this is because for odd length diagonal, if the other diagonal won’t lie on the grid. As such only two outposts will be possible).
Case 1:
If n is even we will have:
1 square having diagonal length as n
3^2 squares having diagonal length as (n-2)
:
:
(n-1)^2 squares having diagonal length as 2
Total = 1^2 + 3^2 + …. + (n-1)^2 = n*(n-1)*(n+1)/6
Case 2 :
If n is odd we have:
2^2 squares with diagonal length as (n-1)
4^2 squares with diagonal length as (n-3)
:
:
(n-1)^2 squares with diagonal length as 2
Total = 2^2 + 4^2 + … + (n-1)^2 = 4*(1^2 + 2^2 + … + ((n-1)/2)^2)= (n-1)*(n+1)*n/6 (which is same as Case 1)
Total no of squares = (n*(n+1)(2n+1) + n(n+1)(n-1))/6 = n(n+1)(2n+1+n-1)/6=n*(n+1)*n/2
So finally given n , answer is n*(n+1)*n/2.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.