Блог пользователя shantanu20

DE Shaw OA off campus for 2023 graduates
Автор shantanu20, история, 2 года назад, По-английски

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:

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

      → Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Can you tell your approach for the 1st problem?

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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
→ Ответить