# 2018 US Open Gold Talent Show: Unclear on why the DP will give the optimal value

Official solution: Contest Results

Click to view my question; don't want to spoil parts of the solution

I understand that we should binary search on y = floor(1000x) where x is the maximum possible ratio.
However, I’m unclear on the dp implementation:

``````for (int j = 0; j < n; j++) {
long long value = 1000*(long long)talent[j] - y*(long long)weights[j];
int inc = weights[j];
for (int k = w; k >= 0; k--) {
int k1 = min(w, k + inc);
if (dp[k] != -infinite) {
if (dp[k1] < dp[k] + value) {
dp[k1] = dp[k] + value;
}
}
}
}
``````

I’m going to try to explain it. First, we loop through each cow. For each cow, we start with the highest possible weight and go backwards to prevent us from using the same cow twice. We check if `dp[k]` is possible, and then update `dp[k1]` if it is optimal.

I think if the first loop was looping through the weights, then dp[w] would be -infinite because no cow can reach it yet.

Now, the part was unclear was if `dp[k]` can get updated to a more optimal value, will `dp[k1]` be updated? I tried coming up with an argument, but it seems a little complicated.

Thanks so much!

Hi. I’ve thought of this for a bit more and my question has changed.

click to view new question
``````for (int j = 0; j < n; j++) {
long long value = 1000*(long long)talent[j] - y*(long long)weights[j];
int inc = weights[j];
for (int k = w; k >= 0; k--) {
int k1 = min(w, k + inc);
if (dp[k] != -infinite) {
if (dp[k1] < dp[k] + value) {
dp[k1] = dp[k] + value;
}
}
}
}
``````

The situation I’m having trouble on is if `dp[k]` gets updated by another cow, will `dp[k1]` also be updated.

First, if k1 = W then we know that dp[W] will get updated for each cow.

Suppose the cow that updates `dp[k]` has weight w. Then, we know the value of `dp[k - w]` must be defined.

If dp[k - w] was defined before we visited the cow with weight k1 - k,
then dp[k - w + k1 - k] = dp[k1 - w] gets updated.

Otherwise, dp[k - w] gets defined after we visit the cow with weight k1 - k.
I know dp[k1 - k] is defined, but what if dp[k1 - k] was used to compute dp[k - w].
How can we guarantee dp[k1 - w] is defined in this situation?

Thanks for the help!

FWIW, my code’s here. It might be a bit more readable than the official solution’s.

I think your solution is more clear than the original, but I think my question still applies.

How can we guarantee dp[k1 - w] is defined in this situation?

I don’t see anywhere this is called in the code?

I wrote:

If `dp[k]` gets updated by another cow, will `dp[k1]` also be updated?

I let the cow that updates dp[k] have weight w. I know that dp[k - w] should exist as a result.

If we want to update dp[k1] (which should be updated by the cow with weight w), then dp[k1 - w] should exist. I know dp[k1 - k] should exist (this equals to `dp[inc]`) and dp[k - w] exists, but I don’t know if this is enough to prove that dp[k1 - w] should exist, because both values may have been updated by the same cow.

Ok so I spent 15 minutes trying to figure out an answer and I couldn’t come up with anything to help you (now I’m confused). I would argue that the official solution is way to complex and there is a much simpler and easier dp solution which runs in O(N(\max(maxCowWeight, W))) which is basically just just O(N*10^6) which runs in just over 1 second for c++ (might tle for java)

The gist of the logic is below:

``````int dp[(int)1e6+6];

for (int i = 0; i < n; i++) {
int a, b; cin >> a >> b;
for (int j = (int)1e6+5; j >=0; j--) {
if (dp[j]!=-1 && j+a<(int)1e6+6 && dp[j+a]<dp[j]+b) {
dp[j+a] = dp[j]+b;
}
}
}
int ans = 0;
for (int i= 0; i < (int)1e6+6; i++) {
if (i>=w) {
ans = max(ans, (dp[i]*1000)/i);
}
}
``````

Hi sorry for the late post.

I posted this question on Codeforces and decided to move the discussion there: 2018 US Open Gold Talent Show: Unclear on why the DP will always give the optimal value - Codeforces.

Thank you all for the help anyway! I really appreciate it!

Hi sorry for the late post.

After talking to another person, I understand that if `dp[k]` gets updated by a certain cow, then that same cow CANNOT be used to update `dp[k1]` . So, this means we do not have to worry about updating `dp[k1]` if `dp[k]` gets updated.

Thanks for the help everyone! I really appreciate it!