Google Code Jam Qualification Round Q3

# Google Code Jam Qualification Round Q3 - d1000000

#### Declaration

This post is released after the end of the Qualification Round of Code Jam.

#### Question

Please refer to: [Code Jam Official Site](https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a46471)

#### Solution

##### Idea

1. Sort the number of faces of the dice \\(\boldsymbol{S} = \\{ S_i \text{ | i = 1,2,3,...,N }\\}\\) from the smallest.
- - For example, we have 4 dice with \\(\boldsymbol{S} = \\{ 3, 9, 6, 7 \\}\\), then

\\[ \boldsymbol{S_{sorted}} = \\{3, 6, 7, 9\\}\\]

- - Another example, \\(\boldsymbol{S} = \\{ 3, 3, 4, 1, 2, 3 \\}\\), then

\\[ \boldsymbol{S_{sorted}} = \\{ 1,2,3,3,3,4 \\}\\]

2. Subtract the index number from \\(\boldsymbol{S_{sorted}}\\), and denoted by \\(\boldsymbol{K}\\):

\\[ K_i = S_{sorted,i} - i \text{ , for i = 1,2,3,...,N }\\]

- - For \\( \boldsymbol{S_{sorted}} = \\{3, 6, 7, 9\\} \\),

\\[ \boldsymbol{K} = \\{2, 5, 4, 5\\}\\]

- - For \\( \boldsymbol{S_{sorted}} = \\{ 1,2,3,3,3,4 \\} \\),

\\[ \boldsymbol{K} = \\{0, 0, 0, -1, -2, -2\\}\\]

3. The most negative number in \\(\boldsymbol{K}\\) is the number of dice we need to take out from the straight.  If all \\(\boldsymbol{K}\\) is non-negative, we can keep all dice in the straight.

- - For \\( \boldsymbol{K} = \\{2, 5, 4, 5\\}\\), since all \\(K_i \geq 0\\), the longest straight \\(L\\):

\\[L = N = 4\\]

- - For \\( \boldsymbol{K} = \\{0, 0, 0, -1, -2, -2\\}\\), since \\(min \boldsymbol{K} = -2 < 0\\), the longest straight \\(L\\):

\\[L = N - 2 = 4\\]

##### Code

1\. Using `NumPy` for better performance
```python
import numpy as np
```

2\. Define a function to calculate the longest straight:
```python
def get_max_dice_straight(S,N):
    #Sort the number of faces of the dice
    S_sorted = np.sort( S, kind="heapsort" )
    #Generate the index numbers
    dice_index = np.arange( 1, N+1 )
    #Subtract the index number from S_sorted
    K = np.subtract( S_sorted, dice_index )
    #Append 0 to K: if all K >= 0, remove 0 dice; else remove by the minimun K_i
    remove_dice = np.amin(np.append(K,0))
    return N + remove_dice
```

3\. Necessary IO:
```python
T = int(input())
if T < 1 or T > 100:
    print("Error Input")
    exit()
for i in range(T):
    N = int( input() )
    line_input = input()
    S = np.array([int(i) for i in line_input.split(" ")])
    print(f"Case #{i+1}: ",end="")
    print(get_max_dice_straight( S, N ))
```

Back to Contents

Loading