#patterns

You are given a sequence of integers S, your task is to find a pair i,j of indices with i<j that maximizes the difference S[j]-S[i]. Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S). You have to output the value of the maximum difference. Input Format An integer N followed by N space separated integers S[i] on a new line. [Read More]

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 A solution consists in finding all the contiguous digits in the string, converting them to integers and putting them in a set for removing duplicates. Finally, outputting the size of the set: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int n; cin >> n; string input; while (n--) { cin >> input; set<int> integers; auto cur = begin(input); while (cur ! [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]