[Hackerearth] Prefix queries

Algorithm: Persistent Trie

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 3e5 + 5;
const int maxbit = 62;
const int MAXNODES = 2e7;
 
// https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/practice-problems/algorithm/prefix-queries-3-2c111491/
struct Node {
    int st, lchild, rchild;
    Node(int st = 0, int lchild = 0, int rchild = 0)
        : st(st), lchild(lchild), rchild(rchild) {}
};
 
int NODES;
Node Tree[MAXNODES];
int version[maxn];
 
int update(int root, int pos, int val, int add) {
    int newNode = ++NODES;
    Tree[newNode] = Tree[root];
    if (pos < 0) {
        Tree[newNode].st += add;
        return newNode;
    }
    bool bit = val >> pos & 1LL;
    if (bit == 0) {
        Tree[newNode].lchild = update(Tree[newNode].lchild, pos - 1, val, add);
    } else {
        Tree[newNode].rchild = update(Tree[newNode].rchild, pos - 1, val, add);
    }
    Tree[newNode].st = Tree[ Tree[newNode].lchild ].st + Tree[ Tree[newNode].rchild ].st;
    return newNode;
}
 
int getMaxPrefix(int root, int pos, int val) {
    if (pos < 0) {
        return 0;
    }
    bool bit = val >> pos & 1LL;
    if (bit == 0 and Tree[ Tree[root].lchild ].st > 0) {
        return 1 + getMaxPrefix(Tree[root].lchild, pos - 1, val);
    } else if (bit == 1 and Tree[ Tree[root].rchild ].st > 0) {
        return 1 + getMaxPrefix(Tree[root].rchild, pos - 1, val);
    }
    return 0;
}
 
int n;
int q;
vector<int> arr;
vector<vector<int>> graph;
vector<vector<pair<int, int>>> queries;
vector<vector<int>> level;
vector<int> par;
vector<int> ans;
 
void dfs(int u = 1, int p = 0, int lvl = 0) {
    version[1] = update(version[1], maxbit - 1, arr[u], 1);
    for (auto it : queries[u]) {
        ans[it.second] = getMaxPrefix(version[1], maxbit - 1, it.first);
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    version[1] = update(version[1], maxbit - 1, arr[u], -1);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    while (tc--) {
        cin >> n;
        arr.clear(); arr.resize(n + 1);
        NODES = 0;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        graph.clear(); graph.resize(n + 1);
        for (int e = 1; e < n; e++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        cin >> q;
        queries.clear(); queries.resize(n + 1);
        for (int i = 0; i < q; i++) {
            int v, x;
            cin >> v >> x;
            queries[x].push_back({v, i});
        }
        ans.resize(q);
        dfs();
        for (int x : ans) {
            cout << x << ' ';
        }
        cout << endl;
 
        for (int i = 0; i <= NODES; i++) {
            Tree[i] = Node();
        }
    }
} 

  

Reduce the Array [DSA Coding Contest - March 23]

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
struct Trie {
    int counter;
    Trie *child[2];
 
    Trie() {
        counter = 0;
        for (int i = 0; i < 2; i++) {
            child[i] = nullptr;
        }
    }
    ~Trie() {
        for (int i = 0; i < 2; i++) {
            if (child[i] and this != child[i]) {
                delete child[i];
            }
        }
    }
};
 
typedef Trie* pnode;
pnode root;
 
void add(int num, int val) {
    pnode curRoot = root;
    for (int i = 30; i >= 0; i--) {
        bool bit = (bool)(num >> i & 1LL);
        if (curRoot->child[bit] == nullptr) {
            curRoot->child[bit] = new Trie();
        }
        curRoot = curRoot->child[bit];
        curRoot->counter += val;
    }
}
 
int get(int num) {
    pnode curRoot = root;
    int otherNum = 0;
    for (int i = 30; i >= 0; i--) {
        bool bit = bool(num >> i & 1);
        if (curRoot->child[bit] and curRoot->child[bit]->counter > 0) {
            otherNum += bit * (1LL << i);
            curRoot = curRoot->child[bit];
        } else if (curRoot->child[bit ^ 1] and curRoot->child[bit ^ 1]->counter > 0) {
            otherNum += (bit ^ 1) * (1LL << i);
            curRoot = curRoot->child[bit ^ 1];
        } else {
            assert(false);
        }
    }
    return num + otherNum + (num | otherNum) - (num & otherNum);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int &x : nums) {
        cin >> x;
    }
    sort(nums.begin(), nums.end());
    root = new Trie();
    for (int x : nums) {
        add(x, 1);
    }
    int ans = 0;
    for (int i = n - 1; i > 0; i--) {
        add(nums[i], -1);
        int cost = get(nums[i]);
        ans |= cost;
    }
    cout << ans << endl;
}
 

[LeetCode] 317. Shortest Distance from All Buildings

 

Problem: 317. Shortest Distance from All Buildings
Category: Graph Theory
Algorithm: BFS
Company: DoorDash, Google, Facebook, Microsoft, Oracle etc.

class Solution {
private:
    int bfs(vector<vector<int>> &grid, int sx, int sy, int houses) {
        const int dr[] = {+0, +1, +0, -1};
        const int dc[] = {+1, +0, -1, +0};
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dist(n, vector<int>(m, 0));
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        queue<pair<int, int>> pq;
        pq.push(make_pair(sx, sy));
        vis[sx][sy] = true;
        int sum = 0;
        while (pq.size() and houses > 0) {
            pair<int, int> cur = pq.front(); pq.pop();
            for (int d = 0; d < 4; d++) {
                int x = cur.first + dr[d];
                int y = cur.second + dc[d];
                if (x >= 0 and x < n and y >= 0 and y < m and grid[x][y] != 2 and vis[x][y] == false) {
                    dist[x][y] = dist[cur.first][cur.second] + 1;
                    vis[x][y] = true;
                    if (grid[x][y] == 0) {
                        pq.push(make_pair(x, y));
                    } else {
                        sum += dist[x][y];
                        --houses;
                    }
                }
            }
        }
        if (houses > 0) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 0 and vis[i][j]) {
                        grid[i][j] = 2;
                    }
                }
            }
            return INT_MAX;
        }
        return sum;
    }
 
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int houses = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ++houses;
                }
            }
        }
        int mini = INT_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    int cost = bfs(grid, i, j, houses);
                    mini = min(mini, cost);
                }
            }
        }
        return mini == INT_MAX ? -1 : mini;
    }
};

[LeetCode] 2300. Successful Pairs of Spells and Potions

Problem: 2300. Successful Pairs of Spells and Potions
Category: Add Hoc
Algorithm: Sorting

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int tspells = spells.size();
        vector<pair<int, int>> arr;
        for (int i = 0; i < tspells; i++) {
            arr.push_back({spells[i], i});
        }
        sort(arr.begin(), arr.end());
        vector<int> ans(tspells);
        sort(potions.begin(), potions.end());
        int cnt = 0;
        for (auto it : arr) {
            while (potions.size() and 1LL * potions.back() * it.first >= success) {
                potions.pop_back();
                cnt++;
            }
            ans[it.second] = cnt;
        }
        return ans;
    } 

};