Question

Intuit | OA | Coding Questions | Set - 19 | 2022

Answer 1

 

I WAS THINKING IN THE DIRECTION OF 0/1 BOUNDED KNAPSACK, A STANDARD DP QUES..
BUT WAS NOT ABLE TO HANDLE THE GROUP SCENARIO MENTIONED IN QUESTION..

 

ANY LOGIC/HINT/CODE/RESOURCE WILL FEEL LIKE HEAVEN TO ME !
DO SHARE ! ALL THE BEST FOR FUTURE :)

Answer 2

Union Find + Knapsack DP - O(NC) [C++]

 

I think union find and knapsack DP should work.
I have this below coded up that pass the sample testcases.
Instead of DP 1 person to 1 person.
we DP 1 group to 1 group.

 

Time(NC)
Space(N + C)

 

class UF{ // C++20
public:
    vector<int> rank, parent;
    int N;
    UF (int n) : N{n}, rank(n), parent(n){
        iota(begin(parent), end(parent), 0);
    }

    int leader(int x){
        return parent[x] == x? x : (parent[x]=leader(parent[x]));
    }

    void unite(int x, int y){
        x = leader(x);
        y = leader(y);
        if (x == y){
            return;
        }
        if (rank[y] > rank[x]){
            swap(x, y);
        }
        if (rank[y] == rank[x]){
            ++rank[x];
        }
        parent[y] = x;
    }

    vector<vector<int>> getGroups(){
        unordered_map<int,int> mp;
        for (int i = 0; i < N; ++i){
            int sz = ssize(mp);
            mp.try_emplace(leader(i), sz);
        }
        vector<vector<int>> ans(ssize(mp));
        for (int i = 0; i < N; ++i){
            ans[mp[leader(i)]].push_back(i);
        }
        return ans;
    }
};

int solve(int N, int C, vector<int> money, vector<int> candy, vector<pair<int,int>> friends){
    UF uf(N);
    for (auto& [a, b] : friends){
        --a; --b;
        uf.unite(a, b);
    }
    vector<vector<int>> groups = uf.getGroups();
    vector<int> dp(C+1);
    for (auto& g : groups){
        vector<int> ndp {dp}; // don't pick any from this group
        for (int person : g){
            for (int j = candy[person]; j <= C; ++j){
                ndp[j] = max(ndp[j], dp[j-candy[person]]+money[person]); // pick from this group
            }
        }
        swap(ndp, dp);
    }
    return dp[C];
}

Some Testcases

    int a = solve(4, 40, {100,20,90,90}, {10,20,30,40}, {{2,3}});
    int b = solve(10, 10, {1,6,3,3,8,4,8,10,1,3},{2,2,3,3,2,3,1,3,3,2},{{10,10}});
    int c = solve(1,0,{1},{1},{{1,1}});
    int d = solve(2,5,{2,1},{1,4},{{1,2}});
    cout << a << '\n';
    cout << b << '\n';
    cout << c << '\n';
    cout << d << '\n';
C:\WINDOWS\system32\cmd.exe /c (a)
190
35
0
2
Hit any key to close this window...