Another Contest 4 Problem 11 - Three Rectangles - Olympiads Online Judge

Another Contest 4 Problem 11 - Three Rectangles

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$ ~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)$ ~\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)$ ~\mathcal O(\log n)~. (Solution)