13 months ago

slime • 380

Hyderabad

1st problem is directly as is from Graph's class!

Distributed Data Servers | Solution

This is same as finding diameter of tree, which is the longest path between any two nodes in a tree.

Below is C++ implementation of the two-pass DFS solutoin taught in class.

#include <vector>
#include <cstring>
using namespace std;

const int MAX_NODES = 2 * 1e5;
vector<int> adj[MAX_NODES];
bool visited[MAX_NODES];
int farthestNode, maxDist;

void dfs(int node, int dist) {
    visited[node] = true;
    if (dist > maxDist) {
        maxDist = dist;
        farthestNode = node;
    }
    for (int i = 0; i < adj[node].size(); i++) {
        if (!visited[adj[node][i]]) {
            dfs(adj[node][i], dist + 1);
        }
    }
}

int getMaxTime(int g_nodes, vector<int> g_from, vector<int> g_to) {
    for (int i = 0; i < g_nodes; i++) {
        adj[i].clear();
    }

    for (int i = 0; i < g_from.size(); i++) {
        adj[g_from[i] - 1].push_back(g_to[i] - 1); // Assuming nodes are 1-indexed
        adj[g_to[i] - 1].push_back(g_from[i] - 1); // Assuming nodes are 1-indexed
    }

    memset(visited, false, sizeof(bool) * g_nodes);
    maxDist = -1;
    dfs(0, 0);

    memset(visited, false, sizeof(bool) * g_nodes);
    maxDist = -1;
    dfs(farthestNode, 0);

    return maxDist;
}

22 months ago

------------- • 70

Demand and supply 

complexity - 2^7 * o(n) 

Correct me if i am wrong 

 

#include <bits/stdc++.h>

using namespace std;

int n;
int shop[100005][8];
int person[100005][8];
int m;
int k, p;
map<int, int> mp;

int dp[100005][1 << 8][3];

int va[1 << 8];

int rec(int i, int mask, int cnt)
{

	// cout << i << endl;
	if (i >= m)
	{

		// cout << mask << endl;
		return va[mask];
	}

	int ans = 0;
	if (dp[i][mask][cnt] != -1)
		return dp[i][mask][cnt];
	if (cnt <= 1)
	{

		int opt1 = rec(i + 1, mask, cnt);

		int newmask = 0;
		for (auto &j : shop[i])
		{
			newmask += (1 << (j - 1));
		}
		int opt2 = rec(i + 1, mask | newmask, cnt + 1);

		return dp[i][mask][cnt] = max(opt1, opt2);
	}
	if (cnt == 2)
	{
		return dp[i][mask][cnt] = rec(i + 1, mask, 2);
	}
}

int main()
{

	cin >> n >> m >> k >> p;
	mp.clear();

	for (int i = 0; i < n; i++)
	{
		int val = 0;
		for (int j = 0; j < p; j++)
		{
			int c;
			cin >> c;
			c -= 1;
			val += (1 << c);
		}
		mp[val] += 1;
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < k; j++)
		{
			cin >> shop[i][j];
		}
	}

	// for (auto &k : mp)
	// 	cout << k.first << " " << k.second << endl;

	// precomputing ans for every mask
	// for this mask how many person get satisfy

	for (int j = 0; j < (1 << 7); j++)
	{
		int curr = 0;
		// cout << j << endl;

		for (auto &h : mp)
		{
			int val = h.first;
			bool fl = 1;

			// cout << val << "->";

			for (int bit = 7; bit >= 0; bit -= 1)
			{
				bool bit1 = val & (1 << bit);
				bool bit2 = j & (1 << bit);

				if (bit1 == 1 && bit2 == 0)
					fl = 0;
			}

			if (fl == 1)
			{

				// cout << j << "->"
				// 	 << " " << h.first << "and"
				// 	 << " ";
				curr += h.second;
			}
		}
		// cout << endl;
		va[j] = curr;
		// cout << endl;
	}
	memset(dp, -1, sizeof(dp));
	cout << rec(0, 0, 0);
}

21 months ago

Kshitiz Kumar • 0

Delhi

Q -1 

ll maxnode  ,maxsum ; 

void dfs(ll node , map<ll ,vll >adj  , vll&vis , ll sum )
{

 maxnode  = node ; 
 maxsum = max(maxsum ,sum ); 




for(auto it: adj[node])
{
  if(!vis[it])
  {
    vis[it]=1 ; 
    dfs(it , adj , vis , sum+1 ) ;}
}


}

void solve()
{
ll n ; cin >> n ;  
vll v1 = {1,2  , 3  ,2 ,5} , v2 = {2, 3 ,4 , 5, 6} ; 

map<ll ,vll >adj ; 
fl(i , 0 ,v1.size())
{
adj[v1[i]].push_back(v2[i]);
adj[v2[i]].push_back(v1[i]);
}

vll vis(n+1 ,  0 ) ; 
vis[1]=1 ;
dfs(1 , adj  ,vis , 0 ) ; 
vll vis1(n+1, 0  ) ;
maxsum= 0 ;

vis1[1]=1;
dfs(maxnode, adj , vis1, 0 ) ; 

cout << maxsum << nl ;
}