Editorial : Coyote & ACME Bombs

Problem : Removing minimum element from every subarray and count all such subarrays whose sum is divisible by K.

Think over another simple problem of similar kind, without removing any element. That is count how many subarrays’ sum is divisible by K. Then only move forward!

Considering some subarray from some index L to some index R where L < R (strictly less). Suppose minimum element of this subarray is at index M where L <= M and M <= R . It is easy to observe that for the left subarray ([L,M-1]) and the right subarray ([M+1,R ]) will have their own minimum element independent of index M. Thus after solving the problem for any subarray, we have to divide the problem in 2 different independent parts. This will be done with the help of recursion (Divide & Conquer).

Now the issue is how to solve the problem for a particular subarray. In a subarray $[L,R]$ with minimum at index $M$, we have to consider these subarrays:-

  1. Subarrays starting at index M and going towards R
  2. Subarrays starting at index M and going towards L
  3. Subarrays starting at some index x less than M and completing at some index y greater than M. That is L<=x<M<y<=R.

Lets solve them one by one :-

  1. Remove the element at index M (bcoz v have to discard element at index M), that is start with element at index M+1 and traverse towards R adding elements one by one and checking at each step whether the sum is divisible by K or not. (can be done using modulo % operator).
  2. Similarly, Remove the element at index M, that is start with element at index M-1 and traverse towards L adding elements one by one and checking at each step whether the sum is divisible by K or not. (can be done using modulo % operator).
  3. This one is interesting. For finding these kind of subarrays, we could take help from the above two subarrays. Lets assume that there are u subarrays starting at index M and going towards index L having reminder r (when divided with K). Also say there are v subarrays starting at index M and going towards index R having reminder K-r. Each pair of these subarray also forms a subarray eligible to be counted. (Why ? If you merge two subarrays having reminder $2$ and $K-2$, the merged subarray will have reminder 0). Thus the answer would be u*v.

After solving for a subarray, one has to call two recursion calls. The time complexity of this problem would be like Quicksort where u divide the subrray into 2 segments and the extra time other than recursion is O(n) (bcoz u have to traverse each segment to save reminders into some map).

U will have to read the solution now after understanding these key points!

The link to the solution is

http://ideone.com/S5fPvC

If u have any queries or doubts, feel free to comment or contact our team!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s