mokoto's blog

By mokoto, history, 4 weeks ago, In English,

in the problem sugarel and love , how to choose two sons such that we can maximize

DP[i][1]={max(DP[j][0]+v[i][j]+DP[t][0]+v[i][t])∣ where j and t are sons of i}. For all other sons, we add max(DP[j][0],DP[j][1],DP[j][2]) as given in editorial

since there can be nC2 choices time complexity would be O(n2) , how to do it in O(n) time .

i think we cant choose first two sums which gives max(DP[j][0]+v[i][j]+DP[t][0]+v[i][t]) as it will not always optimal .

any idea.

 
 
 
 

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

I was under the impression we choose the j with the largest DP[j][0]+v[i][j] and t with the second largest DP[t][0]+v[i][j] and that will maximise the sum.

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

    so what happened .. has it worked..

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

      I finished coding it and it does not work. :(

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

        i think this will work :

        first keep all the maxes i.e maxofall(dp[j][0] , dp[j][1] , dp[j][2])

        now also keep dp[j][0] + v[i][j] — max[dp[j][0] , dp[j][1] , dp[j][2] ) for all children of i .

        sort them and take the first two , and for rest take the maxe's .

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

I thought of a very similar DP state, best(i, k) meaning "the best I can do from the subtree rooted at i using k edges to its sons"

Clearly 0 ≤ k ≤ 2. If we call f(j) the maximum over k of best(j, k) for all j sons of i, then the sum over j of f(j) is best(i, 0)

Now for k = 1, 2 think what terms you should take away from the sum and what you should add to that sum using 1 or 2 edges.

Link to muy submission using this idea : https://csacademy.com/submission/2161792/