WELLLEFT - Editorial


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

Author: iceknight1093
Tester: pols_agyi_pols
Editorialist: iceknight1093






Given N, H, and K, count the number of pairs (A, B) such that 1 \leq A, B \leq N and a frog that jumps A units upward and slips B units downward every second can escape a well of height H within K seconds.


Let’s fix the value of A and try to count the number of valid values of B.
This, summed up across all A, will give us our answer.

Observe that:

  • If A\geq H, the frog will leave the well immediately after its first jump.
    • In this case, B can be anything at all. Since we’re limited to 1 \leq B \leq N, add N to the answer.
  • When A \lt H, the frog definitely needs more than one second to escape the well.
    Note that in this case, if B\geq A, the frog can never leave the well - so we only need to care about 1 \leq B \lt A.

In the second case, since 1 \leq B \lt A, the frog will definitely move upward after each second.
In particular, at the x-th second, the frog will jump up to position x\cdot A - (x-1)\cdot B; and then it’ll fall back down to x\cdot (A-B).
It’s not hard to see that within these x seconds, x\cdot A - (x-1)\cdot B is also the highest point the frog ever reached.

So, for the frog to escape the well (that has height H) within K seconds, the inequality

K\cdot A - (K-1)\cdot B \geq H

should be satisfied.

Since we fixed A, the only variable here is B. So, moving things around a bit:

\begin{aligned} K\cdot A - (K-1)\cdot B &\geq H \\ (K-1) \cdot B &\leq K\cdot A - H \\ B &\leq \frac{K\cdot A - H}{K - 1} \end{aligned}

So, B can be any integer between 1 and \frac{K\cdot A - H}{K - 1}.
If this upper bound is \lt 1 then no valid B exist; otherwise the number of valid B is exactly

\left\lfloor \frac{K\cdot A - H}{K - 1} \right\rfloor

where \left\lfloor \cdot \right\rfloor denotes the floor function.

This can be computed in constant time, so we have a linear time solution since we only iterate through all A from 1 to N.

As an aside, it’s possible to do a bit more math and compute the required summation in \mathcal{O}(\log N) time: see here for instance if you’re interested.


\mathcal{O}(N) per testcase.


Editorialist's code (Python)
for _ in range(int(input())):
    n, k, h = map(int, input().split())
    ans = 0
    for a in range(1, n+1):
        if a >= h: ans += n
        else: ans += max(0, (a*k - h) // (k-1))

Can anybody explain how are you getting 180 in the 3rd testcase, I was getting 165.

1 Like

Bruh , Even i was wondering in contest about it . But after going through editorial and using that equality , it is giving 180 .

Test Case - 20, 6, 18
Hey, since the frog falls after every 1 second, there will be 16 such pairs where the frog won’t be able to jump out of well in k seconds. For example - for (2,1) - (A,B) - the frog will need 17 seconds to jump out of well which is less than the required 6 seconds.
And if we consider all the pairs satisfying 20(N) and 18(H) - they come out to be 196. Considering 60 pairs for (20, 19 and 18 value of n) and sum of 17 natural numbers for the rest.

Yeah I got it! The mistake I did was using k*(A-B) >= h, while it should be k*A - (k-1)*B >= h. Since slipping happens after frog has climbed.

I have a concern that if the constraints are in the range of Integer.Then why taking input as nextInt() is giving wrong answer.Whereas when i used nextLong() it give the AC.While using nextInt() i used this so that the answer is within the range

long aTimesK = (long) a * k;
long maxB = (aTimesK - h) / (k - 1);
if (maxB >= 1) {
validPairs += Math.min(maxB, n);
but still got Wrong answer

can anyone please tell me why This Solution is getting a WA while This solution gets an AC ?
I have been stuck like forever, please help!!!

Damn, I did it using Binary Search. Didn’t thought of this

An efficient floor sum evaluation is also implemented iteratively in AtCoder library.

1 Like

Hello everyone,
I have explained the solution for above problem after submitting the AC solution. Please do read it and share your views.