Can somebody explain how to solve CHEF AND SOCCER(CHEFSOC) of march long challenge without recursion in python
What algorithmic approach is required?
Use DP . Keep track of contagious segment of 2.
For a dog number of ways to score a goal=number of ways it can get ball from behind+number of ways it can get ball from front. And number of ways it can get ball from front depends mainly upon contagious segment of two’s. Just think on these lines you will get the solution.
For further clarification u can however have a look at my solution-
Let f(i) be the number of ways where the sequence ends at position i, then
Ans = \sum_{i=1}^{N}{f[i]}
To reach i either you go from i-1 or i-2 to i OR from i+1 or i+2 to i.
Important thing to notice is you can not jump an index twice.
To jump i, you have to be on index i-1 from which you got i+1, once to the right of i you cannot go to any position left to i.
Thus f(i) consists of only two types of way
A) You reach from its left side, that is from i-1 or i-2
B) You jump from i-1 to i+1 and then possible go further to right and then return back to end at i.
A further consists of 2 ways. One, you reach i from i-1 and/or i-2 and two, i-3 -> i-1 -> i-2 -> i.
Thus if both arr[i-3] and arr[i-2] are 2 then you also have to add f(i-3) to f(i)
for B, you need to figure out how much further to the right you can go before making a U-Turn to end the sequence at i. Maybe, draw some sequence to figure this out.
2 Likes
I first coded a bruteforce (DFS) approach and printed all paths from dog 0 to i (results[i]), searching for a pattern.
I found one, but it’s nos a clean simple formula. I’ll explain the basics and I hope that my (admittedly messy) code does the rest.
First, this is my C code.
So results[i] depends on 3 values:
-
A cumulative factor (lastfactor in the code), where lastfator(i) is a function only of the previous dogs (0,…i-1). More precisely, the previous run lengths of ones or twos.
-
Two values of the Tribonacci sequence, Tribonacci[j] and Tribonacci[j+1]; where j is the relative position in its run of twos (this value is much simpler in the run of ones). Being Tribonacci[0] = 0, Tribonacci[1] = 1, Tribonacci[2] = 1 and Tribonacci[i] = Tribonacci[i-1] + Tribonacci[i-2] + Tribonacci[i-3];
-
A correction based on the next run length of ones or twos, resp. This is the most complicated value having several different cases depending on the parity of the next length, special cases for lengths one and two; and for the next-to-last run.
I can give details on each of those values on request if the code is not clear enough.
One last comment. Despite I settled for this fast enough solution, there is room for a potentially substantial improvement: you don’t actually need to compute each result[i] individually; with some precomputations, you could get the sum of results[i] for the entire run of consecutives ones or twos in just 2 operations: lastfact(i)*(precomputedTribonacciSum(i) + precomputedTribonacciCorrection(i)).
like it said in the other answers u have to keep track of two players
Express the problem as a graph made it easier to visualize for me.
start with player 1 and 2, try to calculate paths increased when third player is added
assume you have calculated solution upto point n(for pints 1,2,3…n), now draw the points n-1, n and n+1 and try out all combinations(8 combinations,But as you will notice that the skill of n does not affect the result. Thus the total number of distinct cases will be 4)
You can draw a directed graph to visualize the new paths which are formed when n+1 is added.
-
skill(n-1) = 1, skill(n) =1 or 2
and the skill of the node to be added that is skill(n+1) = 1 -
skill(n-1) = 1, skill(n) =1 or 2
and the skill of the node to be added that is skill(n+1) = 2 -
skill(n-1) = 2, skill(n) =1 or 2
and the skill of the node to be added that is skill(n+1) = 1 -
skill(n-1) = 2, skill(n) =1 or 2
and the skill of the node to be added that is skill(n+1) = 2
The first case is the easiest, the only new paths will be those ending in n+1, since n+1 cant pass the ball to anybody else. Thus the number of additional paths is e(n) (ie number of paths ending in n)
the second and third cases are similar, but you also need to keep track of the paths going through the edges.
The last case requires you to go back 1 more node, that is node (n-2).
If any variable names are not clear, I will describe them
@aparichit_vyav
i saw your code.
just one question why calculate separately for odd and even when calculating from right to left.
both are doing the same thing.
This was the kind of answer I wanted.Thanks.
I didn’t think it through. Just coded whatever first came to my mind. After seeing the editorial I realized half of my code is redundant. 