Another Contest 4 Problem 11 - Three Rectangles

View as PDF

Submit solution


Points: 0
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


  • 0
    ross_cleary  commented on April 18, 2020, 11:11 p.m. edited

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


    • 5
      Tzak  commented on April 19, 2020, 4:27 a.m.

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