Cannot understand what's wrong here...

Pages: 12
jumper007 (435)
I wanted to take this as a challenge:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=22&problem=1969&mosmsg=Submission+received+with+ID+10318750

And I wrote this code:

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
 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}
int main()
{
	int n, cnt, case_nr, SOP1, SOP2;
	vector<int> P;
	vector<int> SOP;
	
	P.reserve(10001);
	SOP.reserve(10001);
	
	do
	{
		cin >> n;
		case_nr = 1;
		cnt = 1;
		
		if (n == 0)
			break;
		
		vector<int> coll1(0,n);
		
		SOP1 = 0;
		for (int i = 0; i < n; i++)
		{
			P[i+1] = coll1[i] * coll1[i+1];
			SOP1 = SOP1 + P[i+1];
		}
		SOP1 = SOP1 + (coll1[0] * coll1[n-1]);
		
		for (int j = 1; j <= factorial(n); j++)
		{
			
			
			SOP[j-1] = SOP1;
			
			next_permutation(coll1.begin(), coll1.end());
			
			SOP2 = 0;
			
			for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}
			SOP2 = SOP2 + (coll1[0] * coll1[n-1]);
			
			SOP[j] = SOP2;
		}
		
		for (int k = 0; k < factorial(n); k++)
		{
			// how to check how many values are actually different in the vector ?
		}
		
		cout << "Case #" << case_nr << ": " << cnt << endl;
		
		coll1.clear();
		
		case_nr++;
	}while (n != 0);
	
	return 0;
}


PS: Line 67...

But it ends with a "Runtime Error".

EDIT: Shall I use the function "unique_copy" and then just check if element '0' is equal or not with '1' and '1' with '2' and so on ?
Last edited on
Peter87 (11254)
The code doesn't even compile because j is not in scope on line 65.

On line 35 you create a vector with 0 elements initialized to value 5. I bet you put the arguments in the wrong order.

Note that reserve does not change the vector size. It just allocates enough memory to hold that many elements without initializing it.
jumper007 (435)
Oh, on line 65 it's a copy/paste error.

Line 35: Quote from a STL book: ContType c(beg,end) Creates a container and initializes it with copies of all elements of [beg,end)
Did I get it wrong ?

About reserve, what else could I use to change vector size in such a way that it can run properly ?
Last edited on
TheIdeasMan (6847)
The size of the vector is way too large. Factorial 69 is in the order of 1E500 which is bigger than a double, but you are using int which only goes to 2.147 billion.

HTH (Hope this helps)
jumper007 (435)
Quote: "
The size of the vector is way too large.
the order of 1E500 which is bigger than a double
you are using int which only goes to 2.147 billion.
"

I'm confused. The size of my vector is too small, or too large ?

And is the container declaration and assignment on line 35 okay ?
Last edited on
jumper007 (435)
Can someone please explain me the following ?

1) Doesn't vector<int> coll1(0,n); mean that I create a vector container with the following elements ?

1
2
3
4
5
 
coll1[0] = 0;
coll1[1] = 1;
coll1[2] = 2;
.............
coll1[n] = n;


2) How to initialize the vector in such a way, that it wont crash (runtime error because of lack of space, or idk) ?

3) To find out how many different numbers are there in the vector, should I use the function unique_copy, so that I erase the duplicates, and then compare each element with the following, and increase the counter ?

Thanks in advance.

~Raul.
Last edited on
TheIdeasMan (6847)
I'm confused. The size of my vector is too small, or too large ?


I am saying that you are using an int to hold the factorial, the max size that this will hold is 2.147 billion. I am not sure what factorial will produce a number this size, but i do know that factorial 69 is in the order of 1E500, which is bigger than what a double can hold. Your vector holds 10001 ints, so even if you were using doubles 69 would be too much.

It is important to realise what maximums different data types can hold.

