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).
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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).
Name |
---|
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. :)
Nice :) Thanks I wonder how you get the intuition for DP problems right away.