Help in MAXAND18

help
, ,
1

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?

Screenshot (17)
Screenshot (17)985×352 9.93 KB

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
2

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

3

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.

4

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.

2 Likes
5

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?

6

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
7

Thanks for all the help!!!

1 Like
8

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
9

#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
10

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

1 Like
11

Thanks, I’ll check it out.