vatsal's blog

By vatsal, history, 8 years ago, In English

How do I solve problem F from Atcoder Regular Contest 68? Can anyone please explain me in details? The editorial for the problem is long so I think it might be detailed but I don't understand that language(Japanese).

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
8 years ago, # |
Rev. 4   Vote: I like it +13 Vote: I do not like it

I used dynamic programming to solve it. My DP state is (i, left, okay). Basically I start from N and go downwards. I need to select k elements from N to 2, and partition them into 2 decreasing sequences (which represent the two ends of the deque surrounding the element 1 after all elements are inserted into the deque).

i denotes the integer I will consider next. left denotes the number of integers > i, which are not used till now, and can be added to the second sequence when needed.

I have 2 choices for i. If I add it to the first sequence, I go to state (i-1, left, true), and if I skip it (and maybe add it later to second sequence), I go to state (i-1, left+1, false). The boolean variable takes care of overcounting. Basically I add some element to the first sequence, then some (maybe 0) elements to the second sequence and the process repeats.

After 1 has been put in kth position, the remaining n-k elements can be fixed in ways[n-k] ways. This is based on the recurrence, T(1)=1, T(n)=2*T(n-1). If you have some z elements to assign, you can choose either the right or left end of the deque and repeat the process for z-1 values.

Maybe this explanation is not quite clear. You can look at the code for hopefully understanding it better. :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Nice :) Thanks I wonder how you get the intuition for DP problems right away.