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!

@prakhar17252
Can you please check this code why i am getting WA?
#include
using namespace std;
int main()
{
int test,n,ans=0;
cin >> test;
while (test–)
{
ans = 0;
int x;
cin >> n;
ans +=(n * n);
for (int i = 3; i < n; i +=2)
{
x =( n-i) + 1;
ans += (x * x);
}
if (n == 2)
ans = 2;
if (n == 3)
ans += 1;
cout << ans << endl;

}

}

1 Like
for _ in range(int(input())):
    n=int(input())
    s=(n*n)
    if n%2:
        s=s+1
    for i in range(3,n,2):
        s+=(n-i+1)*(n-i+1)
    print(s)

hey can you please tell me why I’m getting WA
I calculated all squares of size 1 and these are equal to n square

instead of n =int(input())

try this

n = input().strip()
n = int(n)

or

n = map(int , input().split())

hope this will work

'
 _ _ _		in a 3 * 3 matrix
|_|_|_|		there are 14 boxes
|_|_|_|		9(1*1) + 4(2*2) + 1(3*3)
|_|_|_| 	so,oddlen boxes = 9 + 1 = 10

 _ _ _ _
|_|_|_|_|	similarly, in a 4 * 4 matrix
|_|_|_|_|	there are 30 boxes
|_|_|_|_|	16(1*1) + 9(2*2) + 4(3*3) + 1(4*4)
|_|_|_|_|	so oddlen boxes = 16 + 4 = 20
'
# _   _   _  _  _
#|_|_|_|_|_|		now, let's take 5 * 5 matrix,
#|_|_|_|_|_|		even though the pattern is clearly visible by now
#|_|_|_|_|_|		for 5 * 5, there are 
#|_|_|_|_|_|		25(1*1) + 16(2*2) + 9(3*3) + 4(4*4) + 1(5*5)
#|_|_|_|_|_|		so oddlen boxes = 25 + 9 + 1 = 35

#As can be clearly seen, the patter followed is:
# n**2 (1*1) + (n-1)**2 (2*2) + (n-2)**2 (3*3) + ... + 1**2 (n*n)
for _ in range(int(input())):
	n,sum_ = int(input()),0
	for i in range(n,0,-2):
		sum_ += i**2
	print(sum_)

here’s my logic and solution

4 Likes

Great work, It helped a lot.

1 Like

very good explaination !

1 Like