PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Dmytro Berezin
Tester: Encho Mishinev
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming, Observations and Patterns.
PROBLEM:
There are N dogs lined in a row numbered from 1 to N, having skill level as given in array A. A dog at position p with skill s can pass ball to dog at position q if 1 \leq |p-q| \leq s. Further, each dog can either pass the ball to another dog receiving the ball for the first time or finish the game by scoring. We have to count the number of ways the game may finish.
Two sequences are considered different if their lengths differ, or there is a valid index i in sequence such that at time i, The dogs holding ball differ in both sequences.
QUICK EXPLANATION
- The total number of sequences ending at position p can be categorized into sequences coming from left side and paths coming from right side to the last dog in sequence.
- Let DP[p] denote the number of paths coming from left side. All paths coming from left to (p-1) position can be extended to pth position. So DP[p] includes DP[p-1]. Also, If Dog at position (p-2) has skill 2, it can directly pass the ball to pth dog, thus DP[p] including DP[p-2] in this case. The third case is when the ball moves from position (p-3) to (p-1) to (p-2) to pth position. For this to happen, both dogs at positions (p-3) and (p-2) should have skill level 2. If they do have the skill, DP[p] include DP[p-3] since all paths ending at (p-3) position can end at pth position in this case.
- Paths coming from right side and ending at pth dog reach (p-1) and follows either of the two pattern, 1, 3 \ldots (x-2), x, (x-1), (x-3), \ldots 4, 2 or 1, 3, \ldots (x-2), x, (x+1), (x-1), (x-3) \ldots 4, 2 where position (p-1) represent 1 in patterns, the start point for both patterns. We have to count the number of such patterns in O(1) time. If z is the number of sequences in the above pattern we can complete, then we have DP[p-1]*z paths ending at pth position coming from the right side.
- For finding the number of values of x for each pattern, all that matters is the position of the nearest dog with skill 1 to the right of pth dog.
EXPLANATION
This problem can go to become way complicated if we are not careful enough in avoiding overcounting sequences. So, Without ado, I am going to divide sequences into two types.
- The sequences which reach position p moving from the left side in the last step.
- The sequences which reach position p moving from the right side in the last step.
For counting sequences of the first type, we shall use dynamic programming. Let DP[p] denote the number of sequences of first type ending at position p. Assuming we have calculated DP[i] for all i < p, we need to calculate DP[p]. There are three different ways we can reach pth position, from position (p-1), from position (p-2) and from position (p-3) to (p-1) to (p-2) to p.
We can always move from position (p-1) to position p (assuming position p is unvisited) irrespective of skills, So, we add DP[p-1] to DP[p] Since all sequences ending at position (p-1) can now be extended to position p.
For moving from position (p-2) to position p directly, The dog at position (p-2) should have 2 as skill. If the condition is satisfied, we add DP[p-2] to DP[p] Since all sequences ending at position (p-2) can now be extended to position p.
In the third case, The ball moves from position (p-3) to (p-1) to (p-2) to position p. For this, both the dogs at positions (p-2) and at position (p-3) should have skill power 2. If the condition is satisfied, Every path ending at position (p-3) can now be extended to position p (different from the first two). So we add DP[p-3] to DP[p] in this case.
We have calculated the number of all possible sequences ending at a given position which move from left side to pth position in the last move.
For the sequences moving from right at last step and ending at pth position, at some point reach (p-1) position and from there, can follow only two patterns to reach pth position. So dog at position (p-1) is required to have skill 2, otherwise, there is no sequence ending at position p from the right side.
Refer the two possible patterns below which are possible. (In following patterns, 1 denote position (p-1), 2 denote position p and so on).
1: 1 3 5 . . . (z-2) z (z-1) . . . 4 2
2: 1 3 5 . . . (z-2) z (z+1) (z-1) . . . 4 2
First few patterns are
1 3 2
1 3 4 2
1 3 5 4 2
1 3 5 6 4 2
For counting the number of values of x for each pattern, we can notice that All positions except position 2 and position x need to have skill value 2. So, For the pattern to exist, all that matters is the nearest position of 1. For counting patterns ending at position p, There are three cases.
- There is no dog with skill 1 after position p.
- The nearest dog with skill 1 to the right of p is at an odd distance from p
- The nearest dog with skill 1 to the right of p is at an even distance from p.
In the first case, The number of valid patterns is the same as the number of dogs (Found by observation), say x after the dog at position p. So, Each sequence ending at position (i-1) can now end in position p as a different sequence in x*DP[i-1] ways.
In the second case, Say the position of such a dog is x. Starting from (p-1), Ball directly ends up at x. Now, All patterns with value y < x are valid and first pattern is valid for x too. Now, if there’s a dog with skill 2 at position (x+1), x is valid for the second pattern too. So, we have counted all the values of x here for which pattern is valid, say c. The number of different sequences ending at position p coming from the right is c*DP[i-1].
In the last case, Say the position of such a dog is x. Starting from (p-1), Ball ends up at position (x-1). Now, If the ball is passed to dog x, it cannot pass to a dog at position (x-1) as that dog cannot receive ball more than once, nor the dog x can pass the ball to (x-2) since it doesn’t have required skill. So, Ball from position (x-1) has to be passed to (x-2) then to (x-4) and so on. Hence, in this case, the first pattern is valid for all positions up to (x-1) which are at an odd distance from p, while the second pattern is valid for all positions up to (x-2) which are at even distance from p. So, we have counted all the values of x here for which pattern is valid, say c. The number of different sequences ending at position p coming from the right is c*DP[i-1].
This way, we have counted all the sequences.
Bonus Problem
Same problem. Instead of standing in a row, Dogs are now standing in a circle. Good Luck solving!
Time Complexity
Time complexity is O(N) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int arr[100100];
int n;
long long mod= 1000000007;
long long dp[100100];
int to_right[100100];
int to_left[100100];
int cnt=0;
bool vis[100100];
void search(int pos){
cnt++;
if(pos - 1 >=1 && !vis[pos-1]){
vis[pos-1] = true;
search(pos-1);
vis[pos-1] = false;
}
if(pos + 1 <= n && !vis[pos+1]){
vis[pos+1] = true;
search(pos+1);
vis[pos+1] = false;
}
if(arr[pos] == 2){
if(pos - 2 >=1 && !vis[pos-2]){
vis[pos-2] = true;
search(pos-2);
vis[pos-2] = false;
}
if(pos + 2 <= n && !vis[pos+2]){
vis[pos+2] = true;
search(pos+2);
vis[pos+2] = false;
}
}
}
int main(){
////freopen("06.txt","r",stdin);
//freopen("06o.txt","w",stdout);
T=readIntLn(1,10);
while(T--){
n=readIntLn(1,100000);
for(int i=1;i<=n;i++){
if(i==n){
arr[i]=readIntLn(1,2);
} else {
arr[i]=readIntSp(1,2);
}
vis[i]=false;
}
if(n == 1){
cout<<1<<endl;
continue;
}
/*cnt = 0;
vis[1] = true;
search(1);
cout<<"Cnt: "<<cnt<<endl;
if(arr[1] == 2){
to_right[1] = 1;
} else {
to_right[1] =0;
}
if(arr[2] == 2){
to_right[2] = 1;
} else {
to_right[2] =0;
}
for(int i=3;i<=n;i++){
if(arr[i] == 2){
to_right[i] = to_right[i-2] + 1;
} else {
to_right[i] = 0;
}
}
if(arr[n] ==2){
to_left[n] = 1;
} else {
to_left[n] = 0;
}
if(arr[n-1] == 2){
to_left[n-1] = 1;
} else {
to_left[n-1] = 0;
}
for(int i=n-2;i>=1;i--){
if(arr[i] == 2){
to_left[i] = to_left[i+2] + 1;
} else {
to_left[i] = 0;
}
}*/
if(arr[n] == 2){
to_right[n] = 1;
} else {
to_right[n] = 0;
}
for(int i=n-1;i>=1;i--){
if(arr[i] == 2){
to_right[i] = to_right[i+1] +1;
} else {
to_right[i] = 0;
}
}
long long sol = 1;
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1];
if(i>2 && arr[i-2] > 1){
dp[i] = (dp[i] + dp[i-2])%mod;
}
if(i > 3 && arr[i-3] == 2 && arr[i-2] == 2){
dp[i] = (dp[i] + dp[i-3])%mod;
}
sol += dp[i];
sol %= mod;
}
for(int i=1;i<=n-3;i++){
if(arr[i] != 2)continue;
int g= to_right[i+2];
if(g % 2)g--;
if(i+3+g > n){
g-=2;
}
if(arr[i+3+g] != 2){
g-= 2;
}
if(g < 0)continue;
sol += dp[i] * (g/2 + 1);
sol %= mod;
}
for(int i=1;i<=n-2;i++){
if(arr[i] != 2)continue;
int g= to_right[i+2];
if(g % 2)g--;
if(i+2+g > n){
g-=2;
}
if(g < 0)continue;
sol += dp[i] * (g/2 + 1);
sol %= mod;
}
cout<<sol<<endl;
//cout<<"Sol: "<<sol<<endl;
}
assert(getchar()==-1);
}
Tester’s solution
Click to view
#include <iostream>
#include <stdio.h>
using namespace std;
const int MOD = 1000000007;
int t;
int n;
int F[100111][2][2];
int a[100111];
int endThere[100111];
int solve(int ind,int lst,int slst)
{
if (F[ind][lst][slst] != -1)
return F[ind][lst][slst];
int ans = 1 + endThere[ind];
if (ind < n)
{
ans += solve(ind+1, 1, lst);
if (ans >= MOD)
ans -= MOD;
if (a[ind] == 2 && ind < n - 1)
{
ans += solve(ind+2, 0, 1);
if (ans >= MOD)
ans -= MOD;
}
}
if (lst == 0)
{
if (a[ind-1] == 2 && ind < n)
{
ans += solve(ind+1, 1, 1);
if (ans >= MOD)
ans -= MOD;
}
}
F[ind][lst][slst] = ans;
//cout<<"F["<<ind<<"]["<<lst<<"]["<<slst<<"]="<<ans<<endl;
return ans;
}
int main()
{
int i,j;
int test;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
F[i][0][0] = -1;
F[i][0][1] = -1;
F[i][1][0] = -1;
F[i][1][1] = -1;
}
endThere[n] = 0;
endThere[n-1] = 0;
for (i=n-2;i>=1;i--)
{
if (a[i] == 1)
{
endThere[i] = 0;
}
else
{
endThere[i] = 1;
if (i + 3 <= n && a[i+3] == 2)
{
endThere[i] += endThere[i+2] + 1;
}
}
}
printf("%d\n",solve(1,1,1));
}
return 0;
}
Editorialist’s solution
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
boolean[] a = new boolean[n];
for(int i = 0; i< n; i++)a[i] = ni()==2;
long[] dp = new long[n];dp[0] = 1;
long ans = 1;
for(int i = 1; i< n; i++){
dp[i]+=dp[i-1];
if(i>=2 && a[i-2])dp[i]+=dp[i-2];
if(i>=3 && a[i-3] && a[i-2])dp[i]+=dp[i-3];
dp[i]%=mod;
ans+=dp[i];
if(ans>=mod)ans-=mod;
}
int nxt = n;
for(int i = n-3; i>= 0; i--){
if(!a[i+2])nxt = i+2;
if(!a[i])continue;
long f = 0;
if(nxt==n){
f = nxt-i-2;
}else{
long x = nxt-i-1;
f = Math.max(0, x-1);
if(x%2==1)f++;
if(x%2==1 && nxt+1<n && a[nxt+1])f++;
}
ans+=(f*dp[i])%mod;
ans%=mod;
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e3+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
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, If it differs. Suggestions are always welcomed. 