2018 ICPC Asia Singapore Regional Contest


2018-12-13 01:00 UTC

2018 ICPC Asia Singapore Regional Contest


2018-12-13 06:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -158 days 17:31:45

Time elapsed


Time remaining


Problem D

Barr the Bear is playing the game Bits with Swanky Shen!

Bits is a very simple game. At the start, a circle of $N$ non-negative integers $A_1$, $A_2$, $A_3$, $\ldots $, $A_ N$ is shown to both players. That is, to the left of the integer $A_ i$ is the integer $A_{i-1}$ if $i > 1$; and the integer $A_ N$ otherwise. To the right of the integer $A_ i$ is the integer $A_{i+1}$ if $i < N$; and the integer $A_1$ otherwise. Also an integer $K$ is given to both players.

To win this game, one must divide the circle of integers into exactly $K$ contiguous non-empty sections, such that the bitwise AND of the powers of all sections is maximized. The power of a contiguous section of integers is the bitwise OR of all integers in that section.

Barr the Bear is lazy and knows that you are wise with bits. Hence, he has hired you to help him to win the game!

Note: The binary bitwise operators OR and AND operate on the base-$2$ representation of the integers and correspond to the operators | and & respectively in C++ or Java.


The first line contains integers $N$ and $K$ ($1 \leq K \leq N \leq 5\cdot 10^5$), namely the number of integers and the number of contiguous non-empty sections required.

The next line contains $N$ integers, the $i^\textrm {th}$ of which is the integer $A_ i$ ($0 \leq A_ i \leq 10^9$).


Output a single integer in one line: The maximum bitwise AND of the powers of the sections in an optimal division of the circle of integers.


In the first sample, the circle is $(2, 3, 4, 1)$. A possible division is $(3, 4)$ and $(1, 2)$. $(3, 4)$ has power $7$ and $(1, 2)$ has power $3$. The bitwise AND of $7$ and $3$ is $3$. Note that a section can possibly wrap around the circle.

In the second sample, a possible division is $(2, 2, 4)$, $(4)$, $(4, 2)$. The sections’ powers are $6$, $4$ and $6$ respectively, which have bitwise AND of $4$. Note that we require the sections to be contiguous integers, so the division $(2, 4)$, $(2, 4)$, $(2, 4)$ is not permissible.

In the third sample, we can only have one section. This section will have all the integers, and thus have power $3$.

Sample Input 1 Sample Output 1
4 2
2 3 4 1
Sample Input 2 Sample Output 2
6 3
2 2 2 4 4 4
Sample Input 3 Sample Output 3
4 1
0 1 2 3