CORNER SUBGRID COUNT CSES : PRAGMA TARGET(POPCNT) V/S PRAGMA O3 OPTIMIZATION

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	145
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	135
7	YuukiS	135
9	chromate00	134
10	soullless	132

I was stuck on this CSES question : Corner Subgrid Count for nearly 2 months, when I had already got the approach at the first view only. (It's not that I have been trying daily since the last 2 months, I got TLE and I left... bruhh — )

And I just figured out that I was not using the correct compile-time optimization (bruh-, what the hell was that). I was trying with Ofast and O3 optimizations but just do popcnt optimization and you are done. My approach (as obvious) was just break each row into bits of size 64, do pairwise-AND and tally the number of bits set in the pairwise-ANDs. Finally, add (count*(count — 1))/2 to the ans.

But I am amazed to see that how powerful a tool pragma actually is and how it can make your life easy :

TLE-ed Code

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
 
#define int long long int
#define ull unsigned long long
 
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
constexpr int V = 1E9;
constexpr int MAXN=1e9;
const int mod=998244353;
 
void solve() 
{
    int n;
    cin >> n ;
    vector<string> v(n);
    for(int i=0; i<n; i++) cin>>v[i];
    int m = v[0].size();
    int B = (m + 63) / 64; 
    vector<vector<unsigned long long>> vals(n, vector<unsigned long long>(B, 0ULL));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (v[i][j] == '1') {
                int b = j >> 6;          // j / 64
                int off = j & 63;        // j % 64
                vals[i][b] |= (1ULL << off);
            }
        }
    }
    // for(auto x: vals)
    // {
    //     for(auto y : x) cout<<y<<" ";
    //     cout<<endl;
    // }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        const ull *Ai = vals[i].data();
        for (int j = i + 1; j < n; ++j) {
            const ull *Aj = vals[j].data();
            int cnt = 0;
            for (int z = 0; z < B; ++z) {
                cnt += __builtin_popcountll(Ai[z] & Aj[z]);
            }
            if (cnt >= 2) ans += 1LL * cnt * (cnt - 1) / 2;
        }
    }
    cout<<ans<<endl;
}
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //auto begin = std::chrono::high_resolution_clock::now();
    //freopen("piggyback.in", "r", stdin);
    //freopen("piggyback.out", "w", stdout);
    int t=1;
    //cin >> t;
    
    while (t--) 
    {
        solve();
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

Accepted Code

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target("popcnt")
 
#define int long long int
#define ull unsigned long long
 
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
 
constexpr int V = 1E9;
constexpr int MAXN=1e9;
const int mod=998244353;
 
void solve() 
{
    int n;
    cin >> n ;
    vector<string> v(n);
    for(int i=0; i<n; i++) cin>>v[i];
    int m = v[0].size();
    int B = (m + 63) / 64; 
    vector<vector<unsigned long long>> vals(n, vector<unsigned long long>(B, 0ULL));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (v[i][j] == '1') {
                int b = j >> 6;          // j / 64
                int off = j & 63;        // j % 64
                vals[i][b] |= (1ULL << off);
            }
        }
    }
    // for(auto x: vals)
    // {
    //     for(auto y : x) cout<<y<<" ";
    //     cout<<endl;
    // }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        const ull *Ai = vals[i].data();
        for (int j = i + 1; j < n; ++j) {
            const ull *Aj = vals[j].data();
            int cnt = 0;
            for (int z = 0; z < B; ++z) {
                cnt += __builtin_popcountll(Ai[z] & Aj[z]);
            }
            if (cnt >= 2) ans += 1LL * cnt * (cnt - 1) / 2;
        }
    }
    cout<<ans<<endl;
}
 
int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //auto begin = std::chrono::high_resolution_clock::now();
    //freopen("piggyback.in", "r", stdin);
    //freopen("piggyback.out", "w", stdout);
    int t=1;
    //cin >> t;
    
    while (t--) 
    {
        solve();
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

If any of you got it Accepted without Pragma, I would love to hear that too

Comments (3)

Write comment?

anaconda666

8 months ago, hide # |

Auto comment: topic has been updated by anaconda666 (previous revision, new revision, compare).

→ Reply

TorMuzZ

7 weeks ago, hide # |

← Rev. 2 →

wrong problem, sorry

yoshi_likes_e5

Would writing a function to wrap popcnt work? There're a few other approaches to do popcnt without this instruction, but popcnt is a trivial 1-cycle operation so these weren't as fast.

anaconda666's blog