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