## Find the Maximum Difference

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]

## Gaming Array

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]

## Gap Up and Down

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]

## Jim and the Orders

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]

## Left Rotation

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]

## Leonardo's Apprentice

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]

## Marc's Cakewalk

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]

## Mars Exploration

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]

## Max Min

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]

## Minimum Absolute Difference in an Array

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]