Digit DP

Here is my Digit DP Implementation

	/*dp[pos][cnt][flag] -> dp form with states*/

	int solve(int b)
	{
	    num.clear();
	    while (b > 0)
	        num.pb(b % 10), b /= 10;
	    reverse(all(num));
	    return call(0, 0, 0);
	}

	int call(int pos, int cnt, int flag)
	{
	    if (cnt > k) return 0;
	    
	        if (pos == num.size())
	    {
	        if (cnt == k) return 1;
	        else return 0;
	    }

	    if (f[pos][cnt][flag] != -1) return f[pos][cnt][flag];
	    f[pos][cnt][flag] = 0;

	    int limit = 9;
	    if (flag == 0)
	        limit = num[pos];

	    for (int i = 0; i <= limit; i++)
	    {
	        int next_flag = flag, next_cnt = cnt;

	        if (i < limit) next_flag = 1;
	        if (i == d) next_cnt++;

	        f[pos][cnt][flag] += call(pos + 1, next_cnt, next_flag);
	    }
	    return f[pos][cnt][flag];
	}

Number of Sub-arrays with Sum equal to k

A solution to the given problem.

	int Sum(int arr[], int n, int sum = 1)
	{
	    unordered_map<int, int> prevSum;
	    int res = 0;

	    int curr_sum = 0;
	    for (int i = 0; i < n; i++)
	    {
	        curr_sum += arr[i];

	        if (curr_sum == sum) res++;

	        if (prevSum.find(curr_sum - sum) != prevSum.end())
	            res += (prevSum[curr_sum - sum]);

	        prevSum[curr_sum]++;
	    }

	    return res;
	}

Calculating prexors in a Tree as a DSU application

This is related to a problem I came across in OJ 4 (DSA) and the following is the solution:

	int n, m, k;
	map<int, int> parent, val;
	int net = 0, ans = INF;

	int power(int x, int N)
	{
	    int y = 1;
	    while (N > 0)
	    {
	        if (N & 1)
	            y = (y * x) % MOD;
	        N /= 2;
	        x = (x * x) % MOD;
	    }

	    return y;
	}

	int Get(int i)
	{
	    if (!parent.count(i)) parent[i] = i, val[i] = 0;
	    return parent[i];
	}

	int Find(int x)
	{
	    int p = Get(x);
	    if (p == x) return x;

	    int r = (parent[x] = Find(p));
	    val[x] ^= val[p];
	    return r;
	}

	void Union(int i, int j, int x)
	{
	    int a = Find(i), b = Find(j);
	    x ^= val[i] ^ val[j];

	    if (a != b)
	    {
	        parent[a] = b;
	        val[a] = x;

	        net--;

	    } else
	    {
	        if (x == 0) return;
	        else
	            ans = 0;
	    }
	}

	signed main()
	{
	    ios_base::sync_with_stdio(false);
	    cin.tie(NULL);

	    cin >> n >> m >> k;
	    net = n + m - 1;

	    while (k--)
	    {
	        int i, j, x;
	        cin >> i >> j >> x;
	        j = 1005 + j;

	        if (ans != 0)
	            Union(i, j, x);
	    }

	    if (ans == 0)
	        cout << 0 << endl;
	    else
	    {
	        ans = power(2, 30);
	        ans = power(ans, net);
	        cout << ans << endl;
	    }
	    return 0;
	}

Interesting Application of Binary Searching

An interesting application of binary searching that can be applied to greedy graph algorithms like MST and Flows.

What is done?

In, normal binary search we search for first/suitable occurence of the correct answer. Here also we do something similar.

Problem

You are to form an MST such that the no. of edges in the MST that are connected to the index 1 is k which is given.

Simply put, $Edges \in MST$ connected to $1$ is equal to $k$.

Solution

We introduce the following idea - to prioritize the edges connected to 1 we add a separate suitable weight to the edges that have the node 1 in them (during the formation of the MST).
Now we binary search over the suitable weight.

The Code:

    int n, m, k;
    int net, connections;
    vi parent, ans;

    struct node
    {
        int u, v, w, weight, index;
    };

    vector<node> edge;

    bool cmp(node a, node b)
    {
        if (a.weight == b.weight)
            return a.u < b.u;
        else
            return a.weight < b.weight;
    }

    int Find(int a)
    {
        if (parent[a] == a)
            return a;
        return parent[a] = Find(parent[a]);
    }

    void Union(int mid)
    {
        net = 0, connections = 0;

        for (int i = 1; i <= n; i++)
            parent[i] = i;

        for (int i = 0; i < m; i++)
        {
            edge[i].weight = edge[i].w;

            if (edge[i].u == 1)
                edge[i].weight += mid;
        }
        sort(all(edge), cmp);

        for (int i = 0; i < m; i++)
        {
            if (net >= n)
                break;

            int a = Find(edge[i].u), b = Find(edge[i].v);
            int c = connections;

            if (a != b)
            {
                if (edge[i].u == 1)
                    c++;

                if (c <= k)
                {
                    ans[++net] = edge[i].index;
                    parent[a] = b;
                    connections = c;
                }
            }
        }
    }

    signed main()
    {
        cin >> n >> m >> k;
        parent.resize(n + 1), ans.resize(n + 1), edge.resize(m);

        vi bandwidth;
        bandwidth.pb(0);
        for (int i = 0; i < m; i++)
        {
            cin >> edge[i].u >> edge[i].v >> edge[i].w;
            edge[i].index = i + 1;

            bandwidth.pb(edge[i].w);

            if (edge[i].u > edge[i].v)
                swap(edge[i].u, edge[i].v);
        }

        int start = -MAX, end = MAX;
        while (start < end)
        {
            int mid = (start + end + 1) / 2;
            Union(mid);

            if (connections == k) start = mid;
            else end = mid - 1;
        }
        Union(start);

        if (net < n - 1 || connections < k)
            cout << -1 << endl;
        else
        {
            int sum = 0;
            for (int i = 1; i <= net; i++)
                sum += bandwidth[ans[i]];

            cout << sum << endl;
        }
        return 0;
    }