Problem Link:
Difficulty:
Easy
Pre-requisites:
Binary Indexed Tree, Ad-hoc
Problem:
You are given a sequence of N positive integers in the range 0 to 2M-1, say A[0], A[1], …, A[N-1]. In how many ways can you partition this sequence into disjoint contiguous subsequences, such that the sum of numbers in each contiguous subsequence modulo 2M in each partition is in the range 0 to 2M-1-1.
Explanation:
The first thing to note is that the sum of any contiguous subsequence of the sequence A, can be got very easily if we maintain a prefix sum array. Let B[i] = A[0] + A[1] + … A[i]. Now, the sum of numbers from A[i] to A[j], is just B[j] - B[i-1], (with the convention that B[-1] = 0). Similarly, the values of the sums modulo 2M will be (B[j] - B[i-1]) modulo 2M.
We now ask, given the sequence of integers A[0], A[1], …, A[N-1], how many ways are there to partition it? In particular, we ask, what will the last partition be? Note that A[j], A[j+1], …, A[N-1] is a valid partition iff (B[N-1] - B[j-1]) % 2M < 2M-1. Given that that is a valid partition, we ask how many ways are there to partition A[0], A[1], …, A[j-1].
That brings us to the following dynamic program: let f(i) = number of ways of partitioning A[0], A[1], …, A[i] in the required manner. Now, again we ask what is a valid last partition. Any prefix sum in the range B[i]-2M-1+1 to B[i] (modulo 2M, with prefix sums wrapping around) is valid. Once we have such a valid last partition, f(i) = sum of answers of previous partitions.
Thus, let us associate f(i) with B[i]. If we ask at each point of time, let dp[j] = number of ways of partitioning the currently seen array such that the prefix sum to this point is j, then, we just need to make the update dp[B[i]] += sum (j from B[i] - 2M-1 + 1 to B[i]) dp[j]. Thus, this is a sum over a contiguous portion of a “dp-array”, and can be efficiently implemented using a Binary Indexed Tree (BIT).
Thus, the overall algorithm’s pseudocode is as follows:
Keep a BIT, over an initial array of size 2^M, whose 0'th entry is 1, others are 0.
for i from 0 to N-1
pref[i] = pref[i-1] + A[i]
if(pref[i] >= 2^(M-1)) //don't wrap around
res = BIT.query(pref[i]-2^(M-1)+1, pref[i])
else //wrap around
res = BIT.query(0, pref[i]) + BIT.query(pref[i]+2^(M-1)+1, 2^M-1)
BIT.update(pref[i], res)
output answer = res // result at final position = pref[N-1].
Related Problem:
Problem “Generic Cow Protests” USACO Feb 11 Gold Contest
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
