I just think it is ((k+n)log()) Because, how should you take keyas left as possible? Also because always keys can be contiguos maybe we can do BS on starting key pos?

what is the proof of "taking continuous key will give us optimal solution" .

I am trying to solve using DP. I defined a recursive function f(i,j). Here i=> ith person and j=> jth key.

f(i,j) = max(f(i-1,j-1), f(i-1,j), abs(p-j)+abs(j-i)). Minimum of all f(n-1,j) is the answer. What is wrong with this solution. WA test case 8.

Use fenwick tree to calculate how many items are left in each prefix. You simulate the algorithm in the problem statement using this.

This picture might help you:

Think of elements being removed in rounds.If an element is removed at ith round then it has been looked up exactly i times.We can maintain total elements remaining to remove and add this to the answer at the beginning of the round.It can be done without fenwick trees.Code

Well, splay is absolutely INTERESTING

Anyway, I will try.

Let's consider the dp array, dp[i][j] denotes the number of ways to get j non-intersecting paths in an annoying graph with height i as the promblem shows in the description, it seems that j can be as large as 1<<i , but never mind. Let's see what are the transitions first.

Now assume we've got all the dp[i-1][x], how can we make it to dp[i][x]? First enum how many paths we have in the left and right child, let's call them l and r. There are 5 types of transitions.

num = dp[i-1][l]*dp[i-1][r]

1. Take the root, and make itself a new path ----> dp[i][l+r+1] += num
2. Don't take the root ----> dp[i][l+r] += num
3. Take the root, and connect it to a path in the left child ----> dp[i][l+r] += num*l*2
4. Take the root, and connect it to a path in the right child ----> dp[i][l+r] += num*r*2
5. Take the root, and it combines two paths ----> dp[i][l+r-1] += num*C(l+r,2)*2

Now the interesting thing is, every time we go from i to i+1, we can only decrease the number of paths by 1, which means that j>k in the dp[i][j] is totally useless, it won't affect the final answer dp[k][1], so the complexity will be O(k^3) which is enough to pass the test.

Wish my poor English hadn't make it too hard to understand :D.

traslated text (still no idea what this means):

Firstly, we note that the operation "put under the bottom of the deck" is tantamount to "starting from the beginning when the deck ends," without shifting the cards anywhere.

Next, we will process all the cards with the same numbers at a time, obviously, Vasily will postpone them one by one. Suppose, at the moment when he laid out all the cards smaller than x, he was in some position p in the deck. Then two cases are possible.

If all the cards equal to x are later than the p position, then he scans all the cards until the last card x, and puts all x equal; Otherwise, if there is a card equal to x before p, it will first scan all the cards to the end of the deck, and then — all the cards from the beginning of the deck to the last card, equal to x, going to position p. Both cases are easy to process, if for each number write out all the positions of cards with such a number in ascending order. In addition, you need any data structure that allows you to count the amount on a segment and change it at a point, for example, if you store for each position 1, if the card is still in the deck, and 0 otherwise. For example, a tree of segments or Fenwick tree

Actually, it can be solved much easier using two pointers: firstly, let's store the array of sets of the positions of some element x, so it would be something like this: in the array Pos the key is the card value, and value is set of the positions of this element. Also let's maintain a set of values(we will name it "values"), which are still left in our array. So now we do the following: while not values.empty(), we look to the last position of the minimum element in the array (*values.begin()) , and look to the next element in the "values". And if the last position of the minimum element in the "values" set is greater, than last position of the next element in "values" set(we can determine it with O(log n) complexity, using the lower_bound function), than we know, that after deleting the last element (*values.begin()) in the array we can not delete anything else, because the next element after *values.begin() always stands leftside from the current minimum element. So the size of the array decreases only by the size of Pos[*values.begin()].size(). If not so(if the last position of the minimum element in the "values" set is less, than last position of the next element in "values" set), than also with the lower_bound function we determine the first position of the next element in "values", that is greater, than the last position of the current minimum element in the array, and after getting the iterator on this element we start deleting all the positions from the set, that are greater, then the last position of minimum element.And we can see the case (ex.: 1 1 1 2 2) that after deleting the minimum element(x = 1) we can also delete all elements that are becoming minimum after x(in this example after deleting 1 we can delete all 2 elements), so we now with only one iteration through array we can delete more than one kind of elements, so we derease our length of array by the size of Pos[x].size() minimum elements x, that we can delete entirely, and by the amount of positions of the last minimum element we could not delete entirely. And before each iterartion we add the current size of the array. That's all:)

Sorry if the explanation is some kind of vague, feel free to ask questions. Here is my code: 28526786

lets divide all man in 2 groups : left men and right man(if their poitions is right or left from office). It is obvious, that the "right" people should go right to the office and take all the keys on their way, it is true for the "left" people also. Of course we can face the situation , that the amount of keys on the way right to the office is to small, so each "right" man can take the next key to the right that is not take or, the next key to the left(if he will skipp one key, the overall distance will only increase).That is absolutely true for the "left" man too. So you can see that it should really be a continuous sequence. If you have any questions, feel free to ask. I hope thois will help you

I think intuitively, you could start by proving that what if the people did not take consecutive keys? If there was a key that was not used by anyone and the key is between two "continuous key parts", would it be better for someone to choose the key instead? In essence, proving by contradiction may be a good start.

To avoid their repetitions.

Could you please explain it in a clearer way?

I understand all your analysis, but when it comes to your code I got screwed up.

Your code works if all the cards all unique. This is because you are sorting them based on value. But what if some values are repeated ?. If you have two values which are equal to minimum and they are left and right of the card removed, you should consider the right one, which you cant guarantee by sorting.

Instead try finding minimum in left half and right half separately using seg tree. Code

There are only at most 2000 score changes, so you have at most 2000 initial score to check

Answer: change treeSet to hashSet

Can you please explain how the solution works ? What is the state represented by dp[i] ?

Why it is optimal to take a continuous sequence of keys as mentioned in the editorial ? "To solve this problem you need to understand the fact that all keys which people will take is continuous sequence of length n in sorted array of keys."

You can use a 2D DP to solve this, see my submission its pretty intuitive.

Link to my submission.