COUNTA - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Samarth Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Dynamic Programming, Combinatorics

PROBLEM

Consider an array A of length N where 0 \leq A_i \leq 10^5. Construct an array B of length N-1 as B_i = min(A_i, A_{i+1}).

You are given the array B, find the number of arrays A of length N, which can be used to construct array B by the above process.

EXPLANATION

This is a DP combinatorics problem, So I recommend pen and paper as well. Also, using M = 10^5 throughout the editorial.

What we can see here is that, Either B_i = A_i or B_i = A_{i+1}. Let’s consider first element A_1.
Either

  • A_1 \gt B_{1} OR
    In this case, it doesn’t matter which value A_N takes, as long as B_1 \lt A_1 \leq M, So there are (M - B_1) ways to choose the last value. Also, A_2 must be equal to B_1 in this case.
  • A_1 = B_1
    In this case, A_2 can take any value in range [max(B_1, B_2), M].

We can see that we only care about whether B_i = A_i or B_i = A_{i+1} and not the actual values of A_i and A_{i+1}.

This suggests a kind of DP where we maintain one state for keeping track of index, and a flag to determine whether B_i = A_i or B_i = A_{i+1}

Let’s denote f(i) as the number of ways to select first i elements of A in valid way such that A_i = B_i
Also, let’s denote g(i) as the number of ways to select first i+1 elements of A such that A_{i+1} = B_i and A_i \gt A_{i+1}. This second condition is added, to avoid double counting of the case where A_i = A_{i+1} = B_i

The final answer would be f(N-1) \times (M - B_{N-1}+1) + g(N-1), as this covers both the cases when A_{N-1} = B_{N-1} (first term) and A_{N-1} \gt B_{N-1} (second term).

For simplicity, let’s denote w(x) = M-x+1, we we need to use it quite frequently. Required answer becomes f(N-1)*w(B_{N-1}) + g(N-1). w(B_{N-1}) denotes the number of ways to select last element when first N-1 elements are already chosen.

Now, let’s see how base cases and transitions work.

Base cases

We can see that f(1) = 1, as A_1 = B_1 is the only way.
For g(1), we choose A_2 = B_1 and A_1 \gt B_1 which can be done in (M-B_1) = w(B_1+1) ways.

Hence, f(1) = 1 and g(1) = w(B_1+1) are the base cases.

Transitions

We need to find formula for f(i) and g(i) represented by terms f(i-1) and g(i-1).

For the computation of f(i), the following cases need to be considered.

  • Contribution of f(i-1) in f(i).
    If we have B_i \geq B_{i-1}, then we can choose A_i = B_i, which can be done in f(i-1) ways.
  • Contribution of g(i-1) in f(i)
    If an array A is included in both f(i) and g(i-1), it implies A_i = B_i and A_i = B_{i-1}. This can only happen when B_i = B_{i-1}. Hence, if B_i = B_{i-1}, each way included in g(i-1) contributes one way in $f(i).

Similarly, for computation of g(i), the following cases need to be considered.

  • Contribution of f(i-1) in g(i)
    $f(i-1) sets A_{i-1} = B_{i-1} and g(i) sets A_{i+1} = B_i. So we only need A_i \geq max(B_{i-1}, B_i+1). Hence, each way in f(i-1) contributes w(max(B_{i-1}, B_i+1) ways in g(i).
  • Contribution of g(i-1) in g(i)
    Only if B_{i-1} \gt B_i that each way in g(i-1) contributes one way in g(i)

I know the above details are quite hard to understand from the pure text. Let’s assume [condition] evaluates to 1 if condition is true, and 0 if false. We can write the above recurrences as follows.

f(i) = [B_i \geq B_{i-1}] f(i-1) + [B_i = B_{i-1}] g(i-1)
g(i) = f(i-1) * w(max(B_{i-1}, B_i+1)) + [B_{i-1} \gt B_i]g(i-1)

Hence, we can compute the values of f(i) and g(i) one by one in increasing order, and compute the final answer as f(N-1) * w(B_{N-1}) + g(N-1)

Questions you may have

  • Why choosing these weird functions?
    Functions are a really nice representation of how dynamic programming works. Referring my code, ways[i][0] represents $f(i) and ways[i][1] represents g(i).
  • How do I debug this kind of problem?
    The best way would be to write a brute force solution. For this problem, I’d recommend writing brute force for N = 4 and M = 10, generating random array B and running 4 nested loops to compute the correct answer in O(M^4). I have added such a snippet for your reference.

I hope you guys found it understandable and clear. Refer my code, written on same lines.

TIME COMPLEXITY

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
#define int long long
//#include <sys/resource.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        n--;
        int b[n];
        for(int i = 0;i<n;i++) cin>>b[i];
        int prev[2];
        //1 represents the case when a[i+1] < a[i]
        //0 represents the case when a[i] <= a[i+1]
        prev[0] = 1;
        prev[1] = (100000 - b[0]);
        for(int i = 1;i<n;i++){
            int curr[] = {0, 0};
            //0 from 1
            if(b[i] == b[i-1]) curr[0] += prev[1];
            curr[0]%=MOD;
            //0 from 0
            if(b[i] >= b[i-1]) curr[0] += prev[0];
            curr[0] %= MOD;
            //1 from 1
            if(b[i] < b[i-1]) curr[1] += prev[1];
            curr[1] %= MOD;
            //1 from 0
            curr[1] += ((min(100000 - b[i-1] + 1, 100000 - b[i])*prev[0])%MOD);
            curr[1] %= MOD;
            prev[0] = curr[0];
            prev[1] = curr[1];
        }
        int ans = prev[1];
        ans += ((prev[0] * (100000 - b[n-1] + 1))%MOD);
        ans %= MOD;
        cout<<ans<<endl;
    }
}
Tester's Solution
t = int(input())
mod = 1000000007
for tc in range(t):
    n = int(input())
    n -= 1
    arr = list(map(int, input().split()))
    dp = [[0 for i in range(2)] for j in range(n)]
    dp[0][0], dp[0][1] = 1, 100000 - arr[0]
    for i in range(1, n):
        if(arr[i] >= arr[i-1]):
            dp[i][0] += dp[i-1][0]
        if(arr[i] == arr[i-1]):
            dp[i][0] += dp[i-1][1]
        if(arr[i] < arr[i-1]):
            dp[i][1] += dp[i-1][1]
        dp[i][1] += (min(100000 - arr[i-1] + 1, 100000 - arr[i]) * dp[i-1][0])
        dp[i][0] %= mod
        dp[i][1] %= mod
    ans = dp[n - 1][1] + dp[n - 1][0] * (100000 - arr[n - 1] + 1)
    ans %= mod
    print(ans)
