XLSQUARE - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

CAKEWALK

PROBLEM:

Given N squares of side length A, whose sides are parallel to the coordinate axises, calculate the side length of the largest square you can make, whose area is completely covered by a subset of these N squares. You may not rotate the squares or overlap them.

EXPLANATION:

Observation: The side length of the largest square is always a multiple of A.
(This is because we are tiling the area of the square completely with squares of side length A).

Thus, if the side length of the mega square is X*A, we will require X*X squares of length A to cover the area of the mega square. All we are left to find is the largest X such that X*X \le N. This is equivalent to X \le \sqrt{N}. So, the largest valid X would then be \lfloor\sqrt{N}\rfloor.

The side length of the largest mega square is thus \lfloor\sqrt{N}\rfloor*A.

TIME COMPLEXITY:

O(1) per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

why I got wrong answer
#include <iostream> #include <cmath> int main() { int T; std::cin>>T; while(T--) { int N,A; std::cin>>N>>A; std::cout<<std::floor(std::sqrt(N))*A<<'\n'; } }

3

Hey, there seems to be a compiler dependent problem caused by the cout statement.

Typecasetung the std::floor(std::sqrt(N)) to int before multiplying it to A gives an AC.