PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rudra_1232
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You have X ones and Y twos. X and Y are both even.
Find the lexicographically smallest palindrome that can be formed using them.
EXPLANATION:
Let S be the final string, and S_i denote its i-th character.
Let L = X + Y denote the length of S.
When aiming to lexicographically minimize a string, it’s by definition optimal to attempt to make its first character as small as possible, then the second character, then the third, and so on.
So,
- Try to make the first character, S_1, equal 1. This is possible only when X \gt 0.
However, S must be a palindrome, so this necessitates making the last character also 1, i.e. set S_{L} = 1.
This reduces X by 2. - Next, try to make S_2 = 1, which in turn makes S_{L-1} = 1.
After that, try with S_3, S_4, \ldots (which will in turn fix S_{L-2}, S_{L-3}, \ldots). - When you run out of ones, all the remaining characters are forced to be 2's.
Simple analysis of this process shows that the first and last \frac X 2 characters will this be ones, and everything else will be twos.
So, the answer is to simply print \frac X 2 ones, then Y twos, and then \frac X 2 ones again.
TIME COMPLEXITY:
\mathcal{O}(X+Y) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y = map(int, input().split())
print('1'*(x//2) + '2'*y + '1'*(x//2))