Problem with Random Tests (Codeforces 1743D)
Tags: Greedy, probabilities

You are given a string $$$s$$$ consisting of $$$n$$$ characters. Each character of $$$s$$$ is either 0 or 1.A substring of $$$s$$$ is a contiguous subsequence of its characters.You have to choose two substrings of $$$s$$$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:  let $$$s_1$$$ be the first substring, $$$s_2$$$ be the second chosen substring, and $$$f(s_i)$$$ be the integer such that $$$s_i$$$ is its binary representation (for example, if $$$s_i$$$ is 11010, $$$f(s_i) = 26$$$);  the value is the bitwise OR of $$$f(s_1)$$$ and $$$f(s_2)$$$. Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.

Input: The first line contains one integer $$$n$$$ — the number of characters in $$$s$$$.The second line contains $$$s$$$ itself, consisting of exactly $$$n$$$ characters 0 and/or 1.All non-example tests in this problem are generated randomly: every character of $$$s$$$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $$$\frac{1}{2}$$$.This problem has exactly $$$40$$$ tests. Tests from $$$1$$$ to $$$3$$$ are the examples; tests from $$$4$$$ to $$$40$$$ are generated randomly. In tests from $$$4$$$ to $$$10$$$, $$$n = 5$$$; in tests from $$$11$$$ to $$$20$$$, $$$n = 1000$$$; in tests from $$$21$$$ to $$$40$$$, $$$n = 10^6$$$. Hacks are forbidden in this problem.

Output: Print the maximum possible value you can get in binary representation without leading zeroes.

Note: In the first example, you can choose the substrings 11010 and 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, their bitwise OR is $$$31$$$, and the binary representation of $$$31$$$ is 11111.In the second example, you can choose the substrings 1110010 and 11100.

Sample Inputs:
5
11010

7
1110010

4
0000

Sample Outputs:
11111

1111110

0

Solution (Python):
n = input()
s = int(input(), base=2)
t = s
for i in range(1, 9):
    t = max(t, s | s >> i)
print('{0:b}'.format(t))

Solution (Python):
n = input()
s = int(input(), base=2)
t = s
for i in range(1, 10):
    t = max(t, s | s >> i)
print('{0:b}'.format(t))

Solution (Python):
n = input()
s = int(input(), base=2)
t = s
for i in range(1, 50):
    t = max(t, s | s >> i)
print('{0:b}'.format(t))