CSES :: Graph Algorithms :: Round Trip

Problem : Please find the problem here.

Explanation : We need to find out the path in the graph where start and end node is the same (a cycle).
This can be easily checked with simple Graph Traveral, check if any of the node's children node, during traversal, is already visited by some other parent.

Code : Used DFS to check cycles in the graph and backtracking the path using the nodes parent array maintained over traversal.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

void DFS(int u, int pu, vector<int> (&adj)[mxN], vector<int> &visited, vector<int> &parent) {
    visited[u] = 1;
    parent[u] = pu;

    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, u, adj, visited, parent);
        } else {
            if (v == pu) {
                continue;
            }
            else {
                int u2 = u;
                vector<int> ans;
                while (u^v) {
                    ans.emplace_back(u);
                    u = parent[u];
                }

                ans.push_back(v);
                ans.push_back(u2);

                cout << ans.size() << '\n';
                for (auto a : ans) {
                    cout << a+1 << ' ';
                }
                exit(0);
            }

        }
    }
}

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

    int n, m;
    cin >> n >> m;

    vector<int> adj[mxN], visited(n, 0), parent(n, 0);


    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v; u--, v--;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i]) DFS(i, -1, adj, visited, parent);
    }

    cout << "IMPOSSIBLE";

    return 0;
}

CSES :: Dynamic Programming :: Removing Digits

Problem : Please find the problem here.

Explanation : Zero ways to get to 0, 1 way to get to 0 from any number 1-9...
Recursively find minimum number of ways a number can be reduce to zero, ignore the condition when one of the digit is zero (that will never reduce the number ).

Code : Used Dynamic Programming.

#include <bits/stdc++.h>

using namespace std;

vector<int> getDigits(int n) {
    vector<int> digits;
    while (n) {
        digits.emplace_back(n%10);
        n /= 10;
    }

    return digits;
}

int calculate(int n) {
    vector<int> DP(n+1, INT_MAX);
    DP[0] = 0;

    for (int i = 1; i <= n; i++) {
        auto digits = getDigits(i);
        for (int d : digits) {
            if (d != 0) {
              DP[i] = min(DP[i], 1 + DP[i-d]);
            }
        }
    }

    return DP[n];
}

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

    int n; cin >> n;

    cout <<calculate(n) << '\n';

    return 0;
}

CSES :: Dynamic Programming :: Grid Paths

Problem : Please find the problem here.

Explanation : Solve the subproblem of finding the number of ways we can get (1,1) from position (n, m) recursively. Ignore all paths leading to restricted blocks. Memoize the solution to ensure a substrcture not processed not more than once.

Code : Used Dynamic Programming.

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

const int mod = 1e9+7;

// DP : Iteration with Memo
int countGridPathIterDP(int n, int m, vector<string> &grid) {

    vector<vector<int>> DP(n, vector<int> (m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
           if (i == 0 && j == 0) {
               DP[i][j] = (grid[i][j] == '*'?0:1);
           }
           else {
               if (i == 0) {
                   DP[i][j] = (grid[i][j] == '*'?0:DP[i][j-1]);
               } else if (j == 0) {
                   DP[i][j] = (grid[i][j] == '*'?0:DP[i-1][j]);
               } else {
                   DP[i][j] = (grid[i][j] == '*'?0:(DP[i-1][j]%mod + DP[i][j-1]%mod)%mod);
               }
           }

        }
    }

    return DP[n-1][m-1];
}

// DP : Recursion with Memo

int countGridPathRecurDP(int n, int m, vector<string> &grid, vector<vector<int>> &DP) {

    if (DP[n][m] != -1)  return DP[n][m];

    if (n == 0 && m == 0 && grid[n][m] != '*') return 1;
     if ((n < 0 || m < 0) || grid[n][m] == '*') return 0;

    DP[n-1][m] = countGridPathRecurDP(n-1, m, grid, DP)%mod;
    DP[n][m-1] = countGridPathRecurDP(n, m-1, grid, DP)%mod;
    DP[n][m] = (DP[n-1][m] + DP[n][m-1])%mod;

    return DP[n][m];
}

int countGridPathRecurDP(int n, int m, vector<string> &grid) {
    vector<vector<int>> DP(n, vector<int> (m, -1));
    return countGridPathRecurDP(n, n, grid, DP);
}

// Plain Recursion
int countGridPathRecur(int n, int m, vector<string> &grid) {
    if (n == 0 && m == 0 && grid[n][m] != '*') return 1;
    if ((n < 0 || m < 0) || grid[n][m] == '*') return 0;

    return (countGridPathRecur(n-1, m, grid)%mod + countGridPathRecur(n, m-1, grid)%mod)%mod;
}

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

    int n; cin >> n;
    vector<string> grid(n+1);
    vector<vector<int>> DP(n+1, vector<int> (n+1, 0));

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    cout << countGridPathIterDP(n, n, grid);
    return 0;
}

CSES :: Dynamic Programming :: Minimizing Coins

