Electronics Shop · Coding Gym

Solutions

A simple solution consists in running two nested for loops to calculate the possible costs. Although this solution is \(O(n \cdot m)\), it’s acceptable since the input is small:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int s, n, m;
cin >> s >> n >> m;
vector<int> k(n);
copy_n(istream_iterator<int>(cin), n, begin(k));
vector<int> u(m);
copy_n(istream_iterator<int>(cin), m, begin(u));

auto cost = -1;
for(auto i : k)
{
    for (auto j : u)
    {
        if (i+j<=s)
            cost = max(cost, i+j);
    }
}
cout << cost;

Linq-based solution, with cartesian product (by fabrizio_sanmar1):

1
2
3
4
5
6
7
8
9


static int getMoneySpent(int[] keyboards, int[] drives, int b) 
{
    var results = keyboards
        .Where(k => k < b)
        .SelectMany(k => drives.Select(d => d + k))
        .Where(x => x <= b);
    
    return results.Any() ?  results.Max() : -1;
}

Another solution in Scala, using for comprehension to generate all possible acceptable costs and finding the maximum between them:

1
2
3
4
5
6
7
8
9


def getMoneySpent(keyboards: List[Int], drives: List[Int], b: Int): Int = {
    val sums = for {
        k <- keyboards
        d <- drives 
        if (k < b && d < b && k + d <= b)
    } yield k + d

    sums.maxByOption.getOrElse(-1)
}

Optimized solution: \(O(n+m (log (n+m))\)

If we sort the first sequence in descending and the other in ascending order we only have to visit each element once, because we can make use of the fact that the sum of the element following the current will be greater/less than the current sum depending on the direction we iterate from:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


sort(begin(k), end(k), greater<>{});
sort(begin(u), end(u));

auto cost = -1;
for (auto i=0, j=0; i<n; ++i)
{
    for (; j<m; ++j)
    {
        if (k[i] + u[j] > s)
            break;
        if (k[i] + u[j] > cost)
            cost = max(cost, k[i]+u[j]);
    }
}
cout << cost;

Binary search on the array of all possible costs (not a cheaper solution)

Maurizio Carli and his coding partner proposed this variation:

create an array with all possible costs
sort such an array
use binary search to find the first element not greater than the budget

Clearly, this solution is slower than the optimized one. It’s instructive to see how all the patterns are combined, though:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


vector<int> sums;
sums.reserve(keyboard.size() * drives.size());
// 1. precalculate all costs
for (auto k : keyboards) 
{        
    for (auto m : drives) 
    {
        sums.push_back(k + m);
    }
}
// 2. sort
sort(begin(sums), end(sums));
// 3. use lower_bound backwards to find the first element that is not greater than the budget
auto it = lower_bound(rbegin(sums), rend(sums), budget, greater<>{});
if (it != rend(sums))
    return *it;
return -1;

It’s interesting to note the usage of lower_bound: since lower_bound returns the first element greater than or equal to another one, by default it may return a value that is greater than the budget. We could just check if this happens and return the previous element in case. But we can stress the pattern a bit more to learn something new. If we run lower_bound backwards we find the first element less than or equal to our budget! It’s just the matter of iterating backwards (with reverse iterators) and adapt lower_bound to work with a descending-sorted sequence (that’s why we use greater).

2 pointers sorting