#patterns

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]

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 We first need to sort the price of flowers in decreasing order, and then distribute these flowers evenly amongst our friends buying the most expensive first. Solution in C++: 1 2 3 4 5 6 7 8 int N, K; cin >> N >> K; vector<int> c; c.reserve(N); copy_n(istream_iterator<int>(cin), N, back_inserter(c)); sort(begin(c), end(c), greater<int>()); cout << accumulate(begin(c), end(c), 0, [=,count=0](int res, int curr) mutable { return res + curr * (count++ / K + 1); }); Solution in C# by Simone Busoli: [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]