Tester: D Teja Vardhan Reddy
Given the size of an array and two integers with their index where they are already filled.Find the number of way to fill the remaining array with following conditions:
The numbers filled should be in range [L,R] (both inclusive).
consecutive positions should have different numbers.
Let i and j are the indexes and X and Y are the corresponding integers which are already filled.
Now, The problem can be divided into 3 sub-problems. First is from index 1 to i, second is from i to j, and third is from j to n (size of array).
Now, it can be solved using dynamic programming. Let’s say we have to solve for index i to j. Index i contain X and index j contain Y. So, first we find the number of way to fill index i+1 with Y ( such that it is not equal to number in index i) , then we find the total number of ways to fill index i+2 with Y and so on till we reach index j. So the number of ways to fill up to index j with Y is its answer. But, if you observe, this series forms geometric progression which can be solved in O(logn) time.
Similarly, we find for index 1 to i, and for index j to n. Then, multiply all these three to get final answer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.