Hope this is a bit clearer.
jumper007 (435)
Okay, but it still won't run. Runtime error comes from the bad initialisation of the vectors I think...
jumper007 (435)
Okay, this is the updated code. After I input 4-5numbers ("n's") the program crashes, giving a runtime error. The output is always '1' though.
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
 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}
int main()
{
	int n, cnt, case_nr, SOP1, SOP2;
	vector<int> P;
	vector<int> SOP;
	
	P.reserve(1001);
	SOP.reserve(1001);
	
	do
	{
		cin >> n;
		case_nr = 1;
		cnt = 1;
		
		if (n == 0)
			break;
		
		vector<int> coll1(0,n);
		
		SOP1 = 0;
		for (int i = 0; i < n; i++)
		{
			P[i+1] = coll1[i] * coll1[i+1];
			SOP1 = SOP1 + P[i+1];
		}
		SOP1 = SOP1 + (coll1[0] * coll1[n-1]);
		
		for (int j = 1; j <= factorial(n); j++)
		{
			
			
			SOP[j-1] = SOP1;
			
			next_permutation(coll1.begin(), coll1.end());
			
			SOP2 = 0;
			
			for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}
			SOP2 = SOP2 + (coll1[0] * coll1[n-1]);
			
			SOP[j] = SOP2;
		}
		
		for (int k = 0; k < factorial(n); k++)
		{
			vector<int> coll2;
			// Ignore this. I know it's wrong.
			unique_copy(coll1.begin(), coll1.end(), coll2.begin());
			for (int l = 0; l < coll2.size(); l++)
			{
				if (coll2[l] != coll2[l+1])
					cnt++;
			}
		}
		
		cout << "Case #" << case_nr << ": " << cnt << endl;
		
		coll1.clear();
		
		case_nr++;
	}while (n != 0);
	
	return 0;
}
Last edited on
TheIdeasMan (6847)
It is as Peter87 was saying :

Note that reserve does not change the vector size. It just allocates enough memory to hold that many elements without initializing it.


You haven't allocated a size for your vector. Googlle "C++ vector example"
Peter87 (11254)
Use resize instead of reserve to set the size of the vector.

Line 35: Quote from a STL book: ContType c(beg,end) Creates a container and initializes it with copies of all elements of [beg,end)
Did I get it wrong ?

The book is talking about iterators. Integers are not iterators so the constructor that is being used is the second constructor on this page http://www.cplusplus.com/reference/stl/vector/vector/ (the book was talking about the third one).
jumper007 (435)
I did search on google, and all the links (that are related to my search) are from www.cplusplus.com reference. I did check the reference before coming on the forums, and that's why I'm here. I don't understand how to initialise the vector.

1
2
3
4
 
v.resize() // not good - that's what I understand.
v.size() // doesn't help
v.capacity() // doesn't help
v.reserve() // doesn't help


Idk any other function...
Last edited on
TheIdeasMan (6847)
About the size of the vector:

The factorial gets very large quickly.

If you are going to use ints, then set a limit of say 20, this will be the size of the vector and the limit for calculating the factorial. Once you have it working, then look at changing the limit to a larger value.

To do this you really need to use doubles, (because it grows so quickly). Using unsigned long long doesn't help much. Doubles go to a max of 1.7E308, so be careful that your factorial answer doesn't exceed this.
jumper007 (435)
Oh, well that helped. Thanks again Peter87.
TheIdeasMan (6847)
THis is the example from cplusplus.com


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
 
// constructing vectors
#include <iostream>
#include <vector>
using namespace std;

int main ()
{
  unsigned int i;

  // constructors used in the same order as described above:
  vector<int> first;                                // empty vector of ints
  vector<int> second (4,100);                       // four ints with value 100
  vector<int> third (second.begin(),second.end());  // iterating through second
  vector<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

  cout << "The contents of fifth are:";
  for (i=0; i < fifth.size(); i++)
    cout << " " << fifth[i];

  cout << endl;

  return 0;
}


