Sheet

[satsat111]

Hello, I'm a C++ beginner trying to solve this problem.

You have a spreadsheet and some cells are inserted with formula. A cell without formula has initial value.However, some cells have buggy formula. The formula of several cells might depend on each other and results in reference error. For example, cell A1 has formula B1 + 2, cell B1 has formula C1 + 2, cell C1 has formula A1 + 2, then the spreadsheet reports reference error.If a cell has formula depending a cell with reference error, itself encounters reference error as well. For example, cell C1 has reference error, cell C4 has formula C1 + 2, then C4 has reference error.

Given a spreadsheet, please output results of all cells.

Input Format

The first line contains two integer : N,M the number of cells in the spreadsheet and the number of cells with formula.

The cells are labeled with 1,2,...N (instead of the usual way we see in spreadsheet applications).

The following M lines describes the formula, for each line is either:
A x1 y - Cell x1 has value y
B x1 x2 y - Cell x1 has formula: cell x2 + value y
...

Output Format

For each cell, please output "#REF!" if it has reference error; otherwise, output its value.

Sample Input

10 9
A 1 10
B 2 1 20
B 3 2 30
B 4 6 2
B 5 4 2
B 6 5 2
C 7 1 2 2
C 8 7 6 3
D 9 1 2 3 8

Sample Output

10
30
60
#REF!
#REF!
#REF!
42
#REF!
108
0

Explanation 0

The formula and result of each cell is listed below:

cell id formula result
1 10 10
2 cell 1 + 20 30
3 cell 2 + 30 60
4 cell 6 + 2 reference error
5 cell 4 + 2 reference error
6 cell 5 + 2 reference error
7 cell 1 + cell 2 + 2 42
8 cell 7 + cell 6 + 3 reference error
9 cell 1 + cell 2 + cell 3 + 8 108
10 (empty cell) 0

Sorry the problem is quite long.
I'd like to solve it step by step, first, how to implement the cin that got three items in a line, and, is there any hint on solving this problem efficiently? Appreciate anyone's help.

 #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int N,M;
    cin>>N>>M;
    while(M--)
    return 0;
}

[seeplus]

The first task is to read in the input into a possible structure. One way to do this is as below. It uses a stuct for each cell then details references to the other cells and the final value to be added. This code will read and store the entered data and then display it. This may be a useful starting point.

#include <iostream>
#include <vector>

struct Form {
	std::vector<unsigned> cells;
	int val {};
};

