Sum of two 'rare' matrices, read as coordinate X, coordinate Y and a value

Question

As I was going through problems with structs on pbinfo.ro, I found a problem in which I'm given the dimensions of two matrices, the number of nonzero elements for each matrix (N1, respectively N2) and then N1 + N2 groups of 3 numbers as follows:

• The coordinates, X and Y
• The value located at those coordinates

What I have to do is write a program that does the sum of these two matrices (they both have the same dimensions) and outputs the sum as given in the input (X, Y, and the value at the coordinates).

Here is the full text of the problem:

Matrice-Rara | www.pbinfo.ro

Requirement

Two rare matrices are given and you are asked to calculate their sum.

A matrix A (n, m) is called rare if most of its elements are equal to zero (at least half). Because of the small number of nonzero numbers, a rare matrix A (n, m) with k nonzero elements can be stored using an array X containing k triplets of form (line, column, value) corresponding to the nonzero values of the matrix. Elements of the array X are stored in lexicographical order by line and column.

For example, the matrix with n = m = 3:

1 0 2
0 0 5
0 2 0

will be saved in X this way: {(1,1,1), (1,3,2), (2,3,5), (3,2,2)}.

Input data

The input file matrice_rara.in contains on the first line the dimensions of the two matrices n m, representing the number of lines and columns, and N1 N2, the number of nonzero elements of matrix A and matrix B. Then the following N1 lines will contain triplets for the matrix A in lexicographical order, and the last N2 lines will contain triplets representing the nonzero elements of matrix B, also in lexicographical order.

Output data

The output file matrice_rara.out will contain on the first line the number of nonzero elements in the matrix C and then the matrix itself in the form of triplets in lexicographical order, one per line.

Restrictions and clarifications

• 1 ≤ n, m ≤ 1,000,000
• 1 ≤ N1, N2 ≤ 300,000
• -1,000,000,000 ≤ A[i][j], B[i][j] ≤ 1,000,000,000
• Time Limit: 1 second
• Memory Limit: 64 MB / 8 MB

What I tried is I read all the triplets in one array of triplets, sorted the array and then added the values of the elements that have the same coordinates into the first element in the array that has the repeating coordinates.

Here is my code:

#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("matrice_rara.in");
ofstream cout("matrice_rara.out");

struct matrix
{
    int coord1, coord2;
    long long val;
} data[600001];

bool operator<(matrix const &a, matrix const &b)
{
    if (a.coord1 == b.coord1) {
        if (a.coord2 == b.coord2) {
            return a.val < b.val;
        }
        return a.coord2 < b.coord2;
    }
    return a.coord1 < b.coord1;
}

int main()
{
    int lin, col, unNul1, unNul2;
    cin >> lin >> col >> unNul1 >> unNul2;

    for (int i = 1; i <= unNul1 + unNul2; i++)
        cin >> data[i].coord1 >> data[i].coord2 >> data[i].val;

    sort(data + 1, data + unNul1 + unNul2 + 1);

    int unNull = 0;
    for (int i = 1; i <= unNul1 + unNul2; i++)
    {
        int start = i;
        while (data[i + 1].coord1 == data[i].coord1 && data[i + 1].coord2 == data[i].coord2 && i + 1 <= unNul1 + unNul2)
            i++, data[start].val += data[i].val;
        if (data[start].val)
            unNull++;
    }
    cout << unNull << "\n";
    for (int i = 1; i <= unNul1 + unNul2; i++)
    {
        if (data[i].val)
            cout << data[i].coord1 << " " << data[i].coord2 << " " << data[i].val << "\n";
        while (data[i + 1].coord1 == data[i].coord1 && data[i + 1].coord2 == data[i].coord2 && i + 1 <= unNul1 + unNul2)
            i++;
    }
}

The code above gets 65 points out of 100, getting correct answers for 6 of the 9 tests, and Wrong Answer for the rest (no TLE).

Any help?

Answer 1

