Life In 19x19

Similar to what peti said about Problem C: I've made so much incremental progress in formulating it as a DP problem, but still I'm running out of time at test case 34 ...

Problem B: after my initial naive approach I decided to cut the string to n pieces (n going 2,3,4,5...) and see if the pieces are identical. If yes, take the piece, drop everything else and start again. At the end multiply the result according to the pieces dropped (i.e.: if I find that cutting to 3 works and then cutting that 1/3 to 2 pieces again works, the multiplier is 6).
What was the final realization for me is that I only needed to check for prime number n-s (as there is no way a string can have 4 repetition when there is no 2). This I found a bit absurd because there is knowingly no quick way to check for primes. Still my clumsy naive implementation of prime number checking yielded the key to solve this problem.

Problem C: at first I implemented a huge recursive multi level loop to evaluate every permutation (so that order matters) of selected k items (where k is 1 to count of all items). The "))((" test case item really freaked me out and I'm so glad that it was among the examples.
Then later I came up with a formula that allowed me to verify a set of selected k items without trying all the permutations but I still needed to try out all possible sets of k items (where k is 1 to count of all items).
I then added a few optimizations (e.g. going with k from count of all items down to 1 and exiting if for whatever k I found a working set). I also noticed that I can freely drop items that (evaluating from left to right) never have fewer '('-s than ')'-s and have equal number of '('-s and ')'-s as I can always append them without ruining the balance. So I dropped them and added their length to the solution.
But then I was still running out of time on test case 3. I added a few more early checks (return 0 if every item has more '('-s than ')'-s or the other way around), improved my naive "get k of n in every permutation" loop, but then I ran out of ideas. The .net fiddle page started freezing on me, and it was 2:30AM so I called it a day, but I'm very curious what I could have missed.

There's a well-known algorithm to generate a list of primes in advance.

My optimization was to factor the length of the input string and then only check substrings that were equal in length to one of the factors. I didn't check in advance, but the maximum number of factors of a number n can be given by the equation 2**(1.5379 * (log(n)/log(log(n)))), which comes out to a max of 4457 factors at the test case limit of 2 million. The average case will be smaller, but even in the worst case that's not too many cases to check in the allotted time.

Like peti29, I implemented a recursive backtracking solution that worked on small data sets but didn't handle the test input. That's actually not surprising.
A lot of problems in programming competitions like this seem like they can be solved with backtracking, but that is almost always the wrong approach. Backtracking is generally O(n!), which blows up the problem space very, very quickly unless you can find a way to severely prune the search tree. I could prune the tree significantly for the average case, but I'm sure the test cases included adversarial input designed to foil most common pruning strategies.

I suspect that there is a numeric solution that doesn't involve ordering the strings at all. I have some idea of the proper data representation (all you need to know about each string is the number of unmatched open parentheses, the number of unmatched closed parentheses, and the length of the string), and some important simplifications (the total number of open and closed parentheses must match, any substrings that consist of matched parentheses can add their length to the solution without further impacting the search space), but I never had the flash of insight that usually accompanies the discovery of the proper algorithm.