Number of possible arrays such that adjacent elements have difference atmost 1

Question

You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

The unknown values will be given as "0" in the input array. Give the number of arrays modulo 1e9+7

The problem could be broken into two parts. One is where the unknown is in between the knowns, then it's simple to calculate the number of arrays, The difference can only be 0,1 or 2. it can't be 3, because eg 2 0 5, then there is No value that gives the correct array. The input will always have a difference between the unknown as possible values. if the difference is 0, 2 0 2, then 3 values are possible, if the difference is 1, 2 0 3, then 1 and 3 are the only possible values, so 2 values possible. for the difference of 2, there is only 1 value so no change in the result is ok.

But the second case where the unknowns are in between unknowns is what troubles me.

#include <bits/stdc++.h>

using namespace std;

const int MOD   = 1e9 + 7;


int main() {

    int n,m;cin>>n>>m;
    vector<int> arr(n);

    for(int i=0;i<n;i++) cin>>arr[i];

    int res=1;

    if(arr[0]==0 && arr[1]!=0)
        res=(res%MOD*3)%MOD;
    if(arr[n-1]==0 && arr[n-2]!=0)
        res=(res%MOD*3)%MOD;

    //for unknowns between knowns
    for(int i=1;i<n-1;i++)
    {
        if(arr[i]==0 && arr[i-1]!=0 && arr[i+1]!=0)
        {
            int val=arr[i+1]-arr[i-1];
            if(val==0)
                res=(res%MOD*3)%MOD;
            else if(val==1)
                res=(res%MOD*2)%MOD;
        }
    }

    //for unknows between unknowns(I don't know how to approach this. Brute force will surely give TLE)
    for(int i=0;i<n;i++)
    {
        int st=i;
        while(i<n && arr[i]==0)
            i++;

        if(arr[i]!=0) i--;

        if(i-st>=1)
        {
            if(st!=0 && i!=n-1)
            {

            }
        }

    }


    cout<<res;


    return 0;
}

for 2 0 2, output is 3 ([2 1 2][2 2 2][2 3 2])

I want to know how to solve the 2nd case of this problem, with continuous unknown values.

Answer 1

The simple implementation of the idea explained above using DP in c++ is as follows:

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007;
typedef long long ll;
ll const N = 1e5 + 5, M = 1e2 + 5;
ll n, m;
ll dp[N][M];
ll a[N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;

    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    if (a[1] == 0)
        for (int i = 1; i <= m; i++)
            dp[1][i] = 1;
    else
        dp[1][a[1]] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            if (a[i] == 0 || j == a[i])
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]) % mod;
    }
    ll ans = 0;
    for (int i = 1; i <= m; i++)
    {
        ans += dp[n][i];
        ans %= mod;
    }
    cout << ans;
}

Answer 2

1. The smaller problem you need to solve is:

   • Given the first and last element, how many ways are there to to fill the other elements?

     In different words: How many combinations of M terms of -1,+0,+1 are there, that add up to last-first?

     A bit more formal, we want

            first + d_0 + d_1 + ... + d_M-1 == last
        ->  d_0 + d_1 + ... + d_M-2 == last-first
     

     This is a combinatorics problem. I'll leave it to you to find the right formula and just pick one example:

        M = 3
        first = 0
        last = 1
     
        solutions:
            0 +0+0+1 == 1 <- 3 different ways to sort the terms
            0 +1-1+1 == 1 <- 3 different ways sort the terms
     

     Write a function find_combinations_between(int first,int last,int M);.

   • The tiny problem: In case you have only first or last given, the solution is simply 3^M.

2. Back to the original problem

   Once you can solve the smaller problem, getting arrays with known/unknown elements in the middle is straightforward.

   Pseudocode:

   int calculate( iterator begin, iterator end) {
       int count = 0;
       auto first = begin;
       auto last = begin;
       // find next known element
       while ( last != end && is_empty( last ) ) {
           ++last;
           ++count;
       }
       // there is none
       if ( last == end) return result * power_of_3( count );
       // ..or recurse to the next sub-interval
       return calculate(last,end) * find_combinations_between(first,last,count);
   }
   

   I think passing iterators can help for clarity a bit. The idea is to split the array into sub-intervals, such that always only first and last elements are known. power_of_3 and is_empty is only used for readability, you could probably replace it with some other call or == 0, respectively. Take the code with a grain of salt, it is meant to outline the idea but may contain mistakes.

3. mod 1e7

   Only when the algorithm itself is working I would incorporate the %1e7 part, hence I ignored it for this answer.

---

PS I am not presenting you a full solution, but rather suggest you change perspective. Your "one unknown in between two knowns" case is a very special case, but you need an overall strategy first. If you follow my recipe then all the complexity is in one place: find_combinations_between. And most importantly, in that function, you can concentrate on the combinatorics problem, while it is irrelevant whether the elements are inside some array or whatever.

PPS: As already mentioned I did not present you a full solution. And I still do not feel like giving one. The above is only how to approach the problem in a different way, but how to actually solve it was left open. As per your request I will add a bit more clarification on how to tackle the find_combinations_between.

Some visualisation may help. As the solution only depends on the difference last - first, I use first = 0 and last = D.

Lets first consider the case where D==M, ie the trivial case where we have to add +1 on every element to reach the correct result:

0
 \
  \
   \
    \
     D

That was easy, right? There is only one solution. Now lets go just a tiny bit more compilcated: What if D == M-1? Then we have to add +1 for all but one element. Possible solutions are

0        0        0         0
 \        \        \        |
  \        \        |        \
   \        |       \         \
   |        \        \         \
   D         D        D         D

ie exactly as many as there are free elements to choose. The same situation you have on the other end, when the only way to reach the right sum is to add -1 on each element (or add -1 on all but one).

It gets more complicated when +1 and -1 can be combined to get the right solution. The visualization above can still help for orientation. Think of all the paths that I didnt not draw in the above images, then you have a tree and need to find the number of possible paths from the root to a given leaf.

I don't know how to explain more without actually implementing it myself, which would mean starting to write code instead of writing the answer here ;). Hence I will again use an example and hope it helps you to find the solution.

Lets say the difference last-first is 2. Then first you need to find, for the given number of elements, lets say 4, all possible increments, that would be

+1 +1 +0 +0 = 2    // start with minimum number of +1s, ie 2 in this case
+1 +1 +1 -1 = 2    // next has 3x +1
                   // 4x +1 is not possible

Next you have to find all different permutations, that would be

+1 +1 +0 +0   // 4*3 because 
+1 +0 +1 +0   // 4 choices for the first +1
+1 +0 +0 +1   // x3 choices for the second
+0 +1 +1 +0
+0 +1 +0 +1
+0 +0 +1 +1

+1 +1 +1 -1  // 4 different ways to place the -1
....

In total that would be 12+4=16 different ways to add +1,0 or -1 to reach from any number x to x+2 in 4 steps.