Maximum Subsequence Value (Codeforces 1365E)
Tags: Others, brute force

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: 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: Print a single integer — the maximum value Ashish can get by choosing some subsequence of $$$a$$$.

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$$$.

Sample Inputs:
3
2 1 3

3
3 1 4

1
1

4
7 7 1 1

Sample Outputs:
3

7

1

7

Solution (Python):
import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
    return sys.stdin.buffer.readline().decode('utf-8')

def main():
    from functools import reduce
    from operator import or_
    n = int(input())
    if n < 3:
        print(reduce(or_, map(int, input().split())))
        exit()
    mask = (1 << 30) - 1
    (upper, lower) = (array('i', [0]) * n, array('i', [0]) * n)
    for (i, x) in enumerate(map(int, input().split())):
        upper[i] = x >> 30
        lower[i] = x & mask
    (ans_upper, ans_lower) = (0, 0)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if ans_upper < upper[i] | upper[j] | upper[k] or (ans_upper == upper[i] | upper[j] | upper[k] and ans_lower < lower[i] | lower[j] | lower[k]):
                    (ans_upper, ans_lower) = (upper[i] | upper[j] | upper[k], lower[i] | lower[j] | lower[k])
    print((ans_upper << 30) + ans_lower)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
best = 0
if n <= 3:
    for i in A:
        best = best | i
else:
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            temp = A[i] | A[j]
            for k in range(j + 1, n):
                best = max(best, temp | A[k])
print(best)

Solution (Python):
from collections import defaultdict
import sys
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
    return int(buff_readline())

def read_int_n():
    return list(map(int, buff_readline().split()))

def read_float():
    return float(buff_readline())

def read_float_n():
    return list(map(float, buff_readline().split()))

def read_str():
    return readline().strip()

def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)

def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()
        error_print(e - s, 'sec')
        return ret
    return wrap

class UnionFind:

    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda : 1)
        self.__rank = defaultdict(lambda : 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False
        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for (k, v) in self.__table.items():
            if k == v:
                g += 1
        return g

def slv(N, A):
    A.sort(reverse=True)
    ans = 0
    for i in range(N):
        t = (1 << A[i].bit_length()) - 1
        ans = max(ans, A[i])
        for j in range(i + 1, N):
            b = A[i] | A[j]
            ans = max(ans, b)
            for k in range(j + 1, N):
                ans = max(ans, b | A[k])
    return ans

def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))
if __name__ == '__main__':
    main()