Does anyone have some test cases for prolem 833 (Water Falls) ?
I always get wrong answer. [/cpp]
833  Water Falls
Moderator: Board moderators

 New poster
 Posts: 4
 Joined: Mon Nov 11, 2002 6:08 am
 Location: Indonesia
833  Water Falls
Best regards,
David
David

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:
?, the problem statement clearly says
a test case to try
output is:
One problem would be ( but not surely) floating point/precision error... my approach is totally on Integers calculations. Just a thought.
so the input suggested by jagadish won't be valid i think.Also no coincidences exist in the vertical projection of all points (the x coordinates of the end points and of the source points are all different).
a test case to try
Code: Select all
1
8
10 12 1 3
4 8 6 10
2 5 7 10
12 11 16 9
13 8 15 9
10 5 18 8
13 5 16 6
8 3 4 5
8
5 13
6 13
15 12
14 9
12 7
15 8
14 6
7 4
Code: Select all
1
1
10
10
10
10
13
8
Istiaque Ahmed [the LAZBOy]
833  Water Falls
I found the weakness of current datasets.
In this case:The answer should be 6, not 5.
However my accepted code outputs 5.
In my code, I sort all segments by their maximal height.
And then determine if the source flows onto the segments in the sorted sequence.
This algorithm is not correct in the above case.
But It is judged as Accepted.
Here is my accepted code, written in C++:
In this case:
Code: Select all
1
2
1 4 5 1
3 3 6 2
1
4 4
However my accepted code outputs 5.
In my code, I sort all segments by their maximal height.
And then determine if the source flows onto the segments in the sorted sequence.
This algorithm is not correct in the above case.
But It is judged as Accepted.
Here is my accepted code, written in C++:
Code: Select all
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
struct Segment {
int x1, y1, x2, y2, minx, maxx;
void refresh() {
if (y1 > y2) {
swap(x1, x2);
swap(y1, y2);
}
minx = min(x1, x2);
maxx = max(x1, x2);
}
friend istream& operator>>(istream& in, Segment& s) {
return in >> s.x1 >> s.y1 >> s.x2 >> s.y2;
}
bool operator<(const Segment& s) const {
return y2 > s.y2;
}
} S[100];
int main() {
int cs; cin >> cs;
while (cs) {
cin >> N;
for (int i=0; i<N; ++i) {
cin >> S[i];
S[i].refresh();
}
sort(S, S+N);
cin >> M;
while (M) {
int x, y;
cin >> x >> y;
for (int i=0; i<N; ++i)
if (y > S[i].y1 && S[i].minx <= x && x <= S[i].maxx) {
x = S[i].x1;
y = S[i].y1;
}
cout << x << endl;
}
if (cs) cout << endl;
}
return 0;
}

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 833  Water Falls
There is no worry about the precision of floating point. My program stores all data with double format and works really fine.the LAZBOy wrote:?, the problem statement clearly saysAlso no coincidences exist in the vertical projection of all points (the x coordinates of the end points and of the source points are all different).
so the input suggested by jagadish won't be valid i think.
a test case to tryoutput is:Code: Select all
1 8 10 12 1 3 4 8 6 10 2 5 7 10 12 11 16 9 13 8 15 9 10 5 18 8 13 5 16 6 8 3 4 5 8 5 13 6 13 15 12 14 9 12 7 15 8 14 6 7 4
Code: Select all
1 1 10 10 10 10 13 8
One problem would be ( but not surely) floating point/precision error... my approach is totally on Integers calculations. Just a thought.
Have you ever...
 Wanted to work at best companies?
 Struggled with interview problems that could be solved in 15 minutes?
 Wished you could study realworld problems?
Re: 833  Water Falls
i guess the only critical input is when endpoints of lines have same x coordinate
sample input:
1
2 13
3
1 10 6 7
6 4 10 5
10 1 6 2
sample input:
1
2 13
3
1 10 6 7
6 4 10 5
10 1 6 2