Storing and processing large arrays to compute dot products

Question

Problem Statement (from HackerRank)

We have two arrays \$a\$ and \$b\$ of length \$N\$, initially all values equals to zero. We have \$Q\$ operations. Let's define three types of operations on this arrays:

• 1 l r c: Increase \$a_l, a_{l+1}, \ldots, a_r\$ by \$c\$.
• 2 l r c: Increase \$b_l, b_{l+1}, \ldots, b_r\$ by \$c\$.
• 3 l r: Print \$a_l\cdot b_l + a_{l+1}\cdot b_{l+1} +\ldots+ a_r\cdot b_r\$ in modulo \$1000000007\$.

Input Format

First line of the input consists of \$N\$ and \$Q\$. Next \$Q\$ lines contain one of the three types of operations.

Constraints

• \$1 \le N \le 10^9\$
• \$1 \le Q \le 200000\$
• \$1 \le c \le 10000\$
• \$1 \le l \le r \le N\$

Output Format

Whenever you get a type 3 operation, you should print the answer in a new line.

Sample Input 1

5 3 
1 1 5 5 
2 2 4 2 
3 3 4

Sample Output 1

20

Sample Input 2

10 20
1 9 9 6768
2 5 5 2202
3 7 7
2 3 9 1167
2 1 7 8465
3 1 5
2 1 1 1860
3 9 9
2 5 5 2153
1 5 7 749
3 1 1
2 8 10 3129
3 1 1
1 2 10 2712
2 1 8 79
1 1 6 4645
1 7 7 1358
3 2 10
1 9 9 8677
3 8 10

Sample Output 2

0
0
7898256
0
0
506356461
98353320

How can I efficiently store and process data for this problem?

#include<stdio.h>
#include<string.h>
int main()
{
    long n,q,ch,l,r,c,i,j;
    /* n, q, l, r, c works as per problem statement.
       ch is used to scan the first digit of operation.
       i and j are used to control the loops. */
    scanf("%ld %ld",&n,&q);
    long a[n],b[n];
    memset(&a, 0, sizeof a);
    memset(&b, 0, sizeof b);
    for(i=0;i<n;i++)    //Init to 0
    {
        a[i]=0;
        b[i]=0;
    }
    for(i=0;i<q;i++)
    {
        scanf("%ld ",&ch);  //Look for the first digit
        switch(ch)
        {
            case 1:
                scanf("%ld %ld %ld",&l,&r,&c);
                l--;
                for(j=l;j<r;j++)
                    a[j]+=c;    //Adds c to every element of a
                break;
            case 2:
                scanf("%ld %ld %ld",&l,&r,&c);
                l--;
                for(j=l;j<r;j++)
                    b[j]+=c;    //Adds c to every element of b
                break;
            case 3:
                scanf("%ld %ld",&l,&r);
                l--;
                c=0;
                for(j=l;j<r;j++)
                    c+=a[j]*b[j];   //Adds the product
                printf("%ld\n",c%1000000007);   //Prints the value after using mod
                break;
        }
    }
}

Answer 1

This is a fairly straightforward implementation that seems to get the job done at least for the simple input you posted. Overall, it's easy to read and understand, given the problem description. Here are some ways I think it could be improved.

Naming

You've named all the variables similarly to how they are named in the problem statement. That's fine for an assignment or exercise, but it would be a real pain to maintain later on. You have a comment describing the names, but it assumes the person reading it has the problem statement. That's rarely the case in the real world.

The variable names n, i, and j aren't terrible. I'd leave i and j, but rename n to something descriptive like numElements (or, if you prefer num_elements).

The names q, l, ch, r, and c are terrible and confusing. I'd make q something like numLines or numInputLines or something like that. l and r are the start and end of the range of indexes you want to modify, so I'd name them start and end.

c and ch are likely to be confused. Also, ch seems like it's a remnant from an earlier version when it was declared as a char type instead of a long. It's used to get the user's input, so you could name it userInput or mode or something more appropriate. c is the value you're adding to all the inputs. Since this is an exercise, it's just an abstract value that doesn't have any real meaning. Normally, I'd suggest calling it whatever it is, but that's hard in this case. Something generic like value or operand could work.

