## 105 - The Skyline Problem

Moderator: Board moderators

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

### 105 P.E.

Hi everyone !

I got Accepted P.E.
but i don't understand what does it mean "presentation error"
could you tell me the difference between AC and AC P.E. ??!!
and what is it for? shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
PE means prsentation error.

The reason it occurs is due to misplaced/overplaced spaces. That is spaces where there shouldn't be any. Although in 24 hr. this is not a problem, but in contest the submission will be rejected and you will receive a penalty.

Ans for problem 105, I think you must have placed an extra space at the end of the outputline.

wbr
New poster
Posts: 2
Joined: Sat Mar 05, 2005 9:33 pm

### 105 - WA - java

i really can't find out why WA...
can anybody please give me some clues or maybe some sample input?
i would really appreciate it!

import java.io.*;
import java.util.*;
class Main{
{
byte[] line = new byte;
int len = 0, ch = -1;
try {
while (true) {
if ((ch < 0) || (ch == '\n'))break;
if (len >= line.length) {
byte[] line1 = new byte[line.length*2];
System.arraycopy(line,0,line1,0,line.length);
line = line1;
}
if (ch != '\r') line[len++] = (byte)ch;
}
}
catch (IOException ee) { return null; }
if ((ch < 0) && (len == 0)) return null;
return new String(line,0,len);
}
public static void main (String[] args) throws Exception
{
int[] koordinate = new int;
while(true){
if(line.countTokens() == 0) break;
int l_i = Integer.parseInt(line.nextToken());
int h_i = Integer.parseInt(line.nextToken());
int r_i = Integer.parseInt(line.nextToken());
for(int i = l_i; i < r_i; i++)
if(koordinate < h_i) koordinate = h_i;
}
String output = "";
for(int j = 0; j < 9999; j++){
if(koordinate[j] != koordinate[j+1])
output = output + (j + 1) + " " + koordinate[j+1] + " ";
}
System.out.println(output.substring(0, output.length()-1));
}
}

wbr
New poster
Posts: 2
Joined: Sat Mar 05, 2005 9:33 pm

### 105 - WA - java

is it possible that Ri < Li.
and if it is possible, what should output look like for input
3 5 1?

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

### input of 105

is it possible to have building's start or ending coordinates coincide (Li, Ri)?
I get WA and this may be a cause.
What other "special" test cases should I watch out for?
Understanding a problem in a natural way will lead to a natural solution

New poster
Posts: 7
Joined: Fri Jan 28, 2005 10:01 pm
Location: Denmark
Contact:
Hi.

Code: Select all

``````if (w_ptr == &head)
{
insert_to_list(w_ptr, &in_node);
else
insert_to_list((w_ptr->back), &in_node);
break;
}
``````
why not just:

Code: Select all

``````if (w_ptr == &head)
``````

lazenca
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

### :-)

Yes, you're right! Your idea make my code more shortly...
I was not far-sighted enough to think of that... Thanks for your concern to this topic
I see the red...
I saw the rain..

Feng
New poster
Posts: 3
Joined: Sat May 28, 2005 8:11 am

### 105 Runtime error

I use sweepline algorithm to solve this question. It yields right result on sample test data, but got "Invalid Memory Reference" after submitted. Could anybody help me to find out what's wrong or provide me some longer test set? Thanks in advance. #include <iostream>
#include <vector>
#include <algorithm>

#define DEBUG 0

using namespace std;

typedef struct {
int x1; // left edge coordinate
int x2; // right edge coordinate
int height; // height
} Block;

typedef struct {
int x; // coordinate
int height; // height
} SLVec; // Sky Line Vector

template < class T > ostream & // template to print any vector
operator << (ostream & os, vector < T > v) {
for (int i = 0; i < v.size (); i++)
os << " " << v;
os << "\n";
return os;
}

vector<Block> blocks;

bool comparator(int r1, int r2) {
return blocks[r1].x2 <= blocks[r2].x2;
}