jumper007 (435)
The code looks like this now:

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
 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}
int main()
{
	int n, cnt, case_nr, SOP1, SOP2;
	vector<int> P (20,0);
	vector<int> SOP (20,0);
		
	do
	{
		cin >> n;
		case_nr = 1;
		cnt = 1;
		
		if (n == 0)
			break;
		
		vector<int> coll1;
		
		for (int c = 0; c < n; c++)
			coll1.push_back(c);
		
		SOP1 = 0;
		for (int i = 0; i < n; i++)
		{
			P[i+1] = coll1[i] * coll1[i+1];
			SOP1 = SOP1 + P[i+1];
		}
		SOP1 = SOP1 + (coll1[0] * coll1[n-1]);
		
		for (int j = 1; j <= factorial(n); j++)
		{
			
			
			SOP[j-1] = SOP1;
			
			next_permutation(coll1.begin(), coll1.end());
			
			SOP2 = 0;
			
			for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}
			SOP2 = SOP2 + (coll1[0] * coll1[n-1]);
			
			SOP[j] = SOP2;
		}
		
		/*vector<int> coll2;
			
		unique_copy(coll1.begin(), coll1.end(), coll2.begin());
		
		for (int k = 0; k < factorial(n); k++)
		{
			if (coll2[k] != coll2[k+1])
				cnt++;
		}*/ // This thing seems to be wrong; The program doesnt even compile if running it.
		
		cout << "Case #" << case_nr << ": " << cnt << endl;
		
		coll1.clear();
		
		case_nr++;
	}while (n != 0);
	
	return 0;
}
Last edited on
TheIdeasMan (6847)
Ok what about this :

 
 
vector<int> P(20,0); // 20 ints,  initialised to zero


My other feeling is that this is a lot of code for what you are trying to do. I am guessing this could be done with one short for loop.
jumper007 (435)
Uhm, I really don't have any idea about how to make it shorter. Sadly performance is not something that I am good at :/

PS: I edited the code in accordance with your tip.
Last edited on
TheIdeasMan (6847)
So you still haven't initialsed the vectors, although you changed the resize to 1001 which is still way too big.

As I said, get it working up to a vector size of 10 say.

Edit: we were replying at the same time.
Last edited on
jumper007 (435)
Something is going wrong. After I insert 2 values (gives wrong answers), it crashes returning -17..... (large number >10 digits)

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
 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}
int main()
{
	int n, cnt, case_nr, SOP1, SOP2;
	vector<int> P (20,0);
	vector<int> SOP (20,0);
	
	do
	{
		cin >> n;
		case_nr = 1;
		cnt = 1;
		
		if (n == 0)
			break;
		
		vector<int> coll1;
		
		for (int c = 0; c < n; c++)
			coll1.push_back(c);
		
		SOP1 = 0;
		for (int i = 0; i < n; i++)
		{
			P[i+1] = coll1[i] * coll1[i+1];
			SOP1 = SOP1 + P[i+1];
		}
		SOP1 = SOP1 + (coll1[0] * coll1[n-1]);
		
		for (int j = 1; j <= factorial(n); j++)
		{
			
			
			SOP[j-1] = SOP1;
			
			next_permutation(coll1.begin(), coll1.end());
			
			SOP2 = 0;
			
			for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}
			SOP2 = SOP2 + (coll1[0] * coll1[n-1]);
			
			SOP[j] = SOP2;
		}
		
		// Probably error comes here.
		for (int k = 0; k < factorial(n); k++)
		{
			vector<int> coll2 (n,0);
			
			unique_copy (coll1.begin(), coll1.end(), back_inserter(coll2));
			
			if (coll2[k] != coll2[k+1])
				cnt++;
		}
		
		cout << "Case #" << case_nr << ": " << cnt << endl;
		
		coll1.clear();
		
		case_nr++;
	}while (n != 0);
	
	return 0;
}
Last edited on
Pages: 12