THIS TESTCASE WILL FAIL HALF OF THE SOLUTION FOR PROBLEM SUMOR:
1
3
20 12 19
20|12|19 = 31
12|19 = 31
19 = 19
31+31+19 = 81
THE correct answer is 81.
testcase are weak for this question. @admin . there are lot many solution which gives 79 and still passes the testcases.
Our solution gave WA during the contest but I’m pretty sure the logic was correct. First of all remove zeros from the array and add the or of the array c+1 times in the answer (c=count of zeros). Keep 30 sets, such that si stores the numbers that have ith bit set. Also create a set ( r ) that has all the elements left.
We do this operation n-c times -
Create a set (nr) of non-removable elements, which stores the numbers that will decrease the value of or, if removed from the array. All the elements present in the sets (si) that have size 1 will come in this set. Now, iterate in the set r and select the smallest element which is not present in nr and remove it, if you find one (this won’t decrease the or value). If not then remove the smallest element from the nr set (this will decrease the or and the difference would be this number). Update the sets r and si by removing this deleted element, wherever present.
The algorithm works for all the cases, but still we got WA. Can the ICPC officials please look into this issue and remove this problem or rejudge the solutions? @admin This is absolutely unfair for teams like us.
If any bit has only one element that has this bit set, then removing this element will decrease the or value as all the other elements have 0 in this bit. So the nr set will have elements from the sets(si) that have size 1.
@admin even I was trying the same approach as @hitesh_0301 mentioned and I too got WA. This will affect many deserving teams. Please look into it. Either remove this problem or rejudge all solutions.