If you have the logical AND operator &&, and the left-hand side expression is false then the right-hand side expression is not evaluated. This is called short-circuit evaluation.

It also means that the left-hand side must be evaluated first, before the code know if the right-hand side needs to be evaluated or not.

Now lets take a conditional expression from your code, and simplify it a little:

data[i + 1].coord1 == data[i].coord1 && i + 1 <= unNul1 + unNul2

This is two sub-conditions combined with the && operator:

1. The left-hand side data[i + 1].coord1 == data[i].coord1, and
2. The right-hand side i + 1 <= unNul1 + unNul2

Due to the short-circuit nature of the && operator, the left-hand side (data[i + 1].coord1 == data[i].coord1) must be evaluated first before the right-hand side (i + 1 <= unNul1 + unNul2).

Now if i happens to be equal to unNul1 + unNul2, then the left-hand side expression will use an index that is out of bounds by one.

To not go out of bounds, you need to check the index i first, which is easiest done by switching the order of the condition to

i + 1 <= unNul1 + unNul2 && data[i + 1].coord1 == data[i].coord1

Now i + 1 will not be out of bounds.

---

As for why it's important it's because uninitialized data will have indeterminate values, and using them in almost all ways will lead to undefined behavior. And with the loop condition as you currently have it, then you will use an index into the parts of the array data that is uninitialized.

Answer 2

If I've understood the intent of the posted code, the OP tried to imlement this algorithm to sum two sparse matrices:

• read the non zero elements of both matrices into a single array big enough to store the maximum number of elements admissible by the problem constraints. Note that the input is well formed and the triplets representing the n.z. elements of the two matrices are already lexicographically sorted (row-major) for each one of those.
• Sort the whole array, lexicographically. Note that in the compare function the value of the n.z. element is considered too.
• Traverse the array and sum the values of two consecutive elements if they have the same coordinates and store the result in the first one. If the resulting value is non zero, the count of n.z. is updated accordingly. The out of bounds accesses, here, were already pointed out.
• Traverse the array a second time to print out the non zero values of the resulting matrix, skipping the values of the successive elements with the same coordinates. Same out of bounds accesses, as before.

Besides the UB due to the accesses out of bounds, it's unclear to me if the accepted solution requires to actually check if the resulting value of each element is non zero.

Even if that is the case, I think that we can take advantage of the already sorted input and incrementally create the resulting matrix by "merging" the two sources. In the following snippet (testable here) I also simplified the comparisons between two elements, by using a single 64-bit value representing a position instead of two 32-bit coordinates.

#include <iostream>
#include <vector>
#include <cstdint>
#include <cassert>
#include <utility>
#include <iterator>

constexpr uint64_t pos_from(uint32_t r, uint32_t c)
{
    return (static_cast<uint64_t>(r) << 32) ^ c;
}

constexpr uint32_t row_from(uint64_t pos)
{
    return (pos >> 32) & 0xFFFFFFFF;
}

constexpr uint32_t col_from(uint64_t pos)
{
    return pos & 0xFFFFFFFF;
}

template <typename T>
class SparseMatrix
{
    uint32_t rows_{}, cols_{};
    std::vector<std::pair<uint64_t, T>> nzs_;
public:
    SparseMatrix(uint32_t r, uint32_t c, uint32_t nzs = 0)
        : rows_{r}, cols_{c}
    {
        nzs_.reserve(nzs);
    }

    std::istream& read_non_zeroes_from(std::istream& is, uint32_t n)
    {
        while(n--)
        {
            uint32_t r, c;
            T value;
            if ( (is >> r >> c >> value)  &&  value)            
                nzs_.emplace_back(pos_from(r, c), value);
        }
        return is;
    }

    std::ostream& write_non_zeroes_to(std::ostream& os)
    {
        os << nzs_.size() << '\n';
        for (auto const& i : nzs_)
            os << row_from(i.first) << ' ' << col_from(i.first) << ' ' << i.second << '\n';
        return os;
    }

