Igor Perić

Problem

While the most typical type of dice have 6 sides, each of which shows a different integer 1 through 6, there are many games that use other types. In particular, 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.

In this problem, we start with a collection of NN dice. The i-th die is a dSi, that is, it has Si sides showing integers 1 through Si. A straight of length ℓ starting at x is the list of integers x,x+1,…,x+(ℓ−1). We want to choose some of the dice (possibly all) and pick one number from each to form a straight. What is the longest straight we can form in this way?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described in two lines. The first line of a test case contains a single integer N, the number of dice in the game. The second line contains N integers S1,S2,…,SN, each representing the number of sides of a different die.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of input dice that can be put in a straight.

Limits

Memory limit: 1 GB.
1≤T≤100

Test Set 1 (Visible Verdict)

Time limit: 5 seconds.
1≤N≤10
4≤Si≤20, for all i

Test Set 2 (Visible Verdict)

Time limit: 15 seconds.
1≤N≤10^5
4≤Si≤10^6, for all i

Sample input

3
4
4
6 10 12 8
6
5 4 5 4 4 4
10
10 10 7 6 7 4 4 5 7 4
1
10

Sample output

Case #1: 4
Case #2: 5
Case #3: 9
Case #4: 1

In Sample Case #1, there are multiple ways to form a straight using all 4 dice. One possible way is shown in the image above.

In Sample Case #2, since none of the dice can show an integer greater than 5, there is no way to have a straight with more than 5 dice. There are multiple ways to form a straight with exactly 5 dice. For example, pick the integers 4 and 5 for both d5⁠’s and then integers 1,2, and 3 for three of the d4⁠’s to form 1,2,3,4,5.

In Sample Case #3, it is possible to form the straight 1,2,3,4,5,6,7,8,9 by discarding one d4 and using the d4⁠’s, d5, and d6 to get 1 through 4; the d7⁠’s to get 5 through 7; and the d10⁠’s to get 8 and 9. There is no way to form a straight of length 10, so this is the best that can be done.

In Sample Case #4, we can only form a straight of length 1, but we can do so by picking any integer for the d10 we are given.

Solution

The first important insight is if we can use any set of dice to form the straight [A, A+1, A+2, … B-1, B] of length K = B – A, we can “convert” this straight into a straight [1, K] by subtracting A-1 from each element. In other words, if a single set of K dice gives us a straight starting from A all the way through B, it must also give us the straight starting from 1 going through K. This removes the need to actually find A and B and allows us to always start searching at 1 instead.

Another insight is that array should be sorted – if we need to pick a dice to use for some number P while building the straight, it makes sense to pick the smallest available dice with number of sides greater than or equal to P, since this maximizes the future options. Sorting the list and starting the search in ascending order of dk will guarantee the optimal strategy.

If we encounter a dice with smaller dk than P while iterating, we simply skip the dice and keep trying the ones with higher dk values until we test all dice.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t, q = 0;
    cin >> t;
    while (q++ < t) {
        cout << "Case #" << q << ": ";

        long n, i;
        cin >> n;
        vector<long> a(n);
        for (i=0;i<n;i++) cin >> a[i];
        sort(a.begin(), a.end());
        
        // keep track of the number of dice we skip
        long c = 0;
        for (i=0;i<n;i++) {
            // check if the dice a[i] can be used to build the number i + 1...
            // ... accounting for c skipped values so far
            if (a[i] < i + 1 - c) c++; // if not, increase the number of skipped dice
        }
        
        // solution is the total number of dice minus the skipped ones
        cout << n - c << endl;
    }
    return 0;
}