Editorial for Andyman's Golf Course - Hole 3 - Prefix Sum Array


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AndyMan68

This problem has quite a few optimizations that can be made. Some of the optimizations are as follows:

Lambda functions

A lambda function is essentially a special function (which may or may not take in input) that is defined by a variable, and is mainly used for short and simple tasks. They can be used without having an identifier in certain situations that don't require one, such as sorting by a customized comparator or with the map() function. An example follows below:

a = lambda x: x+2
print(a(5))

which outputs

7

This lambda function takes in a value x as the input to the function, and returns x+2.

Appending to Lists

Although the conventional way to append to a list is using .append(), simply using += c to a list will append the contents of the list c to the original list.

Reading input

The input format is one that is easier to handle in other languages, but since in Python input is read in one line at a time, efficiently turning each line into an iterable and ensuring the numbers are of integer type is key. By splitting the line of input by space (which is what is done by default with the split() function), and applying the int() function with the map() function to the split input, we can efficiently take input in the given format

map(int, input().split())

Notice that if multiple variables need to be assigned, they can be automatically done as such:

a, b = map(int, input().split())

Assuming there were 2 integers in the line of input, the variables a and b would be set as integers accordingly.

exec() looping

The exec() function allows for a string of code to be executed as an argument. This is a common tool in golfing to do simple loops, as a string of repeated code can be multiplied by simply multiplying the string by some number, and using semicolons to ensure that multiple statements don't combine, this allows for a loop to be made.

exec("print(2+3);"*6)

Which would output 5, 6 times on 6 separate lines.

123 bytes

A combination of these optimizations could lead to the following solution:

d,p=lambda:map(int,input().split()),[0]
a=*d(),
for i in a:p+=[p[-1]+i]
exec("a,b=d();print(p[b]-p[a-1]);"*int(input()))

d stores a lambda function to read in input, and d stores the prefix sum array. It is key to not allow the string to be executed to be too long, or else a memory error may occur.

117 bytes

An alternate solution that does not use exec() looping or lambda functions (but instead reassigns function names to variables) discovered by philomm is as follows:

I=input;N=int;a=[0]
for i in I().split():a+=N(i)+a[-1],
for _ in[0]*N(I()):j,k=I().split();print(a[N(k)]-a[N(j)-1])

115 bytes

The 123-byte solution can be optimized to attain 115 bytes. As a hint, we can remove a line altogether and use a tuple trick from the first hole in the golf course.

The solution to earn full marks is left as an exercise to the reader.

112 bytes

It is even possible to optimize to 112 bytes by changing the lambda function slightly, however any further optimizations are unknown.


Comments

There are no comments at the moment.