Maximum Subsequence Value
Contest: Codeforces Round 648 (Div. 2)
Difficulty rating: 1900
Tags: brute force, constructive algorithms

Ridhiman challenged Ashish to find the maximum valued subsequence of an array $$$a$$$ of size $$$n$$$ consisting of positive integers.

The value of a non-empty subsequence of $$$k$$$ elements of $$$a$$$ is defined as $$$\sum 2^i$$$ over all integers $$$i \ge 0$$$ such that at least $$$\max(1, k - 2)$$$ elements of the subsequence have the $$$i$$$-th bit set in their binary representation (value $$$x$$$ has the $$$i$$$-th bit set in its binary representation if $$$\lfloor \frac{x}{2^i} \rfloor \mod 2$$$ is equal to $$$1$$$).

Recall that $$$b$$$ is a subsequence of $$$a$$$, if $$$b$$$ can be obtained by deleting some(possibly zero) elements from $$$a$$$.

Help Ashish find the maximum value he can get by choosing some subsequence of $$$a$$$.

Input format:
The first line of the input consists of a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of $$$a$$$.

The next line consists of $$$n$$$ space-separated integers — the elements of the array $$$(1 \le a_i \le 10^{18})$$$.

Output format:
Print a single integer — the maximum value Ashish can get by choosing some subsequence of $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, Ashish can pick the subsequence $$$\{{2, 3}\}$$$ of size $$$2$$$. The binary representation of $$$2$$$ is 10 and that of $$$3$$$ is 11. Since $$$\max(k - 2, 1)$$$ is equal to $$$1$$$, the value of the subsequence is $$$2^0 + 2^1$$$ (both $$$2$$$ and $$$3$$$ have $$$1$$$-st bit set in their binary representation and $$$3$$$ has $$$0$$$-th bit set in its binary representation). Note that he could also pick the subsequence $$$\{{3\}}$$$ or $$$\{{2, 1, 3\}}$$$.

For the second test case, Ashish can pick the subsequence $$$\{{3, 4\}}$$$ with value $$$7$$$.

For the third test case, Ashish can pick the subsequence $$$\{{1\}}$$$ with value $$$1$$$.

For the fourth test case, Ashish can pick the subsequence $$$\{{7, 7\}}$$$ with value $$$7$$$.

Example input:
3
2 1 3

Example output:
3

Example input:
3
3 1 4

Example output:
7

Editorial:
Key Idea:
For subsets of size up to $$$3$$$, their value is the bitwise OR of all elements in it. For any subset $$$s$$$ of size greater than $$$3$$$, it turns out that if we pick any subset of $$$3$$$ elements within it, then its value is greater than or equal to the value of $$$s$$$!
Solution:
Let $$$k$$$ be the size of the chosen subset. For $$$k \le 3$$$, $$$\max(k - 2, 1)$$$ is equal to $$$1$$$. This implies that their value is equal to the bitwise OR of all the elements in it (since we need to add $$$2^i$$$ for all $$$i$$$ such that at least $$$1$$$ element in the subset has $$$i$$$-th bit set in its binary representation).
Consider any subset $$$s$$$ of size $$$k \gt 3$$$. Let $$$i$$$ be any number such that the $$$i$$$-th bit is set in at least $$$k - 2$$$ elements of $$$s$$$. If we pick any $$$3$$$ elements of this subset, then by Pigeonhole principle the $$$i$$$-th bit would also be set in at least one of these elements! If this is not true then the there are $$$3$$$ elements in $$$s$$$ which do not have the $$$i$$$-th bit set, which is not possible.
So for any subset $$$s$$$ of size greater than $$$3$$$, its value is less than or equal to the value of any subset consisting of $$$3$$$ elements from $$$s$$$. Hence, we only need to check all subsets of size up to $$$3$$$.
Time complexity: $$$O(n^3)$$$