Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

wish_me's blog

By wish_me, history, 22 months ago, In English,

Hey, Everyone I am unable to understand that how should I apply knapsack in this problem

http://codeforces.com/problemset/problem/741/B

Because it contains different groups.Thus Mine complexity is coming O(W*N*N).I saw the editorial but unable to understand the solution.Can anyone explain ?

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

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

Sorry if I misunderstood your problem regarding the solution,but I will try to explain it entirely. Firstly,imagine the relationships betweeb Hoses as a graph.2 hoses are in the same friendship group if they are in the same connected component.You can run a dfs/bfs to find all the connected components.Why does it matter?If two Hoses are n the same friendship group we can't take one without the other,so we imagine each group as a super-Hose with the weight that is the sum of the weights of the hoses of the group,and the beauty the sum of the beauties of the hoses in the group. Secondly,we have at most n items(there can't be more than n connected components) so we can just apply the classical knapsack in O(n*k):

dp[ i ][ j ]=max(dp[ i-1 ][ j ],dp[ i-1 ][ j-Sweight[ i ] ]+ Sbeauty[ i ]) where Sweight[ i ],Sbeauty[ i ] are the weight and the beauty of i-th super hose.You can optimize knapsack's memory by always holding only the current and the previous line or having just an array and going with the j index in reversed order (from w to 1) but I don't believe this is essential if you have enough memory.

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

    Thanks.I was not applying the idea of connected component.

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

    But I think you didn't cover the case suppose we have three groups (1,2,3),(4,5),(6,7) Now As we can take maximum 1 from each group or can take all elements of the group.Now suppose maximum beauty with weight constraint come from this arrangement (2,4,5,7 i.e 2 nd from 1st set ,all from 2nd set,7 from last set),I hope you understand.

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

      Yeah,I'm sorry.I didn't solve the problem so I wasn't that careful at the statement.Each time you try to insert a super hose,you try to insert each hose that is from its group.So the recurrence becomes dp[ i ][ j ]=max((dp[ i-1 ][ j ],dp[ i-1 ][ j-Sweight[ i ] ]+ Sbeauty[ i ]), max{dp[ i-1 ][j-weight[ x ] ]+beauty[ x ]}),where x is successively,each hose from i-th group.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Run a simple dfs/bfs to find all the connected components. For each connected component store its total weight and beauty and also all the vertices in it.

Now there are 3 cases for each component, either take all of the vertices in it, take only 1 of the vertices in it or don't take anything at all. Now while going through connected components you can simply go through all its vertices and select the one which maximizes the answer.

My submission: http://codeforces.com/contest/741/submission/33745764