main()
{
int x1, x2, height;
while(cin >> x1 >> height >> x2) {
Block block;
block.x1 = x1;
block.x2 = x2;
block.height = height;
blocks.push_back(block);
}
// ordering the right edges
vector<int> redges;
for(int i=0; i<blocks.size(); i++) redges.push_back(i);
sort(redges.begin(), redges.end(), comparator);

// skylining
vector<SLVec> skyline;
vector<int> heights;
heights.push_back(0);
make_heap(heights.begin(), heights.end());
int l=0, r=0; // left/right edge index
int ri = 0;
while(l < blocks.size() || ri < blocks.size()) {
if(blocks[l].x1 <= blocks[r].x2) { // left edge processing
int h = blocks[l].height;
if(h > heights) {
SLVec v;
v.x = blocks[l].x1; v.height = h;
if(DEBUG) cout << "left edge: " << v.x << " " << v.height << endl;
skyline.push_back(v);
}
heights.push_back(h);
push_heap(heights.begin(), heights.end());
l++;
} else { // right edge processing
int h = blocks[r].height;
if(h == heights) { // the highest block closes
pop_heap(heights.begin(), heights.end());
heights.erase(heights.end()-1);
if(heights != h) { // may have blocks with same height
SLVec v;
v.x = blocks[r].x2; v.height = heights;
skyline.push_back(v);
if(DEBUG) cout << "right edge: " << v.x << " " << v.height << endl;
}
} else { // not the highest block
vector<int>::iterator p;
p = find(heights.begin(), heights.end(), h);
if(p != heights.end()) heights.erase(p);
//make_heap(heights.begin(), heights.end());
}
ri++;
if(ri < redges.size())
r = redges[ri];
}
}
// print the result
for(int i=0; i<skyline.size()-1; i++) {
cout << skyline.x << " " << skyline.height << " ";
}
cout << skyline.back().x << " " << skyline.back().height << endl;
}

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
Hi Feng,Too much complex code.No need to use any algorithm for this simple problem.I've accepted the problem using an array of 10001, then scan the values and check the height.And at last print the values if the previous height is not equals the current height.

U can use my method to solve this simple problem.Best of LUCK Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### several notes

WBR,

This happens when you reach the EOF , at that
moment readLn() returns null and of course
Just check the first line of your while(true) cycle.
So it is quite logical that you get WA.

and got ACC using your code. Give me an email
if you still haven't fixed your code. I will send
you the fix.

One more thing.
There's something interesting about the sample
I/O for this problem.

For the 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``````

my ACC program outputs the following:

Code: Select all

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

after my small changes ) produces the output given
in the problem description which is different than my
output but both programs get ACC. Anyway. I won't
further dig into this.

And finally - I don't take into account cases such like L(i) > R(i).
Actually what my program does for such cases ( if any exist ) in the
input is that it skips those triples.

Hope this helps.

wangnoon
New poster
Posts: 7
Joined: Wed Jul 31, 2002 3:20 pm
Location: korea
Contact:

### # 105 ( RE )

I really can't find out why RE...

Does "RUNTIME ERROR(SIGSEGV)" mean what ?

What's wrong with my code? Here my code:

Code: Select all

``````/* @JUDGE_ID: 21640Yj 105 C "PS" */

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

int n ;
int m ;
int a[ 30000 ][ 3 ] ;
int x[ 30001 ] ;
int h[ 30000 ] ;

void input();
void process();
void output();

void main()
{
input();
process();
output();
}
void input()
{
int temp ;
int i , j;
temp = 0 ;
i = 0 ;
j = 0 ;
n=0;
m= 0 ;
while(scanf("%d %d %d\n",&a[n],&a[n],&a[n] ) )
{

x[m] = a[n] ;
m = m + 1 ;
x[m] = a[n] ;
m = m + 1 ;
n = n + 1  ;
}
for ( i = 0 ; i < m-1  ; i ++ )
for ( j = i+1 ; j < m ; j ++ )
if ( x[i] > x[j] )
{
temp = x[i];
x[i] = x[j] ;
x[j] = temp;
}
}
void process()
{
int i ;
int j ;
int st ,en;
i = 0 ;
j = 0 ;
st = 0 ;
en = 0 ;

for ( i = 0  ;i < n ; i ++ )
{
for ( j = 0 ; j < m ; j ++ )
if ( x[j] == a[i] )
{
st = j ;
break;
}
for ( j = m-1 ; j >= 0 ; j -- )
if ( x[j] == a[i] )
{
en = j ;
break;
}
st = st + 1 ;
for ( j = st ; j <= en ; j ++ )
if ( h[j] < a[i] )
h[j] = a[i] ;

}

}
void output()
{
int i ;
i = 0;
for ( i = 1 ; i <  m ;i  ++ )
{
if ( h[i] != h[i-1] )
printf("%d %d ",x[i-1],h[i] );
}
printf("%d %d\n",x[m-1],0);
}
``````
if you help, I will thank very much.
PLS help me wdg
New poster
Posts: 4
Joined: Tue Aug 16, 2005 3:19 pm

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

The input example didn't even give a eof symbol. How can I recognize the input is end in Pascal?
Last edited by wdg on Wed Aug 17, 2005 9:03 am, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
By using eof:

Code: Select all

``````...
some initialisation
...
while not eof do begin
...
some processing
...
end;
...
some more processing
etc.``````

wdg
New poster
Posts: 4
Joined: Tue Aug 16, 2005 3:19 pm
Thank you!

wdg
New poster
Posts: 4
Joined: Tue Aug 16, 2005 3:19 pm
Two more problems arise.(freepascal)
I used command line to give the input, but
1)the program gave a output when the input had not ended. Do I Need To Store All The Output And Do Not Display It Till The Input Is End?
and
2)I wanted to end the input by using ctrl-c or ctrl-z, but it occured a runtime error. How Can I End The Input Normally In Command Line?
My Platform is Win XP. My freepascal is go32v2 edition.