5
\$\begingroup\$

Question (SAD Queries on CodeChef)

The Summed Absolute Difference (SAD) of two arrays. Given arrays (1-indexed) \$P\$ and \$Q\$ of lengths \$p\$ and \$q\$.

Given a collection of \$n\$ arrays \$A_1, \ldots, A_n\$, report \$SAD(A_i, A_j)\$ for several queries \$(i, j)\$.

The first line of input contains a single positive integer \$n\$.

Each of the next \$n\$ lines starts with a positive integer \$s_i\$, the size of \$A_i\$,

followed by \$s_i\$ space-separated integers \$A_{i,1}, \ldots, A_{i,s_i}\$ which denotes the array \$A_i\$. The next line of input consists of a single positive integer \$M\$.

Each of the next \$M\$ lines consists of 2 positive integers \$a\$ and \$b\$ which lie
between \$1\$ and \$n\$ (inclusive), specifying the indices of the arrays for which the SAD value must be reported.

Example

Input:

4  
4 0 3 1 -2
2 0 4
2 2 4
4 4 -3 -4 4

3
3 4
4 2
1 4  

Output:

30
30
60

Explanation

Query 1: The arrays in question are A3 = [2, 4] and A4 = [4, -3, -4, 4].

$$SAD(A3, A4)$$ $$= |2 - 4| + | 2 - (-3) | + |2 - (-4) | + | 2 - 4 |$$ $$+ | 4 - 4 | + | 4 - (-3) | + | 4 - (-4) | + | 4 - 4 |$$ $$= 2 + 5 + 6 + 2 + 0 + 7 + 8 + 0$$ $$= 30$$

Constraints

\$1 \leq n, M \leq 10^5\$

\$1 \leq s_1 + ... + s_n \leq 10^5\$

\$-10^9 \leq A_{i,j} \leq 10^9\$

\$1 \leq i, j \leq n\$ in each of the queries

My approach

#include <iostream>
#include<cmath>

using namespace std;

int main()
{

    long long  int n,x,a,b,sum=0,s=1;
    cin>>n;
    long long int *size=new long long int[n];
    long long int **arr=new long long int*[n];
    for(int i=1;i<=n;i++)
    {
        arr[i]=new long long int[n];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>size[s];

        for(int j=0;j<size[s];j++)
        {
            cin>>arr[i][j];
        }
        s++;
    }
    long long int m;
    cin>>m;
    while(m--)
    {
        cin>>a>>b;
        for(int i=1;i<=size[a];i++)
        {
            for(int j=0;j<size[b];j++)
                sum=sum+fabs(arr[a][i]-arr[b][j]);
        }
        cout<<sum;
        cout<<endl;
        sum=0;
    }
    return 0;
}

How can i reduce the time complexity and space complexity of this program.

I have taken a 1D dynamic array to store the size of arrays and a 2D dynamic array to store the index and the array value for that index

\$\endgroup\$
8
\$\begingroup\$

@vnp has already given an excellent review of your algorithmic problems. I'm not going to duplicate their work. I'm just going to review the code itself.

using namespace std;

Avoid doing the above. It may save you a few keystrokes in a small program like this one, but can turn into a major maintenance headache for a codebase that you need to support. See this question.

long long  int n,x,a,b,sum=0,s=1;
  1. Never declare multiple variables on a single line. It's very easy to screw up the syntax and get some surprising bugs. Declaring each variable on its own line does not make the code slower.
  2. Don't declare variables until they're needed. You need n right away, but you don't use a or b until over 50 lines later.
  3. Give variables descriptive names. In a problem like this, you can get away with using names like n, a, and b because they're the names in the problem. But what is x? I don't even see it being used at all? Is it vestigial from an earlier attempt at the problem?

On to the next lines....

long long int *size=new long long int[n];
long long int **arr=new long long int*[n];

Don't use naked new. Either use smart pointers or - in this case - containers. What you want here is std::vector. There is absolutely zero speed penalty for using a vector rather than allocating an array yourself with new.

You don't free any of the memory you allocate. I don't know if that's tolerated in these coding competitions, but it is undefined behaviour in general. Here's a hot tip: If you are in a coding competition where it's okay to leak memory, and you want to save every cycle so you don't want to pay for freeing any memory, you can still use standard containers. All you need to do is define an allocator that doesn't delete. Which is just:

template <typename T>
struct leaking_allocator
{
    using value_type = T;
    auto allocate(std::size_t n) { return new T[n]; }
    auto deallocate(T*, std::size_t) noexcept { }
};

If you'd used a vector, you wouldn't need both size and arr. You would just need auto A = std::vector<std::vector<long long int>{};. You would read n then do A.resize(n);. Then for each array you would read s and do A[i].resize(s);, and read the next s values into A[i][0] to A[i][s - 1]. The size of any array would be A[i].size().

