Incorrect Tutorial Approach That Gets AC

Revision en1, by super_4004, 2025-12-18 21:27:38

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English super_4004 2025-12-18 21:28:14 9
en1 English super_4004 2025-12-18 21:27:38 1023 Initial revision (published)