105 - The Skyline Problem

All about problems in Volume 1. 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
User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

1

Post by tmdrbs6584 » Tue Feb 28, 2006 10:40 am

Hi logic
Bye logic

f.eliel
New poster
Posts: 10
Joined: Wed Feb 08, 2006 4:31 pm

Post by f.eliel » Tue Feb 28, 2006 2:54 pm

I don

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Tue Feb 28, 2006 7:54 pm

I dont think your code matches the sample input. Just put the main printing FOR loop out of the WHILE loop. Otherwise your code is Ok.

Remove your code after u get AC.
Where's the "Any" key?

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

logic!

Post by sds1100 » Fri Mar 03, 2006 8:26 am

logic

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

Post by sds1100 » Fri Mar 03, 2006 8:37 am

i me too imlazy짱깨
sorry.
sorry i don't know your program..
sorry.sorry.sorry.sorry.sorry.

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm

105 WA

Post by coldfire » Wed Apr 05, 2006 8:07 pm

I tested every possible legal test on my computer, but i can't find the bug .. if anyone could help me ... please ...

I use interval trees for better time...
//{$S-,R-,Q-,B-}

const maxN = 6000;
maxL = 30000;

type triple = record
x, h, s: longint;
end;

var d: array[0..maxN] of triple;
x, y, h, n, i, j, max: longint;
a, b: array[0..maxL] of longint;

procedure read_data;
//var f: text;
begin

// assign(f, '105.in'); reset(f);

n := 0;
while not eof(input) do begin

readln(x, h, y);

if x < y then begin
inc(n); d[n].x := x; d[n].h := h; d[n].s := 1;
inc(n); d[n].x := y; d[n].h := h; d[n].s := -1;
end;

end;

// close(f);

end;

procedure qSort(l, r: longint);
var
i, j, x: longint;
y: triple;
begin
i := l; j := r; x := d[(l+r) DIV 2].x;
repeat
while d.x < x do i := i + 1;
while x < d[j].x do j := j - 1;
if i <= j then
begin
y := d; d := d[j]; d[j] := y;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then qSort(l, j);
if i < r then qSort(i, r);
end;

procedure update(k, l, r, s: longint);
var m: longint;
begin

if (r <= d[j].h) then begin

if s = -1 then begin
dec(a[k]);
if a[k] = 0 then b[k] := b[k * 2] + b[k * 2 + 1];
end else begin
inc(a[k]);
b[k] := r - l + 1;
end;

end else begin

m := (l + r) shr 1;
update(k * 2, l, m, s);
if d[j].h > m then update(k * 2 + 1, m + 1, r, s);

if a[k] = 0 then b[k] := b[k * 2] + b[k * 2 + 1];

end;

end;

procedure main;
begin

qsort(1, n);

i := 1;
while i <= n do begin

j := i; max := b[1];
while (d[j].x = d.x) and (j <= n) do begin
if d[j].h > 0 then update(1, 1, 10100, d[j].s); inc(j);
end;
i := j;

if (b[1] <> max) then
if i <= n then write(d.x, ' ', b[1], ' ') else write(d.x, ' ', b[1]);

end;

end;

begin

// writeln; writeln;
read_data;
main;

end.

frederic
New poster
Posts: 1
Joined: Mon Jul 03, 2006 1:31 am

P 105 Why do i get WA?

Post by frederic » Mon Jul 03, 2006 4:02 pm

Hello,

i don't know why i get WA for this code. The code works on all data i have found in this board so far. Can you give me a hint , please?

(code deleted)

(Edit)
NM, i got ACC now :-)

For me a critical input was:
1 1 2
1 3 2
1 2 2
2 3 4

Correct Answer:
1 3 4 0

Maybe this might help

shaform
New poster
Posts: 4
Joined: Tue Aug 08, 2006 1:55 pm

[Solved]105 The Skyline Problem: Runtime Error

Post by shaform » Tue Aug 08, 2006 2:14 pm

