105 - The Skyline Problem

[jaracz]

Hi everyone !

I got Accepted P.E.
but i don't understand what does it mean "presentation error"
I have correct answers (before i had been gettin' WA)
could you tell me the difference between AC and AC P.E. ??!!
and what is it for?

[shamim]

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]

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{
public static String readLn ()
{
byte[] line = new byte[100];
int len = 0, ch = -1;
try {
while (true) {
ch = System.in.read();
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[10000];
while(true){
StringTokenizer line = new StringTokenizer(readLn().trim());
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]

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

[jakabjr]

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?

[jonaskoelker]

Hi.

I was thinking about this code fragment

Code: Select all

if (w_ptr == &head)
{
  if (head.next == &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)
  insert_to_list(head -> back, &in_node)

since (&head == head.next) == (&head == head.back);

[lazenca]

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

[Feng]

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;
// read the inputs
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[0]) {
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[0]) { // the highest block closes
pop_heap(heights.begin(), heights.end());
heights.erase(heights.end()-1);
if(heights[0] != h) { // may have blocks with same height
SLVec v;
v.x = blocks[r].x2; v.height = heights[0];
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]

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]

WBR,

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

I made 2-3 small changes in your main() method
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

It is strange that your ACC program ( your Java program
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]

Help me please!

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][0],&a[n][1],&a[n][2] ) ) 
	{	
		
		x[m] = a[n][0] ;
		m = m + 1 ;
		x[m] = a[n][2] ;
		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][0] )
			{
				st = j ;
				break;
			}
		for ( j = m-1 ; j >= 0 ; j -- )
			if ( x[j] == a[i][2] )
			{
				en = j ;
				break;
			}
		st = st + 1 ;
		for ( j = st ; j <= en ; j ++ )
			if ( h[j] < a[i][1] ) 
				h[j] = a[i][1] ;

	}

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

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?

[little joey]

By using eof:

Code: Select all

...
some initialisation
...
while not eof do begin
   readln(left,height,right);
   ...
   some processing
   ...
   end;
...
some more processing
etc.

[wdg]

Thank you!

[wdg]

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.