Let me start with “note that”.
# | 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 |
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?
Name |
---|