Let me start with “note that”.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | Petr | 146 |
10 | SecondThread | 144 |
Let me start with “note that”.
As known, 1720D1 - Xor-Subsequence (easy version) has an ambiguous descriptioin. I'm the one of those who got misled during the contest. However, the misunderstood problem is solutable. Let's have a look.
It is the misunderstood version of the problem. The only difference is that in this version $$$b_i$$$ do be the subsequence of $$$a$$$, where any $$$b_i$$$ is an element of $$$a$$$. Note that $$$a_i<200$$$ remains true.
How to use the property of $$$a_i<200$$$?
Consider pair $$$(b_p, a_{b_p})$$$. Many of them are the same.
How to efficiently find the next possible $$$b_j$$$ after the current $$$b_i$$$?
It's noticed that the number of distinct pair $$$(b_p, a_{b_p})$$$ is limited. What's more, such number is $$$200$$$ instead of $$$200^2$$$.
Therefore, we can compute whether placing $$$j$$$ after $$$i$$$ is valid by checking if $$$j \oplus a_i < i \oplus a_j$$$. The complexity of this part is $$$\mathcal O(n^2)$$$.
After knowing all possible pair $$$(i,j)$$$ that $$$j$$$ can be the nect value placed after $$$i$$$. We come up with a $$$dp$$$ like:
However, simly applying this would make an $$$\mathcal O(n^2)$$$ complexity in the worst case. It doesn't take advantage of the former derivation at all!
Try to dp by updating the following $$$f$$$. An observation is that for two indexes $$$i<j$$$ that has $$$a_i = a_j$$$, we only need to update the value of $$$f_i$$$, since their $$$x,a_x$$$ pair are exactly the same. A sequence ending at $$$i$$$ is definitely not worse than the same sequence ending at position $$$j$$$. In a word, we only need to update at most $$$200$$$ position of $$$f$$$ that has different $$$a$$$ value.
How to find these $$$200$$$ indexs? A solution is to binary search in the $$$200$$$ arrays of the indexs that has the same $$$a$$$ value, formally $$$S_i={x|a_i=x}$$$. Assume we are trying to update the dp array with $$$f_i$$$, if putting $$$y$$$ after $$$a_i$$$ is valid(prrproccessed before), then we upper_bound an smallest $$$j$$$ in $$$s_y$$$ that satisfies $$$j>i$$$ and update $$$dp_j$$$ with $$$dp_i+1$$$. This time complexity of this solution $$$O(n \times 200 \times \log n)$$$, which may not pass the $$$2$$$ seconds time limits.
We can see that after we have processed $$$dp_j$$$, the $$$j$$$ in the set $$$S_{a_j}$$$ is no longer useful. If we applied some linear data structure that support removing the front element, which can a queue or a pointer pointing at the last valid index, we can have a $$$\mathcal O(200n)$$$ solution.
However, I had no idea how to solve the misunderstood D2. Could anyone help me?
Название |
---|