CSES :: Range Queries :: Static Range Sum Queries

Problem : Please find the problem here.

Explanation : Save array into a tree where array elements are at the leaves. And each node will represent the sum of the elements of its childrens.

Code : Used segment tree.

#include <bits/stdc++.h>

#define ll long long

using namespace std;

void construct(vector<ll> &tree, vector<ll> &arr, int start, int end, int node) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }

    int mid = (start+end) >> 1;
    int leftNode = node << 1;
    int rightNode = leftNode + 1;
    construct(tree, arr, start, mid, leftNode);
    construct(tree, arr, mid+1, end, rightNode);

    tree[node] = tree[leftNode] + tree[rightNode];
}

ll query(vector<ll> &tree, vector<ll> &arr, int start, int end, int l, int r, int node) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];

    int mid = (start+end) >> 1;
    int leftNode = node << 1;
    int rightNode = leftNode + 1;

    ll leftResult = query(tree, arr, start, mid, l, r, leftNode);
    ll rightResult = query(tree, arr, mid + 1, end, l, r, rightNode);

    return leftResult + rightResult;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q, l, r;
    cin >> n >> q;

    vector<ll>  arr(n), tree(4*n), lazy(4*n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    construct(tree, arr, 0, n-1, 1);

    while (q--) {
        cin >> l >> r;
        cout << query(tree, arr, 0, n-1, l-1, r-1, 1) << '\n';
    }
}

CSES :: Graph Problems :: Labyrinth

Problem : Please find the problem here.

Explanation : Given the starting and end point in the graph, simple graph search can be used to find the shortest path between these points. To backtrack the path, save parent of each node as the direction from where node is traveresd.

Code : Used BFS to find shortest path between two given points in graph.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e3, di[4] = {1, 0, -1, 0}, dj[4] = {0, 1, 0, -1};
const char dn[4] = {'D', 'R', 'U', 'L'};
int n, m, si, sj, ei, ej, d[mxN][mxN];
string adj[mxN], p[mxN];

bool isValid(int i, int j) {
    return i>=0 && i < n && j >= 0 && j < m && adj[i][j] != '#';
}

void BFS(int si, int sj) {
   queue<array<int, 2>> qu;
   qu.push({si, sj});
   adj[si][sj] = '#';

   while (qu.size()) {
        array<int, 2> u = qu.front();
        qu.pop();
        for (int k = 0; k < 4; k++) {
            int vi = u[0]+di[k], vj = u[1]+dj[k];
            if (isValid(vi, vj)) {
                qu.push({vi, vj});
                p[vi][vj] = dn[k];
                d[vi][vj] = k;
                adj[vi][vj] = '#';
            }
        }
   }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> adj[i][j];
            if (adj[i][j] == 'A') {
                si = i, sj = j;
            } else if (adj[i][j] == 'B') {
                ei = i, ej = j;
            }
        }
    }

    BFS(si, sj);

    if (p[ei][ej] != 'B') {
        cout << "YES\n";

       // backtrack the path.
       string path = "";
       while(ei^si || ej^sj) {
            path += p[ei][ej];
            int dd = d[ei][ej]^2;
            ei += di[dd];
            ej += dj[dd];
       }

       reverse(path.begin(), path.end());
       cout << path.size() << '\n';
       cout << path << '\n';

    } else {
        cout << "NO\n";
    }

    return 0;
}

CSES :: Sorting and Searching :: Distinct Numbers

Problem : Please find the problem here.

Explanation : Sort the array and count the number of distinct entries by iterating and checking if the current element of the arrray is equal to immediate previous element.

Code : 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    int arr[n];

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr, arr+n);

    int  uniqueCount = 0, prev = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] != prev) {
            uniqueCount++;
        }
        prev = arr[i];
    }

    cout << uniqueCount;
    return 0;
}

CSES :: Dynamic Programming :: Dice Combinations

Problem : Please find the problem here.

Explanation : The number of ways to get a certain value is dependent on the outcomes of previous die throws.

Code : Iterating over values from 1 to n and for each value And accumulating the ways to reach the current value by summing all the possibilities based on the outcomes of previous throws.

Time Complexity : O(n).

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e6;
const int mod = 1e9+7;

void calculateDiceCombinations(int n, vector<int>& dp) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, 6); j++) {
            dp[i] = (dp[i] + dp[i-j]) % mod ;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n; cin >> n;
    vector<int> dp(mxN, 0);

    dp[0] = 1;
    calculateDiceCombinations(n, dp);

    cout << dp[n] << '\n';

    return 0;
}

CSES :: Tree Algorithms :: Subordinates

Problem : Please find the problem here.

Explanation : Company's employee hierarchy can be intutively mapped as tree structure and for each employee, the subordinate count is the sum of subordinates count of all their direct subordinates.

Code : Used DFS to traverse the tree starting from the node 0. This calculates the subordinates for each employee by summing counts recursively.

Time Complexity : O(N), where n is the number of nodes in the tree.

#include <bits/stdc++.h>

using namespace std;

void DFS(int node, int parent, vector<int> &subordinates, vector<vector<int>> &adj) {
    subordinates[node] = 1;

    for (int next : adj[node]) {
        DFS(next, node, subordinates, adj);
        subordinates[node] += subordinates[next];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> subordinates(n);

    // relation data for employee 1 to n; 0th is boss.
    for (int i = 1; i < n; i++) {
        cin >> x; x--;
        adj[x].emplace_back(i);
    }

    DFS(0, -1, subordinates, adj);

    for (int c : subordinates) {
        cout << c-1 << ' ';
    }
    return 0;
}