Downvote for spamming with tags.

As fas as I understand the problem it can be solved greedily. Fistly we choose the largest element of the array. It will be the last removed element. Secondly we can find the element among the remaining elements which gives the maximum value ORing it with the first element. This element will be the penultimate element. And so on till we can't find such element. The removing sequense of the other elements is insignificant. The complexity is O(30*N).

low_kii_savage Please Help!!!

Can someone check this solution for correctness: (couldn't debug during contest but works on the corner cases that have been discussed)

Any solution will be of the following form: First remove redundant elements (elements on removing which OR doesn't change) Then remove elements that reduce the OR

Removing the redundant elements must be done in sorted (increasing order). To do this we sort the initial array. Then for each element we check if for all its set bits j there exists atleast one more element with bit j set at 1. If for any set bit this isn't true, the element is not redundant and cannot be removed. (Not sure if the increasing order part is necessary but to be on the safer side)

After this process, we are left with N<=32 elements as each element has atleast 1 bit that no other element has and there are <= 32 bits.

Now, each element has a value which is equal to the sum of the values of it's unique (not present in any other element) set bits. For eg if we have 12, 18, 17 = {01100, 10010, 10001} thus 12 has value 6, 18 has value 2 and 17 has value 1. So we remove the element with the least value, update the values of the other elements (for eg here now 18 is the only element with the first bit as set) and then take out the least value again and keep doing this.

So our solution for 12, 18, 17 is 79.

Solution for corner case: 20 — {10100} 19 — {10011} 12 — {01100} So no element here is redundant and we can skip to the 2nd part of the solution.

The values are 0, 3, 8 respectively initially. So we first remove 20. Now the values are 19 and 12 respectively. So we remove 12 and then 19. This gives us the answer 81 as expected.

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 value and the difference would be this number). Update the sets r and si by removing this deleted element, wherever present.

Can you give the link? It would be interesting to know the setter's rating.

And I was thinking that Arab Region Regionals are the worst in the world, thanks man for this blog :D

https://discuss.codechef.com/t/icpc-online-round-2019-updates/42035

Finally, they officially acknowledged that something did go wrong.