Calculating sum after ranged-based subtractions

Question

The puzzle consists from something like this:

You will receive an array of integer with values, then you will receive X numbers. Each number (call it x) represents an index of a 1-indexed array. Look up the value in the array (call it y), then subtract 1 from all the values in the array in the range [x-y, x+y]. The minimum value is 0.

After the given number of operations, you must return the sum of all values in the array.

My code looks like this.

#include <cstdio>
int array[111111];

int main(){
  int m,n;
  unsigned long long int sum = 0;

  //here n is the size of the array, and m is the number of operations
  scanf("%d %d", &n, &m);

  for (int i = 0; i < n; i++){
    scanf("%d", &array[i]);
    sum+= array[i];
  }

  for (int i = 0; i < m; i++) {
    int idx;
    scanf("%d", &idx);
    int count= array[idx - 1];

    for (int j = (idx -1 -count >=0 ? idx -1 -count : 0); j < (idx + count <=n ? idx + count : n); j++)
      if (array[j]){
        sum--;
        array[j]--;
      }
  }

  printf("%d\n", sum);
}

It solves the problem, but does not pass in the worst case, that would be a ton of cases decreasing from the entire array, basically an O(n*n) (I think).

The value restrictions are:

• 1 ≤ N,M ≤ 100000;
• Value inside array index between 0 and 50000.

---

Test case:

Input:

10 4
1 2 0 8 4 2 9 8 1 3
9 5 10 6

Output:

23

Visualization of the test case:

For example, the first number that is read is 9. If we treat the number sequence as a 1-indexed array, we read value 1. This means that we need to subtract 1 from every value in the range [9-1, 9+1], which corresponds to the last three elements of the array.

Answer 1

Performance

