×

# CHEFSOC-March Challenge

 0 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 1 accept rate: 0%

 2 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. My Submission answered 13 Mar, 18:05 70●6 accept rate: 0%
 0 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- https://www.codechef.com/viewsolution/23451543 answered 13 Mar, 17:38 5★viplaw 1●1 accept rate: 0%
 0 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)). answered 13 Mar, 20:36 4★apazala 1●1 accept rate: 0%
 0 @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 16●4●5●11 accept rate: 0% 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×75
×14