## 105 - The Skyline Problem

Moderator: Board moderators

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am
hi, how are you... for soyoja, there are NO negative numbers in the problem 105
There is no knowledge that is no power.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### a clarification about 105 skyline problem

for sample input in the problem is I/o is as follows:

Sample 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

Sample Output:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

and my output for the same input sample is :

1 11 3 13 9 0 12 7 16 3 19 18 23 13 29 0

and i got AC How can this be possible My head has stopped working !!!!!!!!! can anybuddy pls explain

Time that gone is gone forever ...

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
This is a problem indeed. Post this problem in the Bugs and suggestions forum.
Ami ekhono shopno dekhi...
HomePage

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain
Print "\n" and you'll get AC
"From lost to the river" --> Spanish quote

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Hi people. Can you tell me is it possible to get TLE here?? I got!
Please tell me what's wrong with my code, that makes it TLE:

Code: Select all

``````#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[]) {

int i = 0,l[5005],r[5005],h[5005],n;
while (cin >> l[i] >> h[i] >> r[i])
i++;
n = --i;

float x=-0.5;
int ch=0;

while (x<=r[n]+0.5) {
x += 1.0;
int chmax = ch;
for (i=0;i<=n;i++) {
if ((r[i]==floor(x-0.5))&&(h[i]==ch)) {
chmax = 0;
break;
}
}
for (i=0;i<=n;i++) {
if ((l[i] <= floor (x-0.5))&&(r[i] > floor(x-0.5))&&(h[i]>chmax)) {
chmax = h[i];
}
}

if (chmax != ch) {
cout << floor(x-0.5) << " " << chmax << " ";
ch= chmax;
}
}

return EXIT_SUCCESS;
}

``````
Now I lay me down to sleep...
my profile

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
If the maximum x coordinate is m, and the building number is n, your algorithm takes O(mn), which is too slow.

----
Rio

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
thanx, rio. BTW, don't you know, is there any way to optimize such an algorithm or I have to think about a new one?
Now I lay me down to sleep...
my profile

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

### I keep getting WA..

It works for all test cases here...I even tested for L>R and ignored when L=R. The Code works fine...it organizes the builings by its right and left coordenates..and after it, try to draw a line through its height(it saves the heights at a stack of ordered heights) ...

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
typedef struct predio{
long int x;
long int y;
struct predio *st;
struct predio *d;
struct predio *e;
}Tpredio;

