The link to the problem can be seen here: http://naipc.uchicago.edu/2017/_static/naipc2017.pdf

Basically the problem gives a list of strings of parentheses (not necessarily valid) and asks to find the length of the longest valid string of parentheses by concatenating some of the strings from the list.

I was looking at the solution here: http://www.cs.ucf.edu/~dmarino/progcontests/mysols/northamerica/2017/pieces.java

The solution involves placing the strings into a vector and then ordering them based on low (the min value of open minus closed over all intermediary characters) then diff (open minus closed) then length. Then, DP is used to find the longest length that results when concatenating a subsequence from the vector into a valid string of parentheses.

What I am confused about is why the vector can be sorted that way. This seems to imply that any set of strings that form a valid string of parentheses can be rearranged in the sorting order explained above and still form a valid set of parentheses. This seems intuitive (of course you want to have a nonnegative low value for the first string and you want a positive diff value for more open parentheses at the beginning of the string), but why does this work?

If anything I said was unclear, please let me know. Thanks!