[Hackerearth] BanquetSplit

 

Problem Link    : BanquetSplit
Category        : Graph, Lowest Common Ancestor
Contest         : December Circuits'23  

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1e6 + 5;
const int logn = 21;
 
int n;
vector<vector<int>> graph;
int depth[maxn];
int father[maxn][logn];
 
void init(int n) {
    graph.clear(); graph.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        depth[i] = 0;
        memset(father[i], 0, sizeof father[i]);
    }
}
 
void dfs(int u, int p, int lvl) {
    depth[u] = lvl;
    father[u][0] = p;
    for (int i = 1; i < logn; i++) {
        father[u][i] = father[ father[u][i - 1] ][i - 1];
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u, lvl + 1);
    }
}
 
int findLca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (depth[ father[u][i] ] >= depth[v]) {
            u = father[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (father[u][i] != father[v][i]) {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}
 
void solve() {
    cin >> n;
    init(n);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1, 0, 1);
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        int lca = findLca(x, y);
        int dist = depth[x] + depth[y] - 2 * depth[lca];
        if (dist & 1) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
            cout << 1 << " " << dist + 1 << endl;
        }
    }
}
 
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;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
 
}

[Hackerearth] Equal Arrays

 

Problem Link    : Equal Arrays 
Category        : Math
Contest         : December Circuits'23 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
void solve() {
    int n, m;
    cin >> n >> m;
    deque<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    deque<int> brr(m);
    for (int i = 0; i < m; i++) {
        cin >> brr[i];
    }
    int ans = 0;
    while (arr.size() and brr.size()) {
        int sum1 = arr.front(); arr.pop_front();
        int sum2 = brr.front(); brr.pop_front();
        ans++;
        while (sum1 != sum2) {
            if (sum1 < sum2 and arr.size()) {
                sum1 += arr.front(); arr.pop_front();
            } else if (sum2 < sum1 and brr.size()) {
                sum2 += brr.front(); brr.pop_front();
            } else {
                break;
            }
        }
        if (sum1 ^ sum2) {
            cout << -1 << endl;
            return;
        }
    }
    if (arr.size() or brr.size()) {
        ans = -1;
    }
    cout << ans << endl;
}
 
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("C3.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
}

[Hackerearth] Bob and Indices

Problem Link    : Bob and Indices 
Category        : Adhoc
Contest         : December Circuits'23  

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
void input(vector<int> &nums) {
    for (int &num : nums) {
        cin >> num;
    }
}
 
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("B3.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n;
        cin >> n;
        vector<int> A(n), B(n), C(n);
        input(A);
        input(B);
        input(C);
        map<int, int> cache;
        for (int i = 0; i < n; i++) {
            cache[ B[ C[i] ] ]++;
        }
        int ans = 0;
        for (int x : A) {
            ans += cache[x];
        }
        cout << ans << endl;
    } 

} 

[Hackerearth] Find Pairs

Problem Link    : Find Pairs 
Category        : Math
Contest         : December Circuits'23        

#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 = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int n;
    cin >> n;
    map<int, int> cache;
    for (int i = 1; i <= n; i++) {
        int num;
        cin >> num;
        cache[num - i]++;
    }
    int ans = 0;
    for (auto it : cache) {
        ans += it.second * (it.second - 1);
    }
    cout << ans << endl; 

} 

Easiest HLD with Subtree Queries

 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1E5 + 5;
const int logn = 19;
 
int tnode;
int tquery;
vector<vector<int>> graph;
vector<vector<int>> Tree;
int arr[maxn];
int subtreeSize[maxn];
int depth[maxn];
int father[maxn][logn];
int nxt[maxn];
int in[maxn];
int out[maxn];
int tym;
 
void makeTree(int u = 1, int p = 0) {
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        Tree[u].push_back(v);
        makeTree(v, u);
    }
}
 
