I thought that the hard problem (Q4) from last week's contest was pretty interesting. I wasn't able to participate in the contest live, but I figured I'd share my thoughts on the problem, and eventually that turned into describing how I approach difficult problems in general. To be clear, I define a "difficult problem" to be any problem whose optimal solution doesn't immediately appear to me when I'm done reading it.
Here are the general steps I tend to follow when solving a difficult problem, and the reasons why I think those steps shouldn't be excluded:
- Try to reduce the problem to an easier, or equivalent problem
a. This is a classic tactic for solving math problems that also often works on hard programming problems. If the problem is asking you to do A, but you can also solve it by doing B instead and B is easier than A, then it might be worth doing B instead.
i. Here is an easy-to-understand example of how I applied this tactic to an easier problem.
b. Even if B isn't easier to solve than A, rephrasing the problem in terms of B might make it easier to understand. It's also possible that B might not seem easier to solve at first, but it ends up being easier. - Come up with (but do not write code for) a naive solution
a. This might seem obvious, but I actually forego this step for almost every problem I solve, especially during a competition. I don't usually feel like it's a good use of time, but for harder problems, I find that it's helpful to at least throw out an unoptimized solution. This might make it easier to identify which algorithms are most suitable to speed up the solution.
b. If you're not used to solving hard problems, then writing out the naive solution may actually be helpful to you. - Optimize
a. This might sound anti-climactic since it can mean so many different things, but at this point, you're in a good position to turn your simple but intractable solution into a better one.
b. Most optimizations can be presented as an answer to the following question: "What unnecessary operations are you doing, and how can you eliminate them without making your solution incorrect?" A more helpful way to phrase this is "In your naive solution, what information is available to you that you aren't taking advantage of?"
Let's look at last week's hard problem to serve as an example. Go read the problem, and try solving it before reading on if you want.
Brute-force solution (simulation)
The simplest way to approach most problems is to simply simulate exactly what they're asking for. Luckily, this problem lets us do just that. For each subarray, create a copy of the subarray, sort it, and count the number of indices i for which a[i] > a[i+1] + 1. The answer is the sum of all of these counts.
To calculate the time complexity of this approach, think about the number of iterations we're doing, and the type of work that we're doing at each iteration. We have O(N^2) subarrays, which we consider all of, and sorting the subarray will incur O(Nlg(N)) complexity at each iteration. So, we multiply these to come up with a complexity of O(N^3lgN) overall. Unfortunately, this will obviously not pass, even with the relatively low n <= 1000 constraint.
Before moving on, think about how we'd answer the question that I posed in 3b above: what information are we not taking advantage of here?
Optimizing by identifying reusable information
The correct answer to the above question, or at least the answer that led me to a tractable solution, is that we don't need to individually sort each subarray. In other words, when we have a sorted subarray on indices [i, j], we can use it to handle the subarray on [i, j + 1].
When we add element j + 1 to the array, it may add an imbalance value to the new subarray. However, for the elements already in the subarray, only the imbalance status of the element to the left of a[j + 1]'s sorted position can end up changing. So, if we use a structure that maintains sorted order for its elements, then for each subarray's starting index i, we can use the same structure to get the imbalance value for all j on [i, n), only modifying the value of the element before it if applicable. These structures are a set in C++, TreeMap in Java, or SortedList in Python; the former two are implemented using a self-balancing binary tree.
Inserting into any of these structures is generally O(lgN) time, which means our time complexity is reduced to O(N^2lgN), which is feasible for n <= 1000. I would be careful if you're using Python, though - this language is notorious for occasionally timing out when other languages pass. Here's the code:
int sumImbalanceNumbers(vector<int>& nums) {
int ret = 0, n = nums.size();
for (int i = 0; i < n; i++) {
set<int> os;
int imbalance = 0;
for (int j = i; j < n; j++) {
int el = nums[j];
auto it = os.lower_bound(el);
// if this element is already in the set, we don't gain or lose any imbalance
if (it == os.end() or (*it) != el) {
if (it != os.end()) {
// do we gain any value from this new element?
if ((*it) > el + 1)
imbalance++;
}
if (it != os.begin()) {
// do we gain or lose any value from the previous element?
set<int>::iterator previous = prev(it);
if ((*previous) == el - 1 and it != os.end())
imbalance--;
else if ((*previous) != el - 1 and it == os.end())
imbalance++;
}
os.insert(el);
}
ret += imbalance;
}
}
return ret;
}Optimizing by rephrasing the problem
There's actually an even more efficient solution to this problem, which I arrived at by reducing the problem to something easier to calculate (my implementation beat 97% of other C++ solutions by runtime). This post is already a bit too long though, so I think I'll hold off on explaining it for now. Let me know if you'd be interested in a part 2 for that, and feel free to ask any questions in the comments.