Talent show fake solve?

Problems and Contests
#1

For this problem, I just ran the most basic knapsack with the weights as weights and talent for values, then for each weight >= W in the knapsack compared the ratios of dp[weight] * 1000 / weight and took the largest ratio. My code passed all 10 test cases but the intended solution with binary search + dp seems much more complicated.

Link: http://www.usaco.org/index.php?page=viewproblem2&cpid=839
Code: https://pastebin.com/EBvTcx0f

#2

Share code? How do you do knapsack on weights when the sum of the weights is huge?

#3

Oh, I misread the bounds; I thought each weight only went up to 1000.

Code: https://pastebin.com/EBvTcx0f

#4

Looks like the weights in the test data are pretty small for the most part …

#5

The sum of the weights does exceed what I put for MXW in test cases 4-10 but apparently none of the answers require the sum of weights being higher than MXW.

#6

Orz hi benq, here’s my understanding of the question.

If you knapsack and use talent as one of the dp states (instead of weight), then you still get AC, but scdivad doesn’t know if this is the intended solution.

#7

My solution would not have worked if the test data was stricter, so it was not the intended solution.

#8

Yeah, this solution was not supposed to work. Counter cases can be easily generated, but the test data was weak.

#9

I did the same thing and here is why i think it works. If a weight is more then required, and it’s ratio is the best one out of all other weight greater, it is best to just take that weight. Otherwise, we can use the dp to figure out the best answer with weights less then the required.

#10

Well, it doesn’t work. But we can actually solve this problem in \mathcal{O}(nW) time.

  • If we don’t choose any cow with weight \ge W, then we can find an optimal solution with sum of weights <2W in \mathcal{O}(nW) time.
  • Otherwise, we use binary search + greedy in \mathcal{O}(n\log t) time.
#11

oh ok I see. I guess this is why my solution passed.

#12

I also have a solution to the problem without binary search:

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

// O(nlogn + nw) solution:
// sort the cows with decreasing order of the ratio t / w and then do dp

int main()
{
    ifstream cin("talent.in");
    ofstream cout("talent.out");
    int n, w; cin >> n >> w;
    auto greater = [&] (const pair<int, int> &p, const pair<int, int> &q)
    {
        return (ll) p.first * q.second > (ll) q.first * p.second;
    };
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> v[i].second >> v[i].first;
    }
    sort(v.begin(), v.end(), greater);
    pair<int, int> ans = {0, 1};
    auto upd = [&] (pair<int, int> p) // updates answer with new candidate p
    {
        if(greater(p, ans))
        {
            ans = p;
        }
    };
    vector<int> dp(w, -1); // dp[i] is the largest sum of t for a group with i sum of w
    dp[0] = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = w - 1; j >= 0; --j) // loop down so that no cow will be included twice
        {
            if(dp[j] == -1)
                continue;
            if(j + v[i].second >= w) // we can safely update the answer because of the manner we sorted the cows
                                     // in other words adding more cows to the current group will never increase the ratio
                upd(make_pair(dp[j] + v[i].first, j + v[i].second));
            else
                dp[j + v[i].second] = max(dp[j + v[i].second], dp[j] + v[i].first);
        }
    }
    cout << (ll) ((long double) ans.first * 1000 / ans.second);
    return 0;
}