Problem : Please find the problem here.

Explanation : Count number of ways a target sum can be acheived by selecting minimum of the given coins.

Code : Used Dynamic Programming.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e9;

int countMinCoins(int sum, vector<int> &coins, vector<int> &DP) {
    int n = coins.size();
    DP[0] = 0;
    for (int i = 1; i <= sum; i++) {
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i) {
                DP[i] = min(DP[i], DP[i - coins[j]] + 1);
            }
        }
    }

    return (DP[sum] == mxN?-1:DP[sum]);
}

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

    int n, x;
    cin >> n >> x;
    vector<int> coins(n), DP(x+1, mxN);

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

    cout << countMinCoins(x, coins, DP);
    return 0;
}

CSES :: Dynamic Programming :: Coin Combinations I

Problem : Please find the problem here.

Explanation : For a given target, recursively find the number of ways it can be get by choosing any of the given coins.

Code : Used dynamic programming.

#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 :: Graph Algorithms :: Building Roads

Problem : Please find the problem here.

Explanation : Given a graph structure, number of roads here is basically the minimum edges required to make this graph connected. This is intern equal to number of connected components in the graph.
Save any one node from each connected components and print the path in between those nodes.

Code : Used DFS to find connected components.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

void DFS(int u, map<int, set<int>> &adj, vector<bool> &vis) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v]) {
            DFS(v, adj, vis);
        }
    }
}

vector<int> countRoads(int n, map<int, set<int>> &adj, vector<bool> &vis) {
    vector<int> roads;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            DFS(i, adj, vis);
            roads.emplace_back(i);
        }
    }

    return roads;
}

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


    int n, m, a, b;
    cin >> n >> m;

    map<int, set<int>> adj;
    for (int i = 0; i < m; i++) {
        cin >> a >> b; a--, b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }

    vector<bool> vis(n, 0);
    vector<int> result = countRoads(n, adj, vis);

    cout << result.size()-1 << '\n';
    for (int i = 1; i < (int)result.size(); i++) {
        cout << result[0]+1 << ' ' << result[i]+1 << '\n';
    }
    return 0;
}

CSES :: Graph Algorithms :: Message Routes

Problem : Please find the problem here.

Explanation : Travese Graph with BFS to get shortest path between starting and end point And save the parent of each node in an array to backtrack the path between two given points.

Code : Used BFS to traverse the graph.

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5;

bool checkPath(int start, int end, map<int, set<int>> &adj, vector<int> &vis, vector<int> &p) {
    queue<int> qu;
    qu.push(start);
    vis[start] = 1;

    while (qu.size()) {
        int u = qu.front(); qu.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                p[v] = u;
                vis[v] = 1;
                qu.push(v);
            }
        }
    }

    return vis[end];
}

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

    int n, m, x, y;
    cin >> n >> m;

    int a = 0, b = n-1;
    map<int, set<int>> adj;
    vector<int> p(mxN), vis(mxN, 0);

    for (int i = 0; i < m; i++) {
        cin >> x >> y; x--, y--;
        adj[x].insert(y);
        adj[y].insert(x);
    }

    if (checkPath(0, n-1, adj, vis, p)) {
        vector<int> pathNodes;

        while (a != b) {
            pathNodes.emplace_back(b);
            b = p[b];
        }
        pathNodes.emplace_back(a);
        reverse(pathNodes.begin(), pathNodes.end());
        cout << pathNodes.size() << '\n';

        for (int x : pathNodes) {
            cout << x+1 << ' ';
        }
    }
    else {
        cout << "IMPOSSIBLE";
    }
    return 0;
}

CSES :: Range Queries :: Static Range Minimum 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 minimum 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] = min(tree[leftNode], tree[rightNode]);
}

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

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

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

    return  min(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);
    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, 0, n-1, l-1, r-1, 1) << '\n';
    }
    
    return 0;
}

CSES :: Introductory Algorithms :: Missing Number

Problem : Please find the problem here.

Explanation : Apply XOR of all n-1 numbers with numbers between 1 to n.

Code : missing number = (1^2^....^n) ^ (a[0]^a[1]^...a[n-1])

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

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

    int n, x;
    cin >> n;
    ll res = 0;
    for (int i = 0; i < n-1; i++) {
        cin >> x;
        res ^= x;
    }
    for (int i = 1; i <= n; i++) {
        res ^= i;
    }

    cout << res;
    return 0;
}

CSES :: Introductory Problems :: Repetitions

Problem : Please find the problem here.

Explanation : Read the string and keep the count of consecutive equal characters. Update this count on finding the different char and start over.

Code :

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    int mxCount = INT_MIN, count = 1;
    for (int i = 1; i < s.length(); i++) {
        if (s[i] == s[i-1]) {
            count++;
        } else {
            mxCount = max(count, mxCount);
            count = 1;
        }
    }

    mxCount = max(count, mxCount);

    cout << mxCount;

    return 0;
}

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;
}