Author: Pavel Sheftelevich
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima
You are given N memory requests. The system starts with no memory allocated. For each request, the system either allocates or deallocates the memory to exactly match the requested memory. Calculate the total amount of memory allocated.
Keep track of the amount of memory currently allocated. For each request, if the requested memory is more than the current memory, then add the difference to the answer.
This is a fairly straightforward simulation problem. Observe that the memory allocated or deallocated only depends on two things:
- The memory during the previous task (or zero initially) (call it last)
- The memory requested during the current task (let us call it cur)
So, given these two values, when will the system have to allocate more memory? When the current task requests more memory than the previous one. How much memory should we allocate?
Suppose a is the amount of memory we have to allocate. Note that allocation is in addition to the memory the system had before this task. So, the total memory after allocation would be last + a. We want this to be equal to cur. So, last + a = cur. Which gives a = cur - last. For each request that requires allocation, we add the amount allocated to the total.
total = 0 // Stores the amount of memory allocated so far last = 0 // Stores the amount of memory allocated to the last task (initially 0) repeat n times: input cur // Get the amount of memory requested by the current task if cur > last: ans += cur - last // If more memory is required, then we must allocate the difference last = cur output total
A word on implementation
For some language like Python, we can translate the pseudocode above easily. For languages like C/C++ or Java we need to decide the type of each variable. Note that 32 bits are not enough to store the total. Why? Suppose the requests are 10^5 1 10^5 1 10^5 1 … then for each pair of requests of 1 followed by 10^5, we need to allocate (10^5 - 1) memory. Since n can be upto 10^5, the total amount will exceed 32 bits. So we need to use 64 bit data type to store the total.