Subtask 1

For subtask 1, we can store the numbers ~N \bmod 1, N \bmod 2, N \bmod 3, \dots, N \bmod N~ in an array, sort it, and output the ~\lfloor \frac{N+1}{2} \rfloor~th element.

Time complexity: ~\mathcal{O}(N \log N)~

Alternatively, we can use an ~\mathcal{O}(N)~ median finding algorithm, such as std::nth_element in C++.

Subtask 2

Subtask 2 is created to reward solutions that are faster than ~\mathcal{O}(N)~ but not fast enough for subtask 3 or are incorrect because of using only 32-bit integers.

Subtask 3

For subtask 3, we can perform a binary search on the answer. To count how many numbers in the sequence are less than or equal to the number we are testing, note that ~N \bmod x = N - x\lfloor \frac{N}{x} \rfloor~ and there are only ~\mathcal{O}(\sqrt N)~ different possible values of ~\lfloor \frac{N}{x} \rfloor~. When ~\lfloor \frac{N}{x} \rfloor~ is fixed, the numbers ~N \bmod x = N - x\lfloor \frac{N}{x} \rfloor~ form an arithmetic sequence, and we can use simple math to count how many of them are small enough.

Time complexity: ~\mathcal{O}(\sqrt N\log N)~

Subtask 4

Subtask 4 is created to reward ~\mathcal{O}(\sqrt N)~ solutions that use some of the observations in subtask 5.

Subtask 5

For subtask 5, note that ~N \bmod x < x~. When doing the binary search for subtask 3, this means that if the number we are testing is fairly large, we can significantly speed things up by not considering the ~x~ values that are less than the number we are testing, since we know for sure that ~N \bmod x~ is small enough. If we loop across possible ~\lfloor \frac{N}{x} \rfloor~ values and stop when all ~x~ with this value are small enough, we can test a number ~mid~ in ~\mathcal{O}(\frac{N}{mid})~ time instead of ~\mathcal{O}(\sqrt N)~. It turns out this solution is fast enough and passes subtask 5 easily, and we prove this below.

How large is the answer? If we use one of the slower solutions to print out a lot of answers for small ~N~, we can conjecture that the answer grows approximately linear in ~N~. If the correct answer is always around ~cN~ for some constant ~c~, then the solution above takes at most ~\mathcal{O}(\frac{1}{c} \log N)~ time, which would be fast enough. Upon experimenting we can realize that ~c~ appears to be around ~0.1459854~.

It is actually fairly easy to prove a slightly weaker bound. We show that the answer is greater than ~0.1N~, and we do this by showing that there are more than ~0.5N~ numbers of the form ~N \bmod x~ that are greater than ~0.1N~. When ~\frac{N}{2} < x \le N~, ~\lfloor \frac{N}{x} \rfloor = 1~, so ~N \bmod x = N-x~ which takes all numbers between ~0~ and approximately ~\frac{N}{2}~, out of which around ~0.4N~ are larger than ~0.1N~. When ~\frac{N}{3} < x \le \frac{N}{2}~, ~\lfloor \frac{N}{x} \rfloor = 2~, so ~N \bmod x = N-2x~ which takes every other number between approximately ~0~ and approximately ~\frac{N}{3}~, out of which around ~\frac{1/3-0.1}{2}N > 0.11N~ are larger than ~0.1N~. Together, these already give more than ~0.5N~ numbers that are larger than ~0.1N~, proving the claim and showing that the solution above is ~\mathcal{O}(\log N)~.

Time complexity: ~\mathcal{O}(\log N)~

Remark: Repeating the proof above for more values of ~\lfloor \frac{N}{x} \rfloor~, we can actually calculate that ~c~ is exactly ~\frac{20}{137}~. With a bit more work we can show that if ~f(N)~ is the answer to the problem, then the function ~g(N) := f(N)-\lfloor \frac{20}{137}N \rfloor~ is always between ~-2~ and ~2~, and is periodic with a period of ~8220 = 137 \cdot 60~. As a hint towards why something like this should be true, note that the lowest common multiple of ~1,2,3,4,5,6~ is ~60~ and ~\frac{1}{7} < \frac{20}{137} < \frac{1}{6}~.