×

# KCC04 - EDITORIAL

 0 DIFFICULTY: EASY PREREQUISITES: Dynamic Programming , Fibonacci Series PROBLEM: We have to find number of ways in which an N day plan for gym can be executed given that we can not go to the gym on more than one consecutive days. Quick Explanation: We can clearly observe the pattern to be a Fibonacci series and using DP we can compute the N day plan from 1 <= N <= 10^8. Explanation: The plan can be shown as : 0 : Did not went to the gym on a day 1 : Went to gym on a day Plan[i] : Number of ways of going to gym on i th day Plan[1] = 2 (He goes on first day or he does not go on that day as 0 or 1) Plan[2] = 3 (He can go by 3 ways as 00,10,01) Plan[3] = 5 and so on... hence on clear observation we can see that : Plan[i] = Plan[i-1] + Plan[i-2]; We can compute the Plan array earlier by DP with a complexity of O(10^8) for 1<=N<=10^8 Pseudo Code : Plan[1]=2; Plan[2]=3; for i in range 3 to N: Plan[i] = Plan[i-1] + Plan[i-2]; Now we can give the answer to each query in O(1) time hence total complexity for T queries can be O(T). Result = Plan[N] for N day plan. Time Complexity : O(T+10^8) where T<=60000 hence it can be O(10^8)  Editorialist's Solution: Can be found here. This question is marked "community wiki". asked 18 Mar '18, 19:01 4★abhi55 42●6 accept rate: 5% 0★admin ♦♦ 19.8k●350●498●541
 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:

×3,820
×303
×13
×3

question asked: 18 Mar '18, 19:01

question was seen: 121 times

last updated: 21 Mar '18, 15:31