C++

Forum

 
Sheet

Pages: 12
lastchance (6980)
(EDITED - Sorry!) Does this do any better? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#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, const set<int> &sequence )
{
   for ( int c : cells[n].parents )
   {
      if ( cells[c].refError )
      {
         cells[n].refError = true;
         return false;
      }
      set<int> extended = sequence;
      if ( !extended.insert( c ).second || !getValue( c, cells, extended ) )
      {
         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> sequence{ n };
      getValue( n, cells, sequence );
      if ( cells[n].refError ) cout << "#REF!" << '\n';
      else                     cout << cells[n].value << '\n';
   }
}

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

Last edited on
satsat111 (30)
No, don't be, very appreciate the help.
Yes, the number of passed cases improve, but now still got four wrong answers out of ten.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
#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 ( long unsigned 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, const set<int> &sequence )
{
   for ( long unsigned int c : cells[n].parents )
   {
      if ( cells[c].refError )
      {
         cells[n].refError = true;
         return false;
      }
      set<int> extended = sequence;
      if ( !extended.insert( c ).second || !getValue( c, cells, extended ) )
      {
         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 ( long unsigned int n = 1; n < cells.size(); n++ )
   {
      set<int> sequence{ n };
      getValue( n, cells, sequence );
      if ( cells[n].refError ) cout << "#REF!" << '\n';
      else                     cout << cells[n].value << '\n';
   }
}
lastchance (6980)
Well, it's real guesswork as to what is causing wrong answers (though I could see a few opportunities for timeout).

Are you able to post a link to the original task (not your rephrasing of it) so that we can see whether there are any constraints that we might have missed?

Here's one slightly complex try that anticipates a few unlikely possibilities in the input data.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <string>
using namespace std;

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

struct Cell
{
   long long value = 0;
   multiset<int> parents;              // Perhaps a parent cell can be repeated?
   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; )
      {
         // Perhaps input has non-existent cells?
         if ( result[i].value < 1 || result[i].value > N ) result[i].refError = true;

         result[i].parents.insert( result[i].value );
         result[i].value = x;
      }
   }
   return result;
}

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

bool getValue( int n, vector<Cell> &cells, const set<int> &sequence )
{
   for ( int p : cells[n].parents )
   {
      // Direct dependency on reference error
      if ( cells[p].refError )
      {
         cells[n].refError = true;
         return false;
      }

      set<int> extended = sequence;
      // Check for a cycle (all cells in it would fail if so)
      if ( !extended.insert( p ).second )
      {
         for ( int e : extended ) cells[e].refError = true;
         return false;
      }

      // Otherwise recurse onward
      if ( !getValue( p, cells, extended ) )
      {
         cells[n].refError = true;
         return false;
      }

      cells[n].value += cells[p].value;
   }

   // Already updated the cell value, so prevent any further adding
   cells[n].parents.clear();

   return true;
}

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

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

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

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

Last edited on
satsat111 (30)
Hi lastchance, it works now, thanks for your help. I'll try and see which part of constraint is critical.
Last edited on
satsat111 (30)
Hi lastchance, I'd like to ask about !extended.insert( p ).second at line61, who is insert( p ).second, is it the second value of cells[n].parents, why can it check if there's a cycle?thank you.
lastchance (6980)
Although we don't often use the return value, std::set.insert() returns a pair consisting of:
an iterator to the inserted value (if successful); a boolean for whether the insert was successful or not.

The insert will fail (and hence the second element of the pair will be false) if the item that you try to insert in the set is already there - which is the standard test for a cycle: you've seen it before.

If you have a cycle then you have the Catch-22 situation: you can't insert the value at a node ... without knowing the value at that node.
Last edited on
satsat111 (30)
Thank you so much, I understand better now.
Topic archived. No new replies allowed.
Pages: 12