You are using a version without Ads of this website. Please, consider donating:

### Olympiad exercise -- Having issues

 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

My code for this is the following:

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879`` ``````#include #include #include 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& 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& 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 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.

~ Raul ~
Last edited on
What do you mean "syntax issues"? It doesn't compile?
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
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].

 ``123456`` ``````// 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
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.
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
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:
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283`` ``````#include #include #include 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& 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& 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 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 >&, 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 > >, _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 > >]’ 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
 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 > >, _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 > >]’ 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&).
Thanks :D

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

 ``1234567`` ``````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
getA and getB need to be declared as const functions. i.e. a const argument can not call a non-const function.

 ``1234`` ``````inline long long const getA() const { return a; } inline long long const getB() const { return b; }``````

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.

You are using a version without Ads of this website. Please, consider donating: