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.
@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?
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 
ohh got it. Thanks a lot.
Can u please tell me what the actually patterns are?