Another Contest 4 Problem 11 - Three Rectangles

View as PDF

Submit solution


Points: 1
Time limit: 0.5s
Memory limit: 256M

Problem type
Allowed languages
C++

In 2016, I proposed a problem about trying to take three rectangles and seeing if it was possible to combine them to form a square. It got accepted. Please implement this function instead.

bool f(int n)

You may assume 1 \le n \le 10^6.


Comments


  • 2
    ross_cleary  commented on April 18, 2020, 7:11 p.m.

    Any tips on how to not TLE. I think my solution has a O(n + sqrt(n)) time complexity, which should be well under the time limit.


    • 3
      Tzak  commented on April 19, 2020, 12:27 a.m.

      Hint: Aim for \mathcal O(\log n). (Solution)