Miners
DP Formulation The bonus at a mine depends only on its last two deliveries (plus the new one). Encode the state as (a_1, a_2, b_1, b_2) where a_1, a_2 are the last two deliveries to mine 1 and b_1, b_2 to mine 2. Each...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
$N$ food carts arrive sequentially, each carrying one of 3 food types (M, F, G). There are 2 mines. Each cart must be assigned to one mine. When a mine receives a cart, the bonus is the number of distinct food types among its last (up to) 3 deliveries. Maximize the total bonus.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
DP Formulation
The bonus at a mine depends only on its last two deliveries (plus the new one). Encode the state as $(a_1, a_2, b_1, b_2)$ where $a_1, a_2$ are the last two deliveries to mine 1 and $b_1, b_2$ to mine 2. Each coordinate takes values in $\{0,1,2,3\}$ (three food types plus a ``none'' sentinel for fewer than 2 past deliveries). This gives $4^4 = 256$ states.
Transition. For cart $i$ with food type $c$:
Send to mine 1: New state $(c, a_1, b_1, b_2)$. Bonus $= |\{c, a_1, a_2\} \setminus \{3\}|$.
Send to mine 2: New state $(a_1, a_2, c, b_1)$. Bonus $= |\{c, b_1, b_2\} \setminus \{3\}|$.
Complexity
Time: $O(256 \cdot 2 \cdot N) = O(N)$.
Space: $O(256) = O(1)$ (rolling two DP layers).
C++ Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
string s;
cin >> s;
auto encode = [](char c) -> int {
if(c == 'M') return 0;
if(c == 'F') return 1;
return 2;
};
// Pack state (a1, a2, b1, b2) into a single int
auto pack = [](int a1, int a2, int b1, int b2) -> int {
return a1 * 64 + a2 * 16 + b1 * 4 + b2;
};
// Count distinct food types among c, x, y (ignoring sentinel 3)
auto bonus = [](int c, int x, int y) -> int {
bool seen[3] = {};
seen[c] = true;
if(x < 3) seen[x] = true;
if(y < 3) seen[y] = true;
return seen[0] + seen[1] + seen[2];
};
vector<int> dp(256, -1);
dp[pack(3, 3, 3, 3)] = 0;
for(int i = 0; i < N; i++){
int c = encode(s[i]);
vector<int> ndp(256, -1);
for(int st = 0; st < 256; st++){
if(dp[st] == -1) continue;
int a1 = (st / 64) % 4, a2 = (st / 16) % 4;
int b1 = (st / 4) % 4, b2 = st % 4;
// Send to mine 1
int ns1 = pack(c, a1, b1, b2);
int val1 = dp[st] + bonus(c, a1, a2);
ndp[ns1] = max(ndp[ns1], val1);
// Send to mine 2
int ns2 = pack(a1, a2, c, b1);
int val2 = dp[st] + bonus(c, b1, b2);
ndp[ns2] = max(ndp[ns2], val2);
}
dp = ndp;
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
return 0;
}Notes
The problem is a clean DP exercise. The state space is $4^4=256$ because each mine needs only its two most recent deliveries (plus the sentinel for ``no delivery yet''). The bonus function counts distinct types in a window of size 3 (current delivery plus last 2). Since the state space is constant, the algorithm runs in $O(N)$ time.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
string s;
cin >> s;
// Encode food types: M=0, F=1, G=2, none=3
auto encode = [](char c) -> int {
if(c == 'M') return 0;
if(c == 'F') return 1;
return 2; // 'G'
};
// State: (a1, a2, b1, b2) where a1,a2 are last two for mine 1,
// b1,b2 for mine 2. Each in {0,1,2,3}.
// Pack into single int: a1*64 + a2*16 + b1*4 + b2
// Total: 4^4 = 256 states
auto pack = [](int a1, int a2, int b1, int b2) -> int {
return a1 * 64 + a2 * 16 + b1 * 4 + b2;
};
auto bonus = [](int c, int x, int y) -> int {
// Distinct types among c, x, y (ignoring 3 = none)
set<int> st;
st.insert(c);
if(x != 3) st.insert(x);
if(y != 3) st.insert(y);
return st.size();
};
vector<int> dp(256, -1);
dp[pack(3, 3, 3, 3)] = 0; // initial state: no deliveries
for(int i = 0; i < N; i++){
int c = encode(s[i]);
vector<int> ndp(256, -1);
for(int state = 0; state < 256; state++){
if(dp[state] == -1) continue;
int a1 = (state / 64) % 4;
int a2 = (state / 16) % 4;
int b1 = (state / 4) % 4;
int b2 = state % 4;
// Option 1: send cart to mine 1
int b1_val = bonus(c, a1, a2);
int ns1 = pack(c, a1, b1, b2);
ndp[ns1] = max(ndp[ns1], dp[state] + b1_val);
// Option 2: send cart to mine 2
int b2_val = bonus(c, b1, b2);
int ns2 = pack(a1, a2, c, b1);
ndp[ns2] = max(ndp[ns2], dp[state] + b2_val);
}
dp = ndp;
}
int ans = *max_element(dp.begin(), dp.end());
cout << ans << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.