### Timosh's blog

By Timosh, 5 weeks ago,

In the recent National Olympiad in Informatics in our country, there was a problem, that many struggled to solve, it was worth 16 points, for being "the hardest problem". I got a great result then, for solving it fast. However, I forgot the actual solution. Anyways, here is the problem statement, ignoring the stories and drama:

You are given 3 integers, $a$, $b$ and $n$. Your task is to find any integers $x$ ($x \ge a$) and $y$ ($y \ge b$), such that $xy \ge n$, and $xy-n$ is minimised

I remember using a $O(\sqrt{n})$ solution, but not what it actually was. Anyone has ideas?

• +8

 » 5 weeks ago, # |   +14 If $n \leq a.b$ then $x=a$ and $y=b$. Otherwise either $x$ or $y$ should be lower than $\sqrt{n}$, so we can bruteforce it by fixing either $x$ or $y$.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 It is not necessary that they be less than $\sqrt{n}$. UPD: Oh wait it is, never mind, I'm stupid... ugh I wrote this long as hell solution for nothingUPD2 (to reply to below comment because CF doesn't let me post): Yeah, I realize that now. Pretty nice, much better than my way at least
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Not exactly $\sqrt{n}$ but perhaps something like $\sqrt{n} + 5$. My point is that at least one of them is bounded by something in $O( \sqrt{n})$.
•  » » 5 weeks ago, # ^ |   +4 Surprisingly a simple and working approach. Eventhough, my solution does something with numbers from $n$ to $n+ \sqrt{n}$, lol. Anyways, thanks.
 » 5 weeks ago, # | ← Rev. 3 →   0 I guess this might be correct:if(n<=a*b){x=a;y=b;}else{if(a
•  » » 5 weeks ago, # ^ |   0 Proof:Let any solution of above problem be: x=x1 and y=y1 where (x1>y1), so x*y=x1*y1. You can create a lower x*y by taking x=(x1+1) and y=(y1-1) as new x*y=(x1+1)*(y1-1)=x1*y1+(y1-x1-1)b.Similarly if a<=b, then optimal answer will be x=a.
•  » » » 5 weeks ago, # ^ |   0 Counter: $a = 4, b = 4, n = 25$ then the optimal answer is $x = y = 5$.
•  » » » » 5 weeks ago, # ^ |   0 Oh, didn't think about that.Thanks for pointing it out.
 » 5 weeks ago, # | ← Rev. 2 →   +9 If $ab \ge n$, we have $xy \ge ab \ge n$ anyway, so we can just choose $x = a$ and $y = b$ for the optimal answer. Now, assume that $ab < n$ and consider fixing $x$. Then, we have $y \ge \max(\lceil \frac{n}{x} \rceil, b)$, and it's clearly optimal to choose $y = \max(\lceil \frac{n}{x} \rceil, b)$, because $x$ is fixed, and we want to minimize $xy - n$. Now, if $\max(\lceil \frac{n}{x} \rceil, b) = b,$ this means we have $\lceil \frac{n}{x} \rceil \le b$. Also, $y = b$ is fixed (remember that we found the optimal $y$ to be $\max(\lceil \frac{n}{x} \rceil, b)$), so it suffices to minimize $x$, subject to the condition $\lceil \frac{n}{x} \rceil \le b$. You can do this with some math (or binary search, if you aren't in the mood for thinking). Now, the other case: if $\max(\lceil \frac{n}{x} \rceil, b) = \lceil \frac{n}{x} \rceil$, we have $b \le \lceil \frac{n}{x} \rceil$, which means $b - 1 \le \frac{n}{x}$, which means $a \le x \le \frac{n}{b - 1}$. In particular, we have only $\mathcal{O}(\sqrt n)$ values of $\lceil \frac{n}{x} \rceil$, and we can check them all in roughly $\mathcal{O}(1)$ time (it will be a little tedious with three or four conditions to check, but pretty doable), so we are done (also I just realized the first part was kinda unnecessary... oh well).UPD: After seeing the first comment, I realized this entire thing was unnecessary... oh well.