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!

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).There's a good amount of discussion on this here: http://mirror.codeforces.com/blog/entry/51201?#comment-354638.