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. 