PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
It’s always possible to assign objects to the items so that the maximum difference of either permutation is 1. To see this, first let’s look at a simple necessary and sufficient condition for the maximum difference along a permutation to be 1. The first and second locations visited should have opposite items, as do the third and fourth locations, the fifth and sixth locations, etc (if the number of locations is odd, then the last object doesn’t need to be paired). Consider the following graph G on locations 0, 1, …, n-1. For each of the permutations S and T, add an edge between the first and second locations, the third and fourth locations, etc.
Every node in the graph G is the endpoint of at most one edge from each permutation. This implies every cycle in G must alternate between
edges from S and edges from T. In particular, there cannot be any odd length cycles so G is bipartite. Thus, we can assign one of A or B to
each location so that no edge in G has the same object at both endpoints. Such an assignment will then have difference 1 along either
permutation. To find the lexicographically least output string, simply assign A to location 0 and propagate this assignment along the edges
of G. If there are still unassigned locations, then pick the one with least index and repeat.
It is an open problem to determine the optimum answer if there are more than two permutations.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.