#Sort

Solutions This is a simple greedy algorithm. Naming \(t_i\) the time of order \(i\) and \(d_i\) the time needed to complete order \(i\), we sort all the orders by \(t_i + d_i\) and by \(i\). The idea implemented in C++: 1 2 3 4 5 6 7 8 9 10 int N, ti, di; cin >> N; vector<pair<int, int>> orders(N); for (auto i=1; i<=N; ++i) { cin >> ti >> di; orders[i-1] = {ti+di, i}; } sort(begin(orders), end(orders)); for (const auto& o : orders) cout << o. [Read More]

Solutions The sum is minimal when the array is sorted. Both descending and ascending order will yield the minimum sum of the absolute difference of adjacent elements. We need to count the number of swaps in both cases. To find the number of swaps we have to find the number of cycles in the array. For instance, given the following array: 1 1 2 4 3 We can construct a directed graph by making each value of the array point to its sorted position: [Read More]

Solutions Simple observation: there is no point in winning unimportant contests so we can lose them all to get their luck. If \(K\) is greater than the number of important contests, we can lose them all. In this case the luck balance is just the sum of all the contest values. Otherwise, we have to win some important contests but we don’t have to lose more than \(K\). So the number of important contests to win is: [Read More]

Solutions This easy problem can be solved by first sorting the calories in decreasing order: 1 2 3 4 5 6 7 8 9 10 long long n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v), greater<>{}); auto miles = 0ll; for (auto i=0; i<n; ++i) { miles += v[i] * (1ll<<i); } cout << miles; The zip | map | reduce pattern emerges from the code: conceptually, it’s like zipping each calory with the ith power of 2, mapping the pair with product and summing along the way: [Read More]

Solutions Since we need to maximize the number of toys, we can sort the array in incresing order of price and pick them as long as the budget is available. A solution in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iterator> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> prices(n); copy_n(istream_iterator<int>(cin), n, begin(prices)); sort(begin(prices), end(prices)); auto toys = 0, cost=0; for (auto i=0u; i<prices. [Read More]

Solutions The problem reduces to choosing K consecutive numbers in a sorted list for which the value of D is minimum. Which can be easily done by sorting the given number and calculating D for each group of K consecutive number. Here is a possible C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iterator> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <climits> using namespace std; int main() { int N, K; cin >> N >> K; vector<int> v(N); copy_n(istream_iterator<int>(cin), N, begin(v)); sort(begin(v), end(v)); auto tail = 0; auto head = K-1; auto unfairness = INT_MAX; while (head<N) { unfairness = min(unfairness, v[head]-v[tail]); tail++; head++; } cout << unfairness; } This results in a combination of zip | map | reduce patterns that in C++ can be written in terms of inner_product: [Read More]

Solutions The brute force solution consists in calculating the absolute difference of each pair and reducing to the minimum value. This takes \(O(N^2)\). We can find better solution, instead, by making a simple observation: the closest two numbers, the lowest their difference. It’s just like calculating the distance between points on the same axis. Indeed, the formula to calculate the distance between two points \(x1, x2\) on the same axis is simply \(|x1-x2|\). [Read More]

Solutions The naive solution is quadratic and it’s too slow for a few test cases. We show it here, for completeness: 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 #include <iterator> #include <climits> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); auto minLoss = INT_MAX; for (auto i=0; i<n; ++i) { for (auto j=i+1; j<n; ++j) { if (v[i] > v[j]) { minLoss = min(minLoss, v[i] - v[j]); } } } cout << minLoss; } Rust naive solution: [Read More]

Given two unsorted arrays arr1 and arr2 - possibly containing duplicates - for each element in arr1 print the number of elements less than or equal to it in array arr2. Input Format The first line contains an integer N. Two lines follow: the first array: N space-separated elements the second array: N space-separated elements Constraints N and M are at most 100'000 Each array element is at least 0 and at most 100'000. [Read More]

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 ? [Read More]