[Hackerearth] OrOasis

 

Problem Link    : OrOasis 
Category        : Binary Search, Xor
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
// #define int     long long int
#define endl    '\n'
 
const int BITS = 31;
 
void solve() {
    int n;
    cin >> n;
    vector<int> nums(n);
    int total = 0;
    vector<vector<int>> cumBits(n, vector<int>(BITS));
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        total |= nums[i];
        for (int b = BITS - 1; b >= 0; b--) {
            bool val = (nums[i] >> b & 1);
            cumBits[i][b] = val;
            if (i - 1 >= 0) {
                cumBits[i][b] += cumBits[i - 1][b];
            }
        }
    }
    function<int(int, int)> GetOr = [&](int l, int r) {
        if (r >= n or l > r) {
            return 0;
        }
        int orsum = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int cnt = cumBits[r][b];
            if (l - 1 >= 0) {
                cnt -= cumBits[l - 1][b];
            }
            if (cnt) {
                orsum |= (1LL << b);
            }
        }
        return orsum;
    };
    int minlen = INT_MAX;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int lo = i;
        int hi = n - 1;
        int id = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            int x = GetOr(i, mid);
            if (x == total) {
                id = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        if (id != -1) {
            int x = GetOr(i, id);
            int y = GetOr(0, i - 1) | GetOr(id + 1, n - 1);
            if (x ^ y) {
                continue;
            }
            int len = id - i + 1;
            if (len < minlen) {
                minlen = len;
                ans = 1;
            } else if (minlen == len) {
                ans++;
            }
        }
    }
    if (minlen >= n) {
        cout << -1 << endl;
    } else {
        cout << minlen << " " << ans << endl;
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
}

[Hackerearth] Tile Permutation Paradox

Problem Link    : Tile Permutation Paradox
Category        : DP
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
template <const int32_t MOD> struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
const int mod = 1e9 + 7;
using mint = modint<mod>;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n, x;
        cin >> n >> x;
        mint ans = 0;
        {
            vector<mint> dp(n + 1);
            vector<int> table(n + 1);
            function<mint(int)> Solve = [&](int r) {
                if (r > n) {
                    return mint(1);
                }
                mint &ret = dp[r];
                int &tab = table[r];
                if (tab) {
                    return ret;
                }
                tab = 1;
                ret = Solve(r + 1);
                if (r + x - 1 <= n) {
                    ret += Solve(r + x);
                }
                return ret;
            };
            ans += Solve(1);
        }
        {
            vector<vector<mint>> dp(n + 1, vector<mint>(2));
            vector<vector<int>> table(n + 1, vector<int>(2));
            function<mint(int, int)> Solve = [&](int r, int flag) {
                if (r > n) {
                    return mint(1);
                }
                mint &ret = dp[r][flag];
                int &tab = table[r][flag];
                if (tab) {
                    return ret;
                }
                tab = 1;
                ret = 0;
                if (flag == 0) {
                    ret += Solve(r + 1, flag);
                }
                if (r + x - 1 <= n) {
                    ret += Solve(r + x, 1);
                }
                return ret;
            };
            ans -= Solve(1, 0);
 
        }
        cout << ans << endl;
    }
}

[Hackerearth] Prime Query

 

Problem Link    : Prime Query
Category        : Math
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n;
        cin >> n;
        vector<int> arr(n + 1);
        vector<vector<int>> cumsum(n + 1, vector<int>(2));
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            for (int j = 0; j < 2; j++) {
                cumsum[i][j] = cumsum[i - 1][j] + (arr[i] == j);
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int l, r;
            cin >> l >> r;
            int zeros = cumsum[r][0] - cumsum[l - 1][0];
            int ones = cumsum[r][1] - cumsum[l - 1][1];
            int len = r - l + 1;
            int ans = len * (len - 1) / 2 - (zeros * ones);
            ans -= zeros * (zeros - 1) / 2;
            cout << ans << endl;
        }
    }