void dfsSize(int u = 1) {
    subtreeSize[u] = 1;
    for (int &v : Tree[u]) {
        dfsSize(v);
        subtreeSize[u] += subtreeSize[v];
        if (subtreeSize[v] > subtreeSize[ Tree[u][0] ]) {
            swap(v, Tree[u][0]);
        }
    }
}
 
void dfs(int u = 1, int lvl = 1) {
    depth[u] = lvl;
    for (int i = 1; i < logn; i++) {
        father[u][i] = father[ father[u][i - 1] ][i - 1];
    }
    for (int v : Tree[u]) {
        father[v][0] = u;
        dfs(v, lvl + 1);
    }
}
 
void hld(int u = 1) {
    in[u] = ++tym;
    for (int v : Tree[u]) {
        nxt[v] = v == Tree[u][0] ? nxt[u] : v;
        hld(v);
    }
    out[u] = tym;
}
 
int findLca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (depth[ father[u][i] ] >= depth[v]) {
            u = father[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = logn - 1; i >= 0; i--) {
        if (father[u][i] != father[v][i]) {
            u = father[u][i];
            v = father[v][i];
        }
    }
    return father[u][0];
}
 
#define lchild  node * 2
#define rchild  node * 2 + 1
#define mid     (a + b) / 2
 
int STree[maxn * 4];
 
void update(int node, int a, int b, int pos, int val) {
    if (a > b or a > pos or b < pos) {
        return;
    }
    if (a >= pos and b <= pos) {
        STree[node] = val;
        return;
    }
    update(lchild, a, mid, pos, val);
    update(rchild, mid + 1, b, pos, val);
    STree[node] = STree[lchild] ^ STree[rchild];
}
 
int query(int node, int a, int b, int i, int j) {
    if (a > b or a > j or b < i) {
        return 0;
    }
    if (a >= i and b <= j) {
        return STree[node];
    }
    int p = query(lchild, a, mid, i, j);
    int q = query(rchild, mid + 1, b, i, j);
    return p ^ q;
}
 
int queryUp(int u, int v) {
    // v = lca
    int xorsum = 0;
    int L = in[v];
    while (true) {
        int l = in[ nxt[u] ];
        int r = in[u];
        if (l <= L) {
            l = max(l, L);
            xorsum ^= query(1, 1, tnode, l, r);
            break;
        }
        xorsum ^= query(1, 1, tnode, l, r);
        u = father[ nxt[u] ][0];
    }
    return xorsum;
}
 
int queryHld(int u, int v) {
    int lca = findLca(u, v);
    int lft = queryUp(u, lca);
    int rgt = queryUp(v, lca);
    int middle = queryUp(lca, lca);
    return lft ^ rgt ^ middle;
}
 
void updateHld(int u, int val) {
    arr[u] = val;
    update(1, 1, tnode, in[u], val);
}
 
void init() {
    graph.clear(); graph.resize(maxn);
    Tree.clear(); Tree.resize(maxn);
    tym = 0;
    for (int i = 0; i < maxn; i++) {
        subtreeSize[i] = 0;
        in[i] = 0;
        out[i] = 0;
        nxt[i] = 0;
        memset(father, 0, sizeof father[i]);
        depth[i] = 0;
    }
    memset(STree, 0, sizeof STree);
}
 
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--) {
        init();
 
        cin >> tnode;
        for (int i = 1; i <= tnode; i++) {
            cin >> arr[i];
        }
        for (int e = 1; e < tnode; e++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        makeTree();
        dfsSize();
        dfs();
        nxt[1] = 1;
        hld();
 
        for (int i = 1; i <= tnode; i++) {
            updateHld(i, arr[i]);
        }
 
        cin >> tquery;
        while (tquery--) {
            int type;
            cin >> type;
            if (type == 1) {
                int u, val;
                cin >> u >> val;
                updateHld(u, val);
            } else {
                int u, v;
                cin >> u >> v;
                int xorsum = queryHld(u, v);
                cerr << xorsum << " ";
                cout << (xorsum ? "Alice" : "Bob") << endl;
            }
        }
    }
}