You are not logged in. Please login at www.codechef.com to post your questions!

×

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

View Content

Tester's solution

View Content

Editorialist's solution

View Content

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 13 Mar, 18:03

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 15 Mar, 14:13


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 ith 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 this values for i+1 and i+2 and i+3, we can compute it for i;

Relation

All possible combinations:
type 1 = (i)--GOAL.
there is only one combination of type 1 , (i)th dog make a goal itself;
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).
NXT[i] (started from i and ended at i+1 using indices>=i) = 1; as (i)->(i+1)--goal is a member of type 2.
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 :)

link

answered 14 Mar, 09:27

shashi_trent's gravatar image

4★shashi_trent
442
accept rate: 0%

edited 15 Mar, 08:07

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.

link

answered 14 Mar, 17:47

vincode's gravatar image

4★vincode
102
accept rate: 0%

edited 14 Mar, 17:48

Yes....... (dots for minimum 10 characters)

(15 Mar, 06:28) taran_14076★

@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].

link

answered 15 Mar, 02:11

sparky007's gravatar image

3★sparky007
164511
accept rate: 0%

edited 15 Mar, 02:17

That was a typo. Corrected now. Thanks!

(15 Mar, 06:30) taran_14076★

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 ?

link

answered 15 Mar, 02:30

im_amartya's gravatar image

4★im_amartya
32
accept rate: 0%

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

(15 Mar, 14:40) aparichit_vyav4★

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 ?

(15 Mar, 14:51) im_amartya4★

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]

(15 Mar, 16:39) aparichit_vyav4★

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&lt;=t;test++)" {="" scanf("%d",&n);="" for="" (i="1;i&lt;=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--)
link

answered 15 Mar, 12:15

paoner141880's gravatar image

4★paoner141880
1
accept rate: 0%

@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?

link

answered 15 Mar, 13:19

chaudharyv101's gravatar image

4★chaudharyv101
313
accept rate: 0%

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

(15 Mar, 14:14) taran_14076★

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.

link

answered 15 Mar, 15:28

bhargav9427's gravatar image

4★bhargav9427
1
accept rate: 0%

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.

(15 Mar, 19:52) adzo2614★

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?

link

answered 15 Mar, 22:03

shobhit907's gravatar image

4★shobhit907
1
accept rate: 0%

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.

(15 Mar, 22:18) adzo2614★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,212
×1,722
×724
×75
×62
×7

question asked: 13 Mar, 18:03

question was seen: 2,051 times

last updated: 15 Mar, 22:21