#prefix sum

The school term starts soon, and the students need to be sorted into their respective sections. There are \( n \) students numbered \( 1 \) to \( n \), and \( m \) sections numbered \( 1 \) to \( m \). Section needs to have exactly \( a_i \) students. To simplify the process, the school has decided to assign students to sections in increasing student number, which means the first \( a_1 \) students will be assigned section \( 1 \), the next \( a_2 \) students will be assigned section \( 2 \), and so on. [Read More]

Solutions To solve the problem we can easily observe that swapping the first c with the last p minimizes the tastiness. The answer is \(0\) when either: there are not p there are not c the last p is before the first c For example: 1 pppccc Instead, if neither of the conditions above occur, we swap the first occurrence of c with the last occurrence of p and we proceed with computing the tastiness. [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]

Summer is over and people at Gugol are sad and unmotivated. They would prefer going back on vacation instead of working - how to blame them? Ted, head of employee happiness department, has got an idea to cheer people up: he will run a lottery among all the employees and will award the luckiest one with two extra weeks of vacation. The lottery will work this way: Ted will raffle off some ranges of employee ids like \( [120, 200] \) and \( [150, 180] \), a sophisticated algorithm will calculate which is the most frequent employee id in all such ranges, if more than one such an id exists, the sophisticated algorithm will select the smallest one - it corresponds to the employee who has been working at Gugol for more time You are a \( \cancel{slave} \) trainee at Gugol and you have to design and write such a sophisticated algorithm. [Read More]

Solutions We have two similar tasks: find the maximum sum of any nonempty subarray find the maximum sum of any nonempty subsequence The latter is clearly esier since the elements in a subsequence are not necessarily contiguous. The former is a very classical problem that we’ll deal with in a moment. To solve the first task, we can sum all the positive elements. This works as long as we have at least one positive (or zero) element. [Read More]