105 - The Skyline Problem

[subzero]

hi, how are you... for soyoja, there are NO negative numbers in the problem 105

[sakhassan]

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

Thanks in advance

[Jan]

This is a problem indeed. Post this problem in the Bugs and suggestions forum.

[luishhh]

Print "\n" and you'll get AC

[andysoft]

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

[rio]

If the maximum x coordinate is m, and the building number is n, your algorithm takes O(mn), which is too slow.

----
Rio

[andysoft]

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?

[rafastv]

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]

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

please solve my problem...

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* link;
	Node(int point, int data) {
		
		this->point = point;
		this->data = data;
		this->link = NULL;
	}

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

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
		list = add;
		Node* lastnode = new Node(end, 0);
		list->link = lastnode;
		return list;
	}

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

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

	}
	// loc is equal to start or greater.
	if(loc == NULL) {		// Last
		prev->link = add;
		Node* lastnode = new Node(end, 0);
		add->link = lastnode;
		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
			add->link = loc;
			prev->link = add;

			//Change loc
//				loc = add;
			bprev = prev;
			prev = add;
		}
	}
	
	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;
			loc = loc->link;
		}
		else if(loc->data >= height) {// current height is greater than new height
			
			bprev = prev;
			prev = loc;
			loc = loc->link;
		}
	}		
	
	// End is null
	if(loc == NULL) {
		Node* lastnode = new Node(end, 0);
		prev->link = lastnode;
		return list;
	}
	// end point is less than current end
	if (loc->point > end) {

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

	}		
	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 link;
	Node(int point, int data) {
		this.point = point;
		this.data = data;
		this.link = null;
	}
	public String toString() {
		Node temp = link;
		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; 
			temp = temp.link;
		}
		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
			list = add;
			Node lastnode = new Node(end, 0);
			list.link = lastnode;
			return list;
		}

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

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

		}
		// loc is equal to start or greater.
		if(loc == null) {		// Last
			prev.link = add;
			Node lastnode = new Node(end, 0);
			add.link = lastnode;
			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
				add.link = loc;
				prev.link = add;

				//Change loc
//				loc = add;
				bprev = prev;
				prev = add;
			}
		}
		
		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;
				loc = loc.link;
			}
			else if(loc.data >= height) {// current height is greater than new height
				
				bprev = prev;
				prev = loc;
				loc = loc.link;
			}
		}		
		
		// End is null
		if(loc == null) {
			Node lastnode = new Node(end, 0);
			prev.link = lastnode;
			return list;
		}
		// end point is less than current end
		if (loc.point > end) {

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

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

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
and header <iostream.h> to <iostream>
I've had succes

Good luck

[nahid]

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]

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]

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]

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.
Thanks in advance.

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;
	/* basement set shadow */
	for(i=0;i<MAX;i++)
		map[0][i]=1;

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

	/* shadowing */
	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;
}

Please help me!!!

[ashwin.lele]

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]);

}


}