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

×

KCC04 - EDITORIAL

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

abhi55's gravatar image

4★abhi55
426
accept rate: 5%

edited 21 Mar '18, 15:31

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×3,820
×303
×13
×3

question asked: 18 Mar '18, 19:01

question was seen: 121 times

last updated: 21 Mar '18, 15:31