PROBLEM LINK:
Author: Constantine Sokol
Tester: Mahbub
Editorialist: Jingbo Shang
DIFFICULTY:
Medium
PREREQUISITES:
Segment Tree, Binary Search, Persistent Segment Tree.
PROBLEM:
Given A[1…N], and M queries about what is the smallest number that can’t be represented by the sum of some subset of A[Li … Ri] (so called forbidden sum).
EXPLANATION:
First of all, we need to know how to process a single query. That is, given a set of number, determine the forbidden sum. Consider a special case, the answer should be 1 if we have no ones. Based on this observation, we can firstly sort the number ascending. Take the numbers one by one while maintain a sum S (initially S = 0). The algorithm is as following:
S = 0
while (there is the next number x) {
if x <= S + 1:
S = S + x
else
break;
}
the forbidden sum is S + 1.
Suppose we have the next number x. If x is greater than S + 1, because of the numbers are ascending, S + 1 will be never got. Therefore, there is a break. Otherwise, 1 … S + x are all possible.
And also, we can describe the algorithm in an alternative way (but helpful):
S = 0
while (true) {
newS = the sum of {x | x <= S + 1}
if (S == newS):
break
S = newS
}
the forbidden sum is S + 1.
we should observe that, the answer is smaller than the sum of A[1…N], <= 10^9, denoted as P. Moreover, S is increasing exponentionally, as fast as the Fibonacci Number, because the newly added number should be greater than previous loop’s S. Therefore, there will be only O(log P) loops.
Back to the original problem, for a given query, if we can fast perform the “newS = the sum of {x | x <= S + 1}” in the given A[L … R], such as in O(log N) or O(log^2 N) time, then we can solve this problem. Fortunately, we can ask Segment Tree for help.
For the static Segment Tree, we can maintain a sorted list in each node with their prefix sum (O(N log N) space is needed, because there are O(N) numbers stored in each level). When the query covered the whole interval stated by the node, binary search is adopted to fast locate the “x <= S + 1” position and return the prefix sum. Therefore, we can solve each query in O(log^2 N) time.
Furthermore, we can try Persistent Segment Tree to solve this problem in O(log N) time. Persistent Data Structure can help us to deal with the L … R query into the delta of 1 … R query and 1 … L - 1 query. Therefore, we can build the Persistent Segment Tree on their values (each node stands for an interval of values of A[]) and insert the A[i] from i = 1 to N one by one. After that, we can have N + 1 roots stand for different prefixs (ranging from 0 to N. 0-th is an empty tree, i-th is the segment tree after inserted A[1…i]). Each node this time stores the total numbers have been inserted in to this subtree. For a given query [L … R] and the S we maintained, we query the total number <= S + 1 on the R-th tree and (L-1)-th tree, and then get the delta. This process is O(log N).
Finally, using the Persistent Segment Tree, we can solve this problem in O(N log N + M log P log N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.