PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array A with elements in [0, 2].
You can swap two adjacent elements as long as their sum doesn’t exceed 2.
Find the lexicographically smallest final array.
EXPLANATION:
Swapping adjacent elements when they’re equal is pointless, so we don’t consider that at all.
Since our elements are in [0, 2], when swapping different elements we have only three options:
- Swap 0 with 1.
0+1 = 1 \le 2, so this is allowed. - Swap 0 with 2.
0+2 = 2 \le 2, so this is allowed. - Swap 1 with 2.
1+2 = 3 \gt 2, so this is not allowed.
So, really the only thing we can do is swap a 0 with some other element.
That is, we can freely move zeros around in the array, while everything else is fixed in place.
Our aim is to lexicographically minimize the result, and so clearly it’s optimal to just move all zeros to the start.
Thus, the solution is to place all zeros at the start, and then all the 1’s and 2’s in the same order that they were present in the input array.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
big = []
for x in a:
if x > 0: big.append(x)
ans = [0]*(n - len(big)) + big
print(*ans)