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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Mar 14, 2008 3:10 pm

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

ergysr
New poster
Posts: 9
Joined: Sun Oct 07, 2007 1:25 pm

105 WA Need Help Please!!!

Post by ergysr » Sat Sep 06, 2008 8:35 pm

I really can't understand what's wrong with my code :x , 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 105 WA Need Help Please!!!

Post by Jan » Sun Sep 07, 2008 10:53 am

Search the board first. Use an existing thread.
Ami ekhono shopno dekhi...
HomePage

anirudh333
New poster
Posts: 1
Joined: Thu Dec 04, 2008 12:51 pm

Re: 105 WA (I passed all test data which I can find on internet)

Post by anirudh333 » Thu Dec 04, 2008 12:55 pm

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
New poster
Posts: 1
Joined: Sun Jul 26, 2009 3:20 pm

105 skyline problem WA

Post by ctsmith » Mon Aug 03, 2009 9:42 am

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
New poster
Posts: 2
Joined: Sat Dec 05, 2009 3:01 am

Re: 105 - The Skyline Problem

Post by m.kavakebi » Sat Dec 05, 2009 3:07 am

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
New poster
Posts: 5
Joined: Thu Dec 25, 2008 1:24 pm

Re: 105 - The Skyline Problem

Post by rehan » Sat Mar 06, 2010 1:27 am

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
New poster
Posts: 3
Joined: Thu Sep 03, 2009 8:53 pm

Re: Input Stopped !!

Post by mahbub.cse.kuet » Tue Apr 20, 2010 9:15 am

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

Neil
New poster
Posts: 8
Joined: Fri Jun 22, 2012 7:04 am

Re: 105 - The Skyline Problem

Post by Neil » Sat Jul 14, 2012 5:34 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 105 - The Skyline Problem

Post by brianfry713 » Mon Jul 16, 2012 11:45 pm

For your input, my AC code prints:
1 2 5 7 17 0 21 2 23 6 24 10 30 6 32 0
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

help on #105

Post by happyson10 » Wed Nov 14, 2012 11:26 pm

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));
}
}
Last edited by happyson10 on Thu Nov 15, 2012 5:00 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: help on #105

Post by brianfry713 » Thu Nov 15, 2012 1:48 am

Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: help on #105

Post by brianfry713 » Thu Nov 15, 2012 3:26 am

I solved this in less than 30 lines of code by storing the max height on each possible x coordinate.
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

Re: help on #105

Post by happyson10 » Thu Nov 15, 2012 4:54 am

brianfry713 wrote: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
Last edited by happyson10 on Thu Nov 15, 2012 5:05 am, edited 1 time in total.

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

Re: help on #105

Post by happyson10 » Thu Nov 15, 2012 4:55 am

brianfry713 wrote: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.

Post Reply

Return to “Volume 1 (100-199)”