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 | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
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.