Ice Cream Parlor · Coding Gym

Solutions

The brute force approach is easy: just run two nested loops and for each value \( x \) find if it exists a value equals to \( target - x \). This solution is quadratic.

Efficient solutions are based either on sorting or additional storage (e.g. frequency table, hash maps).

A sort-based solution

Suppose we sort the prices \( p \) in ascending order. Consider the sum \( p[0] + p[n-1] \) where \( n \) is the number of available prices. If this sum was less than \( m \), then we should increment the left hand index (we need to “pay more”). On the other hand, if the sum was greater than \( m \), then we should decrement the right hand index (we need to “pay less”). This leads to the following solution based on 2-pointer technique:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


int t; cin >> t;
int n, m, f;
while (t--)
{
    cin >> m >> n;
    vector<pair<int, int>> v(n);
    for (auto i=0; i<n; ++i)
    {
        cin >> f;
        v[i] = {f, i+1};
    }
    sort(begin(v), end(v));

    auto head = begin(v);
    auto tail = prev(end(v));

    while (true)
    {
        if (head->first + tail->first > m)
        {
            tail--;
        }
        else if (head->first + tail->first < m)
        {
            head++;
        }
        else
        {
            cout << min(head->second, tail->second) << " " << max(head->second, tail->second) << "\n";
            break;
        }
    }
}

Clearly, some additional storage is needed to sort the array without losing the original indexes.

The overall complexity is \( O(N \cdot logN \) but it can be even optimized by using a linear-time sorting algorithm since the domain is small (e.g. counting sort or radix sort).

Lookup-efficient data structures solutions

Another approach consists in using a multimap (since duplicates are possible) to lookup every value efficiently:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int t; cin >> t;
int n, m, f;
while (t--)
{
    cin >> m >> n;
    unordered_multimap<int, int> flavors;
    for (auto i=0; i<n; ++i)
    {
        cin >> f;
        flavors.emplace(f, i+1);
    }

    for (auto i : flavors)
    {
        auto it = flavors.find(m-i.first);
        if (it != end(flavors) && it->second != i.second)
        {
            cout << min(i.second, it->second) << " " << max(i.second, it->second) << "\n";
            break;
        }
    }
}

A variation of this approach consists in using a frequency table. In this case, we do not keep track of the indexes with a sort of trick: when we find the matching price (\( m - p[i] \)), we just scan the array to find its position. Since this operation is perfomed only once, the solution stays linear:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


int t; cin >> t;
int n, m;
while (t--)
{
    cin >> m >> n;
    array<int, 100'000+1> freq{};
    vector<int> p(n);
    copy_n(istream_iterator<int>(cin), n, begin(p));
    for (auto i : p)
        freq[i]++;

    for (auto i=0; i<n; ++i)
    {
        const auto x = m - p[i];
        //                   > 1 if x == p[i] (duplicate handling)
        if (x > 0 && freq[x] > (x == p[i]))
        {
            auto it = find(begin(p), end(p), x);
            if (it == next(begin(p), i)) // found the very same element
                it++;
            auto first = (int)(distance(begin(p), it)+1);
            auto second = i+1;
            cout << min(first, second) << " " << max(first, second) << "\n";
            break;
        }
    }
}

Note that the weird condition freq[x] > (x == p[i]) is just syntactic sugar to say “if x is p[i] then we need to have at least two of such values available. For example, suppose we have:

1

2, 2, 3, 5

and suppose we need to find the indexes for k=4. When we check for the first 2, we have:

1
2


const auto x = m - p[i]; // x = 4 - 2 = 2
if (2 > 0 && freq[2] > (2 == 2)) // true, since freq[2] = 2