How to solve atcoder abc 163 E (dynamic programming)?

help
1

problem link
Can you explain the dp solution and how to get the correct states?

1 Like
2

Let take an example 5 9 3 5 2 8 6 => 7 elements. we have reordered the elements acc to the problem. Let be greedy for some part as we say that if we put the elements too far from its initial position then we get large happiness value for those elements. As we see in the example put 9 to index 7 (from the initial index 2) but we can only put one element at a particular index. So for each element, we have 2 choices from its initial position.

  1. Put the element far to the left which is not occupied.
  2. Put the element far to the right which is not occupied.
    Okay now to second observation to get a maximum value of happiness the extreme indexes should have larger values i.e from above example put 9 to index 7 (happiness value is 9*(7-2)=45) then 5 to index 7(happiness value is 5*(7-1)=30)
    by this, we give the chance to the largest elements before others.

so we combine the above two observations and sort the given array (by preserving the initial position using pair or something like that) in decreasing order.
Then for each element in this sorted array, we have two choices as describe above.

1 Like
3

@mattup If we are to write the states, the index, current available leftmost position and current available rightmost position are the important things at some moment of time. That is dp function should look like F(index, left, right) which will lead to a n^3 memory and time complexity. How to handle that?

4

okay observe one thing that l and r are dependent.
our rec(idx,left,right)
this means that we are at index idx and from where left is farthest left index which is not filled (means before left all are filled) and the same thing is for right that right is farthest right index which is free and after that all are filled.
so one thing is clear
that
r=n-(idx-l)
or
l=idx-(n-r)
so in any dp only those variables that are independent are used for state
here we can use dp[idx][left] or dp[idx][right] to uniquely define state for rec(idx,left,right)
or you can also used rec(idx,left) and find r=n-(idx-l);
or rec(id,right) and find l=idx-(n-r);
thus total time complexity will sum up = O(n^2)

1 Like
5

Nicely explained, thanks.