FICE - Editorial

editorial
, , , , ,
#1

Problem Links

Practice

Contest

Author: Ankur Goel

Tester: Ankur Goel

Editorialist: Ankur Goel

Difficulty

Medium

Prerequisites

Fibonacci Series, Recursion

Problem

The King wants to select N common folks as solider from the Fire and Ice island in order to win the battle. He can only select odd number of people from land of fire or ice only in one go.He cannot select bunch of people consecutively from either territory.Find the number of ways the mad king could select his army.

Note :The number of people in each territory is infinite.

Quick Explanation

Ans= 2*Fibo(N)%M

Explanation

The Problem is simply based on the Fibonacci Series. Let 0 denotes the people from Land of Ice and 1 denotes the people from Land of Fire then, the number of binary strings of length n without an even number of consecutive 0s or 1s is 2Fn. For example, out of the 16 binary strings of length 4, there are 2F4 = 6 without an even number of consecutive 0s or 1s – they are 0001, 0111, 0101, 1000, 1010, 1110.

Find the Fibonacci using O(Log N) Algorithm and take the modulo M at every step, otherwise your algo may fail due to Time Complexity or due to the Overflow of Fibonacci Number beyond the range of even 64 bit int.

Author's Solution

Author’s solution can be found here

Related Problems

Ankur and Coins

2 Likes
#2

He cannot select bunch of people consecutively from either territory. Then how is 0111 allowed (111 is a consecutive bunch).

#3

@vir_mis he has selcted 0 from fire and then 3 from ice. 0111 is just a representation.

#4

Let’s write a recurrence for the answer. Let T0(n) be the number of valid strings ending in 0, and T1(n) be the number of valid strings ending in 1. Since n >= 1, the answer is T0(n) + T1(n).

We can find some base cases.

T0(1) = 1, since there is one string of length one that ends with 0, i.e., 0
T0(2) = 1, since there is one string of length two that ends with 0, i.e., 10
Now consider T0(n) for n >= 3. Given a string of length n that ends in 0, there are two cases, of which exactly one applies. The first case is that the string ends in 10, in which case dropping the 0 gives a valid string of length n - 1 ending in 1. The second case is that the string ends in 000, in which case dropping the 00 gives a valid string of length n - 2 ending in 0.

T0(n) = T0(n - 2) + T1(n - 1)
We observe by the symmetry of problem that T0(n) = T1(n).

T0(n) = T0(n - 2) + T0(n - 1)
This is the Fibonacci recurrence. The answer is T0(n) + T1(n) = 2 Fib(n).

6 Likes
#5

Hi, I am trying to find a recursive solution without making use of the Fibonacci numbers.

We pass the number to the recursive function and select every odd number less than the number itself in the first layer of recursion then we make recursive calls to the number - the selected number then again repeat the process and eventually when the number left is equal to zero we increment a global counter by 1. Its kinda hard to explain… just look at my code. The problem is that I am getting TLE help me reduce recursion calls by using memoization or other means.

link to my code - https://gist.github.com/ksraj123/4aea2f088bdaeba95d7914d144556394

Sorry for replying on an old thread. I hope to receive your valuable input.

#6

use memoization by creating an array dp[n] and initialise it with -1.
in base condition write -
if(dp[n]!=-1) return dp[n];
/* remaining code*/
return dp[n]=ans;

#7

Hi, i am getting tle for subtask 2 and 3 even if i am using matrix exponentation for calculating nth term of fibonacci series

my code - https://www.codechef.com/viewsolution/29307944

can somebody help me why i am getting TLE.

#8

Even if we use memoization I think the no. of possibilities for each ‘N’ will exceed the range of any datatype(for numbers as large as N=1000), which is why we need to return the answer by doing modulo with some number ‘M’. Also there’s something wrong in your code because you must’ve misunderstood the question. On line 12 you are taking care that we won’t choose all members from same kingdom when ‘N’ is odd,but we can even also choose all members from same kingdom when ‘N’ is odd.

#9

It means select one from Land of Ice which is denoted by 0 and three from Land of Fire which is denoted by 1.