Author: Raj Sahu
Editorialist: Bhashkarjya Nath
DIFFICULTY:
MEDIUM
PREREQUISITES:
Dynamic Programming
Divide and Conquer Optimization in DP
PROBLEM:
Anand and Tushar own a multinational company and from this year they are planning to hire Interns for the role of software development. They both are smart and want to hire interns based on their skills only so they came up with a plan.
They called all the N interns and asked them to stand in a line and numbered them from 1 to N. Moreover there is an Intelligence value associated with each Intern. Due to the COVID-19 pandemic, they have only K managers to assign for this intern program. To avoid any kind of partiality they decided to Divide N interns into K consecutive disjoint non-empty groups, so that any intern belongs to exactly one group.
Also, there is an amount of Peer Pressure associated with each Intern x which is equal to the sum of the Intelligence value of interns in front of x ( in the same group ) whose Intelligence value is greater than the Intelligence value of x. And, total peer Pressure of a group is the sum of peer pressure of all the interns in that group. Anand and Tushar want to make groups such that the peer pressure among the Interns in the groups should be as minimum as possible.
#SUBTASK DIVISION:
Basic Recursion (for 20 points)
Dynamic Programming (for 50 points)
Dynamic Programming with Divide and Conquer Optimization (for 100 points)
EXPLANATION:
First things first: Precomputations are to be done in order to calculate the peer pressure of each sub-array (from
index i to j where i<=j ) within constant time.
#define long long int ll
const ll maxn = 5001;
ll more[maxn][maxn];
ll cost(ll i, ll j) {
//Returning sum of sub-matrix from [i, i] to [j, j] i.e. total peer pressure of sub-array (i, j)
return more[j][j] - more[i - 1][j] - more[j][i - 1] + more[i - 1][i - 1];
}
memset(more, 0, sizeof(more));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (a[j] > a[i]) {
more[i][j] = a[j];
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
more[i][j] = more[i - 1][j] + more[i][j - 1] - more[i - 1][j - 1] + more[i][j];
}
}
Here we declare a 2d array of max size n*n and initialize it with 0.
Initially more[i][j]=0 if a[j]<=a[i]
Otherwise, more[i][j]=a[j];
Now we take 2d prefix sum of array ‘more’. After this computation more[i][j] will represent prefix sum of 2d submatrix from (1, 1) to (i, j)
After all these precomputations we obtain the peer pressure of sub-array a[i, j] in constant time.
Subtask-1:
The implementation for the first subtask is quite clear. ‘Brute force’ approach, by enumerating all possible partitions
and finding the optimal one.
Time Complexity: Exponential.
Subtask-2
By observation, we find that there are overlapping sub-problems. Therefore, we can memorize the states by using
top-down dynamic programming approach.
Time Complexity: There are total n*k possible states, and to calculate for each state it takes O(n) time. Hence, the
total time complexity is n2
k.
ll rec(vl &a, ll low, ll high, ll k) {
if (k == 1) {
return cost(low, high);
} else if (low > high) return 1e14; // big number
else if (dp[low][k] != -1)return dp[low][k];
else {
ll ans = inf;
for (ll i = low; i <= high; i++) {
ans = min(ans, cost(low, i) + rec(a, i + 1, high, k - 1));
}
return dp[low][k] = ans;
}
}
Subtask-3
Here comes the real thrill,
Please go through this link to know about ‘Divide and Conquer Optimization on DP’.
For further reference read this amazing blog,
https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
SOLUTIONS:
Setter's Solution
arclhm - Online C++0x Compiler & Debugging Tool - Ideone.com