d1000000 (Team)

Try this problem by yourself first! Check the Code Jam Page.

Overview

The following technical log will discuss the solution to the competitive programming problem d1000000 presented at the Qualification Round of the 2022 Google’s Code Jam.

The problem summarizes as the following:

Suppose we have a finite set $D \subset \mathbb{N}$ of $N$ non-negative numbers. The goal is to obtain the largest integer $m \in \mathbb{N}$ such that there is a subset $D^* = \{ D_1,\ \ldots,\ D_m \} \subseteq D$ with $m$ elements such that $k \leq D_k$ for all $k \in \{ 1,\ \ldots,\ m \}$.

O     O     O

o o o

...

Context

A $dK$ is a die with $K$ sides, each of which shows a different integer 1 through $K$. A $d6$ is a typical die, a $d4$ has four sides, and a $d1000000$ has one million sides.

We start with a collection of $N$ dice. The $i$-th die is a $dS_i$, that is, it has $S_i$ sides showing integers 1 through $S_i$. A straight of length $\ell$ starting at $x$ is the list of integers $x,\ x+1,\ \ldots\, x + (\ell - 1)$. We want to choose some of the dice (possibly all) and pick one number from each to form a straight.

The goal is to find the length of the longest straight we can form in this way.

O     O     O

o o o

...

Solution

The problem asks us to find the length of the longest straight of consecutive numbers that can be formed using a collection of $N$ dice, where the $i$-th dice has $S_i$ sides.

Notice that the smaller the integer we consider, the more likely that there is a die that contains a side with that number. We will take this to our advantage to address the problem. We will approach this problem by trying to form a list of maximum length starting from the smallest possible number. For example, if we have two dice with 3 and 5 sides respectively, we can form a of length 2 starting from 1, but we cannot form a straight of length 3 starting from 1. Therefore, the longest straight we can form is of length 2.

Based on this approach, we can start by sorting the dice by the number of sides they have, so that we can start forming the straight from the smallest possible number. We will start the list of consecutive numbers at 1, so that the last added number will be the same as the length of the current straight. We iterate through the sorted list of dice, and for each die, we check if the number of sides is greater than the current length of the straight. If it is, then we can add another number to the list and increment its length by 1. If not, then we move on to the next die and check again. We keep track of the length of the longest straight we have formed so far and return it as the answer at the end of the iteration.

The time complexity of this approach is $O(N \log N)$ due to the sorting step, where $N$ is the number of dice. However, since the upper limit of $N$ is relatively small (up to 105 in Test Set 2), this approach should be efficient enough to pass all test cases.

In terms of implementation, the pseudocode is:

maximum_straight_length(S):  
    sort(S) 
    set length = 0  
        for si in S: 
            if si > length:  
                length += 1  
    return length 

The function takes a list $S$ of integers representing the number of sides of each die, sorts it in ascending order using the built-in sort method, and then iterates through each element in the sorted list. The variable length keeps track of the length of the longest straight formed so far, and is initialized to 0 at the start.

For each element $s_i$ in the sorted list, the function checks if $s_i$ is greater than the current length of the straight. If it is, then the function increments the length of the straight by 1. If not, then the function moves on to the next element in the list.

Finally, the function returns the length of the longest straight formed.

O     O     O

o o o

...

Alternative Solutions

One brute force approach was to compute all the possible permutations of the dice’s subsets, which is not plausible due to the dimensions of the problem.

The presented approach in the previous section originates from ordering the numbers to construct the longest straight later. The alternatives to solve the problem were only focused on the method to order the dice from smallest to largest. The following were the ones considered:

• Standard sorting algorithm to order list. Since we have a list of the dice numbers, sorting it with a standard sorting algorithm will result in $O(N \log N)$ time complexity due to the comparison-based nature of the algorithm. Although this method requires more time to execute, it is the most straightforward method, and it is still efficient. This approach is included in the dart, kotlin and typescript versions of the solution code.

• Counting sort to order list. The problem input constraints make this algorithm a suitable option. While it requires more memory than a standard sorting algorithm, we will have an improvement in $O(N)$ time complexity.

• Heap queue from list. Once we have a list, building the heap runs in $O(N)$ time complexity. This is again an improvement in time than when using a standard sorting algorithm but uses more memory to store the heap. This variation is included in the python version of the solution code.

All the previous are plausible options. Once we have a way to iterate through the dice from smallest to largest, we can compute the largest straight, as discussed previously.