#Patterns

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]

Solutions The brute force solution consists in adding the specified value to each of the given ranges and finally finding the maximum value. Evidently, the complexity of this solution is \( O(N \cdot M)\) (where \(N\) is the size of the array and \(M\) is the number of queries) which is too high to meet time constraints. A better solution is linear on N and allocates \(O(N)\) space, involving adding the specified value solely to the starting endpoint of the ranges and subtracting it from the position immediately after the ending endpoint. [Read More]

Solutions This problem is an application of Find the Maximum Difference. Basically, we need to find out the maximum difference between two numbers in the given array \(max(prices[j] - prices[i])\) with \(i<j\). The bruce force approach is quadratic and does not pass all test cases: for each element we linearly find the biggest next value. As discussed in Find the Maximum Difference, the general solution schema is the following: 1 2 3 4 5 6 7 8 9 auto currMin = INT_MAX; auto currMax = 0; for (auto i : prices) { currMin = min(currMin, i); currMax = max(i - currMin, currMax); } cout << currMax; As long as we iterate the array, currMin keeps track of the smallest element along the way. [Read More]

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]

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]

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]

Solutions We just calculate the resulting area as the product between the number of chars and the maximum height. Here is a Python implementation: 1 2 3 4 5 6 7 8 9 10 11 def get_rect_height(word, height_arr): height = 0 for c in word: height = max(height, height_arr[ ord(c) - ord("a") ]) #ord(character) gives the ascii value return height heights = [int(x) for x in raw_input().split()] #scan heights word = raw_input() print len(w) * get_rect_height(w, heights) Here is a C++ implementation: [Read More]

Solutions A brute-force solution (considering the set of all possible transactions) is clearly too expensive. To grasp the optimal solution, consider this example: 1 1, 7, 2, 3, 6, 7, 6, 7 To obtain the maximum profit, the - possibly - most intuitive set of transactions is: 1 (buy=1, sell=7) + (buy=2, sell=7) + (buy=6, sell=7) = 6 + 5 + 1 = 12 Look at the increasing sub-series 2, 3, 6, 7. [Read More]

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]