Can somebody explain how to solve CHEF AND SOCCER(CHEFSOC) of march long challenge without recursion in python What algorithmic approach is required? asked 13 Mar, 17:28

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 i1 or i2 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 i1 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 i1 or i2 B) You jump from i1 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 i1 and/or i2 and two, i3 > i1 > i2 > i. Thus if both arr[i3] and arr[i2] are 2 then you also have to add f(i3) to f(i) for B, you need to figure out how much further to the right you can go before making a UTurn to end the sequence at i. Maybe, draw some sequence to figure this out. answered 13 Mar, 18:05

Use DP . Keep track of contagious segment of 2. answered 13 Mar, 17:38

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:
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)). answered 13 Mar, 20:36

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 n1, 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. 1) skill(n1) = 1, skill(n) =1 or 2 and the skill of the node to be added that is skill(n+1) = 1 2) skill(n1) = 1, skill(n) =1 or 2 and the skill of the node to be added that is skill(n+1) = 2 3) skill(n1) = 2, skill(n) =1 or 2 and the skill of the node to be added that is skill(n+1) = 1 4) skill(n1) = 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 (n2). If any variable names are not clear, I will describe them
link
This answer is marked "community wiki".
answered 13 Mar, 20:59

@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. answered 15 Mar, 03:12
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. :)
(15 Mar, 14:44)
