PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given an odd integer N, find an array of length N such that:
- Every prefix has its bitwise AND at least as large as its bitwise XOR
- Every suffix has its bitwise AND at most as large as its bitwise XOR
EXPLANATION:
When N = 1 literally any array [x] will work, so let’s focus on N\geq 3.
There are likely several constructions possible.
One fairly straightforward way of coming up with one is to try and extend an answer for length N-2 to an answer for length N.
Let’s start with an answer for 3 — specifically, [5, 6, 3] as provided in the sample tests.
We’ll extend this to a solution for N = 5.
To that end, we use the property that x\oplus x = 0 and x\ \&\ x = x for any integer x.
Look at the array [5, 5, 5, 6, 3], i.e, insert 5 at the beginning twice.
- The prefix XORs are [5, 0, 5, 3, 0].
The prefix ANDs are [5, 5, 5, 4, 0]. - The suffix XORs are [0, 5, 0, 5, 3].
The suffix ANDs are [0, 0, 0, 2, 3].
This is thus a solution for N = 5.
It’s not hard to see that this same idea (insert two occurrences of 5 at the start) then further creates solutions for N = 7, 9, 11, \ldots, because:
- The first two prefix XORs are 5 and 0, while the first two prefix ANDs are 5 and 5.
They satisfy the inequality.
After that follows the array for N-2, which we know already follows the conditions (and starting with two occurrences of 5 changes neither the prefix XOR nor the prefix AND of this smaller array). - The two new suffix ANDs are both zero since the array for N-2 already had an AND of 0.
This is already \leq whatever the two new suffix XORs are, so that condition is satisfied too!
This gives us a pretty simple construction in summary:
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n == 1: print(45446)
else: print(*([5]*(n-3) + [5, 6, 3]))