CBARG - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

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.

SHORT EXPLANATION

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.

EXPLANATION:

This is a fairly straightforward simulation problem. Observe that the memory allocated or deallocated only depends on two things:

  1. The memory during the previous task (or zero initially) (call it last)
  2. 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.

Pseudocode:

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.

Time Complexity:

O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2

why does this code give WA on last three test cases?
http://www.codechef.com/viewsolution/7143471

1 Like
3

@sarvagya3943

u should have used long long int to store memory allocated.

1 Like
4

I am calculating the largest number in the series, because that will be the maximum mem allocated but i am getting the wrong answer… why??

5

@akhil1gupta1 it is wrong because memory is also being deallocated if it is in excess. For eg you allocate memory in this sequence 9 4 15 then according to you it is 15 but it is not correct.You will allocate 9 MB then 5 MB will be deallocated and now you have to further allocate 11 MB more. So answer is 11+9 = 20 MB

6

can anyone point why i am getting tle for this solution http://www.codechef.com/viewsolution/7142162 ???all cases are running just one case(task 5) facing problem…

7

#ohmankur

why r u doing this…

		for(i=0;i<n;i++)
		{
	     
	    	    a[(int) i]=Long.parseLong(s[(int) i]);
	    	    }`enter code here`
8

@shivam9753 i had to cast to int as variable i has been declared long. Well, this was suggested by ide(type mismatch) only otherwise i have to make variable i to int.

9

These are unnecessary things which you can avoid to get rid of TLE.

10

It would be good to change the final test case to

4
1 3 2 4

with answer

5

to illustrate the meaning of accumulating allocations rather than simply finding max allocation.