# COUNTA - Editorial

Setter:
Tester: Samarth Gupta
Editorialist: Taranpreet Singh

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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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


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

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