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

9 Likes

Great work, It helped a lot.

1 Like

very good explaination !

1 Like

Thanks :slight_smile:

man you made this so easy understandable for me…

print(‘Thanks’)

`

1 Like

Thank you so much! Glad I could help :slight_smile:

1 Like

bro im new to competitive programming and also a noob can you please tell me how can i become better in this? i know practicing make perfect but phr v any tips?

Agree on that !

Join a gym, you’ll need it soon ~ pun intended

Also stop copying solutions in contests

Your friend solution
Your solution

Your friend solution 2
Your solution 2

n^2 (1x1) + (n-1)^2 (2x2) + (n-2)^2 (3x3) + … + 1^2 (nxn)
so for n == 8,
8^2 + 6^2 + 4^2 + 2^2 will give the required answer

i.e, 64 + 36 + 16 + 4 = 120. Hope it help : )

Got it @wicked_knight.
Somewhere I have read that to get the total number of squares in n * n chess board, compute 1^2 + 2^2 + 3^2 … n^2. So I thought to get odd number of side squares I have to sum 1^2 + 3^2 …etc.
Thank you for explanation.

1 Like

Welcome

I have found an even simpler solution which worked for all the test cases -

while (t–) {
int n{};
std::cin >> n;
int ans{};
while (n > 0) {
ans += n * n;
n -= 2;
}
std::cout << ans << std::endl;
}

I also worked out the same solution :slight_smile: