11
1
This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.
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.
We will only consider arrays where the elements are either a given integer s
or s+1
. E.g. if s=1
the arrays would only contain 1
and 2
.
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 should not count the reverse of an array as well as the array itself.
Examples
s = 1
, the answer is always n+1
.
s = 2
, the answers counting from n = 1
up are:
2,3,6,10,20,32,52,86
s = 8
, the answers counting from n = 1
up are:
2,3,6,10,20,36,68,130
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
- n = 24 by Anders Kaseorg in Rust (34 seconds)
- n = 16 by Ourous in Clean (36 seconds)
- n = 14 by JRowan in Common Lisp (49 seconds)
So if s=8 then its an array of all possible combinations of 8 and 9, nothing else? – JRowan – 2018-10-24T17:22:59.557
@JRowan No. You don't count any of those arrays that have the same set of sums as some other array. – Anush – 2018-10-24T18:06:35.580
This part i am a little confused about We will only consider arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays would only contain 1 and 2. So if n is 2 and s is 3 what would the arrays to test be? – JRowan – 2018-10-24T18:21:39.037
what about [3,3] and im currently removing the reverse of the lists eg. [3,4]->[4,3] – JRowan – 2018-10-24T18:27:52.853
@JRowan (Corrected) If n = 2 and s = 3 the possible arrays are [3,3], [3,4], [4,3] and [4,4]. You can then remove the reverses as you say. – Anush – 2018-10-24T18:44:22.890
s and n: what is s ... I not understand good... – RosLuP – 2018-10-25T04:30:48.053
Why for the example Input: n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13), output is X = (3, 5, 1, 4) ???? {3,5,4} it is one subset of X and 3+5+4= 12 is not in S – RosLuP – 2018-10-25T06:46:39.783
that S and its result X are your example in the other code-golf tournament of the same problem – RosLuP – 2018-10-25T06:59:43.027
2
@RosLuP Firstly, you meant to post that on the other question, and secondly, [3, 5, 4] is a subset but not a subarray of [3, 5, 1, 4].
– Anders Kaseorg – 2018-10-25T23:17:49.077