Setter: Soham Chakrabarti
Tester: Sunita Sen
Editorialist: Soham Chakrabarti
DIFFICULTY
Easy - Medium
PREREQUISITES
Dynamic Programming
PROBLEM
Given an array of integers of size N and you have to partition the array into exactly K parts. For every single partition - calculate the Greatest Common Divisor.
Sum up all the G.C.D Values and maximize the sum.
EXPLANATION
The best score can only be achieved by formulating for all possible states and using a cache to store the data processed already.
We will be using recursion for this case and memorize the data on the way.
states to remember
Let's consider the states of our memorizing table to be :
1. index i of the element in the original array.
2. K-th partition which the element has been placed.
Therefore, we can clearly have a look at our 2d state.
Now, we progress, with the recursive formula.
We start our recursion with the first element and loop through the elements of the array. While we loop, we also calculate the G.C.D till the i-th element.
For every element we get while looping, we recurse down to a step further, by placing it in a partition Below is the snippet to do so :
snippet to recurse
for(int j = i; j < size_of_array ; ++j) {
gcdTillith = gcd (gcdTillith, array[i]);
int res = recurse(j + 1, k - 1) // calculate for the next index and reduce k as we add a partition
}
What about the base cases ?
There could be two cases down here :
base case 1
When our index reaches the $N$, the size of the array, it means this is the
last state, we have reached the end. In this state, if our $k$ is greater than 0,
it means we have to still partition the data, but we cannot and thus we can
return a large value, since it will get neglected while formulate the maximum
score in our previously called function.
However if, we reach end and out k is also equal to 0, it means, we have
successfully partitioned the array and now we will have to consider the
state. So we can return a 0 for this case. The zero signifies add up the
previous state values and get a result.
base case 2
If we are not at the end of our array, but still we reach a value of K = 0, we
will have to return a large value again.
Why ? think a bit!
TIME COMPLEXITY
The Time complexity will be O(K.N^2)
SOLUTIONS
Setter's Solution
Feel free to share your approach. Suggestions are welcomed as always. 