Timosh's blog

By Timosh, 4 weeks ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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$$$.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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})$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Surprisingly a simple and working approach. Eventhough, my solution does something with numbers from $$$n$$$ to $$$n+ \sqrt{n}$$$, lol. Anyways, thanks.

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I guess this might be correct:

if(n<=a*b){

x=a;

y=b;

}

else{

if(a<b){

x=a;

y=ceil(n/a);

}

else{

x=ceil(n/b);

y=b;

}

}

Edit: This approach has been proved wrong through a counterexample.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Counter: $$$a = 4, b = 4, n = 25$$$ then the optimal answer is $$$x = y = 5$$$.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, didn't think about that.

        Thanks for pointing it out.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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.