Sort by

recency

|

170 Discussions

|

  • + 0 comments

    This problem required very little memoization. I noticed a pattern; consider the number of arrays of length 2: [0,1,1] where index is the ending number x. Using a dynamic coding strategy, you might try to find the number of arrays of length 3 by summing up elements of this array: [2,1,1] You don't add the number of arrays of length 2 ending in the same x, since the numbers can't appear twice in a row. Therefore, index 1 is one greater, since it ignored the one element that was 1 less than the others. Using this array, the number of arrays of length 4 is: [2,3,3] This time, index 1 is one less since it ignored the one element that was one more than the rest. The pattern continues: [6,5,5] [10,11,11]

    So we can ditch using arrays and just consider the number of arrays ending in x>1. The number N(n) of arrays of length n ending in x>1 is equal to (k-1)*N(n-1) + (1 if n is even, -1 if n is odd)

    if x==1, subtract 1 if n is even, add 1 if n is odd

    function countArray(n: number, k: number, x: number): number {
        // Return the number of ways to fill in the array.
        //ending in number col+1
        //array of length row+2
        //NOTE: for EVEN length, there is one less array ending in 1. for ODD, there is one extra.
        // Otherwise, the number of constructable arrays of length n ending in k is equal to the sum of all arrays of length n-1, + or - one depending on n's parity.
        let curr = 1;
        
        let mod = (Math.pow(10,9)+7)
        
        let even;
        let odd;
        //iterate over possible lengths
        for(let i=2; i<n; i++)
        {
            even = i%2
            odd = even==1?0:1
            //add even bonus, remove odd
            curr = (curr*(k-1) + even - odd) % mod
        }
        if(x==1) curr += (-even + odd)
        
        return curr
    }
    
  • + 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

  • + 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
    
  • + 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()
    
  • + 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();
        }
    
    }