Help in MAXAND18

Problem: MAXAND18.
I got 50 points for this problem. I’m very surprised because I got WA in the first subtask (k \leq 2) but AC in the second subtask (k \leq 30). How is this possible?

Here is my code. Please give me a testcase for which my program fails (or let me know the issue).

#include <bits/stdc++.h>

using namespace std;

bool sortbysec(const pair<long long, long long> &a, const pair<long long, long long> &b) {return (a.second < b.second);}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vector <int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        vector <pair<long long, long long>> bits(30, {0, 0});
        for (int i = 0; i < 30; ++i)
        {
            long long bs = 0;
            for (int j = 0; j < n; ++j) if (a[j] & (1LL << i)) bs += (1LL << i);
            bits[i].first = bs, bits[i].second = i;
        }
        sort(bits.rbegin(), bits.rend());
        int prev = -1;
        vector <pair <long long, long long>> temp(0), res(0);
        for (int i = 0; i < 30; ++i)
        {
            if (prev == -1)
            {
                prev = bits[i].first;
                temp.push_back(bits[i]);
            } else {
                if (bits[i].first == prev) temp.push_back(bits[i]);
                else {
                    prev = -1;
                    sort(temp.begin(), temp.end(), sortbysec);
                    for (int i = 0; i < temp.size(); ++i) res.push_back(temp[i]);
                    temp.clear();
                    --i;
                }
            }
            if (i == 29)
            {
                sort(temp.begin(), temp.end(), sortbysec);
                for (int i = 0; i < temp.size(); ++i) res.push_back(temp[i]);
                temp.clear();
                prev = -1;
            }
        }
        long long ans = 0;
        for (int i = 0; i < k; ++i) ans += (1LL << res[i].second);
        cout << ans << '\n';
    }
}

First I find out the contribution of each bit for all numbers. I store that sum along with the bit in a pair. I sort the vector of pairs so that I can get the maximum sum in the beginning. What if multiple sums are equal? I choose the one having the smallest bit (smallest x is to be chosen among all x for which S is maximum). I sort the vectors with the same sum accordingly. I just append that vector to the resultant vector. I iterate over the first k elements of the vector adding 2^{\text{number of bit}} each time.
Please help me fix this issue.

1 Like

Why is this if(i==29) case?

The loop will terminate at i = 29 since it’s less than 30. What I mean is if we reach the last element, we create a temp array because there are no elements after it due to which the last set of elements would’ve been wasted.

It is most probably because of integer overflow. Use long long int for storing the intial array. C++ implicitly converts long long int to int if you assign an integer to a long long int variable.

1 Like

Thanks a lot!!! It was not the vector though. I replaced all ints with long long and then it worked. Should I create a macro for long long and use it over int in the future?

Defining a macro is helpful but I think you shouldn’t use long long all the time , but whenever you feel any value can get close to 10^9 you should switch to long long.

1 Like

Thanks for all the help!!!

1 Like

Ohh. So this is the question you were talking about. I had the same trouble. I did (1 << 31) and it messed up with the 2’s complement bit.

Anyhow using #define int long long is definitely not recommended. I read in a codeforces blog that using long long everywhere can cause TLE. (very rare, but it can).

1 Like

#pragma GCC optimize “trapv”
You can use this to check for integer overflow… but this increases the running time , that is why I only use it to test my code locally.

2 Likes

That happened to me once. I was very surprised.
long long (TLE)
int (AC)

1 Like

Thanks, I’ll check it out.