7
\$\begingroup\$

I have the following problem:
I read from a file the dimension(n) of the matrix(which is n * n) and the matrix.
For each element in the matrix I have to compute sum of row + sum of column + sum of the diagonal which the element is on and is parallel to main diagonal + sum of the diagonal which the element is on and is parallel to antidiagonal, and find the element with max corresponding sum and coordinates(row and column) on which the element is found. Element itself should be taken into count just once.

I have a working program, but I need it to be faster. How could I solve this problem faster? Can my algorithm be improved or I have to write another one? 2 ≤ n ≤ 300, -10000 ≤ m[i][j] ≤ 10000

Input file:

3
 1  -8  3
-2   4  5
 6  -9  7

Output file:

18
0 2

Code:

#include <set>  
#include <iostream>
#include <fstream>
#include <limits>

using namespace std;
int sumOnRow(int row, int n, int **m)
{
    int i;
    int sum = 0;
    for (i = 0; i < n; i++)
        sum += m[row][i];
    return sum;
}

int sumOnColumn(int column, int n, int **m)
{
    int i;
    int sum = 0;
    for (i = 0; i < n; i++)
    {
        sum += m[i][column];
    }
    return sum;
}

int sumOnAD(int i, int j, int n, int **m)
{
    int a = i - 1;
    int b = j + 1;
    int sum = 0;
    while ((a >= 0) && (b < n))
    {
        sum += m[a--][b++];
    }
    a = i + 1;
    b = j - 1;
    while ((a < n) && (b >= 0))
    {
        sum += m[a++][b--];
    }
    return sum;
}

int sumOnMD(int i, int j, int n, int **m)
{
    int a = i + 1;
    int b = j + 1;
    int sum = 0;
    while ((b < n) && (a < n))
    {
        sum += m[a++][b++];
    }
    a = i - 1;
    b = j - 1;
    while ((a >= 0) && (b >= 0))
    {
        sum += m[a--][b--];
    }
    return sum;
}

int main()
{
    fstream in;
    in.open ("inputFile.in");
    if (!in)
    {
        cerr << "Can't open input file\n";
    }
    fstream out;
    out.open ("outputFile.out", ios::out);
    if (!out)
    {
        cerr << "Can't open output file\n";
    }

    short n;
    in >> n;

    int i;
    int **m = new int *[n];
    for (i = 0; i < n; i++)
        m[i] = new int [n];

    int j;
    //read the matrix
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            in >> m[i][j];
        }
    }

    int elementSum = 0;
    int maxSum = INT_MIN;
    int savedI = 0;
    int savedJ = 0;

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            elementSum += sumOnRow(i, n, m);
            elementSum += sumOnColumn(j, n, m);
            elementSum += sumOnMD(i, j, n, m);
            elementSum += sumOnAD(i, j, n, m);
            //element was taken into count both in the sum on row and the sum on column
            elementSum -= m[i][j];
            if (elementSum > maxSum)
            {
                maxSum = elementSum;
                savedI = i;
                savedJ = j;
            }
            elementSum = 0;
        }
    }
    out << maxSum << "\n" << savedI << " " << savedJ;
    return 0;
    }
\$\endgroup\$
7
\$\begingroup\$

For every element, you currently sum \$n\$ elements for the row, column, diagonal and anti-diagonal, so \$4*n\$ elements.
That's a total of \$4*n^3\$ adds.

That can be improved on easily by pre-processing:

  1. Build an array of the sums for all rows, columns, diagonals and anti-diagonals. You need \$4*n\$ space and \$4*n^2\$ adds.
  2. Add the proper sums for each element, that's \$4\$ adds per element, for a total of \$4*n^2\$ adds.
  3. Together, that's \$8*n^2\$ adds.

In conclusion, you can trade \$4*n\$ extra space for a speed-up by a factor of \$n/2\$.

Regarding your current code:

  1. I cannot find anyplace you use something from <set>. So, why include it?

  2. You should avoid using namespace std; It's a plague and just biding its time to bite you later.
    Why is “using namespace std;” considered bad practice?

    You can import selected identifiers with using std::cout;, and qualify others with std::cin.

  3. You know you can introduce a variable in the initializer-part of the for-loop?

  4. There's no need for a separate step to open a fstream. User the right ctor.

  5. You noticed an error, you wrote to stderr about it, so why do you try to muddle on instead of aborting?

  6. You never check whether input failed. Are you completely sure the input is well-formed?

  7. Consider merging your allocations where possible. new and delete are quite costly after all.

  8. return 0; is implicit in main().

  9. You never free the memory you allocated. That's actually a good thing as cleaning up just for the OS to take everything down is wasted effort. Beware false positives in leak-detectors though.
    I suggest a comment // m and m[0] to m[n - 1] intentionally left allocated though, in case anyone (else) later pokes around and might conceivably adopt it into a greater whole. Also shows you considered it.

  10. You might consider investing into a class for square matrices. It's quite easy to build one.

\$\endgroup\$
  • \$\begingroup\$ Finally wrote it. And it's faster and better algorithm. \$\endgroup\$ – Timʘtei Jun 12 '17 at 21:55
1
\$\begingroup\$

It seems like a classic dynamic programming problem (result of N+1 is incremental work reusing result for N).

You would need at minimum this much extra memory: an array of size N of sum_col, an array on size N of sum_diag, an array of size M of sum_row (in case you need to persist these you still need 3*N*M, but if you can get without, say stream the results to the next processing step in the pipeline that's where improvement is possible).

Make sure your array is laid out in memory in a way that nested loops don't jump back and forth. Inner loop counter must be 0..N.

In the inner loop go through the temporary array, add to it the corresponding value from the current row of the matrix and also increment the respective element in the temporary array of size M.

Something like

int data[N][M];
int col_sums[N];
int diag_sums[N];
int row_sums[M];

for (int i = 0; i < M; ++i)
{
    for (int k = 0; k < N; ++k)
    {
        row_sum[k] += data[k][i];
        col_sums[i] += data[k][i];
        // fill diag_sums in the back-to-front order
        // check if hit new max and update records accordingly 
    }
}
\$\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.