Challenge Problem #1
The sorting problem
This article is the first one of its kind, where I’ll go through solutions to challenges at the end of my articles. For this one, the source is this article below.
Be sure to attempt the challenge here if you haven’t already. And let me know if there’s an alternative solution you have :)
Summarised problem description
There are c contests. Submitting a problem to contest i gives satisfaction s[i]. However, the minimum quality of the solution must be m[i]. There are p problems that can be submitted. Problem j has quality q[j] and preparing it for submission will cost d[j] satisfaction.
Each problem can be submitted to exactly one contest, or not submitted at all. What is the maximum achievable satisfaction?
Breaking down the problem
Let’s simplify the question first.
There are several problems that Stuart (the guy in the problem btw) can submit. Each problem costs some satisfaction, but also gives some satisfaction in return. Also, each problem has a quality that determines which contest it can be submitted to.
Observations
When solving such a problem, it helps to make some observations.
First, we know that he can choose any contest to submit each problem to. Therefore, it always makes sense to submit this problem to the contest that gives the highest solution.
So let’s say I’m currently at some problem j.
For every contest i where m[i] <= q[j] I can submit my solution
Of these contests, choose the one where s[i] is the greatest
I get net satisfaction s[i] - d[j]
If this net satisfaction is negative, I choose not to submit the problem to any contest at all. Otherwise, I will submit it.
The naïve solution
At first, it makes sense to solve the problem exactly using the observation above.
Loop through all problems
For each problem loop through all contests I can submit to
Keep a running track of the satisfaction
Sounds good right? Wrong! It’s too slow!
The time complexity of the above solution is O(cp), since there are p problems and c contests. The problem states this.
200K * 200K = 40B. That’s 4 followed by 10 zeroes… too slow!
But you might have guessed, given the article this challenge question was posed in, that the full solution involves sorting. Can you think about how that would look like in the full solution?
Sorting and searching
We’re looking for a second observation that can help us solve this problem. Now, notice that we’re looping through every single contest each time we consider a problem, even though we’re only interested in 2 things.
We only want to consider contests with m[i] <= q[j]
We only want the contest with the largest s[i]
So let’s sort both the problems and the contests in increasing order of q[j] and m[i] respectively.
Now let’s create an array called B. B is managed by a guy named Bob. Bob starts off at the start of the sorted array of contests. His little array B[i] keeps a track of the maximum satisfaction of all contests in the sorted array from index 0 to i.
Bob is our friendly helper! Every time we consider a problem, simply carry out a binary search to find the contest with the largest m[i] <= q[j] in our sorted array of contests. Once we have this, we simply query B[i], that Bob already knows! See the next section for an illustration
So overall, creating Bob’s array has time complexity O(c). Next, for each of the problems, our binary search has a time complexity of O(log(c)). Hence the overall time complexity is O(p*log(c)).
In the end, our time complexity if O(c + p*log(c)). log(200K) is a 2 digit number, so our overall time complexity is less than a million. That’s acceptable, yay!
Illustrated solution
Take this test case, given in the problem.
Next, we sort it and ask Bob for help.
Now we process the first problem.
We can find the yellow range using binary search to find the largest m[i] <= 3. Bob has already calculated at the beginning that the largest s[i] in this range is 5. So I can gain 5-2=3 satisfaction from this.
In the next step, again we use binary search to find the largest m[i] <= 9. The problem can be submitted to any contest in this range, and as Bob has found, the best is the 2nd problem to get satisfaction 5. 5-4=1, so I get satisfaction 1 from this.
The third example is similar. I can only submit to one problem, where m[i] = 1 and s[i] = 1. But since 1-3=-2, I choose not to submit at all as that is better than negative satisfaction.
In total, the answer is 3+1=4.
The person who submitted the solution wanted to remain anonymous, so I will grant him his request. Here is the code, in C++, submitted by this person. It’s commented so you can understand it.
Conclusion
We learnt how to use sorting to improve the time complexity of a difficult solution. Hope you’ve learnt something from this, and keep submitting solutions so that your work can be featured here.
Thanks for reading, and see you in the next one!
