CHEFSOC - EDITORIAL

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. :slight_smile:

5 Likes

i have another Algo.

Given: power-array A[0,1,…,n-1].

Divide it in sub-problem:

sub-prob : i-th dog is starting point and the given power-array is A[i,…,n-1];

solution to this sub-prob will be the no. of combinations of dogs whose indices>=i, and every combination start from i-th dog , and satisfies power sub-array A[i,…,n-1].

let's denote it's answer by ANS[i] .

Note : this point is very necessary , we need to find combinations satisfying Power sub-array starting from i-th and ending at (i+1)-th dog. (and the comb. uses only indices>=i).

Denote the total no. of combinations of this type by NXT[i] .

Now, if we know these values for i+1 and i+2 and i+3, we can compute it for i .

Relation : All possible combinations:

type 1

(i)--GOAL.

i-th dog make a goal itself;

there is only one combination of type 1 

type 2

(i)->(i+1)->>......--GOAL.

type 2 means i-th dog passes ball to i+1 .Now, from i+1 it goes on passing between dogs of indices>=i+1, and lastly made a goal.

no. of combination of second type  = ANS[i+1].(explained earlier).

and as (i)->(i+1)--goal is a member of type 2. 

NXT[i] (started from i and ended at i+1 using indices>=i)    =    1; 

type 3

(i)-->(i+2)->>......--GOAL.

i-th dog passes ball to i+2 if it has power of 2.Now, from i+2 it goes on passing b/w dogs of indices>=i+2, and made a goal at last.

no. of combination of type 3 = ANS[i+2].

type 4

(i)-->(i+2)->(i+1)--GOAL.

i passes to i+2 i(if has power 2) and then ball passed to i+1, and i+1 made a goal.
it differs from type 3 because type 3 never mentions i+1;

no. of comb. of type 4 = 1;

NXT[i] += 1 ; (started from i and ended at i+1 using indices>=i).

type 5

(i)-->(i+2)->(i+1)-->(i+3)->>.......--GOAL.

Extented from type 4, if i+1 has the power of 2 it can pass to i+3. Now, from there ball goes on passing b/w dogs of indices>=i+3;

no.of comb. of type 5 = ANS[i+3];

type 6

(i)-->(i+2)->>---->>(i+3)-->(i+1)--GOAL.

i passes to i+2 (if has power 2), then ball goes on passing b/w dogs of indices>=i+2 and reached to i+3 then passed to i+1 (if i+3 has power 2) and i+1 made a goal at last.

no. of comb. of type 6 = NXT[i+2] .
 (no. of ways i+2 can start to make an end at i+3 using indices>=i+2).

NXT[i] += NXT[i+2] . 
 (as all comb. of type 6 will start from i and end at i+1).

AT last, ANS[0] will be answer to A[0,…n-1].

Here : my submission

Happy coding :slight_smile:

6 Likes

I tried to solve this problem using graphs. I constructed a directed graph, an edge from a to b exists if dog a can pass the ball to dog b.

Now, the problem reduces to finding all the simple paths from start node to all the nodes present in the graph. But that takes Non Polynomial Time, hence not a good solution.

1 Like

@taran_1407
what does this mean
In the second case, Say the position of such a dog is x. Starting from (p-1), Ball directly ends up at x?
and why c *** DP[i-2].
don’t you think it will be c *** DP[i-1].

can anyone elaborate for “In the second case, Say the position of such a dog is x” how to calculate the number of ways to reach p?
For up to x-1 all the pattern is valid so dp[i]=dp[i]+ (no_of_2_upto_x-1)*dp[i-1]?is it correct ?
and what will be the count if x+1 is also 2? this part I’m not getting .can anyone help ?

Can anyone explain the below stuff present in the Testers Solution? Even the author solution and editorials solution too has this kind of snippet. Any link or reference about it will be appreciated! Thanks in advance!

//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--)

@taran_1407 I am unable to understand the 3rd point in quick explanation. Looks like there is a typo.
In my browser it is showing like this, “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…”

What is 1 3\ldots and others like this? Can you explain the 3rd point in a very brief way?

Can anyone please help me to understand this statement in detail. 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.

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.

What does this mean?

Yes… (dots for minimum 10 characters)

That was a typo. Corrected now. Thanks!

It was latex typo. Corrected. You should be able to see it properly now.

Yes, it is correct. The dog can return from any of the indices having 2. if index x+1 also has 2 then it will fall in the third cateogry of the editorial

but I’m facing probelm at the point where the first 1 (at point x is).If x+1 is 1 then dp[i]=dp[i]+(nunber of 2 upto x-1)*dp[i-1] + dp[i-1]{for pattern one for elemnt 1 at x} and if x+1 is 2 then dp[i]=dp[i]+(nunber of 2 upto x-1)*dp[i-1] + dp[i-1]{for pattern one for elemnt 1 at x} +dp[i-1]{for pattern two for elemnt 2 at x+1} . but I’m getting wrong answer .can you explaing why ?

You are overlooking the fact of 1 being at odd/even distance.
If you find 1 at odd distance from i, then dp[i] += (number of 2 till 1) x dp[i-1] + dp[i-1], if there is a 2 immediately after 1. If 1 is at even distance then
dp[i] += (number of 2 till 1) x dp[i-1]

Because the pattern is as follows:

1: 1 3 5 . . . (x-2) x (x-1) . . . 4 2

2: 1 3 5 . . . (x-2) x (x+1) (x-1) . . . 4 2

The ball goes up to position x and from there it can either go back by one position or go further by one position before making back jumps of 2 to reach at position 2(i.e the dog which scores the goal).

So, we have no constraint required for position 2(the last dog that makes the goal).

And, similarly for position x, from where we want to make only 1 step jump either to front or back.

For all other positions we make jumps of 2.

Sequence moving from right at last step and ending at pth position means sequence whose last move is from the right side of pth to pth position.

Now, consider the following positions,

…(p-1),p,(p+1),…

To come back at p from the right of p, we would require a sequence going past p(over p) and then turning back.

For sequence going past p(over p), it is required that we jump over p from (p-1) i.e go past p while keeping p unvisted and then turning back to p at later time.

So to jump from (p-1) over p to (p+1),(p-1) must have the skill of 2 to jump.

Hi,
@taran_1407
For the first case i.e from left side,
why are we considering DP[p-3]?
Since p-3 -> p-1 -> p-2 leads to p but haven’t we considered this scenario in DP[p-2] itself? Isn’t this over counting?

1 Like

No dp(p-2) doesn’t count those ways,dp(p-2) means only the ways to reach ‘p-2’ from left side of the array, not right :slight_smile:

1 Like

ohh got it. Thanks a lot.