Solution to Codejam 2021 1C (Closest Pick) in C

Question

The following code is my solution to the Closest Pick problem from Codejam 2021.

You are entering a raffle for a lifetime supply of pancakes. N tickets have already been sold. Each ticket contains a single integer between 1 and K, inclusive. Different tickets are allowed to contain the same integer. You know exactly which numbers are on all of the tickets already sold and would like to maximize your odds of winning by purchasing two tickets (possibly with the same integer on them). You are allowed to choose which integers between 1 and K, inclusive, are on the two tickets.

You know you are the last customer, so after you purchase your tickets, no more tickets will be purchased. Then, an integer c between 1 and K, inclusive, is chosen uniformly at random. If one of your tickets is strictly closer to c than all other tickets or if both of your tickets are the same distance to c and strictly closer than all other tickets, then you win the raffle. Otherwise, you do not win the raffle.

Given the integers on the N tickets purchased so far, what is the maximum probability of winning the raffle you can achieve by choosing the integers on your two tickets optimally?

This is an easy problem, and we can solve it by sorting all ticket numbers and finding all number gaps between them. Then we can buy two tickets either to cover the largest gap or half of the two largest gaps.

The code below is correct, i.e. it gets two green checkmarks.

I'd appreciate any feedback!

#include <stdio.h>
#include <stdlib.h>

#define MIN_TICKET 1

static int cmp_long(const void *num1, const void *num2) {
    return *(const long *)num1 - *(const long *)num2;
}

static double solve(long *tickets, size_t n_tickets, long max_ticket) {
    qsort(tickets, n_tickets, sizeof(tickets[0]), cmp_long);
    // Sizes of ticket gaps that we can "cover" by being closer than others
    long gaps[n_tickets + 1];
    // Max total number of tickets that we can cover
    long max_gap_size = 0;
    // Size of the leftmost ticket gap
    gaps[0] = tickets[0] - MIN_TICKET;
    // Size of the rightmost ticket gap
    gaps[n_tickets] = max_ticket - tickets[n_tickets-1];
    for (int i = 1; i < n_tickets; i++) {
        long gap_size = tickets[i] - tickets[i-1] - 1;
        // Number of tickets that we can cover by buying a ticket at one of the
        // gap boundaries (divide the size by 2 and round up).
        gaps[i] = (gap_size + 1) / 2;
        // Alternatively, we can buy two tickets at each boundary of a large
        // gap.
        if (gap_size > max_gap_size) {
            max_gap_size = gap_size;
        }
    }
    qsort(gaps, n_tickets + 1, sizeof(gaps[0]), cmp_long);
    // Total size of our two largest options
    long top_two_gap_sizes = gaps[n_tickets - 1] + gaps[n_tickets];
    // Choose between covering one large gap or two smaller gaps.
    if (top_two_gap_sizes > max_gap_size) {
        max_gap_size = top_two_gap_sizes;
    }
    return (double) max_gap_size / max_ticket;
}

int main(void) {
    size_t n_tests = 0;
    scanf("%lu", &n_tests);
    for (int case_num = 1; case_num <= n_tests; case_num++) {
        size_t n_tickets;
        long max_ticket;
        scanf("%lu %ld", &n_tickets, &max_ticket);
        long tickets[n_tickets];
        for (int i = 0; i < n_tickets; i++) {
            scanf("%ld", &tickets[i]);
        }
        double prob = solve(tickets, n_tickets, max_ticket);
        printf("Case #%d: %.6f\n", case_num, prob);
    }
}

Example output

$ cat tests.txt
4
3 10
1 3 7
4 10
4 1 7 3
4 3
1 2 3 2
4 4
1 2 4 2
$ ./solution < tests.txt
Case #1: 0.500000
Case #2: 0.400000
Case #3: 0.000000
Case #4: 0.250000

Answer 1

Enable more compiler warnings

GCC reports some warnings:

gcc-10 -std=c17 -no-pie -g3 -ggdb -Wall -Wextra -Warray-bounds 
-Wconversion -Wmissing-braces -Wno-parentheses -Wpedantic -Wstrict-prototypes
-Wwrite-strings -Winline -fanalyzer -fno-builtin -fno-common
-fno-omit-frame-pointer -fsanitize=address -fsanitize=undefined
-fsanitize=bounds-strict -fsanitize=leak -fsanitize=null -fsanitize=signed-integer-overflow
-fsanitize=bool -fsanitize=pointer-overflow -fsanitize-address-use-after-scope -O2    ex.c   -o ex

ex.c:7:32: warning: conversion from ‘long int’ to ‘int’ may change value [-Wconversion]
    7 |     return *(const long *)num1 - *(const long *)num2;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ex.c: In function ‘solve’:
