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!
↵
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.
↵
