PROBLEM LINK:
Author: Ram Agrawal
Tester: Riddhish Lichande
Editorialist: Prathamesh Sogale
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Greedy, Math, Bitmasking
PROBLEM:
A sequence of positive integers x_1,x_2,…,x_n is valid genesis sequence if for all i from 1 to n−1 all ones (of binary representation) in x_i are in the places of ones (of binary representation) in x_i+_1 (in other words, x_i&x_i+_1=x_i, where & denotes bitwise AND). If n=1 then the sequence is considered valid as well.
For example, the following sequences are valid:
[5,13,29,349] — in binary it’s [101_2,1101_2,11101_2,101011101_2];\
[12] - in binary it’s [1100_2];
The following sequences are not valid:
[3,4,6] — in binary it’s [11_2,100_2,110_2];
[5,3,0] — in binary it’s [101_2,011_2,0_2];
[1,3,4,6] — in binary it’s [0001_2,0011_2,0100_2,0110_2];
Consider two sequences of positive integers a_1,a_2,…,a_n and b_1,b_2,…,b_n. Let’s call this pair of sequences co-genesis if the sequence $a_1$⊕$b_1$,$a_2$⊕$b_2$,…,$a_n$⊕$b_n$ is valid where ⊕ denotes bitwise XOR.
You are given a sequence of integers a_1,a_2,…,a_n. Find the lexicographically minimal sequence b_1,b_2,…,b_n such that sequences a_i and b_i are co-genesis.
The sequence x_1,x_2,…,x_n is lexicographically smaller than the sequence y_1,y_2,…,y_n if there exists 1≤k≤n such that x_i=y_i for any $1$≤$i$<k but x_k<y_k.
EXPLANATION:
In order to build lexicographically minimal co-growing with x_i sequence, it is enough to build its elements iteratively, beginning from y1 and minimizing the ith element assuming that y1,…,yi−1 have already been found.
Assign y1=0. According to the statement, all elements of the sequence are non-negative, so y1 cannot be less than zero. It turns out that yi=0 is the minimal possible first element. The existence of an answer with y1=0 follows from the construction algorithm described below.
Let’s use mathematical induction and construct yi under the assumption that all the previous elements of the sequence have already been constructed. In order to satisfy the condition for the growth of the final sequence, the number xi⊕yi must contain one bits at all places (but not necessarily limited to them), on which there are one bits in the number xi−1⊕yi−1 . Let’s denote xi−1⊕yi−1 for t and find out what bits can be in yi to satisfy this condition:
- If in t stands 0 bit then independently from xi in yi at the same spot we can place any bit because there is no limit on the corresponding bit in xi⊕yi;
- If in t stands 1 bit and in xi — 0 then the corresponding bit in yi should be equal 1, so that in xi⊕yi the corresponding bit also equals one;
- If in tt and in xixi stands 11 bit then in y1 should be 0 bit at the corresponding place for the same reasons.
The bit transformation described above can be given by the expression yi=(t|xi)⊕xi. Indeed, this expression gives us bit ‘one’ at the fixed position if and only if at that place in t stands 1 bit and in xi stands 0 bit. For the full solution, it remains only to apply this formula in a loop from 2 to n.
SOLUTIONS:
Setter's Solution
def f(x, y):
return x & ~y
t = int(input())
for tt in range(t):
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(1, n):
ans[i] = f(ans[i - 1] ^ a[i - 1], a[i])
print(" ".join(map(str, ans)))
Editorialist's Solution
def f(x, y):
return x & ~y
t = int(input())
for tt in range(t):
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(1, n):
ans[i] = f(ans[i - 1] ^ a[i - 1], a[i])
print(" ".join(map(str, ans)))