### Flatfoot's blog

By Flatfoot, 11 years ago,

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 ai elements by adding xi. 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
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
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


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
sum=31


2) Remove last element: Perform the following operations:

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


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
sum=27


3) Remove last element: Perform the following operations:

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


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
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


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


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.

• +20

 » 7 years ago, # |   0 thnk u