Как найти n-ю самую маленькую сумму подмассива, большую, чем x, в прогрессии, где даны первые два числа?

Question

У меня есть прогрессия "a", где даны первые два числа (a1 и a2), а каждое следующее число - наименьшая сумма подмассива, которая больше, чем предыдущее число.

Например, если у меня есть a1 = 2 и a2 = 3, то прогрессия будет

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) ...

Мне нужно найти N-е число в этой прогрессии. (Ограничение по времени составляет 0,7 секунды)

(a1 меньше a2, a2 ​​меньше 1000 и N меньше 100000)

Я пробовал приоритетную очередь, сет, карту, https://www.geeksforgeeks.org/find-subarray-with-given-sum/ и некоторые другие вещи.

Я думаю, что очередь с приоритетом будет работать, но она превышает лимит памяти (256 МБ), поэтому я почти безнадежен.

Вот то, что работает лучше всего на данный момент.

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];
}

Я пытался решить эту проблему последние 4 дня безуспешно. Извините за плохой английский, мне всего 14, а не англоязычный.

РЕШЕНИЕ (Большое спасибо n.m. и גלעד ברקן)

V1 (н.м. раствор)

 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 (решение גלעד ברקן)

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]);
}

Answer 1

Может быть достаточно попробовать каждую соответствующую длину подмассива, чтобы найти следующий элемент.Если мы выполним бинарный поиск по каждой длине для оптимального окна, у нас может быть решение O(n * log(n) * sqrt(n)).

Но мы можем добиться большего, наблюдая, что каждая длина подмассива имеет нижний ограниченный индекс, который постоянно увеличивается как nделает.Если мы сохраняем указатель на самый низкий индекс для каждой длины подмассива и просто повторяем каждый раз вверх, мы гарантируем, что каждый указатель увеличится не более чем в n раз.Поскольку существует O(sqrt n) указателей, у нас есть O(n * sqrt n) полных итераций.

Далее следует черновой вариант идеи указателя.

ОБНОВЛЕНИЕ

Для фактического представления,find_index функция была преобразована в другой увеличивающийся указатель скорости.(Представление здесь , имя пользователя "turnerware"; код C здесь .)

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`)

Просто для забавы и для справки, он печатает последовательность и возможные индексированные интервалы, соответствующие элементу:

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)

Answer 2

Ваша приоритетная очередь слишком велика, вы можете уйти с гораздо меньшей.

Иметь приоритетную очередь представленных подмассивов, например, по тройкам (lowerIndex, upperIndex, sum), с суммой. Для данного массива A размера N для каждого индекса i от 0 до N-2 в очереди находится ровно один подмассив с lowerIndex == i. Его сумма - минимально возможная сумма, превышающая последний элемент.

На каждом шаге алгоритма:

1. Добавить сумму из первого элемента очереди в качестве нового элемента A.
2. Обновите первый элемент очереди (и все остальные с такой же суммой), расширив его upperIndex и обновив сумму, чтобы он был больше, чем новый последний элемент.
3. Добавление нового подмассива из двух элементов с индексами (N-2, N-1) в очередь.

Сложность немного сложна для анализа из-за повторяющихся сумм в п.2 выше, но я думаю, их не должно быть слишком много.

Answer 3

Мне кажется, проблема со скользящим окном.

#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;
}