OJ Board

Posted: **Sun Jan 02, 2005 11:14 pm**

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?

Posted: **Tue Jan 04, 2005 9:08 am**

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.

Posted: **Sat Mar 05, 2005 10:35 pm**

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

Posted: **Wed Mar 09, 2005 2:36 pm**

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

Posted: **Wed Apr 06, 2005 11:48 am**

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?

Posted: **Fri Apr 08, 2005 12:54 am**

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

Posted: **Fri Apr 08, 2005 3:12 am**

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

Posted: **Sun May 29, 2005 10:33 pm**

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

Posted: **Thu Jun 23, 2005 7:04 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

Posted: **Thu Jun 30, 2005 11:56 am**

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

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.

Posted: **Tue Jul 05, 2005 7:15 pm**

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

Posted: **Tue Aug 16, 2005 3:30 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?

Posted: **Tue Aug 16, 2005 5:16 pm**

By using eof:

Code: Select all

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

Posted: **Wed Aug 17, 2005 4:13 am**

Thank you!

Posted: **Wed Aug 17, 2005 5:40 am**

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.

OJ Board

105 - The Skyline Problem

105 P.E.

105 - WA - java

105 - WA - java

input of 105

:-)

105 Runtime error

several notes

# 105 ( RE )

105-wrong answer