105 - The Skyline Problem

[mf]

main() must return int.
And it should return 0. Anything else means your program crashed.

[ergysr]

I really can't understand what's wrong with my code , it solves correctly every input on the forum, but the judge gives me WA!

Code: Select all

#include <iostream>
#include <stdio.h>

#define max 10000
using namespace std;



int main()
{
    int t[max+1];
    int le,he,ri,pos,i,tmp;
    bool flag;
    
    flag=false;
    for (i=1;i<=max;i++) t[i]=0;
    while (scanf("%d %d %d",&le,&he,&ri)!=EOF)
    {
           for (i=le;i<ri;i++) if (he>t[i]) t[i]=he;
    }
    tmp=0;
    
    flag=false;
    for (i=1;i<=max;i++) 
        if (t[i]!=tmp) 
           {
           
          
           if (flag) cout << " " << i << " " << t[i];
           else cout << i << " " << t[i],flag=true;
           tmp=t[i];
           }
           
    
    
          
          

return 0;
          
}

Please provide me any tricky test case!

[Jan]

Search the board first. Use an existing thread.

[anirudh333]

Hi all! Seems the WA has been bugging many people, i was also one among them.
I added a "\n" after i print the answer and i got it accepted. The judge should have given Presentation Error but it gave WA.
here's my code

Code: Select all

#include<iostream>
using namespace std;
int a[10000];
int main()
{
	int x,y,z;
	int maxx = 0;
	while(cin>>x>>y>>z)
	{
		for(int i = x+1;i<=z;i++)
		if(a[i] < y)
		a[i] = y;
		if(maxx < z)
		maxx = z;
	}
	int currh = 0;
	for(int i = 0; i<=maxx;i++)
	{
		if(currh != a[i])
		{
			cout<<i-1<<" "<<a[i]<<" ";
			currh = a[i];
		}
	}
	cout<<maxx<<" "<<0<<"\n";
	return 0;
}

[ctsmith]

dear all

I would like to ask for the test cases and corresponding correct results to check where my code goes wrong. I will post my code if necessary later. I would like to try first.

thank you all.

[m.kavakebi]

some test case

inp:
1 5 10
10 5 20
10 4 30
out:
1 5 20 4 30 0

inp:
1 5 10
2 7 10
10 5 20
10 4 30
out:
1 5 2 7 10 5 20 4 30 0

[rehan]

can anyone plz tell me how the input of the problem be stopped??????
i cant got it reading the problem????? thanks in advance

[mahbub.cse.kuet]

Input ended with EOF(End of File)(Ctrl + Z)

[Neil]

What should the output be for this case?

Code: Select all

1 2 9
5 7 13
13 7 17
21 2 24
23 6 27
24 10 30
27 6 32

The UVa toolkit gives
1 2 5 7 17 0 21 2 23 6 24 10 30 0
But shouldn't it be
1 2 5 7 17 0 21 2 23 6 24 10 30 6 32 0
?

[brianfry713]

For your input, my AC code prints:
1 2 5 7 17 0 21 2 23 6 24 10 30 6 32 0

[happyson10]

