PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter:
Tester: Samarth Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
EasyMedium
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 N1 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(N1) \times (M  B_{N1}+1) + g(N1), as this covers both the cases when A_{N1} = B_{N1} (first term) and A_{N1} \gt B_{N1} (second term).
For simplicity, let’s denote w(x) = Mx+1, we we need to use it quite frequently. Required answer becomes f(N1)*w(B_{N1}) + g(N1). w(B_{N1}) denotes the number of ways to select last element when first N1 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 (MB_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(i1) and g(i1).
For the computation of f(i), the following cases need to be considered.
 Contribution of f(i1) in f(i).
If we have B_i \geq B_{i1}, then we can choose A_i = B_i, which can be done in f(i1) ways.  Contribution of g(i1) in f(i)
If an array A is included in both f(i) and g(i1), it implies A_i = B_i and A_i = B_{i1}. This can only happen when B_i = B_{i1}. Hence, if B_i = B_{i1}, each way included in g(i1) contributes one way in $f(i).
Similarly, for computation of g(i), the following cases need to be considered.
 Contribution of f(i1) in g(i)
$f(i1) sets A_{i1} = B_{i1} and g(i) sets A_{i+1} = B_i. So we only need A_i \geq max(B_{i1}, B_i+1). Hence, each way in f(i1) contributes w(max(B_{i1}, B_i+1) ways in g(i).  Contribution of g(i1) in g(i)
Only if B_{i1} \gt B_i that each way in g(i1) 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_{i1}] f(i1) + [B_i = B_{i1}] g(i1)
g(i) = f(i1) * w(max(B_{i1}, B_i+1)) + [B_{i1} \gt B_i]g(i1)
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(N1) * w(B_{N1}) + g(N1)
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[i1]) curr[0] += prev[1];
curr[0]%=MOD;
//0 from 0
if(b[i] >= b[i1]) curr[0] += prev[0];
curr[0] %= MOD;
//1 from 1
if(b[i] < b[i1]) curr[1] += prev[1];
curr[1] %= MOD;
//1 from 0
curr[1] += ((min(100000  b[i1] + 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[n1] + 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[i1]):
dp[i][0] += dp[i1][0]
if(arr[i] == arr[i1]):
dp[i][0] += dp[i1][1]
if(arr[i] < arr[i1]):
dp[i][1] += dp[i1][1]
dp[i][1] += (min(100000  arr[i1] + 1, 100000  arr[i]) * dp[i1][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[i1])ways[i][0] += ways[i1][0];
if(B[i] == B[i1])ways[i][0] += ways[i1][1];
if(B[i] < B[i1])ways[i][1] += ways[i1][1];
ways[i][1] += ways[i1][0] * f(Math.max(B[i1], B[i]+1));
ways[i][0] %= MOD;
ways[i][1] %= MOD;
}
long ans = (ways[N1][0]*f(B[N1])+ways[N1][1])%MOD;
pn(ans);
// pn(brute(B));
}
long f(long x){
return M+1x;
}
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&(n1)));}
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.