Please read the new rule regarding the restriction on the use of AI tools. ×

shantanu20's blog

DE Shaw OA off campus for 2023 graduates
By shantanu20, history, 21 month(s) 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 (8)
| Write comment?
»
21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Can you tell your approach for the 1st problem?

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) 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