We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Construct the Array
  5. Discussions

Construct the Array

Sort by

recency

|

169 Discussions

|

  • severiano_cuell1
     + 0 comments

    Did not understand why my code passed only first 2 testcases and failed all the rest until I realized that the modulo code was not in the right place.

    If you comment your modulo code and it passes the testcases below when n<12 but will fail as soon as n=12 , then your code is very close to the solution.

    10 10 2 38742049

    11 10 2 348678440

    12 10 2 138105940

  • Tusenka
     + 0 comments

    how to avoid recursion:

    ``cache=[]
_build_dp=_build_dp
def _build_dp(last, s, array, rest, x, n):
    for j in reverse(len(n):
        if len(rest)>n:
            return 0
        if n==2:
            if s!=x:
                return 1
            else:
                return 0  
    _count=0
    if (len(rest)==n):
        for i in rest:
            if i!=s:
                _count+=_build_dp(s, i,  array, [ j for j in rest if j!=i ], x, n-1)
    else:
        for i in array:
            if i!=s:
                _count+=_build_dp(s, i,  array, [ j for j in rest if j!=i ], x, n-1)
        return _count

  • Tusenka
     + 0 comments

    how to avoid recusrion?

    !/bin/python3

    import math import os import random import re import sys

    #

    Complete the 'countArray' function below.

    #

    The function is expected to return a LONG_INTEGER.

    The function accepts following parameters:

    1. INTEGER n

    2. INTEGER k

    3. INTEGER x

    #

    def _build_dp(last, s, array, rest, x, n): if len(rest)>n: return 0 if n==2: if s!=x: return 1 else: return 0
    _count=0 if (len(rest)==n): for i in rest: if i!=s: _count+=_build_dp(s, i, array, [ j for j in rest if j!=i ], x, n-1) else: for i in array: if i!=s: _count+=_build_dp(s, i, array, [ j for j in rest if j!=i ], x, n-1) return _count

    def countArray(n, k, x): _count=0 for i in range(2, k+1): _count+=_build_dp(1, i, range(1, k+1), [ i for i in range(2, k+1) if i!=x], x, n-1) return _count

    if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

k = int(first_multiple_input[1])

x = int(first_multiple_input[2])

answer = countArray(n, k, x)

fptr.write(str(answer) + '\n')

fptr.close()

  • gbednik
     + 0 comments
    const long divide = pow(10, 9) + 7;

    // Return the number of ways to fill in the array.
long countArray(int n, int k, int x) 
{
    if (n == 3)
    {
        if (x == 1)
            return long(k-1)%divide;
        else
            return long(k-2)%divide;   
    }
    else
    {
				// Array of answers for various n and x=1
        vector<long> A;
				// Array of answers for various n and x!=1 (does not depend on specifica value of x)
        vector<long>B;
        
        A.reserve(n-2);
        B.reserve(n-2);
        
				// special case n=3
        A.push_back((k-1)%divide);
        B.push_back((k-2)%divide);
        
				// increase n by 1 recurrently
        for(int i = 0 ; i < n-3 ; i++)
        {
            long a = (k-1)*B.back();
            long b = A.back() + (k-2)*B.back();
            a = a % divide;
            b = b % divide;
            A.push_back(a);
            B.push_back(b);
        }
        if(x == 1)
            return A.back();
        else
            return B.back();
    }

}

  • dunghva1ts42003
     + 0 comments

    public static long countArray(int n, int k, int x) { long mode = 1000000000 + 7; long[][] dp = new long[n + 1][2]; if (n == 2) { if (x == 1) return 0; else return 1; } if (x != 1) { dp[2][0] = 1; dp[2][1] = k - 2; } else { dp[2][0] = 0; dp[2][1] = k - 1; } for (int i = 3; i <= n; i++) { dp[i][0] = dp[i - 1][1] % mode; dp[i][1] = (dp[i - 1][1] * (k - 2) + dp[i - 1][0] * (k - 1)) % mode; }

        return dp[n][0];
}