Why am I getting a WA? (KNPSK)

general
, , , , , , ,
1

After reading the editorial for Knapsack Problem (KNPSK) I coded the following solution:-

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

int main()
{
    int n;
    cin >> n;

    vector <int> w1, w2;

    int w, c;
    for(int i=0; i<n; i++)
    {
        cin >> w;
        if(w == 1)
        {
            cin >> c;
            w1.push_back(c);
        }
        else
        {
            cin >> c;
            w2.push_back(c);
        }
    }

    sort(w1.begin(), w1.end());
    sort(w2.begin(), w2.end());

    vector <int> W1 = w1, W2 = w2;

    int M = 2*w2.size() + w1.size();

    int max_cost[M+1];

    int cur = 0;
    for(w=2; w<=M; w+=2)
    {
        int cost1 = 0, cost2 = 0;
        if(w1.size() >= 1)
        {
            cost1 = w1.back();
        }
        int t = 1;
        if(w1.size() >= 2)
        {
            cost1 = w1.back();
            cost1 += w1[w1.size()-2];
            t = 2;
        }
        if(w2.size() >= 1)
        {
            cost2 = w2.back();
        }
        if(cost1 > cost2)
        {
            cur += cost1;
            if(t == 1)
            {
                w1.pop_back();
            }
            else
            {
                w1.pop_back();
                w1.pop_back();
            }
        }
        else
        {
            cur += cost2;
            w2.pop_back();
        }
        max_cost[w] = cur;
    }

    max_cost[1] = W1.back();
    W1.pop_back();

    cur = max_cost[1];
    for(w=3; w<=M; w+=2)
    {
        int cost1 = 0, cost2 = 0;
        if(W1.size() >= 1)
        {
            cost1 = W1.back();
        }
        int t = 1;
        if(W1.size() >= 2)
        {
            cost1 = W1.back();
            cost1 += W1[W1.size()-2];
            t = 2;
        }
        if(W2.size() >= 1)
        {
            cost2 = W2.back();
        }
        if(cost1 > cost2)
        {
            cur += cost1;
            if(t == 1)
            {
                W1.pop_back();
            }
            else
            {
                W1.pop_back();
                W1.pop_back();
            }
        }
        else
        {
            cur += cost2;
            W2.pop_back();
        }
        max_cost[w] = cur;
    }

    for(int i=1; i<M+1; i++)
        cout << max_cost[i] << " ";

    return 0;
}

The above code gives the correct output for the sample test case provided with the problem but gives WA straightaway on submission? I am unable to figure out the fault in the program logic? On which test cases does the above program fail? Can anyone please help me out so that I get an AC?

2

@ssjgz Can you please help me out?

3

It is most likely an overflow. Cost can be 10^9 and n can be 10^5, so the max weight can be 10^14, which will overflow.

1 Like
4

@everule1 I tried using long for max_cost and cur but that gives “Runtime error (SIGSEGV)”?
How can I resolve this issue?

5

@ssjgz How do I solve the issue, using long gives Runtime error and not using it gives WA?

6

Have you considered all objects of weight 2?

7

What do you mean? Can you provide any test case for which the program fails? I can’t figure out the fault? As for the objects of weight 2 I simply selected the ones with the maximum cost as suggested in the editorial.

8 
5
2 1
2 2
2 3
2 4
2 5
1 Like
9

I see that my program doesn’t output anything for the above test case. Why is this happening?

10

This line has no check to ensure that there is an object of weight 1.

1 Like
11

Thank you @everule1 for correcting the problem. I finally got an AC.

1 Like