PCJ18B - Editorial

PROBLEM LINK:

Practice
Contest

Author: Prakhar Gupta
Tester: Madhav Sainanee
Editorialist: Prakhar Gupta

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Given an N \times N chessboard, find out the number of squares with odd length.

QUICK EXPLANATION

The answer is \displaystyle\sum_{i = 0}^{\lfloor\frac{N}{2}\rfloor} {(N-2i)^2}

EXPLANATION:

For an example, let us take a chessboard of size 8 \times 8.

We take a horizontal rod of size 5 and try to slide it through the chessboard from left to right.
It can take the column numbers 1 \text{ to } 5, 2 \text{ to } 6, 3 \text{ to } 7 and 4 \text{ to } 8.

For a horizontal rod of size 4, it can take the columns 1 \text{ to } 4, 2 \text{ to } 5, 3 \text{ to } 6, 4 \text{ to } 7 and 5 \text{ to } 8.

From the above examples, we can infer that we can fit N - i + 1 rods of length i in an N \times N chessboard horizontally. Similarly, we can fit the same number of rods in the chessboard vertically, since it is a square and is symmetric.

If we consider these rods as the sides of the square of side i, we have N - i + 1 horizontal and vertical choices each. So, the number of squares of length i in a N \times N chessboard is (N - i + 1)^2.

Using this formula, we can replace i = 1, 3, 5…. as the side length of the square and add them up. This gives us \displaystyle\sum_{i = 0}^{\lfloor\frac{N}{2}\rfloor} {(N-2i)^2}.

Complexity: The time complexity is O(N) per test case.

BONUS: Try to solve the question in O(1) per test case.

Click to view

When N is even, the answer is 2^2 + 4^2 + 6^2 + ... + N^2. This can be written as 4 \times (1^2 + 2^2 + ... + \left(\frac{N}{2}\right)^2). This can easily be calculated using sum of squares.

When N is odd, the answer is 1^2 + 3^2 + ... + N^2. This can we written as (1^2 + 2^2 + 3^2 + ... + N^2) - (2^2 + 4^2 + ... + (N-1)^2) \text{ }. The first part can be solved using the sum of squares formula, and the second part can be solves as in the case of even N.

AUTHOR’S SOLUTIONS:

O(N) solution can be found here.
O(1) solution can be found here.

2 Likes

It’s really helpful!