Problem Link:Difficulty:Easy Prerequisites:Binary Indexed Tree, Adhoc Problem:You are given a sequence of N positive integers in the range 0 to 2^{M}1, say A[0], A[1], ..., A[N1]. In how many ways can you partition this sequence into disjoint contiguous subsequences, such that the sum of numbers in each contiguous subsequence modulo 2^{M} in each partition is in the range 0 to 2^{M1}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[i1], (with the convention that B[1] = 0). Similarly, the values of the sums modulo 2^{M} will be (B[j]  B[i1]) modulo 2^{M}. We now ask, given the sequence of integers A[0], A[1], ..., A[N1], 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[N1] is a valid partition iff (B[N1]  B[j1]) % 2^{M} < 2^{M1}. Given that that is a valid partition, we ask how many ways are there to partition A[0], A[1], ..., A[j1]. 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]2^{M1}+1 to B[i] (modulo 2^{M}, 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]  2^{M1} + 1 to B[i]) dp[j]. Thus, this is a sum over a contiguous portion of a "dparray", and can be efficiently implemented using a Binary Indexed Tree (BIT). Thus, the overall algorithm's pseudocode is as follows:
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
This question is marked "community wiki".
asked 20 May '13, 00:08

hi pragrame, please explain the part " let dp[j] = number of ways of partitioning the currently seen array such that the prefix sum to this point is j". Isn't this value of prefix sum at position i which is equal to j, is not fixed??. So please explain use of j in construction of dp again. answered 20 May '13, 01:21

Seriously What the f is wrong with these Editorials @admin . They are just time consuming and irritating ! It has been 3 hours since I have been trying to understand it! It isn't a hard problem!! The editorial is S. Its better to read this myself from the pseudocode!! answered 24 Jul '15, 02:09

I enjoyed this problem very much. First, it seemed very tricky, but then turned out to have a nice neat solution. Thanks to the author and the tester!
@bcurcio I think that if you downvote some post it's polite to write the reason why are you doing so...
@betlista For me the 'explanation' is not clear at all. I think the problem is in paragraph 3 where he tries to define f(i). First it has two definitions in the same paragraph I find confusing. In the first paragraph it says a "valid partition iff (B[N1]  B[j1]) % 2M < 2M1", in the second "Any prefix sum in the range B[i]2M1+1 to B[i] (modulo 2M, with prefix sums wrapping around) is valid". The fourth paragraph it says"we just need to make the update dp[B[i]] += sum (j from B[i]  2M1 + 1 to B[i]) dp[j]. " That's not an explanation, it's reading the pseudocode.
@betlista by the way, how can I view how votes were casted?
@bcurcio, thanks for your answer, that's the only way how the editorial can be improved ;)
For each user you can see his/her "karma history" on profile page, so there you can find who upvoted/downvoted the post ;)