AMSEQT - Editorial

Problem Link:

Practice

Contest

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

5 Likes

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!

2 Likes

@bcurcio I think that if you downvote some post it’s polite to write the reason why are you doing so…

1 Like

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.

@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[N-1] - B[j-1]) % 2M < 2M-1”, in the second “Any prefix sum in the range B[i]-2M-1+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] - 2M-1 + 1 to B[i]) dp[j]. " That’s not an explanation, it’s reading the pseudocode.

2 Likes

@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 :wink:

For each user you can see his/her “karma history” on profile page, so there you can find who upvoted/downvoted the post :wink:

What is wrap around in this context?

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!!