This task asks you to take two arrays of size \(N\) and to create from them a third array containing the \(N\) smallest of all possible sums of one element from the first array and one element of the second. Like many Olympiad tasks, there is a "naive" solution that will work well enough to earn a partial score, but for full marks you will have to find a more efficient solution. We will examine the naive solution and one possible strategy for improvement in this analysis.
The naive solution is simply to find all possible sums. Because there are \(N\) numbers in the second array to add to each of the \(N\) numbers in the first, this approach gives us \(N^{2}\) sums. We can either compute them all and then sort and clull the results, or we can check each sum as we calculate them and keep only the \(N\) smallest. Which solution is better depends on whether you are memory- or processor-constrained.[1] With no constraints, the code is cleaner using the first method.
Ultimately, the naive solution fails because \(N\) can be as large as \(10^{5}\). This means that there can be as many as \(10^{5} \times 10^{5} = 10^{10}\) (ten trillion) addition operations, which will take several minutes even on a fast computer. To meet the problem specification, you will have to find a way to reduce the number of additions.
The problem statement contains a huge hint about improving the algorithm because it states that the two original matricies are sorted. This means that the smallest elements in each matrix appear first, and adding these early terms together will give us (some of) the smallest sums. Unfortunately, we have to be wary of input like
\[ A = [ \,1, \,2, \,3, \,4, \,5 \,] \] \[ B = [ \,1, \,1, \,1, \,1, \,1 \,] \]
which will require us to use all the elements of B. Obviously, we have to have a systematic approach and cannot simply ignore the later elements.
As a first step, consider this (overly) simple strategy to reduces the number of additions to \(2N\):
This approach provides a significant improvement in performance, but we're probably meant to do better. With \(N = 100000\), it takes 20-30 seconds in the replit environment for a C++ implementation to find the sums. In Python, replit won't run the script to completion.
The problem with this approach is that it doesn't reduce the big-O complexity of the algorithm. Although the number of additions has gone from \(N^{2}\) to \(2N\), we must still check \(N\) sums \(N\) times to find the smallest one. For that reason, the complexity remains \(\mathcal{O}(N^{2})\).
We must make a further improvement by sorting the candidate sums after step 1 and taking the first of them in step 2. The replacement sum in step 3 can be added to the sorted group of candidate sums in \(\mathcal{O}(\log n)\) time. Because we do this \(N\) times, the final complexity is \(\mathcal{O}(N\cdot\log N)\). A convenient way to implement this is with a priorty queue. The further improved method is:
Here are implementations in C++ and in Python for your reference.
There are three input files at each of the replits above. Each line contains two integers, separated by a space. If you interpret these as \(a_{i}\) and \(b_{i}\), the ith element of array A and array B respectively, you can compare your answers to the corresponding result text files.
Try coding up the naive solution and running it with larger and larger data sets. You will probably do fine up to about 30,000 entries in the source matricies, but things get bad quickly as you approach 100,000. In the competition, you would get a part score for the naive solution, so it might be worth using if you panic and can't think of an improved solution.