Functions

Your code does a few different things:

1. Gets the size of the arrays and number of lines of input
2. Creates and initializes the arrays
3. Processes the inputs

You should separate those into functions like this:

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

int getNumberOfElementsAndLines (size_t* outElements, size_t* outLines)
{
    long numScanned = scanf("%zu %zu", outElements, outLines);
    int result = (numScanned == 2);
    if ((*outElements < 1) || (*outElements > 1000000000) || (*outLines < 1) || (*outLines > 200000))
    {
        result = 0;
    }

    return result;
}

int allocateAndInitArrays (const size_t numElements, long** outA, long** outB)
{
    // Make sure the inputs are valid
    if ((outA == NULL) || (outB == NULL) || (numElements == 0))
    {
        return 0;
    }

    // Allocate and clear A and if successful, allocate and clear B
    *outA = calloc (numElements, sizeof(**outA));
    *outB = calloc(numElements, sizeof(**outB));

    if (*outB == NULL)
    {
        free(*outA);
        *outA = NULL;
    }

    return ((*outA != NULL) && (*outB != NULL));
}

int getAndProcessInput (long* a, long* b, const size_t numElements, const size_t numLines)
{
    for (size_t i = 0; i < numLines; i++)
    {
        long mode   = 0;
        int numScanned = scanf("%ld ", &mode);
        if (numScanned != 1)
        {
            return 0;
        }

        long l, r, c;
        switch (mode)
        {
            case 1:
                scanf("%ld %ld %ld",&l,&r,&c);
                l--;
                for(long j = l; j < r; j++)
                    a[ j ] += c;    //Adds c to every element of a
                break;

            case 2:
                scanf("%ld %ld %ld",&l,&r,&c);
                l--;
                for(long j = l; j < r; j++)
                    b[ j ] += c;    //Adds c to every element of b
                break;

            case 3:
                scanf("%ld %ld",&l,&r);
                l--;
                c=0;
                for(long j = l; j < r; j++)
                    c += a[ j ] * b[ j ];   //Adds the product
                printf("%ld\n",c%1000000007);   //Prints the value after using mod
                break;


            default:
                // Error in input
                return 0;
                break;
        }
    }

    return 1;
}

Then your main would look something like this:

int main()
{
    int     result  = 0;
    size_t  numElements = 0;
    size_t  numLines = 0;
    result = getNumberOfElementsAndLines(&numElements, &numLines);

    long*   a = NULL;
    long*   b = NULL;
    if (result == 1)
    {
        result = allocateAndInitArrays(numElements, &a, &b);
    }

    if (result == 1)
    {
        result = getAndProcessInput(a, b, numElements, numLines);
    }

    free(a);
    free(b);

    return result;
}

Memory

You'll notice above that I used calloc() to allocate the memory on the heap instead of the stack. Stack space is limited, and there's a lot more memory available on the heap. That may fix your issue getting a segfault.

Error Handling

I added a little bit of error handling. It needs more. You should check to make sure you got valid results from functions like scanf(), for example. What if the user entered a negative number? What if they entered 0? Etc.

Answer 2

Fenwick tree

Instead of using a normal array, you could use a Fenwick tree to store each of the two arrays. Fenwick trees can do range updates (operations 1 and 2) in logarithmic time instead of linear time. The third operation would require \$O(n\log n)\$ time instead of \$O(n)\$ time, so I suppose if there were a lot of those operations, it could make things slower.

Sample implementation

I wrote this sample implementation to show how a Fenwick tree could solve this problem. I combined the Fenwick tree with an additional update array to do the dot product step in linear time. The update array simply stores the change in value from one array index to the next.

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

void rangeUpdate(long *tree, long treeSize,
        long left, long right, long value)
{
    while (left < treeSize) {
        tree[left] += value;
        left |= (left + 1);
    }
    right++;
    while (right < treeSize) {
        tree[right] -= value;
        right |= (right + 1);
    }
}

