Padel tournament · Coding Gym

Solutions

A brute-force approach consists in enumerating all possible combination of pairs and check if any contains all pairs with the same sum. Enumerating and checking all the combinations is clearly expensive.

Actually, there is only one possible combination that would satisfy the constraint and can be found directly.

Intuitively, suppose we are 4 people and we want to play together in pairs. To make the match balanced, we have to join the strongest with the weakest. That’s it. Same story here. To find a solution, first we need to sort the skills, then we combine the players taking one from the tail and another one from the head, iteratively:

1

3 2 5 1 3 4

Sort it:

1

1 2 3 3 4 5

Join players together:

1

(1,5), (2,4), (3, 3)

Here is a C++ solution:

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


bool divide(vector<int>& skills)
{
    sort(begin(skills), end(skills));
    auto l = begin(skills);
    auto r = prev(end(skills));
    const auto value = *l + *r;
    while (l < r && l != end(skills))
    {
        if (*l++ + *r-- != value)
            return false;
    }
    return true;
}

int main() 
{
    int n;
    cin >> n;
    vector<int> skills(n);
    copy_n(istream_iterator<int>(cin), n, begin(skills));
    cout << divide(skills);
}

This is a trivial application of the two-pointer technique.

Another way to see this problem is with zip:

1
2
3
4
5
6


bool dividePlayers(std::vector<int>& skills) 
{    
    sort(skills);
    auto zipped = views::zip_with(std::plus<>{}, views::take(skills, skills.size()/2), views::reverse(skills));
    return adjacent_find(zipped, std::not_equal_to<>{}) == end(zipped);
}

In other words, we lazily form pairs of skills by summing together both the ends of the array, and then we find if all such sums are equal. Here is an example:

1

3 2 5 1 3 4

Sort it:

1

1 2 3 3 4 5

Zip with sum:

1
2
3


1+5, 2+4, 3+3
=
6, 6, 6

To check if the resulting range consists of all equal elements we can use adjacent_find that is just a shorthand to check if all adjacent elements of a range satisfy a predicate. In this case, std::not_equal_to<>{}. If we find any that is not equal to the following one, the constraint is broken.

Here is a Python succinct variant by Simone Santillo, Andrea Battistello and Francesco Solera:

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


n_players = int(input())
data = list(map(int, input().split()))

target_sum = int(sum(data) / (n_players / 2))
if target_sum * (n_players / 2) < sum(data):
    print('0')
    exit()

data_sorted = sorted(data)
r = any(map(lambda x: x[0]+x[1]!=target_sum, zip(data_sorted, data_sorted[::-1])))

print(int(not r))

Other solutions use data structures that allow fast retrieval or a simple frequency table. For example, Elia Giacobazzi and Andrea Naletto ended up with this snippet using Python’s Counter:

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


from collections import Counter

n = int(input().strip())
skills = map(int, input().strip().split())

cache = Counter()

for i in skills:
    cache[i] += 1
    
kmin = min(cache.keys())
kmax = max(cache.keys())
s = kmin + kmax
for k, count in cache.items():
    if count != cache[s - k]:
        print(0)
        break
else:
    print(1)

2-pointers sorting