#StackBounty: #combinatorics #fastest-code Count arrays that are really unique

Bounty: 50

This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness.

Consider an array A of length n. The array contains only positive integers. For example A = (1,1,2,2). Let us define f(A) as the set of sums of all the non-empty contiguous subarrays of A. In this case f(A) = {1,2,3,4,5,6}. The steps to produce f(A) are as follows:

The subarrays of A are (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Their respective sums are 1,1,2,2,2,3,4,4,5,6. The set you get from this list is therefore {1,2,3,4,5,6}.

We call an array A unique if there is no other array B of the same length such that f(A) = f(B), except for the array A reversed. As an example, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6} but there is no other array of length 3 that produces the same set of sums.

Task

The task, for a given n and s is to count the number of unique arrays of that length. You can assume that s is between 1 and 9. You only need to count arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays you are counting only contain 1 and 2. However, the definition of uniqueness is with respect to any other array of the same length. As a concrete example [1, 2, 2, 2] is not unique as it gives the same set of sums as [1, 1, 2, 3].

You should count the reverse of an array as well as the array itself (as long as the array is not a palindrome of course).

Examples

s = 1, the answers for n = 2,3,4,5,6,7,8,9 are:

4, 3, 3, 4, 4, 5, 5, 6

For s = 1, the unique arrays of length 4 are

(1, 1, 1, 1)
(2, 1, 1, 2)
(2, 2, 2, 2)

s = 2, the answers for n = 2,3,4,5,6,7,8,9 are:

4, 8, 16, 32, 46, 69, 121, 177

An example of an array that is not unique with s = 2 is:

(3, 2, 2, 3, 3, 3). 

This has the same set of sums as both of: (3, 2, 2, 2, 4, 3) and (3, 2, 2, 4, 2, 3).

s = 8, the answers for n = 2,3,4,5,6,7,8,9 are:

4, 8, 16, 32, 64, 120, 244, 427

Score

For a given n, your code should output the answer for all values of s from 1 to 9. Your score is the highest value of n for which this completes in one minute.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

Leaderboard


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.