0
$\begingroup$

You are given a list of $0$’s and $1$’s: $B[1]$, $B[2]$, . . . , $B[N]$. A sublist of this list is any contiguous segment of elements—i.e., $A[i]$, $A[i + 1]$, . . . , $A[j]$, for some $i$ and $j$. A sublist is said to be Heavy, if the number of $1$’s in it is at least as much as the number of $0$’s in it.

We want to partition the entire list into Heavy sublists. That is, a valid partition is a collection of Heavy sublists, such that each of the N elements is part of exactly one of the sublists. We want to find the number of ways of doing so.

For example, suppose $N$ was $3$ and $B = [1, 0, 1]$. Then all the sublists in this are Heavy, except for the sublist which contains only the second element $([0])$. The various valid partitions are as follows: $( [1, 0, 1] ) $$( [1, 0], [1] )$
$( [1], [0, 1] )$

Since there are $3$ ways to do this, the answer for this would be $3$.
Compute the number of ways of partitioning the given list into Heavy sublists for the following instances.

(a) $N = 8, B = [0, 1, 1, 0, 0, 1, 1, 1]—i.e., B[1] = 0, B[1] = 1, . . . , B[8] = 1$
(b) $N = 9, B = 1, 1, 0, 0, 1, 0, 0, 1, 1—i.e., B[1] = 1, B[1] = 1, . . . , B[9] = 1$
(c) $N = 9, B = 1, 0, 1, 0, 1, 1, 0, 1, 1—i.e., B[1] = 1, B[1] = 0, . . . , B[9] = 1$

This is the first question that I am asking on Math.SE. I am sorry if I am being too direct in asking the question. source:- Q.$3$ ZIO-$2018$

How can i solve it by mathematical approach?

$\endgroup$
  • $\begingroup$ You should show your own effort, not just copy the given sample test cases. $\endgroup$ – user21820 Jan 16 at 15:53
2
$\begingroup$

For each length of initial segment that is heavy, find the number of valid heavy partitions of the remainder of the list, then add these up. To find the number of valid heavy partitions of the remainder of the list, apply this same method recursively.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can you please be little brief or demonstrate how with an example. well this is a pen and paper test. $\endgroup$ – Ayush Raj Oct 28 '19 at 12:11
  • $\begingroup$ @AyushRaj Oh. I figured from the "dynamic programming" and "computer science" tags this was about programming an algorithm. $\endgroup$ – eyeballfrog Oct 28 '19 at 12:13
  • $\begingroup$ @Ayush I think the answer as given is a descriptive solution. It can be worked out manually for small sets. $\endgroup$ – Daniel Mathias Oct 28 '19 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.