-1
$\begingroup$

Given a circular list of two numbers $-1,+1$.I have to partition them into $M$ sets each containing $K$ numbers. Each set has to consist of consecutive $K$ numbers from that list. The set can start from any point in the list.

1.A set is called positive if number of $+1$ are greater than $-1$.

2.A set is called negative if number of $-1$ are greater than $+1$.

Now I want to know if there's a way to partition them such that the number of positive sets are more than number of negative sets.

Take $K$ to be odd for simplicity so that a set can be either called positive or negative.

For eg- List $A$ = $(-1, -1, 1, 1, -1, 1, 1, -1, -1)$ and I have to partition it into $3$ sets with $3$ numbers in it. Then there are many ways : 1. {$A_3$,$A_4$,$A_5$}, {$A_6$,$A_7$,$A_8$} and {$A_9$,$A_1$,$A_2$}

  1. {$A_2$,$A_3$,$A_4$}, {$A_5$,$A_6$,$A_7$} and {$A_8$,$A_9$,$A_1$}

Here $2$ positive sets and $1$ negative set. So I can partition it.

I can only think of making every possible combination. Is there a way to do it efficiently and optimally.

$\endgroup$
  • $\begingroup$ There are only $K$ such divisions, which is not much to check. $\endgroup$ – Simon Marynissen Feb 17 '17 at 15:23
  • $\begingroup$ @SimonMarynissen How do you check it ? Can you explain it ? $\endgroup$ – Buckster Feb 17 '17 at 16:21
  • $\begingroup$ Just making every possible combination, I can't think of a better way at the moment. $\endgroup$ – Simon Marynissen Feb 17 '17 at 16:24
  • $\begingroup$ @SimonMarynissen This would take quadratic time. Not efficient at all. $\endgroup$ – Buckster Feb 17 '17 at 16:36
  • $\begingroup$ That depends on whether $K$ is much smaller than $|M|$. $\endgroup$ – Simon Marynissen Feb 17 '17 at 16:39
2
$\begingroup$

Let $N=KM$. Let $S_i = A_i+\ldots +A_{i+K-1}$, $A_{N+i}=A_{i}$. Obviously, $\{A_i,\ldots ,A_{i+K-1}\}$ is positive if $S_i$ is positive, and $\{A_i,\ldots ,A_{i+K-1}\}$ is negative if $S_i$ is negative.

The $S_i$ can be calculated recursively with little effort: $$ S_{i+1} = S_i+A_{i+K}-A_{i} $$ For each $j\in \{0,\ldots ,K-1\}$, introduce a counter $p_j$ ("positive") and an counter $n_j$ ("negative").

Start with initializing your counters and calculating $S_1$. Then calculate each $S_i, \; i=1,\ldots, N$ with the recursive formula shown above. If $S_i >0$, increase the $p_j$ for which $j\equiv i\pmod{K}$. If $S_i<0$, increase the $n_j$ for which $j\equiv i\pmod{K}$. At the end, find an index $j$ for which $p_j$ is greater than $n_j$. This $j$ gives you the starting position in the list. Use the biggest $p_j$ if you want to have the optimum.

If we apply this method to the given example, we get (one after another) $$ (S)_{i\in\{1,\ldots,9\}} = (-1,\,1,\,1,\,1,\,1,\,1,\,-1,\,-3,\,-3) $$ For the counters $p_0$ and $n_0$, we have taken the elements $S_3$, $S_6$ and $S_9$ into account (while we calculated the $S_i$). We find that two of them are positive and one is negative, therefore $p_0=2$ and $n_0=1$ in the end.

For the counters $p_1$ and $n_1$, we have taken the elements $S_1$, $S_4$ and $S_7$ into account. We find that one of them is positive and two are negative, therefore $p_1 = 1$ and $n_1=2$.

For the counters $p_2$ and $n_2$, we have taken the elements $S_2$, $S_5$ and $S_8$ into account. We find that two of them are positive and one is negative, therefore $p_2=2$ and $n_2=1$.

For $j=0$ and $j=2$, $p_j>n_j$ holds. Therefore we can split the list either in front of the elements with indices $\equiv 0\pmod{3}$ or in front of the elements with indices $\equiv 2\pmod{3}$.

$\endgroup$
  • $\begingroup$ Can you explain it briefly with the given example? The explanation is little hard to follow. Also if $K,M$ both are odd, is there any more optimization possible ? $\endgroup$ – Buckster Feb 17 '17 at 16:58
  • $\begingroup$ Is that $A_{N+i}$ in the $S_i$ a typo ? $\endgroup$ – Buckster Feb 17 '17 at 17:02
  • $\begingroup$ Where is a $A_{N+i}$ in the $S_i$? $\endgroup$ – Reinhard Meier Feb 17 '17 at 17:05
  • $\begingroup$ The definition $A_{N+i} = A_i$ is used to avoid distinction of cases. We extend the series of $A$s in order to make the description easier. The list is circular $\endgroup$ – Reinhard Meier Feb 17 '17 at 17:07
  • $\begingroup$ Sorry, I got it now. Can you explain with example in the question or any small example,please ? It would be very helpful. It's a little difficult for me to understand the solution as of right now. $\endgroup$ – Buckster Feb 17 '17 at 17:10

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.