Solution to the COCI Programming Competition Puzzle, and Another Problem!

Hi everyone,

Last week, I suggested a programming puzzle. I asked you to peruse the material from each chapter of the book and choose the best approach for solving this problem… check out that post now if you haven’t already :)

This problem is a …

a …

a …

a binary search problem! It’s the Aerodrom problem from COCI 2012-2013 Contest 3. As I mentioned last week, the COCI (Croatian Open Competition in Informatics) website is a fantastic cache of programming competition problems and editorials. I couldn’t find the Aerodrom problem on a programming judge, but that’s OK, because the COCI website contains test data, too, that we can run on our solutions. In fact, I used the test data for this problem to test my code. I used input redirection to read each input file, and compared my output to the corresponding output file.

(I like this problem very much. What kept it out of the book was that the algorithm on the “inside” of the binary search wasn’t as interesting to me as those in the examples I chose: recursion through a tree, greedy algorithm, dynamic programming, etc.)

(Update: this problem is on DMOJ now! Thank you very much to everyone who is adding problems.)

OK, so a binary search problem. Why? Because it meets the two criteria:

1. It’s easier to check feasibility than solve the problem outright.
2. There’s an infeasible-feasible split: the infeasible solutions come first (the times are too small) and they’re followed by the feasible solutions.

Checking Feasibility

Here’s the test case from last week:

2 4
4
7

Can we check in all 4 people within 14 seconds? Let’s see. Our strategy will be to choose a desk as soon as we can, subject to the constraint of taking 14 seconds or less. We can put the first person at the first desk and the second person at the second desk. The first person finishes at time 4, so we can put the third person at the first desk to finish at time 8. The second person finishes at time 7, so we can put the fourth person at the second desk to finish at time 14. So, yes: we can accommodate all 4 people within 14 seconds. This also means that we can accommodate them in 15 seconds, or 16, or any higher number of seconds.

Can we check in all 4 people within 10 seconds? We’ll again put the first person at the first desk and the second person at the second desk. The first person finishes at time 4, so we can put the third person at the first desk to finish at time 8. The second person finishes at time 7, but this time we can’t put the fourth person at the second desk because they would finish at time 14 (past time 10). Unfortunately, we also can’t put them at the first desk, because then they’d finish at time 12 (still past time 10). So there’s no way to accommodate everyone in 10 seconds. This also means that we can’t accommodate them in 9 seconds, or 8, or any lower number of seconds.

Based on what I’ve said so far, it might seem that we need to process each person individually. There are up to 1 billion people, and something I didn’t tell you last time (because I wanted to keep the discussion open) was that the time limit for this problem is 1 second. We might be able to handle a hundred million people in this amount of time, but we’re very unlikely to be able to process a billion.

That’s OK, though, because we can actually get away with a super-fast feasibility check that doesn’t have to process each person individually. Here’s the trick: the queue in the problem is a bit of a red herring. It doesn’t actually matter in what order we process the people, as long as no two people are getting checked in at the same desk during the same time. So we can ask: how many people can each desk process within the time limit? For example, suppose that a desk takes 4 seconds to process a person, and our time limit is 10 seconds. This desk could process 2 people (in a total of 8 seconds), but not 3 people (because that would take 12 seconds).

Here’s another way to think about it. Split up the queue into one mini-queue per desk, where each mini-queue contains the number of people that the desk can process in time. Adding up these numbers gives us the total number of people that can be processed.

The Code

Here’s my code for solving the problem.

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
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 100000 // max number of check-in desks

int can_make_time(long long time,int times[], int num_desks, int num_people) {
  int i;
  long long total = 0;
  for (i = 0; i < num_desks; i++)
    total = total + time / times[i];
  return total >= num_people;
}

void solve(int times[], int num_desks, int num_people) {
  long long low, high, mid;
  low = 0;
  high = (long long) times[0] * num_people;
  while (high - low > 1) {
    mid = (low + high) / 2;
    if (can_make_time(mid, times, num_desks, num_people))
      high = mid;
    else
      low = mid;
  }
  printf("%lld\n", high);
}

int main(void) {
  int num_desks, num_people, i;
  int times[SIZE];
  scanf("%d%d", &num_desks, &num_people);
  for (i = 0; i < num_desks; i++)
    scanf("%d", &times[i]);

  solve(times, num_desks, num_people);
  return 0;
}

The can_make_time function (7) is the feasibility check here. It adds up the number of people that can be processed by each desk, returning true if this total is sufficient and false otherwise.

In the binary search itself (15), small values are infeasible and large values are feasible (it’s like the Living Quality problem in Chapter 6). Setting low to an infeasible value is easy: we can just use 0 (17): we can’t possibly process the people in 0 seconds! But how do we set high to a feasible value? My approach here (18) is to take as a worst-case the option of queueing every person at the first desk. However long that takes is certainly a feasible solution. How long does it take to check everyone in using only the first desk? Well, we take times[0] to check one person in, so we need to multiply that value by the total number of people.

Another Problem

That was fun. Ready for another problem? This time, let’s use a COCI problem that’s on DMOJ. It’s called Lozinke, and it’s a nice example of the kind of speed boost we can achieve if we choose the correct data structure. Rather than rewrite the problem description as I did in the book, I’ll ask you to practice reading an official problem description this time.

Go For It!

Do give that problem a try! I’ll be back on October 21 if you’d like to solve it together. Please feel free to contact me (a question? suggestion? got a cool problem for me?). I also have a newsletter where I send occasional updates. Please see my Contact and Newsletter page. Thanks!