1

For a set S={1,2,3}, I perform all possible contiguous partitioning on the set to get {{1},{2},{3}},{{1,2},{3}},{{1},{2,3}},{{1,2,3}}. Lets call each partition a piece. I need to efficiently calculate sum of the following term over all the partitioning.

(sum of all numbers in the piece)*(length of the piece)

Example: If set is A={1,3,6} then the pieces are:

B = {{1},{3},{6}} and value = (1)*1 +(3)*1 +(6)*1 = 10

B = {{1,3},{6}} and value = (1+3)*2+(6)*1 = 14

B = {{1},{3,6}} and value = (1)*1 +(3+6)*2 = 19

B = {{1,3,6}} and value = (1+3+6)*3 = 30

Total sum of values = 10+14+19+30 = 73.

I am not able to think of any better way other than simulating the required procedure. I need only the total sum and no intermediate values or partitioning. How can this be done efficiently?

P.S> This is not a homework question. I am a programming enthusiast curious to learn the theorems or algorithms related to above concept. I think this is more mathematical, so have asked here and not on stackoverflow.

Gerry Myerson
  • 179,216
Shridhar R Kulkarni
  • 171
  • There is a tricky pattern here which I am not able to find out. Using the pattern we can get the desired answer in less than O(n^2) for sure. – Shridhar R Kulkarni Sep 25 '16 at 12:42
  • For a given set, every element will be multiplied by a number and sum of all such values will be taken. For example if set is {{1,2}} , partitions be like {{1},{2}}, {{1,2}}. So here 1 gets multiplied by 1 and 2, and 2 gets multiplied by 1 and 2 as well. So 1 & 2 both get multiplied by 3 in total and answer will be 13 + 23. If the set is {x,y} answer will be x3+y3. For set of size 2 the multiplication values be [3,3]. I have manually done this for set sizes till 6. [1] [3,3] [7,8,7] [15,18,18,15] [31,38,40,38,31] [61,76,82,82,76,61] For any partition size how can we proceed? – Shridhar R Kulkarni Sep 25 '16 at 15:01
  • it is an outgoing contest : you ask MSE users to do your work ? is this to answer on another pages ? –  Sep 27 '16 at 01:21
  • I didn't know about the rule. This is the first time I asked a question here. Anyways the motive was to share the learnings. – Shridhar R Kulkarni Sep 27 '16 at 08:33

1 Answers1

0

After lots of scribbling on paper and with a friend's help I am here with a solution. Hope it is of some use to the community.

As I mentioned in comment, We had to find the pattern.

Example

A={1,3,6}

B = {{1},{3},{6}} and value = (1)*1 +(3)*1 +(6)*1 = 10

B = {{1,3},{6}} and value = (1+3)*2+(6)*1 = 14

B = {{1},{3,6}} and value = (1)*1 +(3+6)*2 = 19

B = {{1,3,6}} and value = (1+3+6)*3 = 30

Total sum of values = 10+14+19+30 = 73.

Constructing an Equation

Overall if we see, it is 1*(7)+3*(8)+6*(7) = 73.

Where did I get this [7,8,7] from? I counted manually by how much each element gets multiplied to form the result.Irrespective of the elements in set of size 3, the multiplication vector will be [7,8,7].

For various size of sets the multiplication vector is as follows:

1
3 3 
7 8 7 
15 18 18 15
31 38 40 38 31

and so on..

How to find the multiplication vector for any size of input set?

If you notice here, second half of the multiplication vector is the mirror image of the first half. So you need to find the pattern for the first half.

Let us call multiplication vector as count. Let n = size of the given set.

$count[0] = 2^{n}-1$

And for ith element(excluding first, till half of the array)

$count[i] = count[i-1]+ 2^{n-i-1} - 2^{i-1}$

For Programming Enthusiasts

  1. Pay attention to Integer overflows.
  2. Optimize the exponentiation by using modular arithmetic exponentiation.
  3. The subtraction operation in $count[i] = count[i-1]+ 2^{n-i-1} - 2^{i-1}$ should be done using (a-b)%c = (a%c - b%c + c)%c.

Time Complexity

To calculate $(x^y)$ % p time complexity will be $O(logy)$. So for a set of size n the complexity will be O(nlogn)

Shridhar R Kulkarni
  • 171
  • it's a dito of my answer ... you ask a question, wait for answers and then reproduce one of them ( or what you understood ) ... not so fair –  Sep 26 '16 at 19:57
  • Your knowledge(and reputation if you are concerned about it) is far more better than mine(novice). So the motto was not reproduction at all. The way we have shared our learnings are totally different even if the solution is same(I got to know that after your comment.). I had posted my answer without seeing yours. And a step ahead, I could have accepted my own answer but I have not done so. I tried up-voting your answer but I don't have reputation of at least 15 so my up-vote is not yet visible. The aim was to contribute to the community. Still If you still think so I will down my answer. – Shridhar R Kulkarni Sep 27 '16 at 08:52