int main() {
	unsigned N {}, M {};

	std::cin >> N >> M;

	std::vector<Form> calc(N);

	for (unsigned n {}; n < N; ++n) {
		char type {};
		unsigned cellno {};

		std::cin >> type >> cellno;

		for (unsigned f {}, nocells {type - 'A' + 0U}; f < nocells; ++f) {
			unsigned cell {};

			std::cin >> cell;
			calc[cellno - 1].cells.push_back(cell);
		}

		std::cin >> calc[cellno - 1].val;
	}

	for (unsigned cell {1}; const auto& [cells, val] : calc) {
		std::cout << cell++ << "  ";

		for (const auto& c : cells)
			std::cout << c << "  ";

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

Given the input of:

10 9
A 1 10
B 2 1 20
B 3 2 30
B 4 6 2
B 5 4 2
B 6 5 2
C 7 1 2 2
C 8 7 6 3
D 9 1 2 3 8
A 10 10

displays:

1  10
2  1  20
3  2  30
4  6  2
5  4  2
6  5  2
7  1  2  2
8  7  6  3
9  1  2  3  8
10  10

[satsat111]

wow it seems a bit complicated, may I ask the purpose of + 0U in line 22?

[seeplus]

To convert int to unsigned int. type - '0' gives a type of int - but nocells is of type unsigned. Using {} as an initializer requires that narrowing can't occur (ie signed int to unsigned) so + 0U (U for unsigned) type converts to unsigned.

[seeplus]

One simple recursive solution could be:

#include <iostream>
#include <vector>
#include <utility>
#include <set>

struct Form {
	std::vector<unsigned> cells;
	int val {};
};

struct Result {
	int res {};
	bool good {};
};

// Note cell starts at 1!
Result eval(int cell, const std::vector<Form>& cls, std::set<int> visit) {
	if (!cls[cell - 1].cells.empty() && !visit.insert(cell).second)
		return {0, false};

	Result res {cls[cell - 1].val, true};

	for (const auto& c : cls[cell - 1].cells)
		if (const auto res1 {eval(c, cls, visit)}; res1.good)
			res.res += res1.res;
		else
			return {0, false};

	return res;
}

int main() {
	unsigned N {}, M {};

	std::cin >> N >> M;		// M not used

	std::vector<Form> calc(N);

	for (unsigned n {}; n < N; ++n) {
		char type {};
		unsigned cellno {};

		std::cin >> type >> cellno;

		for (unsigned f {}, nocells {type - 'A' + 0U}; f < nocells; ++f) {
			unsigned cell {};

			std::cin >> cell;
			calc[cellno - 1].cells.push_back(cell);
		}

		std::cin >> calc[cellno - 1].val;
	}

	for (unsigned cell {1}; cell <= calc.size(); ++cell) {
		std::set<int> visit;

		std::cout << cell << "  ";

		if (const auto res {eval(cell, calc, visit)}; res.good)
			std::cout << res.res << '\n';
		else
			std::cout << "#REF#\n";
	}
}

9 9
A 1 10
B 2 1 20
B 3 2 30
B 4 6 2
B 5 4 2
B 6 5 2
C 7 1 2 2
C 8 7 6 3
D 9 1 2 3 8
1  10
2  30
3  60
4  #REF#
5  #REF#
6  #REF#
7  42
8  #REF#
9  108

[satsat111]

Hi, I got segmentation fault when running this code, is it because of the complexity?

[seeplus]

What os/compiler are you using? It works OK with VS2022

Note that in the original data, N is 10 but there are only 9 cells listed.

[satsat111]

I'm running it using c++20 , does segmentation fault imply stack overflow,
I changed vector<Form> calc(N) in line 37 to vector<Form> calc(N+1) and the compile message became abort called.

[seeplus]

What is the data being used? The data provided had the cell number starting at 1 and ending at N. If this scheme is not used for the actual data being used, then this will be an error - as the cell number is used to index into the vector.

[seeplus]

This version is based on a std::map rather than a vector, so it doesn't matter re the cell number.

#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <map>

struct Form {
	std::vector<unsigned> cells;
	int val {};
};

struct Result {
	int res {};
	bool good {};
};

using Cells = std::map<unsigned, Form>;

Result eval(int cell, Cells& cls, std::set<int> visit) {
	if (!cls[cell].cells.empty() && !visit.insert(cell).second)
		return {0, false};

	Result res {cls[cell].val, true};

	for (const auto& c : cls[cell].cells)
		if (const auto res1 {eval(c, cls, visit)}; res1.good)
			res.res += res1.res;
		else
			return {0, false};

	return res;
}

int main() {
	unsigned N {}, M {};

	std::cin >> N >> M;		// M not used

	Cells calc;

	for (unsigned n {}; n < N; ++n) {
		char type {};
		unsigned cellno {};

		std::cin >> type >> cellno;

		for (unsigned f {}, nocells {type - 'A' + 0U}; f < nocells; ++f) {
			unsigned cell {};

			std::cin >> cell;
			calc[cellno].cells.push_back(cell);
		}

		std::cin >> calc[cellno].val;
	}

	for (auto& cell : calc) {
		std::set<int> visit;

		std::cout << cell.first << "  ";

		if (const auto res {eval(cell.first, calc, visit)}; res.good)
			std::cout << res.res << '\n';
		else
			std::cout << "#REF#\n";
	}
}

9 9
A 1 10
B 2 1 20
B 3 2 30
B 4 6 2
B 5 4 2
B 6 5 2
C 7 1 2 2
C 8 7 6 3
D 9 1 2 3 8
1  10
2  30
3  60
4  #REF#
5  #REF#
6  #REF#
7  42
8  #REF#
9  108

[satsat111]

oh yes I see, that should be the problem.So what to do with empty cells. It can't be solved by adding the line 65~66 to deal with empty cells.I'm still trying to understand the rest of the code.

#include <iostream>
#include <vector>
#include <utility>
#include <set>

struct Form {
    std::vector<unsigned> cells;
    int val {};
};

struct Result {
    int res {};
    bool good {};
};

// Note cell starts at 1!
Result eval(int cell, const std::vector<Form>& cls, std::set<int> visit) {
    if (!cls[cell - 1].cells.empty() && !visit.insert(cell).second)
        return {0, false};

    Result res {cls[cell - 1].val, true};

    for (const auto& c : cls[cell - 1].cells)
        if (const auto res1 {eval(c, cls, visit)}; res1.good)
            res.res += res1.res;
        else
            return {0, false};

    return res;
}

int main() {
    unsigned N {}, M {};

    std::cin >> N >> M;        // M not used

    std::vector<Form> calc(N+1);

    for (unsigned n {}; n < N; ++n) {
        char type {};
        unsigned cellno {};

        std::cin >> type >> cellno;

        for (unsigned f {}, nocells {type - 'A' + 0U}; f < nocells; ++f) {
            unsigned cell {};

            std::cin >> cell;
            calc[cellno - 1].cells.push_back(cell);
        }

        std::cin >> calc[cellno - 1].val;
    }

    for (unsigned cell {1}; cell <= calc.size(); ++cell) {
        std::set<int> visit;

        std::cout << cell << "  ";

        if (const auto res {eval(cell, calc, visit)}; res.good)
            std::cout << res.res << '\n';
        else
            std::cout << "#REF#\n";     
    }
    for ( ;N<M; N++) 
         std::cout<<0<< '\n';
}

[seeplus]

Does the map version above work?

[satsat111]

The map version shows one abort called, one wrong answer and few terminated due to time out in test cases.

[seeplus]

Do you have the test data used?

[satsat111]

I can only see the test data 0,

10 9
A 1 10
B 2 1 20
B 3 2 30
B 4 6 2
B 5 4 2
B 6 5 2
C 7 1 2 2
C 8 7 6 3
D 9 1 2 3 8

and it shows abort called.

[seeplus]

I think I've mis-read the meaning of N, M. For L37 (of the map version) try (reverse N, M):

std::cin >> M >> N;

10 9
A 1 10
B 2 1 20
B 3 2 30
B 4 6 2
B 5 4 2
B 6 5 2
C 7 1 2 2
C 8 7 6 3
D 9 1 2 3 8
1  10
2  30
3  60
4  #REF#
5  #REF#
6  #REF#
7  42
8  #REF#
9  108

[satsat111]

Hi, now it did pass two test cases, but the rest shows wrong answer and terminated due to time out.

[seeplus]

Well that points to a probable problem with the algorithm used. This could be simple and easily fixed - or major requiring a re-design. However without the data that doesn't process as expected then I'm out. Good luck!

[lastchance]

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <string>
using namespace std;

//======================================================================

struct Cell
{
   long long value = 0;
   set<int> parents;
   bool refError = false;
};

//======================================================================

vector<Cell> readFormulae()
{
   string dummy;
   int N, M;
   cin >> N >> M;   getline( cin, dummy );
   vector<Cell> result( 1 + N );

   for ( int f = 0; f < M; f++ )
   {
      string line;
      getline( cin, line );
      stringstream ss( line );
      int i;
      ss >> dummy >> i;
      ss >> result[i].value;
      for ( int x; ss >> x; )
      {
         result[i].parents.insert( result[i].value );
         result[i].value = x;
      }
   }
   return result;
}

//======================================================================

bool getValue( int n, vector<Cell> &cells, set<int> &parents )
{
   for ( int c : cells[n].parents )
   {
      //      ref error                   cycle                         subtree error
      if ( cells[c].refError || !parents.insert( c ).second || !getValue( c, cells, parents ) )
      {
         cells[n].refError = true;
         return false;
      }
      cells[n].value += cells[c].value;
   }
   cells[n].parents.clear();
   return true;
}

//======================================================================

int main()
{
   vector<Cell> cells = readFormulae();

   for ( int n = 1; n < cells.size(); n++ )
   {
      set<int> parents{ n };
      getValue( n, cells, parents );
      if ( cells[n].refError ) cout << "#REF!" << '\n';
      else                     cout << cells[n].value << '\n';
   }
}

//====================================================================== 

10
30
60
#REF!
#REF!
#REF!
42
#REF!
108
0

[satsat111]

Hi lastchance, when trying your code it shows 4 out of 10 test cases correct and the others got wrong answers.