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
wdg
New poster
Posts: 4
Joined: Tue Aug 16, 2005 3:19 pm

Post by wdg » Wed Aug 17, 2005 9:04 am

I tested it very carfully, but I could not find the wrong place.

Code: Select all

program p105;
var
  cache:array[1..100,1..2] of integer;
  l,h,r,n,size,k,t:integer;
procedure print_n_clear(j:integer);
{ ouput except the nth elements and so on remain; so does clear operation }
var i:integer;
begin
  for i:=1 to j do write(cache[i][1],' ',cache[i][2],' ');
  for i:=j+1 to size do begin
    cache[i-j][1]:=cache[i][1]; cache[i-j][2]:=cache[i][2];
    end;
  size:=size-j;
end;
procedure insert(a,b,loct:integer);
var i:integer;
begin
  for i:=size downto loct do begin
    cache[i+1][1]:=cache[i][1]; cache[i+1][2]:=cache[i][2]; end;
  cache[loct][1]:=a; cache[loct][2]:=b; inc(size);
end;
begin
  fillchar(cache,sizeof(cache),0);
  read(l,h,r); cache[1][1]:=l; cache[1][2]:=h;
  cache[2][1]:=r; cache[2][2]:=0; size:=2;
  while not eof do begin
    read(l,h,r);
    n:=1; while (n<=size) and (l>cache[n][1]) do inc(n);
    if n=size+1 then begin
      print_n_clear(size); cache[1][1]:=l; cache[1][2]:=h;
      cache[2][1]:=r; cache[2][2]:=0; size:=2;
    end
    else begin
      if cache[n-1][2]<h then begin
        if cache[n][1]>r then begin
          insert(r,cache[n-1][2],n); insert(l,h,n);
        end
        else if cache[n][1]<r then begin
          insert(l,h,n); inc(n);
          while (n<=size) and (r>cache[n][1]) do begin
            h:=cache[n][2];
            for k:=n to size-1 do begin
              cache[k][1]:=cache[k+1][1]; cache[k][2]:=cache[k+1][2]; end;
            dec(size); end;
          if n=size+1 then begin cache[n][1]:=r;
            cache[n][2]:=0; inc(size); end
          else insert(r,h,n);
        end
      end
      else if cache[n-1][2]>h then begin
        if cache[n][1]<r then
          if cache[n][2]<h then begin
            t:=cache[n][2]; cache[n][2]:=h; h:=t; inc(n);
            while (n<=size) and (r>cache[n][1]) do begin
              h:=cache[n][2];
              for k:=n to size-1 do begin
              cache[k][1]:=cache[k+1][1]; cache[k][2]:=cache[k+1][2]; end;
              dec(size); end;
            if (n=size+1) then insert(r,0,n)
            else insert(r,h,n);
          end
          else begin
            t:=cache[n][2]; n:=n+1;
            while (n<=size) and (r>cache[n][1]) do begin
              if cache[n][2]<h then begin
                t:=cache[n][2]; cache[n][2]:=h; end;
              inc(n);
            end;
            if n=size+1 then insert(r,0,n)
            else insert(r,t,n);
          end;
      end;
    end;
  end;
  print_n_clear(size);
end.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Aug 17, 2005 11:08 am

As to your first posting:
-sure you need to read all data before you print your answer; you can only calculate the skyline after you know all the buildings.
- I'm not sure how it works in XP (I use Linux), but I think <CTRL>-Z followed by <ENTER> should pass an eof to the program. Personally I prefer to write an input file and pipe it to the program. But with Pascal be carefull with extra blank lines within and at the end of the input.

I have not looked deep into your program, but I think you should rethink and restart from scratch. It is way too complicated (my program is only 17 lines of Pascal). There are only 9999 possible values for the coordinate, so the height of the skyline can be easily stored in an array and adjusted for all buildings.

Endless
New poster
Posts: 1
Joined: Thu Sep 08, 2005 3:29 pm

105 WA? Why?

