PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The prefix sum problem is a classic in parallel computing. It has a recursive solution which halves the size of the problem and leads to logarithmic number of steps. To compute prefix sums for sequence X 1 , X 2 , …, X[N] we form a new sequence X 1 +X 2 , X 3 +X 4 , … lets call it sequence Y. If we could recursively compute prefix sums Z for sequence Y, can we reconstruct the prefix sums W for sequence X? Yes we can, W[i] equals Z[i/2] for even i and Z[(i-1)/2]+X[i] for odd i. We can perform all these computations in-place. Note that sequence Y can be computed in parallel on N/2 machines and the same holds for reconstructing W from Z. Wikipedia has a nice article about this problem with some visualizations.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.