Ccodeforces Contest 1991: B. AND Reconstruction
Problem
https://codeforces.com/contest/1991/problem/B
Intuition
For i <= 1 <= n -1
, we have
b[i]
=a[i] & a[i + 1]
b[i + 1]
=a[i + 1] & a[i + 2]
For the first and last element in a
, we can simply have
a[0]
=b[0]
a[n]
=b[n — 1]
since all the 0
and 1
bits sould remain after taking bitwise &
on a[0]
and a[1]
, same for a[n — 1] & a[n]
.
We can reconstruct a[i + 1]
by b[i]
and b[i + 1]
, since
- After taking the bitwise
&
ona[i]
anda[i+ 1]
, all the0
bits froma[i + 1]
will remain inb[i]
. - All the
0
bits froma[i + 1]
will remain inb[i + 1]
, after performinga[i + 1] & a[i + 2]
- So, if we take
b[i] | b[i + 1]
, we can reconstruct all0
bits froma[i + 1]
, and some1
bits. - We can then validate
a[i + 1]
, by checking ifa[i + 1] & a[i]
=b[i]
anda[i + 1] & a[i+ 2]
=b[i + 1]
. If not, it means we couldn’t reconstructa[i + 1]
fromb[i]
andb[i + 1]
, which means we have to fail fast and return-1
.
Complexity Analysis
- Time Complexity: O(n)
- Spcae Complexity: O(1)
Code
from typing import List
def main():
t = input()
for _ in range(int(t)):
n = input()
a = [0 for _ in range(int(n))]
b = [int(b_i) for b_i in input().split(" ")]
result = reconstruct(a, b)
print(*result)
def reconstruct(a: List[int], b: List[int]) -> List[int]:
for i in range(len(a)):
if i == 0:
a[i] = b[i]
elif i == len(a) - 1:
a[i] = b[-1]
else:
a[i] = b[i] | b[i - 1]
if i > 0 and b[i -1] != a[i] & a[i-1]:
return [-1]
return a
main()