And, of course, your program wouldn't leak (unless you deliberately made it do so by using a leaking allocator).

for(int i=1;i<=n;i++)
{
    arr[i]=new long long int[n];
}

You have an out-of-bounds error here. You're lucky the program doesn't crash. I know the problem talks about 1-based arrays, but C++ arrays are 0-based. You need to do that conversion, either in your head or in the code.

So either:

for(int i = 0; i < n; ++i)
    arr[i] = new long long int[n];

or:

for(int i = 1; i <= n; ++i)
    arr[i - 1] = new long long int[n];

(Note: As Pete Kirkham points out, the above is still wrong. The allocation line should be moved to the next loop, after cin>>size[s];. And instead of allocating n elements, it should be allocating size[s]. The vector versions don't have this bug.)

In the next loop:

for(int i=1;i<=n;i++)
{
    cin>>size[s];

    for(int j=0;j<size[s];j++)
    {
        cin>>arr[i][j];
    }
    s++;
}

You have the same out-of-bounds error. But you also have a needless extra loop variable. Both i and s are doing the same thing here. And you never use s again after this loop. You could simplify this to:

for (int i = 0; i < n; ++i)
{
    cin >> size[i];

    for(int j = 0; j < size[i]; ++j)
        cin >> arr[i][j];
}

But of course, if you used vectors, both of the above loops could simplify to:

auto A = std::vector<std::vector<long long int>>{}; // or, possibly, use leaking allocators here

auto n = 0;
std::cin >> n;
A.resize(n);

for (auto i = 0; i < A.size(); ++i)
{
    auto s = 0;
    std::cin >> s;
    A[i].resize(s);

    for (auto j = 0; j < A[i].size(); ++j)
        std::cin >> A[i][j];
}

or even better and safer, using range-based loops:

auto A = std::vector<std::vector<long long int>>{}; // or, possibly, use leaking allocators here

auto n = 0;
std::cin >> n;
A.resize(n);

for (auto&& arr : A) // for each array in A
{
    auto s = 0;
    std::cin >> s;
    arr.resize(s);

    for (auto&& item : arr) // for each item in A[i]
        std::cin >> item;
}

On to the calculation loop....

while(m--)
{
    cin>>a>>b;
    for(int i=1;i<=size[a];i++)
    {
        for(int j=0;j<size[b];j++)
            sum=sum+fabs(arr[a][i]-arr[b][j]);
    }
    cout<<sum;
    cout<<endl;
    sum=0;
}

Once again, that first inner loop has an out-of-bounds error.

@vnp has already pointed out that you should be using std::abs(), not std::fabs(). But here are some more tips to increase speed and readability:

sum=sum+fabs(arr[a][i]-arr[b][j]);

can be simplified to:

sum += std::abs(arr[a][i] - arr[b][j]);

Because you've declared sum outside of the loop, you have to clear it on each iteration. That's a little brittle. It would be safer and more sensible to declare sum just before calculating the sum.

Also:

cout<<endl;

Never use endl. Especially in performance code. If you want a newline, just write a newline.

So the loop above becomes:

while (m--)
{
    std::cin >> a >> b;

    auto sum = 0LL;
    for (int i = 0; i < size[a]; ++i)
    {
        for (int j = 0; j < size[b]; ++j)
            sum += std::abs(arr[a][i] - arr[b][j]);
    }

    std::cout << sum << '\n';
}

And if you use vectors, the code is basically identical:

while(m--)
{
    std::cin >> a >> b;

    auto sum = 0LL;
    for (int i = 0; i < A[a].size(); ++i)
    {
        for (int j = 0; j < A[b].size(); ++j)
            sum += std::abs(A[a][i] - A[b][j]);
    }

    std::cout << sum << '\n';
}

or with range loops:

while(m--)
{
    std::cin >> a >> b;

    auto sum = 0LL;
    for (auto item_a : A[a]) // for each item_a in A[a]
                             // (don't need && because they're just
                             // long long int, and we're just
                             // reading them)
    {
        for (auto item_b : A[b]) // for each item_b in A[b]
            sum += std::abs(item_a - item_b);
    }

    std::cout << sum << '\n';
}

And finally:

return 0;

There's no need for this. main() returns zero automatically.

Summary

You have two critical problems in your code:

  1. You leak every array you allocate. If this is deliberate, at least document it with a comment. This problem would go away if you used smart pointers and containers. (But if you really want to leak, you can still use smart pointers and containers. You'd just need to use leaking deleters and allocators.)
  2. Many of your loops access out-of-bounds memory. The problem talks about 1-based arrays, but arrays in C++ are 0-based. You need to do that conversion.

You have one problem that will really hurt your efficiency:

  1. Don't use endl.

And you have a few minor problems that are mostly stylistic:

  1. Don't declare variables until right before they're needed.
  2. Don't declare multiple variables all on one line.
  3. Don't use manual memory management - don't use naked new/delete. Use containers and smart pointers. They are zero-cost abstractions.
  4. Space out your code. It's hard to spot errors when each line is just a jumble of symbols.

Some of the above will give you small speed boosts, but as @vnp noted, the real thing that's killing your time is that you didn't think the problem through, and just tried to brute-force it.

However, you have some serious bugs that you should worry about fixing first, before worrying about speed.

\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice review. I would like it even better without the leaking allocators hint. I think such hacks confuse novice programmers, and as such it's better to leave them out completely. \$\endgroup\$ – janos Jul 16 '18 at 4:56
  • 1
    \$\begingroup\$ What exactly is “undefined behaviour” if you don't free allocated memory? \$\endgroup\$ – Martin R Jul 16 '18 at 8:12
  • \$\begingroup\$ Should that be arr[i] = new long long int[n+1]; to agree with arr[i-1] = new long long int[n]; in the 0-based/1-based paragraph? \$\endgroup\$ – Toby Speight Jul 16 '18 at 10:13
  • \$\begingroup\$ @MartinR, undefined behavior is undefined. It's just undefined, by being undefined. \$\endgroup\$ – Incomputable Jul 16 '18 at 16:00
  • \$\begingroup\$ @TobySpeight To match the original code, it should be n... but as Pete Kirkham pointed out, the original code is wrong. I'll add a note about that. \$\endgroup\$ – indi Jul 18 '18 at 2:16
7
\$\begingroup\$
  • Algorithm.

    Thou shalt not brute force.

    When computing \$SAD(P, q_i)\$ you may notice that is bound be rewritten as \$SAD(P', q_i) + SAD(P'', q_i)\$, where \$P'\$ consists of values less than \$q_i\$, and \$P''\$ consists of values greater them \$q_i\$. This in turn is

    \$k' \cdot q_i - \Sigma P' + \Sigma P'' - k'' q_i = \Sigma P'' - \Sigma P' + (k' - k'') \cdot q_i\$

    where \$k', k''\$ are the sizes of the corresponding partitions.

    Now it shall be obvious that some preprocessing may help.

    • Sort the arrays;
    • Compute their partial sums.

    It is a one-time investment, and is linearithmic by the size of arrays.

    To answer the query, loop over the smaller array. Use std::lower_bound to determine a partition point of a larger array and the sizes of its partitions by the element of the smaller one. Use the above formula to get the result for \$q_i\$. Accumulate them.

    The time complexity per query becomes \$O(q \log p)\$ versus your \$O(q\cdot p)\$.

  • Code

    • Don't use namespace std.

    • Floating point (fabs) in a purely integer problem is a big no-no.

    • Don't crowd the operators. It doesn't make your code run faster. Give them some breathing space, e.g:

      for (int i = 1; i <= size[a]; i++)
      
\$\endgroup\$
  • \$\begingroup\$ Could your formula be optimized for when the partition sizes are the same? Instead of iterating over q couldn't you just multiply the difference of the sums by the size of q, since the difference of the sizes multiplied by any q element will be 0. \$\endgroup\$ – tinstaafl Jul 16 '18 at 18:00
  • \$\begingroup\$ @tinstaafl There is plenty of room for optimization indeed. However I am not sure I understand your proposal. Try and post the code perhaps? \$\endgroup\$ – vnp Jul 16 '18 at 18:10
4
\$\begingroup\$

There is nothing in the instructions that imply that the size of the arrays is not greater than the number of arrays, so for an input such as

3
7 1 2 3 4 5 6 7
5 5 4 3 2 1
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

n will be 3, so your code will only allocate arrays of size 3, instead of size[n]:

for(int i=1;i<=n;i++)
{
    arr[i]=new long long int[n]; 
}
\$\endgroup\$
2
\$\begingroup\$

You are probably missing these key ingredients of an industrial code (they would "automagically" uncover few problems):

  1. Unit test(s) with coverage report (gcov if you are compiling with GCC, directly or via the lcov wrapper).
  2. Leaks and heap allocations profiling (valgrind: for leaks and errors valgrind --tool=memcheck, for heap profiling valgrind --tool=massif).
  3. Performance profiling, best with microbenchmarks (google::benchmark with perf for sampled, or gprof for instrumented, the latter is not thread-safe).

Best is to embed them into the build (if you are going to productize the code), they can all be tweaked for pass/fail mode of operation.

... and the code style, but others already covered it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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