From what I understand, your solution is as good as it would get. The "n^2" (it's more like O(n*m)) performance seems inevitable. It also seems that an array is the optimal data structure since you must index into it.

If you really want to remove the worst case (decreasing from the entire array), you could keep a count of the number of times you have subtracted from the whole array and let the array value be array[idx] - theCountIMentioned and the final sum be sum - n * theCountIMentioned. Despite this, the performance would still be nearly n^2, especially since decreasing all but one of the values would be an O(n) operation, so the worst case would be O(n * m).

Readability

On another note: to make the inner loop more readable consider the following two functions:

inline int min(int a, int b){
    return (a < b)? a : b;
}

inline int max(int a, int b){
    return (a > b)? a : b;
}

This would make the inner loop's header much more readable. (It would be for(int j = max(0, idx - 1 - count); j < min(idx + count, n); j++)).

Also, you should make the variable names more readable.

• n = arrayLength or even arrLen.
• m = numberOfOps or even opCt.

Answer 2

Whitespace

Make sure that your whitespace is consistent. The whitespace around operators is very messy, making it more difficult to recognize patterns. Similarly, the usage of whitespace before braces is inconsistent.

Multi-line for-loop

You have a dangerous multi-line for-loop in your code that has no enclosing braces. Sure... it works. If in a few days time you decide to add something below the if-statement, and just assume that the braces are there "because the if-statement is on multiple lines", you have a difficult time figuring out that the lines below the if-statement are outside the inner for-loop. Instead always use braces, or at least when a multi-line block is used.

Alternative algorithm

Instead of updating values for each range, you can instead use slightly more memory and save the actual range for each "operation". Now when we need to look up a number, we look at how many ranges intersect that index, and calculate the effective number. The upside of this approach is that instead of updating 100.000 values, we just save 2 values (min and max). The downside is that we need to repeatedly traverse a number of earlier ranges.

You could opt for a hybrid approach, where you save a fixed number of ranges before batch-updating the array.

It would look something like this:

const int buffer = 50;
int min_range[buffer];
int max_range[buffer];

//...

for (int j = 0; ... ) {
  scanf("%d", &index);
  range = array[index];
  for (int k = 0; k < j % buffer; k++) {
    if (min_range[k] <= index && index <= max_range[k]) {
      range--;
    }
  }
  min_range[k] = index - max(range, 0);
  max_range[k] = index + max(range, 0);

  if (j % buffer == 0) {
    //batch update each index
  }
}

For the worst case scenario where we have 100.000 values with 500.000 in them, and 100.000 operations and a buffer of 50, the old situation would require us to write 100.000 * 100.000 values. That's... a lot. Now we only need to write 100.000 * 2 + (100.000 / 50) * 100.000. That's... still a lot, but a lot less. Keep in mind that the larger the buffer, the more intersections have to be calculated. A buffer of 100.000 would mean that the last operation would need to calculate 100.000 intersections before calculating the final range of that operation.

Answer 3

So, after researching and talking to some people, I came up with an answer that runs fast enough to solve the problem in the given time of the puzzle.

The readability still poor on the main, but this code is for coding marathons, readability is not something you should really care when writing code for something like this. But the functions that I got to solve the problem are well written, so I think it will be clear.

The code:

#include <cstdio>

int A[1010101];
int tree[1010101];
int lazy[1010101];

void build(int node, int start, int end)
{
  if(start == end)
  {
    // Leaf node will have a single element
    tree[node] = A[start];
  }
  else
  {
    int mid = (start + end) / 2;
    // Recurse on the left child
    build(2*node, start, mid);
    // Recurse on the right child
    build(2*node+1, mid+1, end);
    // Internal node will have the sum of both of its children
    tree[node] = tree[2*node] + tree[2*node+1];
  }
}

void updateRange(int node, int start, int end, int l, int r, int val)
{
  if(lazy[node] != 0)
  {
    // This node needs to be updated
    tree[node] += (end - start + 1) * lazy[node];    // Update it
    if(start != end)
    {
      lazy[node*2] += lazy[node];                  // Mark child as lazy
      lazy[node*2+1] += lazy[node];                // Mark child as lazy
    }
    lazy[node] = 0;                                  // Reset it
  }
  if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
  return;
  if(start >= l and end <= r)
  {
    // Segment is fully within range
    tree[node] +=  (end - start + 1) * val;
    if(start != end)
    {
      // Not leaf node;
      lazy[node*2] +=val;
      lazy[node*2+1] += val;
    }
    return;
  }
  int mid = (start + end) / 2;
  updateRange(node*2, start, mid, l, r, val);        // Updating left child
  updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
  tree[node] = tree[node*2] + tree[node*2+1];        // Updating root with max value
}

int queryRange(int node, int start, int end, int l, int r)
{
  if(start > end or start > r or end < l)
  return 0;         // Out of range
  if(lazy[node] != 0)
  {
    // This node needs to be updated
    tree[node] += (end - start + 1) * lazy[node];            // Update it
    if(start != end)
    {
      lazy[node*2] += lazy[node];         // Mark child as lazy
      lazy[node*2+1] += lazy[node];    // Mark child as lazy
    }
    lazy[node] = 0;                 // Reset it
  }
  if(start >= l and end <= r)             // Current segment is totally within range [l, r]
  return tree[node];
  int mid = (start + end) / 2;
  int p1 = queryRange(node*2, start, mid, l, r);         // Query left child
  int p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
  return (p1 + p2);
}

int main(){
  int n,m;

  scanf("%d %d", &n, &m);

  for (int i = 0; i < n; ++i)
  scanf("%d", &A[i]);

  build(1,0,n-1);

  for (int i = 0; i < m; ++i)
  {
    int idx;
    scanf("%d",&idx);

    int count = queryRange(1,1,n,idx,idx);

    updateRange(1,0,n-1,
      (idx -1 -count >=0 ? idx -1 -count : 0),
      (idx + count <=n ? idx + count : n)-1,-1);
  }

  long long sum =0;
  for (int i = 1; i <= n; i++) {
    int leafval=queryRange(1,1,n,i,i);
    sum += leafval > 0 ? leafval : 0;
  }

  printf("%d\n", sum);
}

The solution is based on a segment tree, more specifically the lazy segment tree implementation.

When I need to update a range, I just update the tree branches that correspond to the range, and mark the children as "dirty".

Every time I need to access a node, I have to check if the node is dirty, and update it when needed.

This way, the update runs at O(log N), so, in the worst case, it will be O(M * log N) for the updates.

After that I need to force update of every leaf of the tree, because I have to check if any leaf got a negative value, and discart them. This costs O(N * log N).

On the end, the code is O((M * log N) + (N * log n)).