I have a progression "a", where the first two numbers are given (a1 and a2) and every next number is the smallest sum of subarray which is bigger than the previous number.

For example if i have a1 = 2 and a2 = 3, so the progression will be

2, 3, 5(=2+3), 8(=3+5), 10(=2+3+5), 13(=5+8), 16(=3+5+8), 18(=2+3+5+8=8+10), 23(=5+8+10=10+13), 26(=3+5+8+10), 28(=2+3+5+8+10), 29(=13+16)...

I need to find the Nth number in this progression. ( Time limit is 0.7 seconds)

(a1 is smaller than a2, a2 is smaller than 1000 and N is smaller than 100000)

I tried priority queue, set, map, https://www.geeksforgeeks.org/find-subarray-with-given-sum/ and some other things.

I though that the priority queue would work, but it exceeds the memory limit (256 MB), so i am pretty much hopeless.

Here's what is performing the best at the moment.

int main(){
  int a1, a2, n;
  cin>>a1>>a2>>n;

  priority_queue< int,vector<int>,greater<int> > pq;
  pq.push(a1+a2);

  int a[n+1];//contains sum of the progression
  a[0]=0;
  a[1]=a1;
  a[2]=a1+a2;

  for(int i=3;i<=n;i++){

    while(pq.top()<=a[i-1]-a[i-2])
      pq.pop();

    a[i]=pq.top()+a[i-1];

    pq.pop();

    for(int j=1; j<i && a[i]-a[j-1]>a[i]-a[i-1] ;j++)
      pq.push(a[i]-a[j-1]);

  }
  cout<<a[n]-a[n-1];
}

I've been trying to solve this for the last 4 days without any success. Sorry for the bad english, i am only 14 and not from an english speaking coutry.

SOLUTION (Big thanks to n.m. and גלעד ברקן)

