Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

abbuben7982's blog

By abbuben7982, history, 12 months ago, In English,

I was going through the tutorial 1111 E Tutorial and I'm finding it hard to understand the dp equation given :

dp[i][j] = dp[i-1][j]⋅(j-h[i]) + dp[i-1][j-1]

(I am putting my understanding and it might be wrong. Do correct if i'm going wrong.)

So, I understand that dp[i-1][j-1] means that we are dividing the first i-1 people into atmost j-1 groups and just allocating the ith person to a newer group.

I am finding difficulty in the first part : dp[i-1][j]⋅(j-h[i])

j-h[i] mean that after allocating the first i-1 people into atmost j groups, we can now allocate the ith person only into those groups which do not have ancestors(present in the query) in that group.

Suppose that the tree is

1-2-6-4-5-3 | 7 and query elements being 2, 3. So, h[6] = 1(which is element 2 because 2 is the ancestor of 6 and 3 is not);

Let's say for element 6, and j=3 we can allocate 1 and 2 in different groups. So, 1,2 will take up 2 groups (dp[i-1][j-1] = 2) and now for allocating 6, we can add 6 in dp[i-1][j]*(j-h[i]) ways.

Can anyone explain to me what will be the value of dp[i-1][j]*(j-h[i]) here.

According to me dp[i-1][j] will be 2 because still, we can allocate the first 2 elements(1,2) into atmost 5 groups in 1 way(2 groups). and value of j-h[i] will be 3-1=2. So, 1*2=2 ways. Can anyone tell me what are those 2 ways?

In above example j-h[i] means that we have atmost 3 groups(Is it 3 grps or 3 non-empty grps (I'm in doubt)!!) and we have element 2 as the ancestor of 6 in the query, so we can't put 6 with 2. Hence we can put 6 with 1 and leave 2 alone OR we can put 1,2,6 each in a different group, but we have included the later case in dp[i-1][j-1] case.

Hence, there is only one way of allocating element 6(ie- with element 1) and leaving element 2 alone in a group.

So, Aren't we calculating j-h[i] in a wrong way? Kindly help me with this doubt.

  • Vote: I like it
  • 0
  • Vote: I do not like it

12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Suppose u and v are the ancestor of i, then u is the ancestor of v or v is the ancestor of u, so u and v belong to different groups, that means all ancestors of i belong to different groups and i can't belong to these groups(the number of groups is h[i]). There are j groups at all, so i can belong to j — h[i] groups. So there are dp[i][j-1] * (j — h[i]) ways.

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

    So, that means that if the first 2 groups are non-empty and rest 3 groups are empty then that means there are 3 ways. Right?

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

This problem is too hard for you.