PRDEXC - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given X, Y, P. You can repeatedly increment either X or Y by 1.
Find the minimum number of increments to make their product become \ge P.

EXPLANATION:

In order to make the product of two numbers grow quickly, it’s always optimal to increment the smaller one among them.

Thus, a simple solution to this problem is as follows:

while x*y < p:
    if x <= y, increment x
	else, increment y

Implementing this using a while loop is enough to solve the problem.
This runs in \mathcal{O}(\sqrt P) time in the worst case so it’s easily fast enough, because after at most 2\sqrt P increments, both X and Y will be \gt \sqrt P and so their product will exceed P.

Alternately, you can use the small constraints to brute-force a solution as follows:

  • Fix K, the total number of increments made.
  • Then fix R, the number of increments made to X.
    This will result in Y having K-R increments.
  • With this, check if (X+R) \cdot (Y+K-R) \ge P or not.
  • The answer is the smallest K for which at least one valid R exists.

To see why this is fast enough, again note that the answer can’t exceed 2\sqrt P so the total work done is bounded by \mathcal{O}(\sqrt P\cdot \sqrt P) = \mathcal{O}(P).

TIME COMPLEXITY:

\mathcal{O}(\sqrt P) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y, p = map(int, input().split())
    ans = 0

    while x*y < p:
        ans += 1
        if x <= y: x += 1
        else: y += 1
    print(ans)