[LeetCode] 2467. Most Profitable Path in a Tree

Problem

https://leetcode.com/problems/most-profitable-path-in-a-tree/description/

Leetcode - Most Profitable Path in a Tree

Type - DFS/BFS, Tree, Shortest Path, Backtracking

Difficulty - Medium

Approach && Solution

First, I thought “Moving Bob first will makes the problem easier than considering concurrent simulation for Alice and Bob”.

Since the given graph is tree, that path between two nodes is unique.

Thus, Bob only affects the specific path: bob's starting pos-to-zero.

Alice’s profit for node i can be determined by comparing the visited times of Alice and Bob.

• If Alice visits first, Alice can get profit amount[i].

• Else if Alice and Bob visit simultaneously, Alice can get profit amount[i]/2.

• Else(If Bob visited first), Alice get 0(nothing) in node i.

Data Structures:

• adj: adjacency list for the given tree.

  • adj[u] contains the list of adjacent nodes of u.

• bobVisited: Bob’s visited time table.

• past: stores the previous node on the path from bob to 0; (It used for backtracking)

• q: queue for BFS.

• s/mp: hashset/hashmap for storing nodes in true path.

  • It helps to restore the wrong bobVisited data.

• profit: Alice’s profit from 0 to node i.

• aliceVisited: Alice’s visited time table.

Steps

1. Simulate Bob to reach the node 0 with BFS.

   Store Bob’s visiting time with bobVisited[i] .
   Store path with past[i].

2. Backtrack - 0 to bob.
   By tracing back(with array past), we can know the node where Bob actually visited.
   If node is not on Bob’s path, mark it not visited in bobVisited.

3. Now, It’s Alice’s turn.

   1. Start BFS from node 0.

   2. For each child node, update profit[child] from Alice’s and Bob’s visited time table data.

   3. If current node is leaf, update the maximum profit answer.

Complexity

Time Complexity: O(n) - Performing BFS twice.

Space Complexity: O(n) - Since graph has n-1 edges only, It’s not O(n²).

Code (C++ | Go)

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = amount.size();
        vector<vector<int>> adj(n);

        for(const auto &edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }

        // bob go first.
        // since the path is distinct between two nodes in tree,
        // bob's move will make the game simple.
        // Store bob's visited time for compare to alice's visiting time.
        vector<int> bobVisited(n, -1);
        bobVisited[bob] = 0;

        vector<int> past(n);
        iota(past.begin(), past.end(), 0);

        queue<int> q;
        q.push(bob);

        while(!q.empty()) {
            int curr = q.front();
            q.pop();

            for(const auto &next : adj[curr]) {
                if(bobVisited[next] == -1) {
                    bobVisited[next] = bobVisited[curr]+1;
                    past[next] = curr;
                    q.push(next);
                }
            }
        }

        set<int> s;
        int traceNode = 0;
        while(traceNode != bob) {
            s.insert(traceNode);
            traceNode = past[traceNode];
        }
        s.insert(bob);

        for(int i = 0; i < n; ++i) {
            if(s.find(i) == s.end()) {
                bobVisited[i] = -1;
            }
        }


        // Alice, Let's Go!
        q.push(0);

        vector<int> profit(n, 0);
        profit[0] = amount[0];

        vector<int> aliceVisited(n, -1);
        aliceVisited[0] = 0;

        int ans = -1e9;
        while(!q.empty()) {
            int curr = q.front();
            q.pop();
            bool flag = true;
            for(const auto &next : adj[curr]) {
                if(aliceVisited[next] == -1) {
                    flag = false;
                    aliceVisited[next] = aliceVisited[curr] + 1;
                    if(bobVisited[next] == -1 || aliceVisited[next] < bobVisited[next]) {
                        profit[next] = amount[next] + profit[curr];
                    } else if(bobVisited[next] == aliceVisited[next]) {
                        profit[next] = amount[next]/2 + profit[curr];
                    } else {
                        profit[next] = profit[curr];
                    }
                    q.push(next);
                }
            }
            // case leaf
            if(flag) {
                ans = max(ans, profit[curr]);
            }
        }

        return ans;
    }
};

func mostProfitablePath(edges [][]int, bob int, amount []int) int {
    n := len(amount)
    adj := make([][]int, n)
    for i := 0; i < n; i++ {
        adj[i] = make([]int, 0)
    }

    for _, edge := range edges {
        u := edge[0]
        v := edge[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }

    q := []int{bob}
    past := make([]int, n)
    bobVisited := make([]int, n)
    for i := 0; i < n; i++ {
        past[i] = i
        bobVisited[i] = -1
    }
    bobVisited[bob] = 0

    for len(q) > 0 {
        curr := q[0]
        q = q[1:]

        for _, next := range adj[curr] {
            if bobVisited[next] == -1 {
                bobVisited[next] = bobVisited[curr] + 1
                past[next] = curr
                q = append(q, next)
            }
        }
    }

    mp := make(map[int]bool)
    traceNode := 0
    for traceNode != bob {
        mp[traceNode] = true
        traceNode = past[traceNode]
    }
    mp[traceNode] = true

    for i := 0; i < n; i++ {
        if _, exists := mp[i]; !exists {
            bobVisited[i] = -1
        }
    }

    q = append(q, 0)
    aliceVisited := make([]int, n)
    profit := make([]int, n)
    for i := 1; i < n; i++ {
        aliceVisited[i] = -1
    }
    profit[0] = amount[0]

    ans := int(-1e9)
    for len(q) > 0 {
        curr := q[0]
        q = q[1:]
        flag := true

        for _, next := range adj[curr] {
            if aliceVisited[next] == -1 {
                flag = false
                aliceVisited[next] = aliceVisited[curr] + 1
                if bobVisited[next] == -1 || aliceVisited[next] < bobVisited[next] {
                    profit[next] = amount[next] + profit[curr]
                } else if aliceVisited[next] == bobVisited[next] {
                    profit[next] = amount[next]/2 + profit[curr]
                } else {
                    profit[next] = profit[curr]
                }
                q = append(q, next)
            }
        }

        if flag {
            ans = max(ans, profit[curr])
        }
    }

    return ans
}