How to solve Number of jumps for a thief to cross walls problem?

general
, , ,
1

Help needed in solving Number of jumps for a thief to cross walls problem problem. The optimal solution proposed on the link is incorrect. Kindly help me.

2

What test cases is it failing?

3

@trashmaster

1

9 6 1

11

1 Like
4

please be more specific

5

Sorry, I have no reputation to answer to comment, so I answer here.

As you can see, answer for provided test is 2 jumps: 0 ->(jump) 9 ->(down) 3 -> (jump) 12.

But solution from editorial gives answer 1 + (11 - 3) / 3 + 1 = 1 + 2 + 1 = 4 (last one from some magic condition).

I don’t know if there exist correct solution with O(1) calculation per wall, but I got AC with next O(logH) per query solution - binary search.

Function ‘if thief climbs by infinity wall, is he at height H or higher at the end of M-th day’ is monotonic: some first days he was lower, but after some day thief will be higher and higher than H. Exactly that first day when he is equal or higher we are searching.

There is pseudocode of my binsearch:

res = h

for (left = 1, right = h - 1; left <= right; ) {

mid = (left + right) / 2

midH = mid * x - (mid - 1) * y

if (midH >= h) { res = mid; right = mid - 1; }

else { left = mid + 1; }

}

P.S. I found small bug - I actually found not answer, but answer - 1, now fixed.

1 Like
6

x=9 y=6 n=1
A[]={11}

Is that ok? Let me know if any more information is needed.

7

Actually I understood that my binsearch could be replaced by O(1) solution:

y + (mid - 1) * (x - y) < h \le y + mid * (x - y)

(mid - 1) * (x - y) < h - y \le mid * (x - y)

(mid - 1) < (h - y) / (x - y) \le mid

So we get that mid is ceil((h - y) / (x - y)).

ceil(a / b) = (a div b) + (a mod b > 0 ? 1 : 0)

For provided test we have ceil((11 - 6) / (9 - 6)) = ceil(5 / 3) = 2.

1 Like