import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main
{
public static ArrayList<Integer> RESULT_X = new ArrayList<Integer> (); //represent the vertical line (x-coordinate)
public static ArrayList<Integer> RESULT_Y = new ArrayList<Integer> (); //represent the horizontal line (height), the last one is 0

/*
* Time O(), Space O()
* @return the
*/
private int addTriplet(int xIndexStart, int ln, int hn, int rn) {

int returnValue = xIndexStart; //represent a right vertical line (x-coordinate) of the new Rect
int xIndexEnd = RESULT_X.size() -1 ;

if(RESULT_X.get(xIndexEnd) < ln){ //case 1, the new Rect is in the right without interleaving.
returnValue = ++xIndexEnd;
addPoint(xIndexEnd, ln, hn);
addPoint(++xIndexEnd, rn, 0);
return returnValue;

}else if(RESULT_X.get(xIndexEnd) == ln){ //case 2, the new Rect is in the right with a point interleaving.
returnValue = xIndexEnd;
if(RESULT_Y.get(xIndexEnd - 1) != hn){
addPoint(xIndexEnd, ln, hn);
xIndexEnd ++;
}
updatePointX(xIndexEnd, rn);

return returnValue;
}

//the other cases, the right point is in [xIndexStart, xIndexEnd)
int xIndexLeft = searchX_binary(xIndexStart, xIndexEnd, ln); // represent a left vertical line (x-coordinate) of the new Rect
int xIndexRight = searchX_binary(xIndexLeft, xIndexEnd, rn); // represent a right vertical line (x-coordinate) of the new Rect
returnValue = xIndexLeft;

//case 3, the new Rect is in the exits Skyline.
//the right point is at left of xIndexEnd and the height ---
//or the right point and the xIndexEnd are in the same Vertical line. and the height ---
if( (xIndexRight < xIndexEnd && RESULT_Y.get(xIndexRight) >= hn) || ( xIndexRight == xIndexEnd && RESULT_X.get(xIndexRight) == rn && RESULT_Y.get(xIndexRight - 1) >= hn ) )
return returnValue;

//case 4, the new Rect will create 2 new points.
// add the right point
addPoint(xIndexRight+1, rn, RESULT_Y.get(xIndexRight));

// add the left point
int xTmp = ln;

if(RESULT_Y.get(xIndexLeft) >= hn ){ // the new Rect's top Horizon line cross a Vertical line
for( int i=xIndexLeft; i<=xIndexRight; i++){
if( RESULT_Y.get(i) <= hn){
xIndexLeft = i;
xTmp = RESULT_X.get(i) ;
break;
}
}
}else{ // the new Rect's left Vertical line cross the Horizon line
if(RESULT_X.get(xIndexLeft) < ln)
xIndexLeft = xIndexLeft + 1;
xTmp = ln;
returnValue = xIndexLeft;
}

addPoint(xIndexLeft, xTmp, hn);
xIndexRight ++;
xIndexLeft ++;

//remove the points between right and left, inclusive, because they are covered by the new Rect.
for(int i = xIndexLeft; i<=xIndexRight; i++)
deletePoint(xIndexLeft);

return returnValue ;
}

/**
* add a new point in result_x and result_h.
* @param index, the index of x and y
* @param x, x-coordinate
* @param h, height
*/
private void addPoint(int index, int x, int h){
RESULT_X.add(index, x);
RESULT_Y.add(index, h);
}

private void deletePoint(int index){
RESULT_X.remove(index);
RESULT_Y.remove(index);
}

private void updatePointX(int index, int x){
RESULT_X.remove(index);
RESULT_X.add(index, x);
}


/*
* insert into {1, 3} with 0, it would be insert into index -1
* insert into {1, 3} with 1, it would be insert into index 0
* insert into {1, 3} with 2, it would be insert into index 0
* insert into {1, 3} with 3, it would be insert into index 1
* insert into {1, 3} with 4, it would be insert into index 1
*/
private int searchX_binary(int left, int right, int xn){

int mid, xTmp;
while(left <= right){
mid = left + ((right - left) >> 1);
xTmp = RESULT_X.get(mid);

if( xTmp == xn )
return mid;
else if( xTmp < xn){
left = mid + 1;
}else{
right = mid - 1;
}

}

return Math.min(left, right);
}

/*
* Time O(the num of triplet) Space O()
*/
public void drawSkyline(ArrayList<Integer> input) {
//check
if(input == null || input.size() == 0)
return;

//init
int i = 0;
RESULT_X.add(input.get(i++)); // L1
RESULT_Y.add(input.get(i++)); // H1
RESULT_X.add(input.get(i++)); // R1
RESULT_Y.add(0); // right border.

int xIndexStart = 0;
for( ; i< input.size(); ){
xIndexStart = addTriplet(xIndexStart, input.get(i++), input.get(i++), input.get(i++) );
}

//output
StringBuilder sb = new StringBuilder();

for( i=0; i< RESULT_X.size(); i++){
sb.append(RESULT_X.get(i));
sb.append(" ");
sb.append(RESULT_Y.get(i));
sb.append(" ");
}
sb.deleteCharAt(sb.length() - 1);

System.out.println(sb.toString());
}

/*
*
*/
private boolean isValid(int x1, int h, int x2){
//check
if( x1 <=0 || h <=0 || x2<=0 || x1 >= x2 )
return false;

return true;
}


/**
* @param args
*/
public static void main(String[] args) {
Main sv = new Main();

ArrayList<Integer> input = new ArrayList<Integer> ();

try {
int x1, x2, h;

String line;
StringTokenizer idata;
while ((line = readLn (255)) != null){
idata = new StringTokenizer (line);
x1 = Integer.parseInt (idata.nextToken());
h = Integer.parseInt (idata.nextToken());
x2 = Integer.parseInt (idata.nextToken());

if(sv.isValid(x1, h, x2)){
input.add(x1);
input.add(h);
input.add(x2);
}

}
}
catch (Exception e) {
//e.printStackTrace();
}finally{

}

sv.drawSkyline(input);

}

static String readLn(int maxLg) // utility function to read from stdin
{
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;

try {
while (lg < maxLg) {
car = System.in.read();

if ((car < 0) || (car == '\n'))
break;
lin[lg++] += car;
}
}
catch (IOException e) {
return (null);
}

if ((car < 0) && (lg == 0))
return (null); // eof
return (new String(lin, 0, lg));
}
}

[brianfry713]

Don't use a package.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

[brianfry713]

I solved this in less than 30 lines of code by storing the max height on each possible x coordinate.

[happyson10]

Don't use a package.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

thanks, let me removed the package. And please help to check why it return WA

[happyson10]

I solved this in less than 30 lines of code by storing the max height on each possible x coordinate.

thanks, I knew the solution, it's pretty clear and simple, In fact, mine is kind of from it, the difference is
1 mine doesn't store for each possible x coordinate.
2 mine does binary search instead of one by one.

so mine need more code, while the performance is better. BTW, let me remove some code, such as StdIn class.