Editorial for Andyman's Golf Course - Hole 3 - Prefix Sum Array
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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
, times on
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 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 -byte solution can be optimized to attain
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 bytes by changing the lambda function slightly, however any further optimizations are unknown.
Comments