I was doing this problem: _____https://codeforces.net/problemset/problem/1862/F and my approach to solving was to binary search on the time required, and the predicate for the search would be whether the time is enough -- determined by a DP check as follows: given some time t, we have w*t water and f*t fire available, so we try to use as much of the water as possible, and then see if enough fire remains. I don't understand why the following implementation of this idea does not work and was hoping someone could help:↵
↵
~~~~↵
bool possible(vector<int>& s, int a, int b, int n, int t) {↵
// s1 = size of container 1 (how much water we have)↵
// s2 = size of container 2 (how much fire we have)↵
int s1 = t*a, s2 = t*b;↵
↵
// definition of dp[i][j][k]:↵
// first i elements↵
// using j of them↵
// using or not using kth one↵
// considering these i, j, k, what is the min space remaining in container 1?↵
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(2, 1e15)));↵
↵
for (int i = 0; i <= n; i++) dp[i][0][0] = s1;↵
↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= i; j++) {↵
dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]);↵
↵
for (int k = i-1; k >= j-1; k--) {↵
int op1 = ((dp[k][j-1][0] != 1e15 && dp[k][j-1][0] >= s[i-1]) ? dp[k][j-1][0] - s[i-1] : 1e15);↵
int op2 = ((dp[k][j-1][1] != 1e15 && dp[k][j-1][1] >= s[i-1]) ? dp[k][j-1][1] - s[i-1] : 1e15);↵
↵
dp[i][j][1] = min({dp[i][j][1], op1, op2});↵
}↵
}↵
}↵
↵
int mn = s1;↵
↵
// take the min space left in container 1 across all possibilities↵
for (int i = 0; i <= n; i++) {↵
mn = min({mn, dp[n][i][0], dp[n][i][1]});↵
}↵
↵
int sm = 0;↵
↵
for (auto i : s) sm += i;↵
↵
return (sm-(s1-mn) <= s2);↵
}↵
↵
void solve() {↵
int a, b, n;↵
cin >> a >> b >> n;↵
↵
vector<int> s(n);↵
↵
for (int i = 0; i < n; i++) cin >> s[i];↵
↵
int curr = 0;↵
↵
// binary searching on the time required ("curr")↵
for (int p = 30; p >= 0; p--) {↵
int pwp = (1ll<<p);↵
↵
while (curr+pwp <= 1e6 && !possible(s, a, b, n, curr+pwp)) curr += pwp;↵
}↵
↵
cout << curr+1 << endl;↵
}↵
↵
signed main() {↵
cin.tie(0)->sync_with_stdio(0);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~
↵
~~~~↵
bool possible(vector<int>& s, int a, int b, int n, int t) {↵
// s1 = size of container 1 (how much water we have)↵
// s2 = size of container 2 (how much fire we have)↵
int s1 = t*a, s2 = t*b;↵
↵
// definition of dp[i][j][k]:↵
// first i elements↵
// using j of them↵
// using or not using kth one↵
// considering these i, j, k, what is the min space remaining in container 1?↵
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(2, 1e15)));↵
↵
for (int i = 0; i <= n; i++) dp[i][0][0] = s1;↵
↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= i; j++) {↵
dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]);↵
↵
for (int k = i-1; k >= j-1; k--) {↵
int op1 = ((dp[k][j-1][0] != 1e15 && dp[k][j-1][0] >= s[i-1]) ? dp[k][j-1][0] - s[i-1] : 1e15);↵
int op2 = ((dp[k][j-1][1] != 1e15 && dp[k][j-1][1] >= s[i-1]) ? dp[k][j-1][1] - s[i-1] : 1e15);↵
↵
dp[i][j][1] = min({dp[i][j][1], op1, op2});↵
}↵
}↵
}↵
↵
int mn = s1;↵
↵
// take the min space left in container 1 across all possibilities↵
for (int i = 0; i <= n; i++) {↵
mn = min({mn, dp[n][i][0], dp[n][i][1]});↵
}↵
↵
int sm = 0;↵
↵
for (auto i : s) sm += i;↵
↵
return (sm-(s1-mn) <= s2);↵
}↵
↵
void solve() {↵
int a, b, n;↵
cin >> a >> b >> n;↵
↵
vector<int> s(n);↵
↵
for (int i = 0; i < n; i++) cin >> s[i];↵
↵
int curr = 0;↵
↵
// binary searching on the time required ("curr")↵
for (int p = 30; p >= 0; p--) {↵
int pwp = (1ll<<p);↵
↵
while (curr+pwp <= 1e6 && !possible(s, a, b, n, curr+pwp)) curr += pwp;↵
}↵
↵
cout << curr+1 << endl;↵
}↵
↵
signed main() {↵
cin.tie(0)->sync_with_stdio(0);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~
