#Patterns

Naive solutions The naive solution consists in simulating the game: until no elements are left, continuously remove the maximum element and the elements on its right. This might be simplified a bit by performing only a “logical” removal, keeping an index updated to the rightmost element still in the valid range. For example: 1 2 3 5 4 6 9 7 ^ last element in range Bob “removes” 9: 1 2 3 5 4 6 9 7 ^ last element in range It’s clear now that 7 is not in range anymore so Andy picks 6. [Read More]

John has been analyzing stocks and their prices as his latest assignment. Being a beginner in stocks, he has selected a stock HRC and collected the low, high and close prices for n days in the form of arrays: \(low\), where \(low_i\) is the lowest value of the stock on \(i^{th}\) day. \(high\), where \(high_i\) is the highest value of the stock on \(i^{th}\) day. \(close\), where \(\) is the closing value of the stock on \(i^{th}\) day. [Read More]

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 A tradeoff of this problem is about using a temporary array or not. In the latter case, the steps to do are simpler because we can just copy the two parts the array: all the elements before the rotation point and then all the element after. Here is a Java implementation: 1 2 3 4 5 6 7 8 9 10 11 public static int[] rotateArray(int[] arr, int d) { int n = arr. [Read More]

Solutions A simple solution that makes use of extra space consists in simply copying words backwards to a temporary array starting from the last one. However, an classical in-place solution exists and works in two steps: first reverse the string blindly and then reverse every single word individually. Note that the input of this puzzle contains multiple lines and empty ones must be preserved. Here is a C++ solution: 1 2 3 4 5 6 7 8 9 10 11 12 std::string s{std::istreambuf_iterator<char>(std::cin), {}}; // read full input into memory, preserving newlines and spaces std::reverse(begin(s), end(s)); // reverse the string blindly auto head = begin(s); while (head ! [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 This is an easy problem we can experiment with. The simplest solution consists in counting how many characters mismatch: 1 2 3 4 5 6 7 char c1, c2, c3; auto cnt = 0; while (cin >> c1 >> c2 >> c3) { cnt += (c1 != 'S') + (c2 != 'O') + (c3 != 'S'); } cout << cnt; We can use the reduce pattern: 1 2 3 4 static const char match[] = {'S', 'O', 'S'}; cout << accumulate(istream_iterator<char>(cin), istream_iterator<char>(), make_pair(0, 0), [](pair<int, int> s, char c) { return make_pair(s. [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]