8
\$\begingroup\$

The exercise is as follows:

Player A will write list \$ a \$ consisting of \$ n \$ numbers. Player B will take a look at the paper. After that the A player will ask player B \$q\$ questions. Each question will be of the following form:

If I give you two \$ R \$ and \$ L \$ in \$ a \$ such that (\$ 1<=L<=R<=n\$ ), calculate the following value:

$$ 1*a[L] + 2*a[L+1] + 4*a[L+2] + ... + 2^{R-L-1}*a[R-1]+2^{R-L}*a[R] $$

Because the numbers can be really large, we need to find the residue that the result will give when divided by \$ 10^9 + 7\$.

Input is as follows:

n q
a1 a2 an
L1 R1
L2 R2
Lq Rq

The output is: on one line the result for one query.

The problem:

I need to improve performance so it is finished within 1 second. I think the problem may be because I have 2 for loops. Because the number of numbers can be up to 200,000 as well as the pairs. This means that in the worst case it has to go through the process 40,000,000,000 times.

Can someone please tell me how to improve the performance?

#include <iostream>

using namespace std;

const int MAXN = 200000;

int residues[MAXN];
int numbers[MAXN];
int pairs[MAXN][2];

void findResidues(int i)
{
    residues[i] = (residues[i - 1] * 2) % 1000000007;
}

long long int sumBetween(int first, int second)
{
    long long int sum = 0;
    int pos = first;
    while(pos <= second)
    {
        sum += (long long)residues[pos - first] * numbers[pos];
        sum %= 1000000007;
        pos++;
    }
    return sum;
}

int main()
{
    residues[0] = 1;
    int n, q ;
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> numbers[i];
        findResidues(i + 1);
    }
    for(int i = 0; i < q; i++)
    {
        cin >> pairs[i][0] >> pairs[i][1];
        cout << sumBetween(pairs[i][0] - 1, pairs[i][1] - 1) << endl;
    }
    return 0;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I have big gripe with a lot of these "programming challenges", because almost all of them are actually maths problems, and the actual "programming" part of them is mostly trivial. I have no problem with those challenges, per se, but simply don't call them programming challenges, and specifically do not imply that solving them somehow makes you a good programmer. There's a reason Project Euler is named after a mathematician, not a programmer, for example. \$\endgroup\$ Aug 16, 2020 at 9:59
  • \$\begingroup\$ Are they fun? Sure. Are they interesting puzzles? Yes. Are they in any way, shape or form useful for teaching programming or judging programming skills? Not in the slightest. \$\endgroup\$ Aug 16, 2020 at 10:00
  • \$\begingroup\$ I think while finding a solution is clearly in the realm of mathematics and often relies on some piece of theory which one either happens to know from experience (perhaps such as this) or must hunt for (especially having taken some brilliant mathematician years to evolve, it is unseemly to ask during limited-resource challenges, such as in-person interviews) .. once found, generating an implementation of it, or better optimizing an existing solution (as in this case) is extremely valuable for programmers to practice and consider. \$\endgroup\$
    – ti7
    Aug 19, 2020 at 15:55

4 Answers 4

6
\$\begingroup\$
  • int pairs[MAXN][2]; wastes memory. You don't need to read all the queries at once:

      for(int i = 0; i < q; i++)
      {
          cin >> L >> R;
          cout << sumBetween(L - 1, R - 1) << endl;
      }
    

    works equally well. Besides, the problem statement doesn't say how many queries are there; it could be way more than the size of the array.

  • Your feeling that you use the wrong algorithm is well founded. Bruteforcing is almost always wrong. Look at the underlying math first. I don't want to spell out everything, just a couple of hints:

    • \$1*a_{L} + 2*a_{L+1}+ ... + 2^{R-L}*a_{R} = \dfrac{2^L*a_{L} + 2^{L+1}*a_{L+1}+... + 2^R*a_{R}}{2^L}\$

    • The numerator above is a difference of two partial sums of the \$2^n*a_{n}\$ sequence.

    • \$1000000007\$ is a prime number, so division by \$2^L\$ modulo 1000000007 is a multiplication by a multiplicative inverse of 2 modulo 1000000007 (which is trivial to find) to the same power.

    I hope it is enough to get you going in the right direction. You should be able to answer each query in constant time.

\$\endgroup\$
4
\$\begingroup\$

The code is already using symbolic constants such as MAXN, the code would be clearer if 1000000007 was a numeric constant as well.

Are you sure that first and second will always be integers you may need to make these long long as well. When using a long long there is no reason to specify int as well, the values will be integer unless otherwise indicated.

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Pass the array residues into the functions findResidues() and sumBetween()

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

Use C++ Container Classes

The code is currently using old C programming style arrays, it would be better to use C++ container classes such as std::array or std::vector. Either one of these classes will allow you to use iterators which could possibly speed up the implementation.

Possibly std::vector would be a better type to use that std::array would be in this particular problem. std::vector is a variable length array. If you want to continue using MAXN as the maximum size you can reserve the memory.

Gather All the Data Before Processing the Data

Currently the program is creating the resedue information as the data is being input. Rather than breaking up calculations by getting new input first get all of the input and then process the data. Getting all the input at once should help speed up the program, and will make the algorithm easier to follow.

Break up the main() function a little more into 2 functions that get input and then functions that do the calculations.

Use size_t or Another unsigned Variable Type When Indexing Arrays or Other Indexed Variable Types

When indexing into arrays it is safer to use size_t because this is unsigned and the value can't go negative if it gets too large. Indexing by negative numbers can cause an immediate out of range exception.

\$\endgroup\$
2
  • \$\begingroup\$ Overlapping computation and I/O can be good if you're limited by a slow I/O device (like reading a file that's not hot in pagecache). Assuming there's hardware and/or OS readahead, so spending time computing does give the disk some time to get some data into memory before you ask for more. With buffered I/O, you're not getting a system call for every cin >>, and you're making the same total number of system calls. It's probably better to avoid potentially-large arrays in your program, unless you actually prep large strings for one big multi-line cout<< to reduce locking overhead. \$\endgroup\$ Aug 16, 2020 at 10:25
  • \$\begingroup\$ OTOH yes, doing a batch of computation at once can give the optimizer more room to auto-vectorize, and not touching IO buffer data structures between computations can let more of your data stay hot in cache. \$\endgroup\$ Aug 16, 2020 at 10:27
2
\$\begingroup\$

This looks to me like a issue about efficiency, not style.

We can use prefix sums instead of brute forcing each case. (learn more here)

Create an array prefix of size n + 1. At the ith index, find whatever the sum would be for the first i numbers. For example, if the list a was a_1, a_2, a_3, ..., a_n), prefix would be 0, a_1, a_1 + 2*a_2, a_1+2*a_2+4*a_3, ....

Then, if we wanted to query from L to R, we could find prefix[R]-prefix[L-1]. As a basic example, pretend L=2, R=3. Then, the difference mentioned above would be prefix[3]-prefix[1] = 2*a_2+4*a_3, which is double of the sum that we are expecting. Afterwards, we can divide by 2^{L-1} to get what the exercise wants.

I'm a little busy right now, but I will post some code as soon as possible.

\$\endgroup\$
1
\$\begingroup\$

The std::endl flushes the buffer every time, which makes the code slower. Instead of it, you should use '\n' so the buffer only flushes when it's full.

For further reading, check out std::flush

Hope it makes your code faster!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ There should be an even bigger win if input, output and data processing are all separated. \$\endgroup\$
    – pacmaninbw
    Aug 14, 2020 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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