I've tested my codes many times.
I even used some input files with random numbers, and I didn't find any problems.
But after I submited it, I got RE.
It said : Invalid memory reference
Well, I know there are some easier ways to solve The Skyline Problem, but I just want to know why this code couldn't work.

Code: Select all

Removed after solved.
Last edited by shaform on Fri Aug 11, 2006 8:04 am, edited 2 times in total.

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania

Post by nev4 » Wed Aug 09, 2006 4:27 pm

This code is so big and it uses pointers to pointers, there is no wonder why RE. Try to code even without pointers if possible.
My solution for this to examine all blocks in a row and test if next is over current, if not test it comes from current's side, if not, does begin new block.

shaform
New poster
Posts: 4
Joined: Tue Aug 08, 2006 1:55 pm

Post by shaform » Fri Aug 11, 2006 8:09 am

I think you are right.
Anyway, I finally got Accept.
Thanks.

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

This can be shorter

Post by hedgehog1204 » Mon Aug 21, 2006 7:48 am

This can be shorter. This is in Python, but can be easily converted to whatever:

Code: Select all

# Program that solves The Skyline Problem
# http://acm.uva.es/p/v1/105.html

max = 10000						# maximum x coordinates
h = [0 for i in range(max)]		# skyline heights for x=i

file = open('input.txt')
for line in file:						# initialize variables with data from file:
	vars = line.split()
	for i in range(int(vars[0]), int(vars[2])):	# update skyline hights
		if h[i] < int(vars[1]):
			h[i] = int(vars[1])
# print out the skyline:			
i = 0		
while h[i] == 0:
	i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
	if h[j] != hi:
		print j, h[j],
		hi = h[j]
file.close()

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

It can be shorter

Post by hedgehog1204 » Mon Aug 21, 2006 7:50 am

Code: Select all

max = 10000						
h = [0 for i in range(max)]		
file = open('input.txt')
for line in file:						
	vars = line.split()
	for i in range(int(vars[0]), int(vars[2])):	
		if h[i] < int(vars[1]):
			h[i] = int(vars[1])		
i = 0		
while h[i] == 0:
	i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
	if h[j] != hi:
		print j, h[j],
		hi = h[j]
file.close()

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

This works for me

Post by hedgehog1204 » Mon Aug 21, 2006 7:53 am

Code: Select all

max = 10000						
h = [0 for i in range(max)]		
file = open('input.txt')
for line in file:						
	vars = line.split()
	for i in range(int(vars[0]), int(vars[2])):	
		if h[i] < int(vars[1]):
			h[i] = int(vars[1])		
i = 0		
while h[i] == 0:
	i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
	if h[j] != hi:
		print j, h[j],
		hi = h[j]
file.close()

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

Try this approach:

Post by hedgehog1204 » Mon Aug 21, 2006 7:56 am

Code: Select all

max = 10000                  
h = [0 for i in range(max)]      
file = open('input.txt')
for line in file:                  
   vars = line.split()
   for i in range(int(vars[0]), int(vars[2])):   
      if h[i] < int(vars[1]):
         h[i] = int(vars[1])      
i = 0      
while h[i] == 0:
   i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
   if h[j] != hi:
      print j, h[j],
      hi = h[j]
file.close()

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:

Try this approach (Python):

Post by hedgehog1204 » Mon Aug 21, 2006 7:57 am

Code: Select all

max = 10000                  
h = [0 for i in range(max)]      
file = open('input.txt')
for line in file:                  
   vars = line.split()
   for i in range(int(vars[0]), int(vars[2])):   
      if h[i] < int(vars[1]):
         h[i] = int(vars[1])      
i = 0      
while h[i] == 0:
   i += 1
print i, h[i],
hi = h[i]
for j in range(i+2, max):
   if h[j] != hi:
      print j, h[j],
      hi = h[j]
file.close()

Post Reply

Return to “Volume 1 (100-199)”