#preprocessing

Solutions This problem is not particularly difficult, but it does require combining a few key ideas. One of the main challenges depends on the programming language used, since date manipulation is involved. While all mainstream languages provide adequate tools to handle dates, practical difficulties may still arise. At the time of writing, the latest C++ compiler available on HackerRank is outdated and does not support some of the more recent additions to std::chrono. [Read More]

Solutions This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums. To answer to the first type of queries, we need to cache the running maximums of the prices: 1 2 3 4 5 6 7 8 vector<int> prefixMax(n); auto runningMax = p.front(); prefixMax[0] = runningMax; for (auto i=1; i<n; ++i) { prefixMax[i] = max(runningMax, p[i]); runningMax = prefixMax[i]; } In C++, we have a very useful standard algorithm to perform the same routine: [Read More]