C++

Forum

 
 
Olympiad exercise -- Having issues

jumper007 (435)
Bounderies
At the border of state A with the state B there are N devices of defense. For each device k it is also known the length [Ak, Bk] in which they operate (border is considered to be a straight line, and each tool covers a particular segment on this line). To reduce the costs of maintenance, the head of state has decided that some of the N devices for the defense have to be dismantled. More specifically, we will dismantle redundant devices. A device i is called redundant if there is at least one device j so that the interval [Aj, Bj] includes the interval [Ai, Bi] (more explicitly, Aj < Ai and Bi < Bj).

Task
Find out how many of the N devices are redundant.

Input
On the first line of the file “granita.in” you will have an integer N, representing the number of defending devices. On the following N lines there will be pairs of two integers, a and b (a<b), representing the start and the end of the interval on which the device works (more explicitly, assuming that on line i we have a and b, then [a, b] = [Ai, Bi]).

Output
The file “granita.out” will contain a single line on which you will print the integer number representing the number of redundant devices.

Restrictions
1 <= N <= 16.000
0 <= Ai < Bi <= 2.000.000
All integers Ai will be distinct
All integers Bi will be distinct

Example:

Granita.in
5
0 10
2 9
3 8
1 15
6 11

Granita.out
3


My code for this is the following:

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

using namespace std;

int n;

class Boundary{
	long long a, b;

	public:
		inline long long const getA() { return a; }
		inline long long const getB() { return b; }
		friend bool operator<(Boundary&, Boundary&);
		friend bool operator>(Boundary&, Boundary&);
		friend istream& operator>>(istream&, Boundary&);
};

bool operator<(Boundary& x, Boundary& y){
	return x.getA() < y.getA();
}

bool operator>(Boundary& x, Boundary& y){
	return x.getB() > y.getB();
}

bool compare(long long x, long long y){
    return x > y;
}

istream& operator>>(istream& is, Boundary& br){
	is >> br.a >> br.b;
	return is;
}

void readData(vector<Boundary>& Bo, Boundary& br){
	ifstream in("granita.in");
	Bo.clear();

	if (in && !in.eof()){
		in >> n;
	}

	while (in && !in.eof() && in >> br){
		Bo.push_back(br);
	}
}

void processAndWrite(vector<Boundary>& Bo, int& count){
	std::ofstream out("granita.out");

	// Sort I
	sort(Bo.begin(), Bo.end());
	for (size_t i = 1; i < n; i++){       // Correction:  size_t i = 0; i < n-1; i++
		if ((Bo[i].getA() < Bo[i+1].getA()) && (Bo[i].getB() > Bo[i+1].getB())){
			count++;
		}
	}

	// Sort II
	/*sort(Bo.begin(), Bo.end(), compare);
	for (size_t i = 1; i < n; i++){
		if ((Bo[i].getA() < Bo[i+1].getA()) && (Bo[i].getB() > Bo[i+1].getB())){
			count++;
		}
	}*/

	out << count;
}

int main(int argc, char *argv[]){
	vector<Boundary> Br;
	Boundary br;
	int count = 0;
	readData(Br,br);
	processAndWrite(Br,count);
	return 0;
}


Though, it seems not to work because of the syntax issues...
I know the program is not complete yet, but I wanted to ask an expert in order to understand what my syntax mistakes are so far.

PS: The current exercise has to be solved using the Greedy method.

Thanks in advance.
~ Raul ~
Last edited on
helios (17506)
What do you mean "syntax issues"? It doesn't compile?
jumper007 (435)
Well, Visual C++ 2010 returns the following error:

Debug Assertion Failed!
Program: [...]Granita.exe
File: C:\[...]\vc\include\vector
Line: 932

Expression: vector subscript out of range

For information on how your program can cause an assertion failure see the Visual C++ documentation on asserts.


And it force-breaks. I think it does it when it reaches the "sort" function. At least that's what Code::Blocks returned.

EDIT: Could it be because I had declared the Operator < and > overload as "friend" with two parameters instead of declaring it without keyword "friend" and with only one parameter ?
Last edited on
AbstractionAnon (6954)
The sort at line 54 should be ok, but I see a problem at lines 55-56.

Assuming n is 5, the last iteration throught the loop will compare Bo[4] and Bo[5]. That will cause a vector fault since the elements of the vector are 0-4.
Also, your loop variable is starting at 1 which will cause you to skip Bo[0].

helios (17506)
1
2
3
4
5
6
 