Editorialist's Solution
import java.util.*;
import java.io.*;
class COUNTA{
    //SOLUTION BEGIN
    long MOD = (long)1e9+7;
    int M = (int)1e5;
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[] B = new int[1+N];
        for(int i = 1; i< N; i++)B[i] = ni();
        //ways[i][0] => Number of ways to choose first $i$ elements of $A$ such that $A_i = B_i$
        //ways[i][1] => Number of ways to choose first $i+1$ elements of $A$ such that $A_{i+1} = B_i$ and $A_i > A_{i+1}$
        long[][] ways = new long[1+N][2];
        ways[1][0] = 1;
        ways[1][1] = f(B[1]+1);
        for(int i = 2; i< N; i++){
            if(B[i] >= B[i-1])ways[i][0] += ways[i-1][0];
            if(B[i] == B[i-1])ways[i][0] += ways[i-1][1];
            if(B[i] < B[i-1])ways[i][1] += ways[i-1][1];
            ways[i][1] += ways[i-1][0] * f(Math.max(B[i-1], B[i]+1));
            
            ways[i][0] %= MOD;
            ways[i][1] %= MOD;
        }
        long ans = (ways[N-1][0]*f(B[N-1])+ways[N-1][1])%MOD;
        pn(ans);
//        pn(brute(B));
    }
    long f(long x){
        return M+1-x;
    }
    long brute(int[] B){
        //works only for N = 4 and small M. Add or remove loops and conditions for changing N
        long ways = 0;
        for(int i1 = 0; i1 <= M; i1++)
            for(int i2 = 0; i2 <= M; i2++)
                for(int i3 = 0; i3 <= M; i3++)
                    for(int i4 = 0; i4 <= M; i4++)
                        if(Math.min(i1, i2) == B[1] && Math.min(i2, i3) == B[2] && Math.min(i3, i4) == B[3])
                            ways++;
        return ways;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new COUNTA().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

10 Likes

5
9 8 8 9
The answer for above test case according to the code given above is 993200016.
Can anyone give an example of one possible array A.
Thanks.

9 9 8 9 9.
The second and fourth nines can be anything till 1e5.

2 Likes
1
5
2 5 1 1

How can be its answer 999099867 (Setter’s Code)

I think there could be only two types of arrays 2 X 5 1 1 OR 2 5 X 1 1
where 5<=X<=1e5

am I missing something ??

Another: 2 5 X 1 Y

1 Like

Ohh…Got it, bro. Thanks

Shouldn’t the condition for the contribution of g(i-1) be [Bi < Bi-1] instead, following from the above explanation

1 Like

Thanks for pointing out. Corrected.

1 Like

I followed this approach , editorial is quite complicated:
Define dp(i,0) → Number of ways to have array (a1,a2,a3,…,ai) such that ai is equal to bi .
Define dp(i,1) → Number of ways to have array (a1,a2,a3,…,ai) such that ai is not equal bi .
See solution for details: CodeChef: Practical coding for everyone