shantanu20's blog

DE Shaw OA off campus for 2023 graduates
By shantanu20, history, 19 months ago, In English

I got 3 questions. First was medium but doable. I was not able to solve question 2 and 3. Can someone help me out with the solution Question 2:

Question 3:

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
19 months ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

For Q3 first use dsu to get disconnected components of graph. We can add additional edges in each component without issue. Now check the disconnected components which do not contain any disconnected_nodes. We can add edges among them without issue and lets call this new component as R. Last, choose the biggest component with a disconnected_node and we can add edges among the nodes of that component and R. Max Number of edges in a component of size n is nC2. Get maximum number of edges and subtract current number of edges to get answer For Q2, we can use repeated z-algorithm along with dp.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    so connect all components which do not have node a disconnected node. Now take the largest components which has a disconnected component . And now connect both these components

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Yes. But we also have to add additional edges in each connected component which already has a disconnected_node.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        find the component with largest no of nodes having one disconnected node and count no of edges in that component. let say it equals to n. and lets say m edges in that component. then find all nodes which doesnt have disconnected node and add to n. then the ans will be :- nc2-m;

        → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think in Q2 this greedy solution won't work...hence i did it with dp

    → Reply
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can you tell your approach for the 1st problem?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you multiply any integer by 2 you are just right shifting the bits and you want msb as right as possible so its optimal to do all the operation for one integer only, check for all the integer in O(1) and return the maximum

    → Reply
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Q3 

We First Perform DSU, After this Suppose we get x connected Components , we will have root[i] and sz[i] the root node ( or parent node  ) and size of the ith component respectively. First of all  we will add (sz[i]C2 - initial number of edges in component i)edges in the ith component 

Now will we divide the Components into to disjoint sets , if any node of a component i is present in disconnected_nodes array it will go to second set otherwise it will go to first set.

  We can say that any edge cannot be added between any two components in second set while any two nodes in the first can have edge between them. So if number of nodes in first set is y then it will finally have yC2 edges. Now we can select at max one component from set 2 and joins all its nodes to each of the y nodes and leave the remaining components  as it is. So we will select one component from second set that maximizes the answer. This component will be one having maximum size on second set
→ Reply