Post by Endless » Thu Sep 08, 2005 3:35 pm

Hi.

Which is the right output to this input:

Code: Select all

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
28 10 39
39 20 39
39 20 39
40 10 50
100 2 101
101 2 300
300 2 500
500 1 520
510 1 540
541 5 542
542 4 542
550 4 560
My output:

Code: Select all

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Location: SUST, BANGLADESH
Contact:

Post by roni » Sat Sep 17, 2005 1:06 pm

Out of AC code:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0
roni(SUST)

moja
New poster
Posts: 1
Joined: Wed Sep 28, 2005 3:41 pm

105 - The Skyline Problem

Post by moja » Wed Sep 28, 2005 4:02 pm

Hello, I don't know in what condition my code will get WA
Could everyone give me some test cases?
Thank you very much!!

The following are test data which I passed.

Code: Select all

input:
0 11 5

output:
0 11 5 0

Code: Select all

input:
3 2 4 
3 1 7 
5 2 6 

output:
3 2 4 1 5 2 6 1 7 0

Code: Select all

input:
1 11 5 
2 6 7 
3 13 9 
12 7 16 
14 3 25 
19 18 22 
23 13 29 
24 4 28 
28 10 39 
39 20 39 
39 20 39 
40 10 50 
100 2 101 
101 2 300 
300 2 500 
500 1 520 
510 1 540 
541 5 542 
542 4 542 
550 4 560

output:
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 20 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Code: Select all

input:
-5 5 1 
1 6 2 
1 2 7 
3 12 10 
4 3 5 
7 5 20 
8 15 12 
11 12 13 
16 14 19 
21 2 22 
23 1 30 
26 10 28 
26 12 27 
32 5 36 
34 3 38 
34 3 40 
37 2 42 
38 2 44 
45 1 46 

output:
-5 5 1 6 2 2 3 12 8 15 12 12 13 5 16 14 19 5 20 0 21 2 22 0 23 1 26 12 27 10 28 1 30 0 32 5 36 3 40 2 44 0 45 1 46 0
The following is my code.

Code: Select all

//* Q105 The Skyline Problem */ 
#include <stdio.h> 

typedef struct _NODE_T
{
    int                h; /* height */
    int                r; /* right */
    struct _NODE_T*    next;
}NODE_T;

NODE_T*    pt_head      = {0};
NODE_T*    pt_tail      = {0};
NODE_T*    pt_free_node = {0};
int        left         = -1;

NODE_T* mymalloc(void)
{
    NODE_T*    pt_node;

    if(pt_free_node != NULL) {
        pt_node      = pt_free_node;
        pt_free_node = pt_free_node->next;
    }
    else {
        pt_node = (NODE_T*)malloc(sizeof(NODE_T));
    }

    return pt_node;
}

void myfree(NODE_T* pt_node)
{
    if(pt_free_node) {
        pt_node->next = pt_free_node;
        pt_free_node  = pt_node;
    }
    else {
        pt_free_node  = pt_node;
        pt_node->next = NULL;
    }
}

/* reduce duplicate item */
void reduce_result(void)
{
    NODE_T*    pt_node;
    NODE_T*    pt_node2;

    for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
        if(pt_node->next) {
            if(pt_node->r == pt_node->next->r) {
                if(pt_node->h < pt_node->next->h) {
                    pt_node->h = pt_node->next->h;
                }
                pt_node->next = pt_node->next->next;
            }
        }
    }
}

