Problem link
I will describe my thoughts : Let’s say you are at the nth position and you want to find if there exists some choice of indices such that (sum of all a[i]) = (sum of all b[i]) * k for some k. So define F(index, A, B) = true if there exists such choice of indices i <= index such that A = sum of all a[i] and B = sum of b[i] is possible to achieve. Recurrence is fairly simple :
F(index, A, B) = F(index - 1, A, B) | F(index - 1, A - a[i], B - b[i])
The idea is our k will given in the input. And sum of all a[i] and b[i] <= 100*100. So we call F(n, A, B) only for values where A = B * k. And if there exists such choices such that A = sum of those a[i] and B = sum of those b[i], can be achieved then A is a candidate for the maximum answer.
And for the recurrence, at the nth index you have 2 choices, take the nth item or don’t.
But the problem is I will need a dp[100][10000][10000]. Either my approach is completely off the track or it’s possible to improve it. But I don’t understand what the editorial says and also others solutions are not understandable to me. So if anybody can take the trouble to explain your solution, it will be much appreciated.
1 Like
tl;dr: you can improve the DP approach.
You have the constraint that \dfrac{\sum{a_i}}{\sum{b_i}} = k. Let’s play with that a bit, which you’ve actually done already. Take the equation \sum{a_i} = k \cdot \sum{b_i}, and just move k into the sum: \sum{a_i} = \sum{k \cdot b_i}. The issue is we still care about a_i and k \cdot b_i separately, so let’s combine them, now we want: \sum{a_i - k \cdot b_i} = 0. Because of the input constraints, -999 \leq a_i - k \cdot b_i \leq 99, so there are 1099 possible values for each input value, and thus 109900 total sums of values you can have.
Let f(pos, val) be the maximum possible total taste at position pos where \sum{a_i - k \cdot b_i} = val. You already have the recurrence - either you take the element at pos or you don’t. The last issue is handling negative indices. You can do this without adding an extra log or constant factor by noticing that the minimum possible value you could ever have is above C = -10^5. So, just always access dp[pos][val - C] and your indices will stay positive, like normal. The answer is then f(n - 1, 0) (0-indexed) because the balance has to be 0. The dp has O(1) transitions and less than 10990000 possible states, so it’ll pass easily.
(This is also the approach that the editorial describes, by the way)
edit: Sorry, initially totally wrong on the number of states you could have
1 Like
Ah, thanks a lot. That is an excellent explanation.