API tools faq
paste
RainX_69

DE_SHAW OFF-CAMPUS OA QUESTION

RainX_69
Dec 23rd, 2022 (edited)
150
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.53 KB | Source Code | 0 0
raw download clone embed print report
  1. /*
  2.  
  3.                                                     D.E. Shaw | Off-Campus | 2023 Batch
  4.  
  5.                                                             Problem statement
  6.  
  7. There is an undirected graph of g_nodes nodes numbered from 1 to g_nodes and g_edges where the ith edge connects the nodes numbered g_from[i] and g_to[i]. There is also an array of m integers, disconnected_nodes, which represents the array of nodes that are not reachable from one another via any path. No two nodes in the array are connected directly or indirectly.
  8.  
  9. Find the maximum number of edges that can be added to the graph such that the set of disconnected_nodes remain disconnected, the graph does not contain any self-loops, and there are no multiple edges between two nodes.
  10.  
  11. Example
  12.  
  13. g_nodes = 4 , disconnected_nodes = [1, 3]
  14. g_from = [1],  g_to = [2]
  15. The optimal solution is to connect node 4 to nodes 1 and 2. This adds a total of 2 edges. No more edges can be added as nodes 1 and 3 cannot have a path between them
  16.  
  17.  
  18. Testcase
  19.  
  20. Input:
  21. g_nodes = 6
  22. g_edges = 4
  23. g_from = [1,1,2,4]
  24. g_to = [2,3,3,5]
  25. disconnected_nodes = [2,4]
  26.  
  27. Output:
  28. 3
  29.  
  30. Explanation: 3 edges can be added to the graph, node 6 can be connected to nodes 1, 2 and 3
  31.              It can be shown that 3 is maximum number of edges that we can add
  32. */
  33.  
  34.  
  35. -------------------------------------------------------------------------------------------------------------------------------------
  36.                                                         THOUGHT PROCESS
  37. 1) Find graphs with no forbidden nodes, and merge them
  38.  
  39. 2) Find the largest node count from subgraph containing forbidden node
  40.  
  41. 3) Merge all graphs with no forbidden node and merge largest graph with a forbidden node
  42.  
  43. 4) Go to each component and find edges to draw using formula n*(n-1)/2-existing edges, where n is the component nodes and existing        edge is the edge that already exists in this component
  44. -------------------------------------------------------------------------------------------------------------------------------------
  45.  
  46.  
  47.                                                             __________CODE_________
  48.  
  49. #include <bits/stdc++.h>
  50. using namespace std;
  51.  
  52. vector<int> parent;
  53. vector<int> dense;
  54. vector<int> component_count;
  55. vector<int> edge_count;
  56. unordered_set<int> unfriendlyNodes;
  57.  
  58. void initialise(int n, vector<int> &nodes){
  59.     parent.resize(n+1);
  60.     dense.resize(n+1,0);
  61.     component_count.resize(n+1,1);
  62.     edge_count.resize(n+1,0);
  63.     for(int i=1;i<=n;i++){
  64.         parent[i]=i;
  65.     }
  66. }
  67.  
  68. int findParent(int node){
  69.     if(node==parent[node]){
  70.         return node;
  71.     }
  72.     return parent[node]=findParent(parent[node]);
  73. }
  74.  
  75. void balancer(int par, int child){
  76.     parent[child]=par;
  77.     edge_count[par]+=edge_count[child]+1;
  78.     component_count[par]+=component_count[child];
  79.     edge_count[child]=0;
  80.     edge_count[child]=0;
  81. }
  82.  
  83. void merge(int node1, int node2){
  84.     int Pnode1=findParent(node1);
  85.     int Pnode2=findParent(node2);
  86.     if(Pnode1==Pnode2){
  87.         edge_count[Pnode1]++;
  88.         return;
  89.     }
  90.     if(dense[Pnode1]<dense[Pnode2]){
  91.         balancer(Pnode2,Pnode1);
  92.     }
  93.     else if(dense[Pnode1]>dense[Pnode2]){
  94.         balancer(Pnode1,Pnode2);
  95.     }
  96.     if(dense[Pnode1]==dense[Pnode2]){
  97.         dense[Pnode1]++;
  98.         balancer(Pnode1,Pnode2);
  99.     }
  100. }
  101.  
  102. int helper(int n){
  103.    
  104.     /* STEP 1: We will filter graphs having no forbidden Nodes */
  105.     unordered_set<int> rep;  // contains representative of graphs having no forbidden node
  106.     for(int i=1;i<=n;i++){
  107.         if(unfriendlyNodes.find(findParent(i))==unfriendlyNodes.end()){
  108.             rep.insert(findParent(i));
  109.         }
  110.     }
  111.    
  112.    
  113.    
  114.    
  115.     /* STEP 2: We will now merge the graphs having no forbiddenNodes to make a super graph */
  116.     int superGraph=-1;
  117.     auto itr=rep.begin();
  118.     if(rep.size()>0){
  119.         superGraph=*itr;
  120.         itr++;
  121.     }
  122.     for(;itr!=rep.end();itr++){
  123.         merge(superGraph,*itr);
  124.         // removing this imaginary edge used to connect two subgraphs
  125.         edge_count[findParent(superGraph)]--;
  126.     }
  127.    
  128.    
  129.    
  130.     /* STEP 3: We will not find the maximum component_count of graph having forbiddenNode */
  131.     int mxnode=-1;
  132.     int mxSize=-1;
  133.     for(auto node: unfriendlyNodes){  // get the highest sized forbidden node
  134.         int representative=findParent(node);
  135.         if(mxSize<component_count[representative]){
  136.             mxnode=representative;
  137.             mxSize=component_count[representative];
  138.         }
  139.     }
  140.    
  141.    
  142.    
  143.     /* STEP 4: We will merge the superGraph with the highest sized forbidden node graph */
  144.     if(superGraph!=-1){  // if there exists a super graph
  145.         merge(superGraph,mxnode);
  146.         // removing this imaginary edge used to connect two subgraphs
  147.         edge_count[findParent(mxnode)]--;
  148.     }
  149.    
  150.    
  151.    
  152.    
  153.     /* STEP 5: We will now calculate the edges we can make, each component having n nodes can have max
  154.                of total=n*(n-1)/2 edges and if there are already x ExistingEdges, extra edges which can
  155.                be drawn are total-x */
  156.     int res=0;
  157.     unordered_set<int> vis;
  158.     for(int node=1;node<=n;node++){
  159.         if(vis.find(findParent(node))!=vis.end()){
  160.             continue;
  161.         }
  162.         int ExistingEdges=edge_count[findParent(node)];
  163.         int totalConnectedEdges=component_count[findParent(node)]*(component_count[findParent(node)]-1)/2;
  164.         res+=totalConnectedEdges-ExistingEdges;
  165.         vis.insert(findParent(node));
  166.     }
  167.     return res;
  168. }
  169.  
  170.  
  171.  
  172. int main(){
  173.    
  174.     /* BELOW ARE THE TEST CASES */
  175.    
  176.    
  177.     // int g_nodes = 7;
  178.     // int g_edges = 6;
  179.     // int g_from[6]= {1, 1, 2, 3, 4, 6};
  180.     // int g_to[6]= {2, 3, 3, 4, 5, 7};
  181.     // vector<int> forbiddenNodes={1,7};
  182.     // initialise(g_nodes,forbiddenNodes);
  183.     // for(int i=0;i<g_edges;i++){
  184.     //     merge(g_from[i],g_to[i]);
  185.     // }
  186.     // for(auto node: forbiddenNodes){
  187.     //     unfriendlyNodes.insert(findParent(node));
  188.     // }
  189.     // cout<<helper(g_nodes);
  190.    
  191.    
  192.    
  193.     // int g_nodes=4;
  194.     // int g_edges=1;
  195.     // vector<int> forbiddenNodes={1,3};
  196.     // int g_from[g_edges]= {1};
  197.     // int g_to[g_edges]= {2};
  198.     // initialise(g_nodes,forbiddenNodes);
  199.     // for(int i=0;i<g_edges;i++){
  200.     //     merge(g_from[i],g_to[i]);
  201.     // }
  202.     // for(auto node: forbiddenNodes){
  203.     //     unfriendlyNodes.insert(findParent(node));
  204.     // }
  205.     // cout<<helper(g_nodes);
  206.    
  207.    
  208.    
  209.     // int g_nodes=6;
  210.     // int g_edges=4;
  211.     // vector<int> forbiddenNodes={2,4};
  212.     // int g_from[g_edges]= {1,1,2,4};
  213.     // int g_to[g_edges]= {2,3,3,5};
  214.     // initialise(g_nodes,forbiddenNodes);
  215.     // for(int i=0;i<g_edges;i++){
  216.     //     merge(g_from[i],g_to[i]);
  217.     // }
  218.     // for(auto node: forbiddenNodes){
  219.     //     unfriendlyNodes.insert(findParent(node));
  220.     // }
  221.     // cout<<helper(g_nodes);
  222.    
  223.    
  224.    
  225.     // int g_nodes=23;
  226.     // int g_edges=18;
  227.     // vector<int> forbiddenNodes={7,17,19};
  228.     // int g_from[g_edges]= {1,1,1,2,3,4,6,8,9,10,11,13,14,15,22,19,19,23};
  229.     // int g_to[g_edges]= {2,3,4,3,4,5,7,9,10,11,12,14,15,16,19,20,21,19};
  230.     // initialise(g_nodes,forbiddenNodes);
  231.     // for(int i=0;i<g_edges;i++){
  232.     //     merge(g_from[i],g_to[i]);
  233.     // }
  234.     // for(auto node: forbiddenNodes){
  235.     //     unfriendlyNodes.insert(findParent(node));
  236.     // }
  237.     // cout<<helper(g_nodes);
  238.    
  239.    
  240.     // int g_nodes=8;
  241.     // int g_edges=6;
  242.     // vector<int> forbiddenNodes={1,8};
  243.     // int g_from[g_edges]= {1, 1, 2, 4, 5, 6};
  244.     // int g_to[g_edges]= {2, 3, 3, 5, 6, 7};
  245.     // initialise(g_nodes,forbiddenNodes);
  246.     // for(int i=0;i<g_edges;i++){
  247.     //     merge(g_from[i],g_to[i]);
  248.     // }
  249.     // for(auto node: forbiddenNodes){
  250.     //     unfriendlyNodes.insert(findParent(node));
  251.     // }
  252.     // cout<<helper(g_nodes);
  253.    
  254.    
  255.    
  256.     // int g_nodes=7;
  257.     // int g_edges=7;
  258.     // vector<int> forbiddenNodes={1,7};
  259.     // int g_from[g_edges]= {1, 1, 2, 2, 3, 4, 5};
  260.     // int g_to[g_edges]= {2, 3, 3, 4, 5, 5, 6};
  261.     // initialise(g_nodes,forbiddenNodes);
  262.     // for(int i=0;i<g_edges;i++){
  263.     //     merge(g_from[i],g_to[i]);
  264.     // }
  265.     // for(auto node: forbiddenNodes){
  266.     //     unfriendlyNodes.insert(findParent(node));
  267.     // }
  268.     // cout<<helper(g_nodes);
  269.  
  270.    
  271.  
  272.     int g_nodes=7;
  273.     int g_edges=0;
  274.     vector<int> forbiddenNodes={1,7};
  275.     int g_from[g_edges]= {};
  276.     int g_to[g_edges]= {};
  277.     initialise(g_nodes,forbiddenNodes);
  278.     for(int i=0;i<g_edges;i++){
  279.         merge(g_from[i],g_to[i]);
  280.     }
  281.     for(auto node: forbiddenNodes){
  282.         unfriendlyNodes.insert(findParent(node));
  283.     }
  284.     cout<<helper(g_nodes);
  285.    
  286.  
  287. }
Tags: dsa Graphs DE-SHAW OA DISJOINT_SETS OFF-CAMPUS
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!