833 - Water Falls

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
david_ciang
New poster
Posts: 4
Joined: Mon Nov 11, 2002 6:08 am
Location: Indonesia

833 - Water Falls

Post by david_ciang »

Does anyone have some test cases for prolem 833 (Water Falls) ?

I always get wrong answer. :( [/cpp]
Best regards,

David

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish »

i guess the only critical input is when endpoints of lines have same x co-ordinate

sample input:

1
2 13
3
1 10 6 7
6 4 10 5
10 1 6 2
if u can think of it .. u can do it in software.

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

?, the problem statement clearly says
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).
so the input suggested by jagadish won't be valid i think.
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
output is:

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. :)
Istiaque Ahmed [the LA-Z-BOy]

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

833 - Water Falls

Post by DJWS »

I found the weakness of current datasets.

In this case:

Code: Select all

1

2
1 4 5 1
3 3 6 2
1
4 4
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++:

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;
}

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 833 - Water Falls

Post by DD »

the LA-Z-BOy wrote:?, the problem statement clearly says
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).

so the input suggested by jagadish won't be valid i think.
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
output is:

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. :)
There is no worry about the precision of floating point. My program stores all data with double format and works really fine.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

x3xd
New poster
Posts: 1
Joined: Mon Aug 22, 2011 12:46 am
Contact:

Re: 833 - Water Falls

Post by x3xd »

i guess the only critical input is when endpoints of lines have same x co-ordinate

sample input:

1
2 13
3
1 10 6 7
6 4 10 5
10 1 6 2

Post Reply

Return to “Volume 8 (800-899)”