Could someone provide any hint?



Edited by author 10.06.2017 23:14

Here's a brainless but simple way i did it.

0. Mini-optimization: remove all repeated numbers, leaving only unique ones, and reduce k respectively. Let A be the array with those unique numbers.
1. Make a list of indices that point to numbers which have 1st bit 1, 2nd bit 1, ..., 32nd bit 1. Like for example: L[1..32][0..nmax], L[5][0] — amount of numbers which have 1 on 5th bit, A[L[5][1]], A[L[5][2]], ... — those numbers.
2. Main algo. Make current_result = 0. Going from higher bit to lower (i = 1..32), if list is not empty (L[i][0] > 0) and ith bit is 0 in current_result, then choose random index j, and do current_result = current_result or L[i][j]. Increase i and repeat either till you reach the last bit or reach the limit of numbers to be deleted. Then update the best reached result.
3. Spam step 2 for a certain time. I initially decided to consume entire 2s, but apparently even 200ms is enough to ac.

Clever way is DP, yeah, but requires thinking :)