Too late to notice I believe (it has already been 3 years), and very aware there could be a possibility I am wrong (but would still like to make the statement).
I believe Problem B Gardener in div. 2 843 And the Array's tutorial is incorrect and that test cases might be lacking.
Through simple observation, I noticed that the case
1
3
2 1 2
2 1 4
3 1 2 3
should return a NO not a YES (the tutorial solution returns YES). That is since although all bits in the third number exist at least twice in numbers in the rest of the array, the sub-sequence cannot be formed as 2 other numbers have exclusive bits. In other words, trying to OR them will result an extra bit that is not in the third number. Other configurations can also be proven to not work.
I was not planning on writing a blog post about this. However, I believe that many AC solutions (including mine) use the same tutorial approach.
Auto comment: topic has been updated by super_4004 (previous revision, new revision, compare).
Yes is the correct answer, the two subsequences $$$(a, b)$$$ are $$$([1, 2, 3], [2, 3])$$$
$$$f(a) = (2^1 + 2^2) | (2^1 + 2^4) | (2^1 + 2^2 + 2^3) = 2^1 | 2^2 | 2^3 | 2^4$$$
$$$f(b) = (2^1 + 2^4) | (2^1 + 2^2 + 2^3) = 2^1 | 2^2 | 2^3 | 2^4$$$
In other words a subsequence containing all numbers, and another containing all but the fist
I see. I completely forgot that I can include the same index in both sets. I thought it wasn't allowed since it says
Two subsequences are considered different if the sets of indexes of their elements in the original sequence are different, that is, the values of the elements are not considered when comparing the subsequences.`I assumed here that this must mean that all indices must be different (indices cannot be reused).
Thank you for the clarification!