Consider an array A of length n. The array contains only integers in the range 1 to s. For example take s = 6, n = 5 and A = (2, 5, 6, 3, 1). Let us define g(A) as the collection of sums of all the non-empty contiguous subarrays of A. In this case g(A) = [2,5,6,3,1,7,11,9,4,13,14,10,16,15,17]. The steps to produce g(A) are as follows:

The subarrays of A are (2), (5), (6), (3), (1), (2,5), (5,6), (6,3), (3,1), (2,5,6), (5,6,3), (6,3,1),(2,5,6,3), (5,6,3,1), (2,5,6,3,1). Their respective sums are 2,5,6,3,1,7,11,9,4,13,14,10,16,15,17.

In this case all the sums are distinct.

However, if we looked at g((1,2,3,4)) then the value 3 occurs twice as a sum and so the sums are not all distinct.

Task

For each s from 1 upwards, your code should output the largest n so that there exists an array A of length n with distinct subarray sums.

Your code should iterate up from s = 1 giving the answer for each s in turn. I will time the entire run, killing it after one minute.

Your score is the highest s you get to in that time.

In the case of a tie, the first answer wins.

Examples

The answers for s = 1..12 are n=1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9.

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

  • s = 19 by Arnauld in C
  • I don't think the requirement of making the programs output results starting from \$ s=1 \$ is a good idea. Once a particular \$ s \$ value is known, the program could simply output that number instead of doing any calculation. You might instead measure the solution that is able to find the largest \$ s \$ value in under a minute? – FryAmTheEggman Nov 8 at 21:35
  • 2
  • 1
    I downvoted this challenge because the nature of this challenge encourages some extent of hard-coding the solutions, and requiring the answer to "actually compute the output" is a non-observable requirement; there is no clear distinction between what is computed and what is hard-coded. – JungHwan Min Nov 9 at 3:31
  • 4
    @JungHwanMin Oh no! I am confused as the scoring system is basically the same as codegolf.stackexchange.com/questions/174407/… and codegolf.stackexchange.com/questions/165504/… and codegolf.stackexchange.com/questions/157049/… and... (and so on). What can I change to make you happy with my question? – Anush Nov 9 at 10:45
  • 3
    @JungHwanMin What's the difference between hard-coding the number 9 and hard-coding an array of length 9? It's good practice to avoid unobservable requirements whenever possible, but it's rather difficult for some kinds of challenges (fastest-code, anything related to quines, etc.). – Dennis Nov 9 at 15:48

C (gcc), s = 19

This is basically a port of my Node.js answer. It goes one step further with the default compiler options and two steps further with -O2 or -O3.

#include <stdio.h>
#include <string.h>
#include <stdint.h>

void search(uint8_t * arr, int n, uint8_t * sum, int * max, char * str, int depth) {
  int i, j, k, s;
  char tmp[16];

  // do we have a better array?
  if(depth > *max) {
    for(str[0] = '\0', i = 0; i < depth; i++) {
      sprintf(tmp, "%d ", arr[i]);
      strcat(str, tmp);
    }
    *max = depth;
  }

  // try to append i = 1 to n to the current array
  for(i = 1; i <= n; i++) {
    // provided that doing so does not produce a sum that was already encountered
    if(!sum[i]) {
      for(sum[s = i] = 1, j = depth; j && !sum[s += arr[j - 1]]; j--) {
        sum[s] = 1;
      }
      if(!j) {
        // this is valid: set the value in arr[] and do a recursive call
        arr[depth] = i;
        search(arr, n, sum, max, str, depth + 1);
      }
      // whether the recursive call was processed or not, we have to clear the flags
      // that have been set above
      for(sum[s = i] = 0, k = depth - 1; k >= j; k--) {
        sum[s += arr[k]] = 0;
      }
    }
  }
}

int solve(int n, char * str) {
  int     max = 0;              // best length so far
  int     hi = n * (n + 1) / 2; // highest possible sum for n
  uint8_t sum[hi + 1];          // encountered sums
  uint8_t arr[n];               // array

  memset(sum, 0, (hi + 1) * sizeof(uint8_t));
  search(arr, n, sum, &max, str, 0);

  return max;
}

/////////////////////////////////////////////////////////////////////////////////////

void main() {
  char str[128];
  int  n, res;

  for(n = 1; n <= 19; n++) {
    res = solve(n, str);
    printf("N = %d --> %d with [ %s]\n", n, res, str);
  }
}

Try it online!

  • Thanks again! I wonder what speedups will be possible. – Anush Nov 9 at 19:40
  • 1
    @Anush Just compiling with -O3 allows to reach \$N=19\$ on TIO. – Arnauld Nov 9 at 22:10
  • Could you add the main function to your answer so people can just copy and paste? – Anush Nov 10 at 19:13
  • 1
    @Anush Sure. Done. – Arnauld 2 days ago

Node.js, s = 17

Just a simple recursive search to get the ball rolling. Returns both the length and a valid array.

solve = n => {
  var max = 0,  // best length so far
      best,     // best array so far
      sum = {}; // encountered sums

  (search = a => {
    var i, j, k, s;

    // do we have a better array?
    if(a.length > max) {
      max = a.length;
      best = [...a];
    }

    // try to prepend i = 1 to n to the current array
    for(i = 1; i <= n; i++) {
      // provided that doing so does not produce a sum that was already encountered
      if((sum[j = 0, s = i] ^= 1) && a.every(n => sum[j++, s += n] ^= 1)) {
        search([i, ...a]);
      }
      // reset the flags that have been toggled above
      for(sum[s = i] ^= 1, k = 0; k < j; k++) {
        sum[s += a[k]] ^= 1;
      }
    }
  })([]);

  return [ max, best ];
}

Try it online!

  • Thank you for the first answer! – Anush Nov 9 at 16:55

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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