Problem Link
Author: Rudransh Tripathi
Editorialist: Rudransh Tripathi
Difficulty
Easy
Prerequisites
DFS, BFS, DSU, Dynamic - Programming
Problem
There are N businessmen from 0 to N−1 who are ready to invest in real estate. Some of them are friends and thus form a group. You have been given M facts that businessmen u and v are friends. The same fact can be given multiple times. If X and Y are friends and Y and Z are friends, then it is always true that X and Z are also friends.
You have been given N real estate amount values, curr_i , corresponding to each person from 0 to N−1 and their predicted values, pred_i , in the future. For every group, there are a number of real estate properties to choose from but the total investment by each group (the sum of all the chosen real estate amount values), must not exceed K available funds. Determine the sum of maximum profit that can be earned by each group.
Note: Each group is assigned K funds. In case a businessman has no friends, he will be the sole investor.
Explanation
Assumption: Let P be the number of connected components and Q be the size of any connected component.
Using DFS/BFS/DSU, find out all the connected components and store them.
After finding out all the connected components (0 to N - 1) , apply modified Knapsack 0-1 on each of them to get maximum profit and add them.
For modified knapsack, in a DP[][] table let’s consider all the possible values from 0 to K as the columns and all possible values from 0 to Q(size of a connected component) as the rows.
First, fill the 0^{th} row and column with zeroes.
The state DP[i][j] will denote maximum value the knapsack can take with maximum amount j and i businessmen.
Now two possibilities can take place:
-
curr_{i-1} > j
DP[i][j] = DP[i - 1][j] -
curr_{i-1} \leq j
DP[i][j] = max(DP[i - 1][j], profit[i - 1] + DP[i - 1][j - curr[i - 1]])
For first possibility, DP[i][j] state will be same as DP[i - 1][j].
For second possibility, if we do not fill i^{th} current amount in j^{th} column then DP[i][j] state will be same as DP[i - 1][j] but if we fill the given column, DP[i][j] will be equal to the value of profit[i - 1] + value of the column equal to [j - curr[i - 1]] in the previous row. Here, profit[i - 1] is denoted by [pred[i - 1] - curr[i - 1]]. So, we take the maximum of these two to fill the current state.
Print the final summation of DP[Q][K] from every connected component where Q determines the size of the connected component and K is the funds available.
Example
5 7
2
0 1
3 4
3 9 6 3 2
5 3 1 4 9
Solution
3 Groups will be formed.
Group 1: [0, 1]
Curr = [3 9]
Pred = [5 3]
Profit = [2 -6]
DP
0 0 0 0 0 0 0 0
0 0 0 2 2 2 2 2
0 0 0 2 2 2 2 2
Group 2: [2]
Curr = [6]
Pred = [1]
Profit = [-5]
DP
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Group 3: [3, 4]
Curr = [3 2]
Pred = [4 9]
Profit = [1 7]
DP
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1
0 0 7 7 7 8 8 8
Ans = 2 + 0 + 8 = 10
Time Complexity
Assumption: Let P be the number of connected components and Q be the size of any connected component.
O((N + M) + (P * Q * K))
Solution
C++ Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
const int MAX = 3e3 + 5;
#define int long long int
#define pb push_back
#define d(x) cout<<x<<"\n"
#define time_passed 1.0 * clock() / CLOCKS_PER_SEC
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
vector<int> graph[MAX];
vector<vector<int>> connected;
int solveDP(vector<int> curr, vector<int> pred, int k)
{
int n = curr.size();
vector<vector<int>> dp((n + 1), vector<int>((k + 1), 0));
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < k + 1; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (curr[i - 1] <= j)
dp[i][j] = max(pred[i - 1] - curr[i - 1] + dp[i - 1][j - curr[i - 1]], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[n][k];
}
void dfs2(int v, int vis[], vector<int> &v1)
{
vis[v] = 1;
v1.pb(v);
for (auto x : graph[v]) {
if (vis[x] == 0)
dfs2(x, vis, v1);
}
}
void dfs1(int n)
{
int vis[n] = {0};
for (int v = 0; v < n; v++) {
if (vis[v] == 0) {
vector<int> v1;
dfs2(v, vis, v1);
connected.pb(v1);
}
}
}
void solve()
{
int n, k;
cin >> n >> k;
int m;
cin >> m;
while (m--)
{
int u, v;
cin >> u >> v;
graph[u].pb(v);
graph[v].pb(u);
}
dfs1(n);
int current[n];
int predicted[n];
for (int i = 0; i < n; i++)
cin >> current[i];
for (int i = 0; i < n; i++)
cin >> predicted[i];
/*cout << connected.size() << "\n";
for (int i = 0; i < connected.size(); i++)
{
for (int j = 0; j < connected[i].size(); j++)
cout << connected[i][j] << " ";
cout << "\n";
}*/
int ans = 0;
for (int i = 0; i < connected.size(); i++) {
vector<int> choose = connected[i];
vector<int> curr;
vector<int> pred;
for (int j = 0; j < choose.size(); j++) {
curr.pb(current[choose[j]]);
pred.pb(predicted[choose[j]]);
}
ans += solveDP(curr, pred, k);
}
cout << ans << "\n";
}
int32_t main(void)
{
//#ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
//#endif
fastio
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
cerr << "\n" << "Time elapsed : " << time_passed << "\n";
return 0;
}
Python Solution
import sys
sys.setrecursionlimit(10**6)
#sys.stdin = open('input.txt', 'r')
#sys.stdout = open('output.txt', 'w')
MAX = 2005
graph = [[] for i in range(MAX)]
connected = []
def get_ints():
return map(int, sys.stdin.readline().strip().split())
def get_lists():
return list(map(int, sys.stdin.readline().strip().split()))
def solveDP(curr, pred, k):
n = len(curr)
dp = [[0 for x in range(k + 1)] for x in range(n + 1)]
for i in range(0, n + 1):
for j in range(0, k + 1):
if i == 0 or j == 0:
dp[i][j] = 0
elif curr[i - 1] <= j:
x = pred[i - 1] - curr[i - 1] + dp[i - 1][j - curr[i - 1]]
z = dp[i - 1][j - curr[i - 1]]
y = dp[i - 1][j]
dp[i][j] = max(x, y)
else:
dp[i][j] = dp[i - 1][j]
#for row in dp:
# print(*(row))
return dp[n][k]
def dfs2(v, vis, v1):
vis[v] = 1
v1.append(v)
for i in graph[v]:
if vis[i] == 0:
dfs2(i, vis, v1)
return v1
def dfs1(n):
vis = [0] * n
for v in range (0, n):
if vis[v] == 0:
v1 = []
connected.append(dfs2(v, vis, v1))
if __name__=="__main__":
n, k = get_ints()
m = int(input())
while(m):
u, v = get_ints()
graph[u].append(v)
graph[v].append(u)
m -= 1
dfs1(n)
current = []
predicted = []
current = get_lists()
predicted = get_lists()
ans = 0
for i in range(0, len(connected)):
arr = connected[i]
curr = []
pred = []
#print(arr)
for j in range(0, len(arr)):
curr.append(current[arr[j]])
pred.append(predicted[arr[j]])
ans += solveDP(curr, pred, k)
sys.stdout.write(str(ans))
Java Solution
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
public static void dfs2(int edges[][], boolean visited[], ArrayList<Integer> arr, int start)
{
visited[start] = true;
arr.add(start);
int n = edges.length;
for (int j = 0; j < n; j++)
{
if (edges[start][j] == 1 && !visited[j])
{
dfs2(edges, visited, arr, j);
}
}
}
public static void dfs1(int edges[][], int start, ArrayList<ArrayList<Integer>> farr)
{
boolean visited[] = new boolean[edges.length];
for (int i = 0; i < edges.length; i++)
{
if (!visited[i])
{
ArrayList<Integer> arrans = new ArrayList<Integer>();
dfs2(edges, visited, arrans, i);
Collections.sort(arrans);
farr.add(arrans);
}
}
}
public static int max(int a, int b)
{
return (a > b) ? a : b;
}
public static int solveDP(int[] curr, int[] pred, int k, int size)
{
int i, w;
int K[][] = new int[size + 1][k + 1];
for (i = 0; i <= size; i++)
{
for (w = 0; w <= k; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (curr[i - 1] <= w)
K[i][w] = max(pred[i - 1] - curr[i - 1] + K[i - 1][w - curr[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[size][k];
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int k = s.nextInt();
ArrayList<ArrayList<Integer>> farr = new ArrayList<ArrayList<Integer>>(n);
int e = s.nextInt();
int edges[][] = new int[n][n];
for (int i = 0; i < e; i++)
{
int fv = s.nextInt();
int sv = s.nextInt();
edges[fv][sv] = 1;
edges[sv][fv] = 1;
}
dfs1(edges, 0, farr);
int[] curr = new int[n];
int[] pred = new int[n];
for (int i = 0; i < n; i++)
{
curr[i] = s.nextInt();
}
for (int i = 0; i < n; i++)
{
pred[i] = s.nextInt();
}
int ans = 0;
for (int i = 0; i < farr.size(); i++)
{
ArrayList<Integer> choose = farr.get(i);
int[] curr1 = new int[farr.get(i).size()];
int[] pred1 = new int[farr.get(i).size()];
for (int j = 0; j < farr.get(i).size(); j++)
{
curr1[j] = curr[farr.get(i).get(j)];
pred1[j] = pred[farr.get(i).get(j)];
}
ans += solveDP(curr1, pred1, k, farr.get(i).size());
}
System.out.print(ans);
}
}