Problem statement: Problem link "One day Jibon started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1st string and generated subsequent strings from it by replacing all the b's with ab and all the a's with b. For example, if he ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the N'th string has length X and M'th string has length Y. He wondered what will be length of the K'th string."
I observed that the i'th string length, L[i] = L[i-1] + L[i-2]. So, summery is, Given L[n] = x, and L[m] = y, find L[k] = ?, where L[i] = L[i-1] + L[i-2]. If it is impossible, then print "Impossible".
Since, n and m is not always consecutive, how to find L[k]?
You already observed L[i] = L[i-1] + L[i-2]. But, to solve the problem, we need to get into a little more depth on how we can come to that conclusion.
Suppose, number of 'a' in 1st string is x and number of 'b' in i-th string is y. Total length is x + y.
What is the number of 'a' in 2nd string? y. Number of 'b'? x + y. Total length is x + 2y.
What is the number of 'a' in 3rd string? x + y. What is the number of 'b'? x + 2y. Total length is 2x + 3y.
What is the number of 'a' in 4th string? x + 2y. Number of 'b'? 2x + 3y. Total length is 3x + 5y.
See any pattern? Focus on the total length only, since the input is given in total length.
1 — x + y (total length in 1st string)
2 — x + 2y (total length in 2nd string)
3 — 2x + 3y (total length in 3rd string)
4 — 3x + 5y
5 — 5x + 8y
6 — 8x + 13y
.
.
See the recurrence? Yes, the same as what you already observed. L[i] = L[i-1] + L[i-2].
If total length of i-th string is denoted as f(i), we can say f(n) = f(n-1) + f(n-2).
Now, you are given f(n) and f(m) in input, you have to find f(k). So how do we do that?
Suppose, you are given f(4) and f(6).
So, f(4) = 3x + 5y f(6) = 8x + 13y
Can't you find values of x and y from these 2 equations?
Now, how do you find the co-efficients of x and y for a given n and f(n)?
Notice a pattern here, in f(4), 3 is the 4th Fibonacci number if you assume Fibonacci series is 1 1 2 3 5 8... Again, in f(4), 5 is the 5th number in a series that is 1 1 2 3 5 8...
So, in f(n), co-efficient of x is the n-th number and co-efficient of y is the (n+1)-th number in the series: 1 1 2 3 5 8....
I believe you now have all the tools needed to solve this problem, good luck :)
When should I print impossible?
To understand that, you need to delve in this part more.
f(4) = 3x + 5y. f(6) = 8x + 13y.
You have these 2 equations. Now how will you find x and y?
Playing around with the equations, you should end up in,
x = ( f(4)*13 — 5*f(6) ) / (3*13 — 8*5)
What if (3*13 — 8*5) was 0? You would be dividing by zero. Could you find the value of x then? No. Thus, impossible.
Thanks a lot. Got Accepted !!
Beside the denominator be zero, when the calculated value of x and y is less than 0 and the nominator is not divisible by denominator — also in these case we need to print Impossible.