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
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

105 P.E.

Post by 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?

:o

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by 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
New poster
Posts: 2
Joined: Sat Mar 05, 2005 9:33 pm

105 - WA - java

Post by 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
New poster
Posts: 2
Joined: Sat Mar 05, 2005 9:33 pm

105 - WA - java

Post by wbr »

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

Post by 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?
Understanding a problem in a natural way will lead to a natural solution

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

Post by 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
New poster
Posts: 18
Joined: Sat Sep 18, 2004 2:14 pm
Location: Dongguk University@COREA
Contact:

:-)

Post by lazenca »

Yes, you're right! :wink:

Your idea make my code more shortly...
I was not far-sighted enough to think of that... :oops:

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

Post by 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. :D

#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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by 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 :D

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

several notes

Post by 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
New poster
Posts: 7
Joined: Wed Jul 31, 2002 3:20 pm
Location: korea
Contact:

# 105 ( RE )

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

105-wrong answer

Post by 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?
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

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

Post by wdg »

Thank you!

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

Post by 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.

Post Reply

Return to “Volume 1 (100-199)”