Permuting Two Arrays · Coding Gym

Solutions

We can find the answer by sorting one of the arrays in ascending order and the other in descending order. Then we check if the sum of all elements in pairs is greater than or equal to \(K\).

It’s a greedy algorithm and its proof is left to the reader (see here).

In C++:

1
2
3
4
5
6
7
8


sort(begin(v1), end(v1));
sort(begin(v2), end(v2), greater<int>());
bool ok = true;
for (auto i=0; i<N && ok; ++i)
{
    ok = (v1[i]+v2[i])>=K;
}
cout << (ok ? "YES" : "NO") << endl;

This code hides some patterns - in C# by Simone Busoli and Antonio D’Angelico:

1
2
3
4


A.OrderBy(a => a)
  .Zip(B.OrderBy(b => -b), Tuple.Create)
  .All(t => t.Item1 + t.Item2 >= k)
 ? "YES" : "NO";

Conceptually, in C++ one can use inner_product (left to the reader), although it goes to the end even if a failing condition is found.

C++20 will have ranges and it will be possibile to write such a solution:

1
2
3
4
5
6
7


// A and B are sorted
auto pairs = ranges::view::zip(A, B);
auto ok = ranges::all_of(pairs, [=](auto stuff) {
    return (stuff.first + stuff.second) >= k;
});

cout << (ok ? "YES" : "NO") << endl;

Everything is lazy, meaning that zip and all_of keeps on generating results until all_of’s condition is false.

An Haskell solution by alepez:

1

compute (k, as, bs) = all (>= k) $ zipWith (+) (sort as) (reverse $ sort bs)

A similar solution in Python by enrico_lovisotto

1
2
3
4
5
6
7
8
9


def twoArrays(k, A, B):
    A_prime = sorted(A)
    B_prime = sorted(B, reverse=True)
    
    possible = all(a + b >= k for a, b in zip(A_prime, B_prime))
    if possible:
        return "YES"
    else:
        return "NO"

patterns sort