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?
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$$$.
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 nothing
UPD2 (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
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})$$$.
Surprisingly a simple and working approach. Eventhough, my solution does something with numbers from $$$n$$$ to $$$n+ \sqrt{n}$$$, lol. Anyways, thanks.
I guess this might be correct:
if(n<=a*b){
x=a;
y=b;
}
else{
if(a<b){
}
else{
}
}
Edit: This approach has been proved wrong through a counterexample.
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)<x1*y1. But we cannot decrease y less than b so optimal value of y=b if a>b.
Similarly if a<=b, then optimal answer will be x=a.
Counter: $$$a = 4, b = 4, n = 25$$$ then the optimal answer is $$$x = y = 5$$$.
Oh, didn't think about that.
Thanks for pointing it out.
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.