#patterns

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]

Bob has an array \( a \) with \( n \) positive integer elements. Bob likes order, so he wants his array to be sorted in non-decreasing order. He decides to swap two elements in the array to make his array sorted. (A swap is defined as switching two elements at distinct locations in the array.) Your task is to determine if this can be done. If he can’t sort the array with one swap, print \( -1 \). [Read More]

Solutions If the string is already a palindrome, -1 is the answer since no character need be removed. If the given string is not a palindrome, we must find one character that, once removed, will make it a palindrome. We can do this by checking if str[i] == str[N - 1 - i] where N is the length of the string for all i starting from i=0. Once this condition fails, all we have to do is to check if str[0:i-1] + str[i+1:N-1] is a palindrome. [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]

Solutions You might see this problem as one on intervals. Here, the input is sorted and the lenght of each interval is fixed (the duration of the recording). Every interval spans from ts[i] to ts[i] + duration (excluded). The solution to this problem is the cardinality of the set containing all the seconds recorded. For example, consider this input: 1 2 3 5 2 4 10 First, the app records from 2 to 7 (excluding the latter): [Read More]

Solutions A good strategy consists in selling one share only if that increases someday in the future. The best time to sell it corresponds to highest price reached after the day we buy the stock. For instance: 1 2 5 100 The best strategy is: at day 1 we buy the stock and we pay 2 at day 2 we buy the stock and we pay 5 (we don’t sell the stock bought before yet) at day 3 we sell both the stocks by earning 100-2 + 100-5 = 193 In other words, the best strategy consists in buying every stock at price \(p_i\) only if in the future the stock price \(p_i\) is surpassed. [Read More]

Solutions To solve this challenge we need to calculate the “distance” between the first and the last character, the second and the second to last, etc. We can do it only for the first half of the string: 1 2 a b c d => |a-d| + |b-c| That can be coded in C++ as follows: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 size_t T; cin >> T; string s; while (T--) { cin >> s; auto count = 0; auto first = s. [Read More]

Crypto Bank provides $n$ crypto currencies, each of which has a fixed conversion rate with respect to dollar. The conversion rate w.r.t dollar is not subject to change over time. But as you may have imagined, the conversion rate between each pair of crypto currencies may change over time, due to economic and political factors. Ron has $m$ bitcoins with him. The conversion rate of a bitcoin w.r.t dollar is $k$. [Read More]