V1 (n.m.'s solution)

 using namespace std;

 struct sliding_window{
   int start_pos;
   int end_pos;
   int sum;
   sliding_window(int new_start_pos,int new_end_pos,int new_sum){
     start_pos=new_start_pos;
     end_pos=new_end_pos;
     sum=new_sum;
   }
 };

 class Compare{
 public:
    bool operator() (sliding_window &lhs, sliding_window &rhs){
       return (lhs.sum>rhs.sum);
    }
 };

 int main(){
   int a1, a2, n;
   //input
   cin>>a1>>a2>>n;
   int a[n+1];
   a[0]=a1;
   a[1]=a2;

   queue<sliding_window> leftOut;

   priority_queue< sliding_window, vector<sliding_window>, Compare> pq;
   //add the first two sliding window positions that will expand with time
   pq.push(sliding_window(0,0,a1));
   pq.push(sliding_window(1,1,a2));

   for(int i=2;i<n;i++){
     int target=a[i-1]+1;

     //expand the sliding window with the smalest sum
     while(pq.top().sum<target){
       sliding_window temp = pq.top();
       pq.pop();
       //if the window can't be expanded, it is added to leftOut queue
       if(temp.end_pos+1<i){
         temp.end_pos++;
         temp.sum+=a[temp.end_pos];
         pq.push(temp);
       }else{
         leftOut.push(temp);
       }
     }

     a[i]=pq.top().sum;
     //add the removed sliding windows and new sliding window in to the queue
     pq.push(sliding_window(i,i,a[i]));
     while(leftOut.empty()==false){
       pq.push(leftOut.front());
       leftOut.pop();
     }

   }
   //print out the result
   cout<<a[n-1];
}

V2 (גלעד ברקן's solution)

int find_index(int target, int ps[], int ptrs[], int n){
  int cur=ps[ptrs[n]]-ps[0];
  while(cur<target){
    ptrs[n]++;
    cur=ps[ptrs[n]]-ps[0];
  }
  return ptrs[n];
}

int find_window(int d, int min, int ps[], int ptrs[]){
  int cur=ps[ptrs[d]+d-1]-ps[ptrs[d]-1];
  while(cur<=min){
    ptrs[d]++;
    cur=ps[ptrs[d]+d-1]-ps[ptrs[d]-1];
  }
  return ptrs[d];
}

int main(void){
  int a1, a2, n, i;
  int args = scanf("%d %d %d",&a1, &a2, &n);
  if (args != 3)
    printf("Failed to read input.\n");

  int a[n];
  a[0]=a1;
  a[1]=a2;

  int ps[n+1];
  ps[0]=0;
  ps[1]=a[0];
  ps[2]=a[0]+a[1];
  for (i=3; i<n+1; i++)
    ps[i] = 1000000;

  int ptrs[n+1];
  for(i=0;i<n+1;i++)
    ptrs[i]=1;

  for(i=2;i<n;i++){
    int target=a[i-1]+1;
    int max_len=find_index(target,ps, ptrs, n);
    int cur=ps[max_len]-ps[0];
    int best=cur;

    for(int d=max_len-1;d>1;d--){
      int l=find_window(d, a[i-1], ps, ptrs);
      int cur=ps[l+d-1]-ps[l-1];

      if(cur==target){
        best=cur;
        break;
      }

      if(cur>a[i-1]&&cur<best)
        best=cur;
    }
    a[i]=best;
    ps[i+1]=a[i]+ps[i];
  }

  printf("%d",a[n-1]);
}

3 Answers

1
n.m. On Best Solutions

Your priority queue is too big, you can get away with a much smaller one.

Have a priority queue of subarrays represenred e.g. by triples (lowerIndex, upperIndex, sum), keyed by the sum. Given array A of size N, for each index i from 0 to N-2, there is exactly one subarray in the queue with lowerIndex==i. Its sum is the minimal possible sum greater than the last element.

At each step of the algorithm:

  1. Add the sum from the first element of the queue as the new element of A.
  2. Update the first queue element (and all others with the same sum) by extending its upperIndex and updating sum, so it's greater than the new last element.
  3. Add a new subarray of two elements with indices (N-2, N-1) to the queue.

The complexity is a bit hard to analyse because of the duplicate sums in p.2 above, but I guess there shouldn't be too many of those.

2
גלעד ברקן On

It might be enough to try each relevant subarray length to find the next element. If we binary search on each length for the optimal window, we can have an O(n * log(n) * sqrt(n)) solution.

But we can do better by observing that each subarray length has a low bound index that constantly increases as n does. If we keep a pointer to the lowest index for each subarray length and simply iterate upwards each time, we are guaranteed each pointer will increase at most n times. Since there are O(sqrt n) pointers, we have O(n * sqrt n) total iterations.

A rough draft of the pointer idea follows.

UPDATE

For an actual submission, the find_index function was converted to another increasing pointer for speed. (Submission here, username "turnerware"; C code here.)

let n = 100000

let A = new Array(n)

A[0] = 2
A[1] = 3

let ps = new Array(n + 1)

ps[0] = 0
ps[1] = A[0]
ps[2] = A[0] + A[1]

let ptrs = new Array(n + 1).fill(1)

function find_index(target, ps){
  let low = 0
  let high = ps.length
  while (low != high){
    let mid = (high + low) >> 1
    let cur = ps[mid] - ps[0]
    if (cur <= target)
      low = mid + 1
    else
      high = mid
  }
  return low
}

function find_window(d, min, ps){
  let cur = ps[ptrs[d] + d - 1] - ps[ptrs[d] - 1]

  while (cur <= min){
    ptrs[d]++
    cur = ps[ptrs[d] + d - 1] - ps[ptrs[d] - 1]
  }
  return ptrs[d]
}

let start = +new Date()

for (let i=2; i<n; i++){
  let target = A[i-1] + 1
  let max_len = find_index(target, ps)
  let cur = ps[max_len] - ps[0]
  let best = cur

  for (let d=max_len - 1; d>1; d--){
    let l = find_window(d, A[i-1], ps)
    let cur = ps[l + d - 1] - ps[l - 1]

    if (cur == target){
      best = cur
      break
    }

    if (cur > A[i-1] && cur < best)
      best = cur
  }

  A[i] = best
  ps[i + 1] = A[i] + ps[i]
}

console.log(A[n - 1])
console.log(`${ (new Date - start) / 1000 } seconds`)

Just for fun and reference, this prints the sequence and possible indexed intervals corresponding to the element:

let A = [2, 3]
let n = 200
let is = [[-1], [-1]]
let ps = [A[0], A[0] + A[1]]
ps[-1] = 0

for (let i=2; i<n + 1; i++){
  let prev = A[i-1]
  let best = Infinity
  let idxs
  
  for (let j=0; j<i; j++){
    for (let k=-1; k<j; k++){
      let c = ps[j] - ps[k]
      if (c > prev && c < best){
        best = c
        idxs = [[k+1,j]]
      } else if (c == best)
        idxs.push([k+1,j])
    }
  }
  
  A[i] = best
  is.push(idxs)
  ps[i] = A[i] + ps[i-1]
}

let str = ''

A.map((x, i) => {
  str += `${i}, ${x}, ${JSON.stringify(is[i])}\n`
})

console.log(str)

0
Dopevoponop On

Looks like a sliding window problem to me.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    if(argc != 4) { 
        cout<<"Usage: "<<argv[0]<<" a0 a1 n"<<endl;
        exit(-1);
    }
    int a0 = stoi(argv[1]);
    int a1 = stoi(argv[2]);
    int n  = stoi(argv[3]);
    int a[n];                           // Create an array of length n
    a[0] = a0;                          // Initialize first element
    a[1] = a1;                          // Initialize second element
    for(int i=2; i<n; i++) {            // Build array up to nth element
        int start  = i-2;               // Pointer to left edge of "window"
        int end    = i-1;               // Pointer to right edge of "window"
        int last   = a[i-1];            // Last num calculated
        int minSum = INT_MAX;           // Var to hold min of sum found
        int curSum = a[start] + a[end]; // Sum of all numbers in the window
        while(start >= 0) {             // Left edge is still inside array
            // If current sum is greater than the last number calculated
            // than it is a possible candidate for being next in sequence
            if(curSum > last) {         
                if(curSum < minSum) {   
                    // Found a smaller valid sum 
                    minSum = curSum;
                }   
                // Slide right edge of the window to the left
                // from window to try to get a smaller sum. 
                // Decrement curSum by the value of removed element
                curSum -= a[end];
                end--; 
            }   
            else {
                // Slide left edge of window to the left
                start--;
                if(!(start < 0)) {
                    // Increment curSum by the newly enclosed number
                    curSum += a[start];
                }   
            }   
        }   
        // Add the min sum found to the end of the array.
        a[i] = minSum;   
    }   
    // Print out the nth element of the array
    cout<<a[n-1]<<endl;
    return 0;
}