Alternating Characters

Solutions This problem can be solved by counting the number of equal adjacent characters: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 size_t T; cin >> T; string s; while (T--) { cin >> s; auto cnt = 0; for (auto i=1; i<s.size(); ++i) { if (s[i]==s[i-1]) cnt++; } cout << cnt << "\n"; } This is an application of zip | map | reduce pattern: [Read More]

Birthday Chocolate

Solutions The solution to this problem when d=1 can be used to solve Picking Numbers as well. A linear solution consists in: computing the prefix sum of the input array keeping a window of size m counting how many times the window bounds differ by d Here is a solution in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, d, m; cin >> n; vector<int> v(n+1); copy_n(istream_iterator<int>(cin), n, next(begin(v))); cin >> d >> m; partial_sum(begin(v), end(v), begin(v)); auto cnt = 0; for (auto i=0; i<=n-m; ++i) { cnt += v[i+m] - v[i] == d; } cout << cnt; The loop can be replaced with zip | map | reduce combination of patterns: [Read More]


Solutions The problem is very simple: we just count how many capital letters the string has and we sum 1. A C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <string>#include <iostream>#include <algorithm>#include <iterator> using namespace std; int main() { cout << (count_if(istream_iterator<char>(cin), istream_iterator<char>(), [](char c){ return isupper(c); })+1); } Here is a Python solution by Yuri Valentini: 1 2 ss = raw_input(). [Read More]

Compare the Triplets

Solutions This is clearly an easy problem we can experiment with. The easiest way to write the solution in C++ is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 array<int, 3> a, b; copy_n(istream_iterator<int>(cin), 3, begin(a)); copy_n(istream_iterator<int>(cin), 3, begin(b)); int alice_points = 0; int bob_points = 0; for(int i = 0; i < 3; i++) { if (a[i] > b[i]) alice_points++; if (a[i] < b[i]) bob_points++; } A little more efficient: else if [Read More]

Counting Valleys

Solutions Intuition: we keep track of how many steps we are on or under the sea (e.g. variable level). When we go down (e.g. we read D) we decrement our level by one. When we go up we increment our level by one and also check if we were just one level below the sea. If the case, we are walking through a valley (e.g. we increment a counter). C++ Here is a C++ implementation of the idea above: [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]

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: [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]