Insights

  1. Obviously, the global max and min value will appear in the final formula.

  2. When global min is red, we need to paint all smaller value in each bag red to minize red max, this also anchors blue max to the global max and max the blue min => since it is the bigger of each bag already => i.e., it must be optimal

  3. From now on, we try checking all locally optimal solutions, classified the rank of red min, and the globally optimal solution would be the best of the locally optimal solutions.

  4. When the globally second smallest value is in the same bag as globally min value, we must paint global min to blue, which is exactly same case as 2)

  5. When the globally second smallest value is not in the same bag as the globaly min value, the optimal solution is exactly same as case 2, except that for the globally min pair, we paint global min as blue, and its counter part is red

  6. Therefore, we can check all locally optimal points one by one, by doing such flipping, and increase the possible rmin values. Notice that this impliies both the max value and min value will be blue in these classes

This turned out to be a very hard problem for me to solve. The second try gives WA too!!!