fck_cheater's blog

By fck_cheater, history, 3 years ago, In English

We are given some graph nodes and every node has three things:

  1. Cost to include this node

  2. Money we get while we include this node.

  3. It's parent who should be included if this node is included ( It's may possible to not having a parent for some node )

Now I have to choose some nodes out of these such that total cost of selected nodes shouldn't exceed M and we should be able to earn maximum possible money.

How to solve this problem?

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If there's a cycle of parent relationships, we can combine these into one big node, with cost and money the sum of cost and money of all the nodes in the cycle. For the nodes that don't have a parent, we can connect them to a (fake) root node, with cost and money 0. After this, the graph becomes a directed tree, with as root the fake node we created. I don't know what the constraints are, but if M is small and the number of nodes is too, then we could use Tree DP.

Let $$$DP[u][c]$$$ = Maximum amount of money that can be made in the subtree of node u, with a cost of c. Transitions will be, for every child c of a node u, $$$DP[u][i+j] = max(DP[u][i+j],DP[u][i]+DP[c][j])$$$.

For all states initialize with $$$-\infty$$$, except for $$$DP[u][cost_u]=money_u$$$. When done with subtree u, set $$$DP[u][0]=0$$$. The answer to the problem will be $$$max_{cost \leq M}(DP[root][cost])$$$ I think the DP should run in $$$O(N \cdot M^2)$$$, which is a bit slow, but maybe feasible.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Can you please remove your answer and upload it later , possibly 24 hours later. The lack of a link and throwaway account indicates this question is from a contest currently going on. Also since many companies are having their placement tests, you might be unknowingly aiding cheaters.