SpongeBobSquarePants's blog

By SpongeBobSquarePants, history, 5 weeks ago, In English

Hello everyone. I participated in the lowe's coding round and there was this question I was not able to solve completely. I did brute force and passed some test cases though.

The problem says, You are given a connected undirected graph. It has n nodes and m edges. Each node has some sweetness value that will be given to us.

The game is as follows:

  1. Alice moves first and she may break a node. Each edge connected to this node will vanish.
  2. Bob will pick any connected component(containing all or some nodes)
  3. Alice will pick any remaining connected components if there are any

The game ends in three steps. Both of them want to maximize their score by collecting maximum possible sweetness. They are not trying to minimize each other' score.

Determine the maximum score of Alice and Bob respectively. Assume both plays the game optimally.

Graph nodes index starts from 1. If no connected component left, alice gets 0

Input: number of test cases then n, m and then sweetness of each node and then the edges.

Example:

1

6 7

4 3 7 5 9 2

1 2

2 3

1 3

3 4

4 5

5 6

4 6

For this answer is 11 14

I tried to construct a spanning tree and also strongly connected components but couldn't understand.

How to solve this problem? I did this with DFS and max heap. Brute force. What is optimal way of doing this problem

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Lowe's hiring challenge is still ongoing till midnight today. So, please ask tomorrow.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Round 1 as well? This one came in 1st round.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then, you should write in BOLD that this was from round 1. Since, round 2 of the same Lowe's hiring coding contest was held today and you wrote this blog today, so anyone's intuition will say that it is from today's round. In fact, there were many guys who did the same thing.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    These hiring challenges are really destroying competitive programming.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can you please elaborate why you think so?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        It has created a lot of desperate people who do not actually care about competitive programming but need to be good anyway. This in turn has increased the number of people with a shitty attitude, including but not limited to cheaters.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I do agree, these type of hirings have cultivated the cheater culture.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sir the contest is over I am not doing cheating in any way. Can't I ask a simple question on CF?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In a good way or you mean sarcastically :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain exactly why you think so ? Cuz, the companies can't interview all the candidates who apply for a particular job profile, as there are too many of them. Also, they can't give standard interview problems which can be googled easily. So, they have to stick to something similar to competitive programming. Although, the problems are much easier and many times are slight variation of the standard algorithms.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You have explained why these companies do this, but this is not at all a refutation of "hiring challenges are destroying competitive programming".

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, but my point was the companies "have" to do it. I agree with your point though. Moreover, many people (not all) who get hired by these challenges often start a youtube channel where they propagate many misconceptions regarding competitive programming, resulting in more cheating.

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

round 1 is over

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution is to use the DFS tree.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate further because my dfs gave me TLE. I deleted all nodes and then computed cost every time.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In the following, I'll denote as $$$\mathrm{sw}[u]$$$ the sweetness value of $$$u$$$. Build the DFS tree (shamelessly linking to my own blog, oh no) of the graph. In every vertex $$$v$$$, store the total sweetness value of the subtree of that vertex, call that value $$$\mathrm{sub}[v]$$$.

      Let's consider removing some vertex $$$u$$$. What connected components are there after removing the vertex $$$u$$$? For every child $$$v$$$ of $$$u$$$ such that there is no back-edge from a descendant of $$$v$$$ to a proper ancestor of $$$u$$$, there will be a component with total sweetness value $$$\mathrm{sub}[v]$$$. The rest of the vertices will be in one connected component connected to the parent of $$$u$$$. We have found the sizes of all these components, so we can calculate the value of the largest one, give it to Bob and give all other vertices to Alice. Thus, we can check the scores of both players if Alice removes the vertex $$$u$$$ at first. Calculate these scores for every choice of $$$u$$$.

      The complexity will be $$$O(m)$$$.