    friend SparseMatrix operator+ (SparseMatrix const& a, SparseMatrix const& b)
    {
        assert(a.rows_ == b.rows_  &&  a.cols_ == b.cols_);
        SparseMatrix sum(a.rows_, a.cols_, std::max(a.nzs_.size(), b.nzs_.size()));

        auto i = a.nzs_.cbegin();
        auto j = b.nzs_.cbegin();
        auto dest = std::back_inserter(sum.nzs_);
        while ( i != a.nzs_.cend()  &&  j != b.nzs_.cend() )
        {
            if ( i->first < j->first )
            {
                *dest = *i;
                ++i;
            }
            else if ( j->first < i->first )
            {
                *dest = *j;
                ++j;
            }
            else
            {
                auto sum_value = i->second + j->second;
                if (sum_value)
                    *dest = {i->first, sum_value};
                ++i;
                ++j;   
            }
        }
        std::copy(i, a.nzs_.cend(), dest);
        std::copy(j, b.nzs_.cend(), dest);
        return sum;
    }
};

int main()
{
    uint32_t n, m, N1, N2;
    if ( !(std::cin >> n >> m >> N1 >> N2) )
        std::cerr << "Error: unable to read initial data.\n";

    SparseMatrix<int32_t> a(n, m, N1);
    if ( !a.read_non_zeroes_from(std::cin, N1) )
        std::cerr << "Error: unable to read triplets of the first matrix\n";

    SparseMatrix<int32_t> b(n, m, N2);
    if ( !b.read_non_zeroes_from(std::cin, N2) )
        std::cerr << "Error: unable to read triplets of the second matrix.\n";

    auto c = a + b;
    c.write_non_zeroes_to(std::cout);
}

Answer 3

Well, I just managed to get to 100 points. Basically, my mistake was the way I defined the operator<, or in the source I posted here (since then I rewrote it a couple of times), the fact that I wrote an if statement wrong, not the while one. Here's the new source:

#include <fstream>

using namespace std;

ifstream cin("matrice_rara.in");
ofstream cout("matrice_rara.out");

struct matrixEntry {
    int l, c;
    int val;
} matrix1[300001], matrix2[300001], finalMatrix[300001];

bool operator< (const matrixEntry &a, const matrixEntry &b)
{
    return a.l < b.l || (a.l == b.l && a.c < b.c);
}

bool operator> (const matrixEntry &a, const matrixEntry &b)
{
    return a.l > b.l || (a.l == b.l && a.c > b.c);
}

int matrixSum(int matrix1Size, int matrix2Size)
{
    int i = 1, j = 1, k = 0;
    while (i <= matrix1Size && j <= matrix2Size)
    {
        if (matrix1[i] < matrix2[j])
            finalMatrix[++k] = matrix1[i++];
        else if (matrix1[i] > matrix2[j])
            finalMatrix[++k] = matrix2[j++];
        else
        {
            finalMatrix[++k] = matrix1[i++];
            finalMatrix[k].val += matrix2[j++].val;
            if (finalMatrix[k].val == 0)
                k--;
        }
    }
    while (i <= matrix1Size)
        finalMatrix[++k] = matrix1[i++];
    while (j <= matrix2Size)
        finalMatrix[++k] = matrix2[j++];
    return k;
}

int main()
{
    int unNul1, unNul2, lin, col;

    cin >> lin >> col >> unNul1 >> unNul2;

    for (int i = 1; i <= unNul1; i++)
        cin >> matrix1[i].l >> matrix1[i].c >> matrix1[i].val;
    for (int i = 1; i <= unNul2; i++)
        cin >> matrix2[i].l >> matrix2[i].c >> matrix2[i].val;

    int unNull = matrixSum(unNul1, unNul2);
    cout << unNull << "\n";
    for (int i = 1; i <= unNull; i++)
    {
        cout << finalMatrix[i].l << " " << finalMatrix[i].c << " " << finalMatrix[i].val << "\n";
    }
}