In this article we are going to look at a dynamic programming problem called magical cows which was featured in the Mount Allison Programming Showdown (MAPS 2020). It is a type of problem one is likely to encounter in a technical phone interview or on-site interview, and both the approach and solution to the problem are quite intuitive and worth knowing. You can practice this problem on kattis with marked difficulty as medium.
About the problem:
A farmer has several farms with magic cows. Every midnight the amount of cows in each farm doubles, but there’s a condition that he can only have C cows at the most on any given farm. Whenever the amount of cows exceeds C, the farmer should move half the cows to a replacement farm altogether.
So we are to seek out the amount of farms needed on a selected day with the given number of cows on each farm with a minimum of one cow on day zero.
Here C ( 1 <= C <= 1000 ) is the utmost number of cows per farm, N ( 1 <= N <= 1000 ) is the number of initial farms, and M ( 1 <= M <= 50 ) is the number of queries.
Example 1:
Input: C = 2, N = 5, M = 3
cows =[1,2,1,2,1]
queries =[0,1,2]
Output: [5,7,14]
Explanation:
Approach:
The key observation from the above example is that instead of keeping track of all cows on every farm we are able to keep track of the frequency of farms with a specific number of cows. Storing the precise number of cows in every farm would end in exponential storage growth.
The approach for dynamic programming is to keep track of the frequency of farms with a particular number of cows within the dp table, where rows represent days and columns represent the frequency of farms with a certain number of cows.
Example:
Input: C = 8, N = 4
cows = [1,3,2,1]
We first fill in the number of cows we have at day zero, as given in the input. The idea is that for a particular farm, you double the number of cows. If the number of cows on each farm goes over the allowed capacity then we double the number of farms with that capacity.
For day 1:
As we first had two farms with one cow, now we have two farms with two cows. Increment it and do the same for the rest of the farms and repeat the operations on the upcoming days. The final result will look like below:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int MAX_DAYS = 50;
const int MAX_COWS = 1000;
int dp[MAX_DAYS][MAX_COWS];
int n, c, m, q;
int query(int day) {
int farms = 0;
for (int i = 0; i < n; i++)
farms += dp[day][i];
return farms;
}
int main() {
cin >> n >> c >> m;
vector < int > cows(n), queries(m);
for (int y = 0; y < n; y++) cin >> cows[y];
for (auto co: cows) dp[0][co]++;
for (int day = 0; day < MAX_DAYS; day++)
for (int x = 1; x <= c; x++)
if (x <= c / 2)
dp[day + 1][x * 2] += dp[day][x];
else
dp[day + 1][x] += 2 * dp[day][x];
for (int i = 0; i < m; i++) {
cin >> q;
cout << query(q) << endl;
}
}
Input:
5 2 3
1 2 1 2 1
0 1 2
Output:
5
7
14
Time complexity: O(n2), we are using nested loops; one for days and the other for the frequency of cows.
Space complexity: O(n2), for declaring a two-dimensional matrix.