HackerRank Combinatorics – Insane DFS

Challenge: Insane DFS

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 150.0 / 150

Submission status: Accepted

Submission score: 1.0

Submission ID: 464775810

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/insane-dfs/problem

Cerinta

Imagine you have a rooted tree consisting of $n$ vertices. Consider the following function:
    
    int order[n]; // initially consists of -1
    int pointer = 0;
    void dfs(int vertex, int depth) {
      order[pointer] = depth;
      pointer++;
      for each child of vertex
        dfs(child, depth + 1);
    }

In the end this function produces an array $order[]$. We will call an array _suitable_ if and only if it can be produced as a result of running $dfs(root, 0)$ on a rooted tree with $n$ vertices. 

You are given an array $a$, whose elements are either question signs or integer numbers. How many suitable arrays can you get, if you are allowed to replace any question sign with non-negative integer number? Print this number modulo $10^{9} + 7$.

**Input Format**  

The first line contains a single integer $n$, that is the size of array $a$. The next line contains $n$ elements of the array: $a[0], a[1], \dots, a[n-1]$. Each element is either a question sign, or a non-negative integer number which doesn't exceed $200$.  

**Constraints**  
$1 \le n \le 10^5$  
$0 \le a[i] \le 200$

**Output Format**

Print a single integer $-$ the number of suitable arrays you can get modulo $10^{9} + 7$.

**Sample Input #0**

    3
    ? ? ?    

**Sample Output #0**

    2

**Sample Input #1**

    2
    1 ?

**Sample Output #1**

    0

**Sample Input #2**

    4
    0 ? 1 ?

**Sample Output #2**

    2

**Explanation**

In **sample#0** there are two possible arrays: [0, 1, 2] and [0, 1, 1];

In **sample#1** there cannot be any suitable arrays, because each of them starts with 0.

Cod sursa

# Enter your code here. Read input from STDIN. Print output to STDOUT

'''
Over all possible rooted trees of n vertices, how many possible outputs can the DFS() function yield that match array S? (I renamed A to S instead)

The output array delineates the depths of the nodes as it traverses depth-first. For example

        o            Depth 0
      /   \
     o     o         Depth 1
    / \     \
   o   o     o       Depth 2
            / \
           o   o     Depth 3
          /|\   \
         o o o   o   Depth 4
   
yields order [0,1,2,2,1,2,3,4,4,4,3,4]

Necessary conditions: 

1. Clearly, there is only one root node, and its depth is 0, so 0 must be at the start of S, either in the form of a "?" or a 0.
2. 0 cannot be present anywhere in S other than the very front.
3. If the search traverses from parent to child, the depth increases by 1.
4. If we hop to another child or subtree instead, its depth can only be less than or equal to current depth

In other words, we are counting the number of sequences (that match S) such that a value can increase by at most 1, or drop down to any positive integer. So:
1. output[0] = 0
2. output[i] - 1 <= output[i-1]

So when looking at S, let's look at sequences of ? characters between fixed elements. For example:
[...,5,?,?,?,?,?,?,?,?,?,?,8,...]
Let a=5 and b=8. Let n = 10, the number of "?" between a and b.
The first ? must start with some number in the range [1 to a+1] => [1 to 6] inclusive.
The last ? must be in the range [max(1,b-1) to (a + n)] => [7 to 15] inclusive.
How many valid sequences are there? 
In general, comb(2*n+a-b+1,n) - comb(2*n+a-b+1,n-b)
'''

import sys

MOD = 10 ** 9 + 7
MAXN = 10 ** 5
MAXAI = 200
factLim = 2 * MAXN + MAXAI
fact = [1] + [0] * (factLim)
for i in range(1, factLim + 1):
    fact[i] = fact[i - 1] * i % MOD
    
def comb(n, k):
    if k < 0 or n < 0 or k > n: return 0
    if k == 0 or k == n: return 1
    return fact[n] * pow(fact[k] * fact[n - k], MOD - 2, MOD) % MOD

def preliminaryCheck_isInvalid(S,N):
    #if first char isn't a 0 or '?', it's some other number. Invalid!
    if S[0] != "?" and S[0] != 0: 
        return True
    for i in range(1, N):
        #if S[i] could not possibly be as high as it is. Invalid!
        if S[i] != "?" and S[i] > i: 
            return True
        #if there's a 0 anywhere else other than the start. Invalid!
        if S[i] == 0: 
            return True
        #Cannot make a depth jump like this. Invalid!
        if (S[i] != "?" and S[i - 1] != "?") and S[i] - 1 > S[i - 1]: 
            return True
    #basic checks OK
    return False  

#number of valid sequences to fill a section of L "?"s between two numbers a and b
#such that S[i] takes on any number from 1 to S[i-1]+1
def numQuestionSeq(a, b, n): 
    return comb(2 * n + a - b + 1, n) - comb(2 * n + a - b + 1, n - b)

def numSuitable(S, N):
    if preliminaryCheck_isInvalid(S, N): 
        return 0
    S[0] = 0
    #the extra 1 gives bIndex a sentinel val to use later. N will not count this.
    S += [1]  
    aIndex = 0
    bIndex = 1
    ans = 1
    while aIndex < N and bIndex < N:
        while bIndex < N and S[bIndex] == "?":
            bIndex += 1
        n = bIndex - aIndex - 1
        a, b = S[aIndex], S[bIndex] 
        if n > 0: ans = ans * numQuestionSeq(a, b, n) % MOD
        aIndex = bIndex
        bIndex += 1   
    return ans

N = int(sys.stdin.readline())
S = [int(k) if k.isdigit() else k for k in sys.stdin.readline().split()]
print(numSuitable(S,N))