Editorial for Ikea

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Split the string into adjacent fixed pairs: (0,1), (2,3), ....

For any valid assignment, each pair must contain exactly one table and one price tag. If a pair were TT or ##, both cells would need to match outside the pair, which forces an imbalance and eventually fails at an endpoint (the first and last positions only have one neighbor). So each pair is either T# or #T.

That immediately gives the answer:

T# means the table uses the tag on its right, so output R.
#T means the table uses the tag on its left, so output L.

Process all $n$ ~n~ pairs in order and append one character per pair. Time complexity is $O(n)$ ~O(n)~ besides the output string.

Solution (Python)

n = int(input())
s = input().strip()

ans = []
for i in range(0, 2 * n, 2):
    if s[i] == "T":
        ans.append("R")
    else:
        ans.append("L")

print("".join(ans))

Comments

There are no comments at the moment.