PARALLEL - Editorial

PROBLEM LINKS

Practice
Contest

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.

1 Like