Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Hints
Hint 1
Show Hint
How does one read a question to tell if it is a good candidate for the first question?Hint 2
Answer to Previous Hint
The first question always needs to have every one of its "wow..." moments matched with a prior "Idea" moment. In order to read this effectively, you can use a stack to store unmatched moments.
If at any point the stack is empty and you see a "wow..." moment, this question is not a valid candidate for the first position. The length of the stack after reading tells you how many "Idea" moments are left to close.Show Hint
Notice that there is some symmetry to this problem. The second question always needs to match any remaining Idea moments from the first question with wow... moments of its own.
As such, it might be helpful to think of the second question as "reversing" the actions of the first question, and so in determining candidates for the second question, it may be helpful to read them in reverse order of moments. How can you tell by reading a question in reverse order if it is a valid candidate for the second position?Hint 3
Answer to Previous Hint
Because we now read from right to left, we can similarly use a stack, but put "wow..." moments on the stack instead and match them with "Idea" moments as they are read. If at any point the stack is empty and you see an "Idea" moment, this question is not a valid candidate for the second position.Show Hint
Once you've done this, you know, for every question, whether it is a valid candidate for the first or second question, as well as how many unmatched moments it has (a first question candidate can only have unmatched "Idea"s, and a second question candidate can only have unmatched "wow..."s).
How can we use these numbers to determine the number of valid pairs? Maybe it makes sense to group all questions that have the same outcome? (Valid first question, leaves 3 "Idea"s, for example.)Solution
View Solution
As the hints describe, we can first figure out, for each question, whether it is a valid candidate for the first or second question (or both, if it is balanced), and how many unmatched moments it has. We can then track how many first question candidates (and, separately, how many second question candidates) have 0 unmatched moments, 1 unmatched moment, 2 unmatched moments, etc. up until possibly 
~a~ unmatched moments.
Then, we can count how many pairs make for a balanced workshop by pairing a first question candidate with a second question candidate that leaves the same number of unmatched moments. For each number of unmatched moments, the number of pairs is just the product of the two counts, and the answer is the sum of these products!
Be careful with the 0 case, however, as we don't allow the same question to be used twice. So if there are 
~c~ questions that are both valid first/second questions, then there should be 
~c\times (c-1)~ valid pairings (remove the ~c~ pairings that pair a question with itself).
As always, be careful with integer overflow, as we could be multiplying two large numbers together!
Comments