void calculate(int l, int h, int r) 
{
    NODE_T*    pt_node;
    NODE_T*    pt_node2;
    NODE_T*    pt_node3;

    if(pt_head == NULL) {
        pt_node       = mymalloc();
        pt_node->h    = h;
        pt_node->r    = r;
        pt_node->next = NULL;

        pt_head       = pt_node;
        pt_tail       = pt_node;
        return;
    }

    /* check if left bigger than rightest node */
    if(l > pt_tail->r) {
        pt_node        = mymalloc();
        pt_node->h     = 0;
        pt_node->r     = l;

        pt_node2       = mymalloc();
        pt_node2->h    = h;
        pt_node2->r    = r;

        pt_node->next  = pt_node2;
        pt_node2->next = NULL;

        pt_tail->next  = pt_node;
        pt_tail        = pt_node2;

        return;
    }

    for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
        if(l <= pt_node->r) {
            if(h == pt_node->h) {
                if(r <= pt_node->r) { /* new input is under pt_node */
                    return;
                }
                else {
                    l = pt_node->r;
                    continue;
                }
            }
            else if(h < pt_node->h) {
                if(r <= pt_node->r) {
                    return;
                }
                else {
                    l = pt_node->r;
                    continue;
                }
            }
            else {
                if(r == pt_node->r) {
                    pt_node2       = mymalloc();
                    pt_node2->h    = h;
                    pt_node2->r    = r;

                    pt_node2->next = pt_node->next;

                    pt_node->r     = l;
                    pt_node->next  = pt_node2;

                    if(pt_node == pt_tail) {
                        pt_tail = pt_node2;
                    }
                    return;
                }
                else if(r < pt_node->r) {
                    pt_node2    = mymalloc();
                    pt_node2->h = h;
                    pt_node2->r = r;

                    pt_node3    = mymalloc();
                    pt_node3->h = pt_node->h;
                    pt_node3->r = pt_node->r;

                    pt_node->r  = l;

                    pt_node2->next = pt_node3;
                    pt_node3->next = pt_node->next;
                    pt_node->next  = pt_node2;

                    if(pt_node == pt_tail) {
                        pt_tail = pt_node3;
                    }
                    return;
                }
                else {
                    pt_node2      = mymalloc();
                    pt_node2->h   = h;
                    pt_node2->r   = r;

                    pt_node->r    = l;
                    pt_node3      = pt_node->next;

                    pt_node->next = pt_node2;

                    while(pt_node3 != NULL) {
                        if(pt_node3->r > r) {
                            break;
                        }

                        pt_node2->next = pt_node3->next;
                        myfree(pt_node3);
                        pt_node3 = pt_node2->next;
                    }

                    if(pt_node3 == NULL) {
                        pt_tail = pt_node2;
                    }
                    else {
                        pt_node2->next = pt_node3;
                    }

                    return;
                }
            }
        }
    }

    if(h == pt_tail->h) {
        pt_tail->r = r;
        return;
    }

    pt_node       = mymalloc();
    pt_node->h    = h;
    pt_node->r    = r;
    pt_node->next = NULL;

    pt_tail->next = pt_node;
    pt_tail       = pt_node;

    return;
}

void print_result(void)
{
    NODE_T*    pt_node;

    printf("%d", left);
    for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
        printf(" %d %d", pt_node->h, pt_node->r);
    }

    printf(" 0\n");
}

int main(void) 
{ 
    int l, h, r;

    while (scanf("%d %d %d", &l, &h, &r)==3) 
    { 
        if(left == -1) {
            left = l;
        }
        calculate(l, h, r);
    } 

    reduce_result();
    print_result();

    return 0;
}

wrcstar
New poster
Posts: 2
Joined: Mon Oct 03, 2005 7:09 pm

105 why WA?

Post by wrcstar » Mon Oct 03, 2005 7:13 pm

This is my code. Why WA?

program Task105;

var skyline : array [0..10000] of integer;
i,l,h,r : integer;
blank : integer;
begin
for i:=0 to 10000 do skyline:=0;
while EoF(input) do begin
ReadLn(l,h,r);
for i:= l to r-1 do
if(skyline < h) then skyline:=h;
end;


blank:=0;
for i:=1 to 10000 do
if(skyline[i-1] <> skyline) then begin
if(blank = 0) then begin
Write(i,' ',skyline);
blank:=blank+1;
end
else Write(' ',i,' ',skyline);
end;


end.

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm

Post by BJM » Sat Oct 08, 2005 8:05 pm

