C++ Bitset algorithm

user_14042260 0
Viewed 143

I am given a nxn grid with filled with 1 or 0. I want to count the number of subgrids where the corner tiles are all 1s. My solution goes through all pairs of rows and counts the number of matching 1s then it uses the formula numOf1s * (numOf1s-1)/2 and adds to the result. However, when I submit my solution on https://cses.fi/problemset/task/2137, there is no output on inputs with n = 3000 (probably caused by some error). What could the error be?

int main()
    {
    
        int n; cin>> n;
        vector<bitset<3000>> grid(n);
        for(int i=0;i<n;i++){
            cin >> grid[i];
        }
        long result = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                int count = (grid[i]&grid[j]).count();
                result += (count*(count-1))/2;
            }
        }
        cout << result;
    }
algorithm c++
2 Answers

This solution will cause a time limit exceeded. bitset::count() is O(n) in worst case. The total complexity of your code is O(n^3). In the worst-case the number of operations would be 3000^3 > 10^10 which is too large.

user_87046120

I'm not sure this solution is the best you can come up with, but it is based on the original solution, with a homebrew alternative for the bitset. This allows me to work with 64 bits blocks, and using a fast popcnt(). An hardware version would be even better, as it would be to work with AVX registers, but this should be more portable and it works on cses.fi. Basically instead of generating a long intersection bitset and later count the number of ones, the function count_common() makes a piece of the intersection and immediately uses it just to count the ones.

The stream extractor could be probably improved, saving some more time.

#include <iostream>
#include <array>
#include <cstdint>
#include <climits>
 
uint64_t popcnt(uint64_t v) {
    v = v - ((v >> 1) & (uint64_t)~(uint64_t)0 / 3);
    v = (v & (uint64_t)~(uint64_t)0 / 15 * 3) + ((v >> 2) & (uint64_t)~(uint64_t)0 / 15 * 3);
    v = (v + (v >> 4)) & (uint64_t)~(uint64_t)0 / 255 * 15;
    uint64_t c = (uint64_t)(v * ((uint64_t)~(uint64_t)0 / 255)) >> (sizeof(uint64_t) - 1) * CHAR_BIT;
    return c;
}
 
struct line {
    uint64_t cells_[47] = { 0 }; // 3000/64 = 47
 
    uint64_t& operator[](int pos) { return cells_[pos]; }
    const uint64_t& operator[](int pos) const { return cells_[pos]; }
};
 
uint64_t count_common(const line& a, const line& b) {
    uint64_t u = 0;
    for (int i = 0; i < 47; ++i) {
        u += popcnt(a[i] & b[i]);
    }
    return u;
}
 
std::istream& operator>>(std::istream& is, line& ln) {
    is >> std::ws;
    int pos = 0;
    uint64_t val = 0;
    while (true) {
        char ch = is.get();
        if (is && ch == '\n') {
            break;
        }
        if (ch == '1') {
            val |= 1LL << (63 - pos % 64);
        }
        if ((pos + 1) % 64 == 0) {
            ln[pos / 64] = val;
            val = 0;
        }
        ++pos;
    }
    if (pos % 64 != 0) {
        ln[pos / 64] = val;
    }
    return is;
}
 
struct grid {
    int n_;
    std::array<line, 3000> data_;
 
    line& operator[](int r) {
        return data_[r];
    }
};
 
std::istream& operator>>(std::istream& is, grid& g) {
    is >> g.n_;
    for (int r = 0; r < g.n_; ++r) {
        is >> g[r];
    }
    return is;
}
 
int main()
{
    grid g;
    std::cin >> g;
 
    uint64_t count = 0;
    for (int r1 = 0; r1 < g.n_; ++r1) {
        for (int r2 = r1 + 1; r2 < g.n_; ++r2) {
            uint64_t n = count_common(g[r1], g[r2]);
            count += n * (n - 1) / 2;
        }
    }
    std::cout << count << '\n';
    return 0;
}
user_60703410
Related