ex.c:20:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
   20 |     for (int i = 1; i < n_tickets; i++) {
      |                       ^
ex.c:38:34: warning: conversion from ‘long int’ to ‘double’ may change value [-Wconversion]
   38 |     return (double) max_gap_size / max_ticket;
      |                                  ^
ex.c: In function ‘main’:
ex.c:44:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
   44 |     for (int case_num = 1; case_num <= n_tests; case_num++) {
      |                                     ^~
ex.c:49:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
   49 |         for (int i = 0; i < n_tickets; i++) {
      |                           ^
ex.c:43:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |     scanf("%lu", &n_tests);
      |     ^~~~~~~~~~~~~~~~~~~~~~
ex.c:47:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |         scanf("%lu %ld", &n_tickets, &max_ticket);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ex.c:50:13: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |             scanf("%ld", &tickets[i]);

These are all avoidable.

Check the return value of library functions

If a function be advertised to return an error code in the event of difficulties, thou shalt check for that code, yea, even though the checks triple the size of thy code and produce aches in thy typing fingers, for if thou thinkest "it cannot happen to me", the gods shall surely punish thee for thy arrogance. — The Ten Commandments For C Programmers

scanf() returns the number of input items successfully matched and assigned, it deserves to have its value checked:

if (scanf("%zu", &n_tests) != 1) {
    complain ();
}

Note that the correct format specifier for size_t is zu, not lu.

Use size_t for sizes, cardinalities, or ordinal numbers

//for (int case_num = 1; case_num <= n_tests; case_num++) {
//        size_t n_tickets;
//        long max_ticket;

for (size_t case_num = 1; case_num <= n_tests; case_num++) {
     size_t n_tickets;
     size_t max_ticket;

qsort's comparison function risks invoking undefined behaviour

return *(const long int*)num1 - *(const long int*)num2;

This subtraction could result in integer overflow, which would invoke undefined behaviour.

A common idiom is to subtract two integer comparisons:

return (*(const long int*)num1 > *(const long int*)num2) - (*(const long int*)num1 < *(const long int*)num2);

Or a more readable, but less compact, alternative:

const long int *a = num1;
const long int *b = num2;

return (*a > *b) - (*a < *b);

Or if you'd prefer an if/else ladder:

if (*a > *b) {
   return 1;
} else if (*a < *b) {
   return -1;
}
return 0;

Or perhaps:

return (*a < *b) : -1 : *a > *b;

Answer 2

Common mistakes

This echoes @Haris Enable more compiler warnings:

As part of a code review, when such trivial errors are found so readily, it casts an overall disappointment on code.

Avoid the 3 rookie mistakes: Enable all warnings, check spelling (looks OK here), auto format (looks OK here).

Bug

max_gap_size missies gaps[0] and gaps[n_tickets]. @G. Sliepen.

Name

Took a while before I realized gaps[i] was not in the same units as gap_size, but only half that. Perhaps a different name for gaps[i]?

Missing K

Coding goals discuss "integer between 1 and K", yet code lacks K (and c).

Code does have max_ticket, yet in realizing a coding goal (think contract specification), best to have an unambiguous match between specified goals and code.

Why long?

Code uses long as if that range meets the unstated range of the coding goals. int may be more efficient. unsigned long long may be necessary. Since coding goal is unclear, be flexible.

Consider typedef long int_ticket; and related print/scan specifiers to make code adaptable.

Pedantic: overflow

Code may overflow in tickets[i] - tickets[i-1] - 1 and others.

To prevent with #define MIN_TICKET 1, code should validate input of scanf("%ld", &tickets[i]); against acceptable range: [1...K].

Liekwise, code like gaps[n_tickets - 1] and others fail when n_tickets == 0. Code should test max_ticket for acceptable range.

---

---

Deeper

Then we can buy two tickets either to cover the largest gap or half of the two largest gaps.

This is incomplete (a bug). Consider the case of tickets 30, 70 where K == 100. The best two tickets are 29, 71. This is not covered in OP's stated goal.

Below is an untested (real-life is calling) re-write employing a different scheme.

1. Sort N items by value.

2. Sort N-1 differences. Find 2 best.

3. Consider the 2 edges and the 2 best differences (at half value). Select the best 2 of 4 and compare that against the 1 largest difference.

4. Use an abstract ticket type. Use size_t for array indexing and sizing.

5. Handle ticket counts 2 and fewer. Some other minor ideas employed also.

#define TICKET_MIN 1
typedef unsigned ticket;

static int ticket_cmp(const void *num1, const void *num2) {
  ticket t1 = *(const ticket*) num1;
  ticket t2 = *(const ticket*) num2;
  return (t1 > t2) - (t1 < t2);
}

double ticket_solve(size_t tickets_n, ticket tickets[tickets_n],
    ticket ticket_max) {
  if (tickets_n == 0) {
    return 1.0;
  }
  qsort(tickets, tickets_n, sizeof tickets[0], ticket_cmp);
  ticket difference[tickets_n - 1];
  for (size_t i = 1; i < tickets_n; i++) {
    difference[i - 1] = tickets[i] - tickets[i - 1];
  }
  qsort(difference, tickets_n - 1, sizeof difference[0], ticket_cmp);

  // The best choice using 2 tickets in one interval.
  ticket best_bounded = 0;

  // The best choices using 1 ticket / interval.
  ticket interval[4] = {0};

  if (tickets_n > 1) {
    best_bounded = difference[tickets_n - 1] - 1;
    // Only half as value is placed in interval middle.
    interval[0] = (difference[tickets_n - 1] - 1) / 2;
    if (tickets_n > 2) {
      interval[1] = (difference[tickets_n - 2] - 1) / 2;
    }
  }

  // Now consider the end points
  if (tickets[0] > TICKET_MIN) {
    interval[2] = tickets[0] - TICKET_MIN;
  }
  if (tickets[tickets_n - 1] < ticket_max) {
    interval[3] = ticket_max - tickets[tickets_n - 1];
  }

  qsort(interval, 4, sizeof interval[0], ticket_cmp);
  ticket best2intervals = interval[3] + interval[2];
  ticket best = best_bounded > best2intervals ? best_bounded : best2intervals;
  return (double) best / (ticket_max - TICKET_MIN + 1u);
}

Bonus: performance improvement

qsort(gaps, n_tickets + 1, sizeof(gaps[0]), cmp_long); is overkill. It is O(n_tickets * ln(n_tickets)) (and O(n_tickets) memory) and only the 2 highest values are needed.

Instead, a O(n_tickets) (and O(1) memory) solution:

  ticket difference_max[2] = { 0, 0 };
  for (size_t i = 1; i < tickets_n; i++) {
    if (tickets[i] - tickets[i - 1] > difference_max[0]) {
      if (tickets[i] - tickets[i - 1] > difference_max[1]) {
        difference_max[0] = difference_max[1];
        difference_max[1] = tickets[i] - tickets[i - 1];
      }  else {
        difference_max[0] = tickets[i] - tickets[i - 1];
      }
    }
  }

Answer 3

We don't really need to store and sort the entire list of gaps. We're just interested in the largest gap we can cover with two tickets (that's max_gap_size) and the largest two gaps that can each be covered by a single ticket. We can use a simple form of insertion sort to create the latter, which scales better for both time and space.

The code for that is reasonably straightforward:

static const long min_ticket = 1;

static void swap(long *a, long *b)
{
    long tmp = *a;
    *a = *b;
    *b = tmp;
}

static double solve(long *tickets, size_t n_tickets, long max_ticket)
{
    // First, put the tickets in sequential order
    qsort(tickets, n_tickets, sizeof *tickets, cmp_long);

    // Largest two ranges that we can cover using one ticket.
    // Start with the two ends, which we can completely cover with a single ticket
    long gaps[2] = {tickets[0] - min_ticket, max_ticket - tickets[n_tickets-1]};
    if (gaps[0] > gaps[1]) {
        swap(&gaps[0], &gaps[1]);
    }
    // Largest range that we can cover completely using two tickets
    long max_gap_size = 0;

    // iterate over the interior gaps
    for (size_t i = 1;  i < n_tickets;  ++i) {
        if (tickets[i] <= tickets[i-1] + 1) {
            // no gap
            continue;
        }
        const long gap_size = tickets[i] - tickets[i-1] - 1;
        // Number of tickets that we can cover by buying a single
        // ticket in this gap (divide the size by 2 and round up).
        const long single_ticket_size = (gap_size + 1) / 2;
        if (single_ticket_size > gaps[1]) {
            // new biggest single-ticket range
            gaps[0] = gaps[1];
            gaps[1] = single_ticket_size;
        } else if (single_ticket_size > gaps[0]) {
            // new second-biggest range
            gaps[0] = single_ticket_size;
        }
        // Alternatively, we can buy two tickets to cover a single gap
        // completely.
        if (gap_size > max_gap_size) {
            max_gap_size = gap_size;
        }
    }

    // Total size of our two largest single-ticket options
    const long top_two_gap_sizes = gaps[0] + gaps[1];
    // Choose between covering one large gap or two smaller gaps.
    if (top_two_gap_sizes > max_gap_size) {
        max_gap_size = top_two_gap_sizes;
    }
    return (double)max_gap_size / max_ticket;
}

I also added a shortcut for the "no gap" case where ticket numbers are equal or consecutive. Not only does this reduce processing, but it also avoids an overflow if we switch to unsigned ticket numbers (which we should, given we know the lowest-numbered ticket is 1).

And I replaced the preprocessor macro MIN_TICKET with a properly-typed constant value - that's always good practice where possible.