Binary Search, or Equations, or Pizzas?

Hi all,

I recently found a neat little COCI problem on DMOJ. Check it out!

(If you’re put off that it’s only a 3-point problem: give it a chance, there may still be some learning for you here.)

Binary Search

OK, so we have a snail climbing a pole. Every day it climbs up $a$ meters and then, at night, slides down $b$ meters. How long does the snail take to get to the top?

Could it get to the top in 5 days? Well, maybe. And if it does, then it would also get to the top in 6 days or 7 days or more. If it doesn’t, then there’s no way it would get to the top in 4 days or 3 days or less.

At this point, my Algorithmic Thinking book readers might already be thinking of tackling this problem using binary search. Pick the middle $m$ of the range and see how high the snail gets with $m$ days. Then cut off the low side or high side, depending on whether the snail can get to the top or not in $m$ days. (See Chapter 6 for all of the details.)

Here’s some code using this approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int can_make_top(int num_days, int a, int b, int height) {
  return (num_days - 1) * a - (num_days - 1) * b + a >= height;
}

void solve(int a, int b, int height) {
  int low, high, mid;
  low = 0;
  high = height;
  while (high - low > 1) {
    mid = (low + high) / 2;
    if (can_make_top(mid, a, b, height))
      high = mid;
    else
      low = mid;
  }
  printf("%d\n", high);
}

int main(void) {
  int a, b, height;
  scanf("%d%d%d", &a, &b, &height);
  solve(a, b, height);
  return 0;
}

In num_days days, how high does the snail get (7)? Well, it goes up by a on each of the first num_days - 1 days, and also goes down by b for each of the first num_days - 1 days. But then, on day num_days, it blasts up another a – and if that’s enough to get it to the top, then it’s done and doesn’t slide down b that day.

This binary search solution is fast enough to pass all of the test cases in time.

Solving the Equation Directly

It turns out that for this problem, a binary search is overkill. We can solve the problem directly by just rearranging an equation. Let’s start with the equation from the binary search solution:

(num_days - 1) * a - (num_days - 1) * b + a >= height

Let’s factor that num_days - 1 out of there to simplify this a little:

(num_days - 1) * (a - b) + a >= height

Given a number of days, we can substitute that for num_days to learn how high the snail gets in that many days. That’s cool, and we used it above in the binary search solution. But what we really want to be able to do is substitute a height and obtain the number of days. So instead of height showing up by itself on one side of the equation, we want to rearrange it so that num_days shows up by itself.

Let’s start by moving the a over:

(num_days - 1) * (a - b) >= height - a

Now we can divide by a / b:

(num_days - 1) >= (height - a) / (a - b)

All that’s left is to move the 1 over:

num_days >= (height - a) / (a - b) + 1

Given a, b, and height, this tells us the number of days we need. For example, if a is 5, b is 1, and height is 6, then we get:

num_days >= (6 - 5) / (5 - 1) + 1

And, simplifying:

num_days >= 1 / 4 + 1

which is … 1.25?? Hmm, not quite. We need to move this up to the next integer, which is 2. We can use C’s ceil function for that.

This all results in the following solution to the problem:

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void) {
  int a, b, height;
  scanf("%d%d%d", &a, &b, &height);
  printf("%d\n", (int)ceil((height - a) / ((double)a - b) + 1));
  return 0;
}

A couple of things to notice (9):

• In the denominator, I cast a to double so that the denominator is a double. This ensures that floating-point division occurs, rather than integer division.
• I cast the entire result to an integer, because ceil returns a double.

Pizza Time!

There’s a little trick that we can use to obviate the use of ceil. It makes me happy whenever I’m able to use this. I mean, yeah, our solution with ceil is perfectly fine, but…

To see this trick, let’s talk about pizzas. Suppose that we need at least a certain number of slices of pizza for a party. Each pizza has 10 slices, so we’re going to have to bump up to the next full pizza if we need a number of slices that isn’t divisible by 10. For example, if we need 40 slices, we can order 4 pizzas. If we need 45 slices, then we need to order 5 pizzas. You could use ceil for this if you wanted: just use ceil on the result of dividing the number of slices that you need by 10.

If we don’t want to use ceil, then we have to be careful. For example, it’s sometimes wrong to integer divide the number of slices we need by 10, and then add 1. For 45 slices, it works: 45 / 10 + 1 = 5. But for 40 slices, it doesn’t: 40 / 10 + 1 = 5. It’s broken for any number of slices that’s already divisible by 10, since then we don’t need that extra +1 pizza.

Here’s the trick: before you divide by 10, add 9. Adding 9 pushes 40 slices up to only 49, not enough to break the 50-slice barrier. So we still get 4 after the division. Adding 9 pushes 41 or 42 or any other 40-something number of slices above 50, so we get 5 after the division!

What on earth does this have to do with our snail problem? Well, in our solution, we had to divide by a - b. All we have to do to avoid the ceil, then, is to use the pizza trick and first add a - b - 1 to the numerator. It’s just like for the pizzas: we add denominator - 1 to the numerator.

That gives us our final solution for this problem. Here it is!

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void) {
  int a, b, height;
  scanf("%d%d%d", &a, &b, &height);
  printf("%d\n", (height - a + a - b - 1) / (a - b) + 1);
  // Could simplify to printf("%d\n", (height  - b - 1) / (a - b) + 1);
  return 0;
}

Thank you for reading!