long getVal(const long *tree, long treeSize, long i)
{
    long ret = 0;

    while (i >= 0) {
        ret += tree[i];
        i &= i + 1;
        i--;
    }
    return ret;
}

int main(void)
{
    long  arraySize  = 0;
    long  numQueries = 0;
    long *tree1      = NULL;
    long *tree2      = NULL;
    long *update1    = NULL;
    long *update2    = NULL;

    if (scanf("%ld %ld\n", &arraySize, &numQueries) != 2)
        exit(1);
    arraySize += 2;
    tree1   = calloc(arraySize, sizeof(*tree1));
    tree2   = calloc(arraySize, sizeof(*tree2));
    update1 = calloc(arraySize, sizeof(*tree1));
    update2 = calloc(arraySize, sizeof(*tree2));
    if (tree1 == NULL || tree2 == NULL || update1 == NULL || update2 == NULL)
        exit(1);
    for (long i = 0; i < numQueries; i++) {
        long operation = 0;
        long left      = 0;
        long right     = 0;
        long value     = 0;
        if (scanf("%ld", &operation) != 1)
            exit(1);
        switch (operation) {
            case 1:
            case 2:
            {
                long *tree   = (operation == 1) ? tree1 : tree2;
                long *update = (operation == 1) ? update1 : update2;
                if (scanf("%ld %ld %ld\n", &left, &right, &value) != 3)
                    exit(1);
                rangeUpdate(tree, arraySize, left, right, value);
                update[left]    += value;
                update[right+1] -= value;
                break;
            }
            case 3:
            {
                long     val1   = 0;
                long     val2   = 0;
                uint64_t result = 0;

                if (scanf("%ld %ld\n", &left, &right) != 2)
                    exit(1);

                val1   = getVal(tree1, arraySize, left);
                val2   = getVal(tree2, arraySize, left);
                result = (uint64_t) val1 * val2;
                for (long i = left+1; i <= right; i++) {
                    val1 += update1[i];
                    val2 += update2[i];
                    result += (uint64_t) val1 * val2;
                }
                printf("%ld\n", (long) (result % 1000000007));
                break;
            }
        }
    }
}

Answer 3

For N = 10⁹ you have to store about 7.4 GB data, if you merely use longs with a size of 4 bytes.

This is not feasible, which, I assume, is the whole point of the problem.

You have 200000 Qs - storing the Qs instead takes up only 11 bytes per Q - one byte to determine the operation, 8 bytes for the two values which can go up to 10⁹and 2 bytes for c, which fits into 16 bits, as it's not higher than 10000.

If you store Q, you end up with around 2 MB of data.

You could apply the Q operations at runtime to a single long (long) and then print each value individually. This algorithm will be memory-efficient, but very very slow.

Looking at the problem, we will have a lot of array members having the same value. There are only 200000 operations but 1000000000 array entries - we can change 200000 different values - if we do this, we still have (10⁹ - 200000) array entries with the very same value. Even if we modify 200000 ranges, this doesn't change the fact, merely the distribution of distinct values. So it's much more efficient to store a value and then for which array range this value is valid.

In example:

value 0 - [0,4343] [489289,999999999]
value 3 - [4344,4345]
value 7 - [4346,489288]

This is a mixture of storing the value and storing the operation. When you need to print a value, you look up the range and print the value.

As you see, we need less than 64 bytes for this simple example to store the information how the 7.4 GB data is compromised of, yet we can print the value for each and every array position.

Even if we have reduced the data, we still need to optimize the remaining data. We can't just dump it into a linked list - as stated, we can end up with Q+1 entries (200001), we can't afford to search the entries with an effort of O(n), let alone (r-l) * O(n).

But if we put the data into a binary search tree, we can find the correct array entry in 18 steps within the 200000 entries. This costs us some more memory, not only due to the overhead, but as we need the array index as key, we can't group all identical values together, just as long as they are one range. So the example above will need 4 nodes in the binary search tree, to separate the value 0 twice.

So, when you combine these two approaches, you should be able to get a decent memory and processor time consumption.