//   n is never set ---v
for (size_t i = 1; i < n; i++){
//              v---------------v---- These indices are wrong. You're iterating in the
        if ((Bo[i].getA() < Bo[i+1].getA()) && (Bo[i].getB() > Bo[i+1].getB())){
//range [1;count). Either iterate in [0;count-1) and use indices i and i+1, or iterate in
//[1;count) and use indices i-1 and i.
Last edited on
toum (353)
In the loop just after the sort, you're reading index i+1.
If you must have i+1<n, then you must have i < n-1.
jumper007 (435)
Oh right. Let me check whether it works or not after this change.

EDIT: Thanks a lot guys. I know it was quite a stupid mistake, but thanks for pointing it out for me. Topic closed.
Last edited on
jumper007 (435)
Uhm.. Sorry for bothering again. I completed the task and it works for the given example. Now I tried to upload my source code on the server so that I can get my score but it gives a compilation error (Their compilator is GNU C++).
Does anyone know why this might have happened ? I mean, it works like a charm on Visual C++.

My code 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 <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

class Boundary{
	long long a, b;

	public:
		inline long long const getA() { return a; }
		inline long long const getB() { return b; }
		friend bool operator<(Boundary&, Boundary&);
		friend bool operator>(Boundary&, Boundary&);
		friend istream& operator>>(istream&, Boundary&);
};

bool operator<(Boundary& x, Boundary& y){
	return x.getA() < y.getA();
}

bool operator>(Boundary& x, Boundary& y){
	return x.getB() > y.getB();
}

bool compare(long long x, long long y){
    return x > y;
}

istream& operator>>(istream& is, Boundary& br){
	is >> br.a >> br.b;
	return is;
}

void readData(vector<Boundary>& Bo, Boundary& br){
	ifstream in("granita.in");
	Bo.clear();

	if (in && !in.eof()){
		in >> n;
	}

	while (in && !in.eof() && in >> br){
		Bo.push_back(br);
	}
}

void processAndWrite(vector<Boundary>& Bo, int& count){
	std::ofstream out("granita.out");
	int MinDif = INT_MAX;
	long long x, y;

	// Sort I
	sort(Bo.begin(), Bo.end());
	for (size_t i = 0; i < n-1; i++){

		if (Bo[i].getB() - Bo[i].getA() < MinDif){
			MinDif = Bo[i].getB() - Bo[i].getA();
			x = Bo[i].getA();
			y = Bo[i].getB();
		}
	}

	for (size_t i = 0; i < n; i++){

		if ((Bo[i].getA() < x) && (Bo[i].getB() > y)){
			count++;
		}
	}

	out << count;
}

int main(int argc, char *argv[]){
	vector<Boundary> Br;
	Boundary br;
	int count = 0;
	readData(Br,br);
	processAndWrite(Br,count);
	return 0;
}


The compilation error returned:
user.cpp: In function ‘void processAndWrite(std::vector<Boundary, std::allocator<Boundary> >&, int&)’:
user.cpp:52: error: ‘INT_MAX’ was not declared in this scope
user.cpp:57: warning: comparison between signed and unsigned integer expressions
user.cpp:66: warning: comparison between signed and unsigned integer expressions
In file included from /usr/include/c++/4.4/algorithm:62,
from user.cpp:3:
/usr/include/c++/4.4/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&) [with _Tp = Boundary]’:
/usr/include/c++/4.4/bits/stl_algo.h:2268: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Boundary*, std::vector<Boundary, std::allocator<Boundary> > >, _Size = int]’
/usr/include/c++/4.4/bits/stl_algo.h:5220: instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Boundary*, std::vector<Boundary, std::allocator<Boundary> > >]’
user.cpp:56: instantiated from here
/usr/include/c++/4.4/bits/stl_algo.h:89: error: no match for ‘operator<’ in ‘__a < __b’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:90: error: no match for ‘operator<’ in ‘__b < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:92: error: no match for ‘operator<’ in ‘__a < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:96: error: no match for ‘operator<’ in ‘__a < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:98: error: no match for ‘operator<’ in ‘__b < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)


EDIT: This is quite the same as Code::Blocks returned. Except of the INT_MAX.
Last edited on
helios (17506)
user.cpp:52: error: ‘INT_MAX’ was not declared in this scope
Defined in <climits>

/usr/include/c++/4.4/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&) [with _Tp = Boundary]’:
/usr/include/c++/4.4/bits/stl_algo.h:2268: instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Boundary*, std::vector<Boundary, std::allocator<Boundary> > >, _Size = int]’
/usr/include/c++/4.4/bits/stl_algo.h:5220: instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Boundary*, std::vector<Boundary, std::allocator<Boundary> > >]’
user.cpp:56: instantiated from here
/usr/include/c++/4.4/bits/stl_algo.h:89: error: no match for ‘operator<’ in ‘__a < __b’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:90: error: no match for ‘operator<’ in ‘__b < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:92: error: no match for ‘operator<’ in ‘__a < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:96: error: no match for ‘operator<’ in ‘__a < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
/usr/include/c++/4.4/bits/stl_algo.h:98: error: no match for ‘operator<’ in ‘__b < __c’
user.cpp:20: note: candidates are: bool operator<(Boundary&, Boundary&)
The signature for bool operator<(Boundary&, Boundary&) should be bool operator<(const Boundary&, const Boundary&).
jumper007 (435)
Thanks :D

But still, if I mark the operators as const, I will get an error on:

1
2
3
4
5
6
7
 
bool operator<(const Boundary& x, const  Boundary& y){
	return x.getA() < y.getA();
}

bool operator>(const Boundary& x, const  Boundary& y){
	return x.getB() > y.getB();
}


PS: This is the error pointed out by Visual C++ compiler.

How could I fix that ?
Last edited on
AbstractionAnon (6954)
getA and getB need to be declared as const functions. i.e. a const argument can not call a non-const function.

1
2
3
4
 
inline long long const getA() const
{ return a; }
inline long long const getB() const
{ return b; }


jumper007 (435)
Yes indeed, thank you. I have just started using Object-Orientated Programming today and I am trying to understand everything.
Again, thank you all for all the help and the patience.

~ Raul ~
Topic archived. No new replies allowed.