For your third case the answer is:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Not

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 20 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Also, you don't need to worry about negatives since the problem states that all coordinates are positive integers <10,000.

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Post by Ming Han » Thu Nov 17, 2005 11:21 am

Code: Select all

#include <stdio.h>

int main(){
    
    int dat[5000][4] = {0};
    int c = 0;
    int pos[20010] = {0};
    int i;
    
    while(scanf("%d %d %d",&dat[c][0],&dat[c][1],&dat[c][2])==3){
        for (i=dat[c][0];i<=dat[c][2];i++){
            if (dat[c][1]>pos[i]) pos[i] = dat[c][1];
        }
        c++;
    }
    int last = 0;
    
    
    for (i=dat[0][0];i<=dat[c-1][2]+2;i++){
        if (pos[i]>last){
            printf("%d %d ",i,pos[i]);
            last = pos[i];
        }else if (pos[i]<last){
            if (i==dat[c-1][2]+2) printf("%d %d",(i-1),pos[i]);
            else printf("%d %d ",(i-1),pos[i]); 
            last = pos[i];
        }
    }
    return 0;
}
this is weird! I keep getting PE!
:: HanWorks ::

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:

Post by nukeu666 » Tue Dec 06, 2005 1:50 pm

i need help...dunno why im getting WA

Code: Select all

#include<stdio.h>
int main()
{
  int ht,h[10000],right=0,a,t=0,l[10000],r[10000];
  for(a=0;a<10000;a++)
    h[a]=0;
  while(scanf("%d %d %d",&l[t],&ht,&r[t])==3)
    {
      if(l[t]>right)
        right=l[t];
      if(r[t]>right)
        right=r[t];
      for(a=l[t];a<r[t];a++)
        if(h[a]<ht)
          h[a]=ht;
      t++;
    }
  ht=0;
  for(a=0;a<=right;a++)
    {
      if(h[a]!=h[a+1]&&ht==1)
        printf(" %d %d",a+1,h[a+1]);
      if(h[a]!=h[a+1]&&ht==0)
        {ht=1;printf("%d %d",a+1,h[a+1]);}
    }
}
its working fine for all inputs in this thread
google

gladiatorcn
New poster
Posts: 8
Joined: Wed Mar 30, 2005 9:46 am

105 Presentation error

Post by gladiatorcn » Wed Dec 14, 2005 11:15 am

What is a presentation error?

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
int space[10000], ans[10000];
ostream_iterator<int> outS(cout," ");

fill(space,space+10000,0);

int i,j,h;
while(cin>>i>>h>>j)
{
for(int p=i;p<j;p++)
{
if(h>space[p]) space[p]=h;
}
}

//output
int last=0;
int end=0;
for(int p=1;p<10000;p++)
{
if(space[p]!=last)
{
ans[end++]=p;
ans[end++]=space[p];
last=space[p];
}
}
copy(ans,ans+end,outS);
cout<<endl;

return 0;
}

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Wed Dec 14, 2005 11:44 am

Looks like you have a space after the last 0.

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

105... Help!

Post by f.eliel » Fri Feb 17, 2006 2:33 am

I know these way to read the multiple inputs:

Code: Select all

while (scanf("%d %d %d", &li, &hi, &ri)==3) {
But i don't know how to make it stop reading.
I looked at a lot of topics but i couldn't find it.
Can anyone help me?
Thanks.

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

Post by f.eliel » Fri Feb 17, 2006 5:27 am

I realized tha i was not doing anything wrong, i just didn't the problem...
But now i having trouble in the output. I don't know how to get the space after the last zero of...

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Fri Feb 17, 2006 10:01 am

I don't understand what you mean. But I know there is no space after the last zero.
I stay home. Don't call me out.

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

105 WA

Post by f.eliel » Mon Feb 27, 2006 5:12 pm

I don't understand why i got WA...
Last edited by f.eliel on Tue Feb 28, 2006 9:34 pm, edited 1 time in total.

Post Reply

Return to “Volume 1 (100-199)”