COM_AND_CON - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: wuhudsm
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have N occurrences of string < and M occurrences of >.
In one operation, you can take two of them, say A and B, delete both A and B, and create A \circ B where \circ is one of \{<, =, >\} depending on how A compares to B lexicographically.

Find the lexicographically smallest final string after all operations.

EXPLANATION:

The final string will only contain the characters '<', '=', '>' in some order, of which '<' is the smallest.
Since we’re aiming to lexicographically minimize the final string, we’ll thus want as many copies of '<' at the beginning at possible.

Note that < will always compare smaller to any other string formed using these characters: the only exception is that it will compare equal to itself.
So, as soon as we perform any single operation - which will result in a string of length 3, say S - we can then repeatedly combine each remaining copy of <with S to obtain two more copies of < in the prefix.

For example, if we create <=< in the first move, then with another < we obtain <<<=<, another < will give <<<<<=<, and so on.

The question now is: what should our first move be?

If M = 0, i.e. there are no occurrences of > at all, then the first move is forced to be < = <, after which the process will just proceed as in the example above.
That is, when M = 0, we’ll end up with the string <<<<...<<<=<, which has 2N-3 occurrences of < and a single =, with the = appearing at the penultimate position.

If N = 0 (so there are no occurrences of <), a similar greedy strategy works: the first move is forced to be >=>, and thereafter it’s optimal to just keep combining this with an occurrence of > to its left since that’s the only way to obtain a < here (note that < is a prefix of >=>, and hence compares smaller than it).
In this case, the resulting string is <><><>...<>>=>, i.e. 2M-4 copies of <> to begin and the last three characters are >=>.

That leaves the case where N \gt 0 and M \gt 0, i.e. we have both < and >.
Here, with a bit of analysis, it can be seen that the optimal strategy is as follows:

  1. Combine a < and a > to obtain <<>.
  2. Repeatedly combine this longer string with < to its left to obtain <<<<...<<>, using up all N-1 remaining copies of <.
  3. Repeatedly combine the longer string with > to its right to obtain <<<...<<><><><>...<>, using up all remaining M-1 copies of >.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    if n == 0:
        print('><'*(m-2) + '>=>')
    elif m == 0:
        print('<<'*(n-2) + '<=<')
    else:
        print('<<'*n + '>' + '<>'*(m-1))
1 Like