Tpredio *criaPonto(long int x, long int y, Tpredio *st){
Tpredio *p;
p=(Tpredio*)malloc(sizeof(Tpredio));
(*p).x=x;
(*p).y=y;
(*p).st=st;
(*p).d=NULL;
(*p).e=NULL;
return p;
}
Tpredio* inserePonto(Tpredio *novo,Tpredio *ant, Tpredio *prim){
Tpredio *aux,*aux2;
if ((*novo).x>(*ant).x){
aux2=(*ant).d;
(*novo).d=aux2;
if (aux2!=NULL)
(*aux2).e=novo;
(*novo).e=ant;
(*ant).d=novo;
} else {
aux=ant;
if ((*novo).x==(*ant).x){
if (((*novo).y)>((*ant).y)){
while ((((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)) && ((*novo).y>(*((*aux).e)).y)){
aux=(*aux).e;
}
aux2=(*aux).e;
(*novo).e=aux2;
if (aux2!=NULL)
(*aux2).d=novo;
else
prim=novo;
(*novo).d=aux;
(*aux).e=novo;
}
else {
aux2=(*ant).d;
(*novo).d=aux2;
if (aux2!=NULL)
(*aux2).e=novo;
(*novo).e=ant;
(*ant).d=novo;
}
} else {
while (((*aux).e!=NULL) && ((*novo).x<(*((*aux).e)).x)){
aux=(*aux).e;
}

if (((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)){
if ((*novo).y>(*((*aux).e)).y) {
while ((((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)) && ((*novo).y>(*((*aux).e)).y)){
aux=(*aux).e;
}
}
}
aux2=(*aux).e;
(*novo).e=aux2;
if (aux2!=NULL)
(*aux2).d=novo;
else
prim=novo;
(*novo).d=aux;
(*aux).e=novo;
}
}
return prim;
}

Tpredio *defineAnt(Tpredio *novo,Tpredio *ant){
if ((*novo).x>(*ant).x)
return novo;
if (((*novo).x==(*ant).x) && ((*novo).y<=(*ant).y))
return novo;
else
return ant;
}

Tpredio *insereLista(Tpredio *prim, Tpredio *p){
Tpredio *l,*aux;
l=NULL; aux=NULL;
if (prim==NULL){
l=criaPonto((*p).x,(*p).y,(*p).st);
return l;
} else {
l=prim;
if ((l!=NULL) && ((*p).y<(*l).y)){
while (((*l).d!=NULL) && ((*p).y)<(*((*l).d)).y){
l=(*l).d;
}
aux=criaPonto((*p).x,(*p).y,(*p).st);
(*aux).d=(*l).d;
(*l).d=aux;
return prim;
} else {
aux=criaPonto((*p).x,(*p).y,(*p).st);
(*aux).d=prim;
return aux;
}

}
}
Tpredio *removeLista(Tpredio *prim, Tpredio *p){
Tpredio *l,*aux;
l=prim;
if (l!=NULL){
while (((*l).st!=p) && ((*l).d!=NULL)) {
aux=l;
l=(*l).d;
}
if (((*l).st)==p){
if (l==prim){
aux=(*prim).d;
(*prim).d=NULL;
free(prim);
prim=aux;
} else {
(*aux).d=(*l).d;
(*l).d=NULL;
free(l);
}
}
}
return prim;
}
int main(int argc, char** argv){
long int x1,x2,x3,y,h_max,h_ant,conta,x_prox;
Tpredio *ant,*novo,*prim,*aux,*plista;
conta=0;
novo=NULL;prim=NULL;
while (scanf("%ld %ld %ld",&x1,&y,&x2)!=EOF){
if (x1>x2){
x3=x1;
x1=x2;
x2=x3;
}
if ((x1!=x2) && (y>0)){
if (conta==0){

novo=criaPonto(x1,y,NULL);
ant=novo;
aux=novo;
novo=criaPonto(x2,y,NULL);
prim=aux;
prim=inserePonto(novo,ant,prim);
(*prim).st=novo;
ant=defineAnt(novo,ant);
conta++;
} else {
novo=criaPonto(x1,y,NULL);
prim=inserePonto(novo,ant,prim);
aux=novo;
ant=defineAnt(novo,ant);
novo=criaPonto(x2,y,NULL);
(*aux).st=novo;
prim=inserePonto(novo,ant,prim);
ant=defineAnt(novo,ant);
}}
}
aux=prim;
h_ant=0;
h_max=0;
plista=NULL;
while ((*aux).d!=NULL){
x_prox=(*(*aux).d).x;

if (plista!=NULL)
h_ant=(*plista).y;
else
h_ant=0;

if ((*aux).st==NULL)
plista=removeLista(plista,aux);
else
plista=insereLista(plista,aux);

while (((*aux).d!=NULL)&&(x_prox==(*aux).x)){
aux=(*aux).d;
if ((*aux).st==NULL)
plista=removeLista(plista,aux);
else
plista=insereLista(plista,aux);
if ((*aux).d!=NULL)
x_prox=(*(*aux).d).x;
}

if (plista!=NULL)
h_max=(*plista).y;
else
h_max=0;

if (h_max!=h_ant)
printf("%ld %ld ",(*aux).x,h_max);

if ((*aux).d!=NULL)
aux=(*aux).d;
}
printf("%ld 0\n",(*aux).x);
while ((*aux).e!=NULL){
novo=aux;
aux=(*aux).e;
(*novo).e=NULL;
(*novo).d=NULL;
free(novo);
}
(*aux).e=NULL;
(*aux).d=NULL;
free(aux);
return 0;
}
``````

What am I missing here? If a building such as 1 1 1 exists, what should I print? 1 1 1 0? or nothing? thanks

kantaki
New poster
Posts: 10
Joined: Tue May 29, 2007 6:18 pm

### 105 Compile error

I got compile error with cpp.
and i got runtime error with java.

two codes are same algorithm...

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

class Node {
public:
int point;
int data;
Node(int point, int data) {

this->point = point;
this->data = data;
}

void print() {
printf("%d %d", &point, &data);
while(loc != NULL) {
printf(" %d %d", loc->point, loc->data);
}
}
};

Node* addNode(Node* list, int start, int height, int end) {
Node *add = new Node(start, height);
Node *loc = list;
Node *prev = NULL;
Node *bprev = NULL;

if(list == NULL) {	// Add no element
Node* lastnode = new Node(end, 0);
return list;
}

else if(list->point > start) {	// Add first node
Node* lastnode = new Node(start, height);
}

while(loc != NULL && loc->point < start) {
bprev = prev;
prev = loc;
}
if(bprev!=NULL) {

}
// loc is equal to start or greater.
if(loc == NULL) {		// Last
Node* lastnode = new Node(end, 0);
return list;
}
else if (loc->point == start) {	// loc = start
if(loc->data < height) {		// loc is less than height
loc->data = height;
}
}
else {	// temp != start
if(prev->data < height) {	// height is greater than current height

//Change loc
bprev = prev;
}
}

while(loc != NULL && loc->point <= end) {	// Change mid of start and end
if(loc->data < height) {	// current height is less than new height
loc->data = height;

bprev = prev;
prev = loc;
}
else if(loc->data >= height) {// current height is greater than new height

bprev = prev;
prev = loc;
}
}

// End is null
if(loc == NULL) {
Node* lastnode = new Node(end, 0);
return list;
}
// end point is less than current end
if (loc->point > end) {

Node* lnode = new Node(end, bprev->data);

}
return list;

}

void main()
{
Node* data = NULL;
int start, height, end;
while(scanf("%d %d %d", &start, &height, &end)==3) {
data = addNode(data, start, height, end);
}
data->print();
}
``````

Code: Select all

``````import java.io.*;
import java.util.*;

class Node {
int point;
int data;
Node(int point, int data) {
this.point = point;
this.data = data;
}
public String toString() {
String ret;
ret = Integer.toString(point) + " " + Integer.toString(data);

int bdata = data;

while(temp!=null) {
if(bdata != temp.data)
ret += " " + Integer.toString(temp.point) + " " + Integer.toString(temp.data);
bdata = temp.data;
}
return ret;
}
}

class Sky {
public static Node addNode(Node list, int start, int height, int end) {
Node add = new Node(start, height);
Node loc = list;
Node prev = null;
Node bprev = null;

if(list == null) {	// Add no element
Node lastnode = new Node(end, 0);
return list;
}

else if(list.point > start) {	// Add first node
Node lastnode = new Node(start, height);
}

while(loc != null && loc.point < start) {
bprev = prev;
prev = loc;
}
if(bprev!=null) {

}
// loc is equal to start or greater.
if(loc == null) {		// Last
Node lastnode = new Node(end, 0);
return list;
}
else if (loc.point == start) {	// loc = start
if(loc.data < height) {		// loc is less than height
loc.data = height;
}
}
else {	// temp != start
if(prev.data < height) {	// height is greater than current height

//Change loc
bprev = prev;
}
}

while(loc != null && loc.point <= end) {	// Change mid of start and end
if(loc.data < height) {	// current height is less than new height
loc.data = height;

bprev = prev;
prev = loc;
}
else if(loc.data >= height) {// current height is greater than new height

bprev = prev;
prev = loc;
}
}

// End is null
if(loc == null) {
Node lastnode = new Node(end, 0);
return list;
}
// end point is less than current end
if (loc.point > end) {

Node lnode = new Node(end, bprev.data);

}
return list;

}

public static void main(String[] args) {

Node data = null;

try {
while(true) {
Scanner conIn = new Scanner(System.in);
int start, height, end;
start = conIn.nextInt();
height= conIn.nextInt();
end = conIn.nextInt();

data = addNode(data, start, height, end);
conIn = new Scanner(System.in);
}
}
catch (Exception ee) {
System.out.println(data);
}
}

}
``````

marc1s
New poster
Posts: 1
Joined: Tue Dec 18, 2007 4:40 pm
Location: Girona
When I compile your cpp program I got the following error

Code: Select all

``````c++ pro.cpp -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
In file included from /usr/include/c++/4.1.3/backward/iostream.h:31,
from pro.cpp:3:
/usr/include/c++/4.1.3/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.
pro.cpp:114: error: ::main must return int
``````
Changing in function main: void to int

Good luck

nahid
New poster
Posts: 18
Joined: Wed Oct 04, 2006 8:59 pm
Contact:

### input limit of 105

105 problem description clearly told about positve integers. and my code replys right outputs due to the possible inputs which i got on net but not for negatve co-ordinates. what i should do?

shiggy
New poster
Posts: 3
Joined: Sat Jan 19, 2008 5:28 am
Like some people said in other threads, I my AC programs gives
1 11 3 13 9 0 12 17 16 3 19 18 22 3 23 29 0
for the test case stated in the problem.

I solved it by printing the x,y coordinates of the corners in the generated image, which isn't what is described by the problem but it gives an accepted solution.

phleet
New poster
Posts: 1
Joined: Thu Feb 07, 2008 4:33 am
I've made multiple versions of this, even trying to accomodate for the weird AC that shiggy got, but all get WA. This is the version that should accomodate for everything (gives the same output for the test input provided as the problem lists). I am completely stuck and can't find testcases that give this an answer which doesn't make sense.

Code: Select all

``````#include <stdio.h>
int top[20001];
int main() {
int a,a1,b,c,maxc=0;
for (int i = 0; i < 20000; i ++) {
top[i] = 0;
}

scanf("%d %d %d",&a1,&b,&c);
for (int i = 2*a1; i <= 2*c; i++) {
if (b > top[i]) top[i] = b;
}
if (c > maxc) maxc = c;

while (scanf("%d %d %d",&a,&b,&c) != EOF) {
if (c <= a) continue;
for (int i = 2*a; i <= 2*c; i++) {
if (b > top[i]) top[i] = b;
}
if (c > maxc) maxc = c;
}

printf("%d %d",a1,top[2*a1]);
for (int i = 2*a1+2; i <= 2*maxc; i+=2) {
if (top[i] > top[i+1]) {
printf(" %d %d",i/2,top[i+1]);
} else if (top[i-1] < top[i]) {
printf(" %d %d",i/2,top[i]);
}
}

return 0;
}
``````
Can anyone see anything wrong with the logic there?

sawang
New poster
Posts: 1
Joined: Wed Feb 27, 2008 6:29 pm

### 105 RE Need help!

I use a 2-D array as a map to record the building block area
then I check the corner coordinate to gain the vector list

I got the same output as the problem statement.

and I checked the array boundary to see if there are any potential illegal reference, however , I found none.

Can anyone help me?
I would really really appreciate that.

The following is my code

Code: Select all

``````#include <stdio.h>
#define MAX 10002

int main(void)
{
int map[MAX][MAX];
int left,height,right;
int limitL,limitH,limitR;
int vector[MAX*2][2];
int vec_count=0;

int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[i][j]=0;
for(i=0;i<MAX;i++)
map[0][i]=1;

limitL = MAX-1;
limitR = 1;
limitH = 1;

while( scanf("%d %d %d",&left,&height,&right)==3 )
{
if( left < limitL )
limitL = left;
if( right > limitR )
limitR = right;
if( height > limitH )
limitH = height;

for(i=1;i<=height;i++)
for(j=left;j<right;j++)
{
map[i][j]=1;
}
}

/* printf("%d %d %d\n",limitL,limitH,limitR); */
/* record coordinate into vector array */
for( j=limitL ; j<=limitR ; j++ )
{
i=0;
while( map[i][j] == 1 )
{
i++;
}
vector[vec_count][0]=j;
vector[vec_count][1]=i-1;
vec_count++;
}

/* print vector */
int row = vector[0][1];
printf("%d %d",vector[0][0],vector[0][1]);
for(i=0;i<vec_count;i++)
{
if( vector[i][1] == row )
continue;
row = vector[i][1];
printf(" %d %d",vector[i][0],vector[i][1]);
}
printf("\n");

return 0;
}
``````

ashwin.lele
New poster
Posts: 1
Joined: Fri Mar 14, 2008 2:03 pm

### 105 Compilation Error

This is my first problem which i think i have solved

Correction Now This gives Runtime Error
I don't have linux so i can't really test this
Also this works in TurboC

#include<stdio.h>

struct dat
{
int x1;
int h;
int x2;
};
void main()
{
struct dat pos[100];
int arr[500];
int i=0,j,k=1,x;
int sbx1,sbx2,sbh,psbh=0;

while(scanf("%d %d %d",&pos.x1,&pos.h,&pos.x2)==3)
i++;

for(x=0;x<100;x++)
arr[x]=0;

arr[0]=sbx1=pos[0].x1;
arr[1]=sbh=pos[0].h;
arr[2]=sbx2=pos[0].x2;
k=3;
for(j=1;j<i;j++)
{
if(pos[j].x1<sbx2)
{
if(pos[j].x1<sbx1)
{
if(pos[j].x2<sbx2)
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=sbh;
arr[k+1]=sbx2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=pos[j].h;
arr[k+1]=sbx2;
}
psbh=pos[j].h;
sbx1=pos[j].x2;

}

}
else
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx2=pos[j].x2;
}
k=k-2;
sbh=pos[j].h;

}

}

}
else
{
if(pos[j].h>sbh)
{
if(pos[j].x2<sbx2)
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
arr[k+2]=sbh;
arr[k+3]=sbx2;
sbx1=pos[j].x2;
psbh=pos[j].h;
k=k+2;
}
else
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
}
else
{
if(pos[j].x2>sbx2)
{
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
sbx1=sbx2;
sbx2=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
}
else k=k-2;
}

}

}
else
{

arr[k]=0;
psbh=0;
arr[k+1]=pos[j].x1;
arr[k+2]=pos[j].h;
arr[k+3]=pos[j].x2;
sbx1=pos[j].x1 ;
sbx2=pos[j].x2;
sbh=pos[j].h;
k=k+2;
}

k=k+2;
}
printf("\nOUTPUT \n");
for(x=0;x<=k;x++)
{
printf(" %d ",arr[x]);

}

}