ESTHND - Editorial

Author: Rudransh Tripathi
Editorialist: Rudransh Tripathi

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():

def get_lists():

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;

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

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

8 Likes

DFS + Knapsack => Solution

2 Likes