Test Set 1

There are multiple ways to solve Test Set 1 of this problem. A particularly funny one is to throw the solution of an old finals problem at it (even the Test Set 1 solution of that problem works).

Test Set 2

Test Set 2 has very big numbers, so we need insights that are specific to this problem.

Insight 1. If a straight from ~A~ to ~B~ can be done, then one from ~1~ to ~B-A+1~ can be done as well using the same dice in the same order, since a die showing a number ~X~ can always be used to show number ~X-A+1~.

Insight 2. If a straight is done with a ~di~ showing number ~X~ and a ~dj~ showing number ~X+1~ with ~i > j~, we can build the same straight but using ~dj~ for ~X~ and ~di~ for ~X+1~.

Insight 2b. Any straight that can be done, can also be done while using the dice in non-decreasing order of number of faces.

Combining insights 1 and 2b gives an algorithm: start by sorting the dice. Then, in that order, try to extend the current straight if possible. Or, in pseudo-code:

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

This algorithm requires only linear time beyond sorting the input, which means ~\mathcal O(N \log N)~ overall. This is fast enough to pass Test Set 2.