My submission for 283A - Cows and Sequence did not pass the system test because it was not efficient enough, in particular I had to update the first a_i elements by adding x_i. Later, Akshai told me how to avoid this.

Example:

Suppose you have the sequence 0,1,2,3,4,5 and you have to add x = 7 to the first a = 3 elements. What you do is you store an array "added_X" that keeps track of the added x values. added_X is initialized with 0. We will also keep a variable "sum" that keeps track of the total sum of elements in the sequence array.

sequence: 0,1,2,3,4,5
added_X:  0,0,0,0,0,0
sum=15

Now, we somehow have to add x=7 to the first a=3 elements. We could change the sequence array but instead we store that information in the added_X array by setting added_X[a-1]+=x where added_X is 0-indexed:

sequence: 0,1,2,3,4,5       // not changed
[actual]: 7,8,9,3,4,5       // <-- not stored and only shown for illustration purposes
added_X:  0,0,7,0,0,0        // added_X[a-1]+=x, i.e. added_X[2]+=7 
sum=sum+(x*a)=15+(7*3)=36   // change sum

Now, to illustrate why the array "added_X" is so useful, we will remove the last elements.

1) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 36-5-0 = 31
added_X[last-1] = added_X[last-1] + added_X[last] = 0+0=0

With this last operation we carry the information about the added x values to the left because we know that all numbers to the left in the sequence have been increased by x.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1,2,3,4 
[actual:] 7,8,9,3,4       
added_X:  0,0,7,0,0       
sum=31

2) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 31-4-0 = 27
added_X[last-1] = added_X[last-1] + added_X[last] = 0+0 = 0

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1,2,3 
[actual:] 7,8,9,3       
added_X:  0,0,7,0       
sum=27

3) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 27-3-0 = 24
added_X[last-1] = added_X[last-1] + added_X[last]

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1,2 
[actual:] 7,8,9       
added_X:  0,0,7       
sum=24

The next removal will make clear why the array added_X is so useful

4) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 24-2-7 = 15
added_X[last-1] = added_X[last-1] + added_X[last] = 0+7 = 7

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1 
[actual:] 7,8       
added_X:  0,7   // <--- Note how "information" is passed to the left       
sum=15

5) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 15-1-7 = 7
added_X[last-1] = added_X[last-1] + added_X[last] = 0+7 = 7

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0 
[actual:] 7       
added_X:  7   // <--- Note how "information" is passed to the left       
sum=7

Note: The case where we have to append an element k to the sequence can be dealt as follows:

1. First, we just append k to the sequence array.

2. Second, we set sum=sum+k.

3. Third, we append 0 to the added_X array.