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

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

Re: help on #105

Post by brianfry713 »

First write the most simple code possible that will get AC. Then try and optimize it if you want.
Last edited by brianfry713 on Thu Nov 15, 2012 11:25 pm, edited 1 time in total.
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 »

brianfry713 wrote:First write the simplistic code possible that will get AC. Then try and optimize it if you want.
I'm agree, simple coding is very important, and there is a balance among performance, code lines and readability
In fact, i think there is a room to make my above code smaller without the logic changing.

At the same time, I have tested lots of cases, i want to find out why it returns WA. would you help ? any test case i missed?

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

Re: help on #105

Post by brianfry713 »

Input:

Code: Select all

1 11 5
2 5 10
6 9 8
6 8 8
AC output:

Code: Select all

1 11 5 5 6 9 8 5 10 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

Re: help on #105

Post by happyson10 »

thank you very much

it's ok after correct one line to.
if( (RESULT_X.get(xIndexRight) < rn && RESULT_Y.get(xIndexRight) >= hn) || ( RESULT_X.get(xIndexRight) == rn && RESULT_Y.get(xIndexRight - 1) >= hn ) )

nm_varun
New poster
Posts: 5
Joined: Tue Dec 25, 2012 7:27 am

Re: help on #105

Post by nm_varun »

Can someone help me out with this (WA)? I can't understand what kind of case I'm missing -

Code: Select all

issue resolved
Last edited by nm_varun on Sat Dec 29, 2012 6:22 pm, edited 1 time 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 »

print a newline at the end.
Check input and AC output for thousands of problems on uDebug!

nm_varun
New poster
Posts: 5
Joined: Tue Dec 25, 2012 7:27 am

Re: help on #105

Post by nm_varun »

Thanks a lot. This kind of presentation problem is so irritating.

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

Re: help on #105

Post by brianfry713 »

Almost every problem requires you to print a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

nm_varun
New poster
Posts: 5
Joined: Tue Dec 25, 2012 7:27 am

Re: help on #105

Post by nm_varun »

Except the ones that don't. Anyway, this is the kind of thing that used to be caught under PE when I used to actually do the competition stuff

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

Re: help on #105

Post by brianfry713 »

Can you give an example of a problem on this judge that requires no newline at the end of the last line?
Missing newlines will usually result in WA on this judge. Don't count on getting PE, if you do, you're probably missing or adding a space.
Check input and AC output for thousands of problems on uDebug!

wawa
New poster
Posts: 5
Joined: Thu Dec 16, 2010 8:17 am

Re: 105 - The Skyline Problem

Post by wawa »

THis problem has gotten me crazy. I've tried all test cases in the forum, seems to be alright. Here is my code, which the spaceFlag is just to print with no space in the end of the output.
Anybody can help me w this?

Code: Select all

#include<iostream>
#include<stdio.h>
using namespace std;
const int MAX = 20000;
int main()
{
	int x;
	int y;
	int h;
	int pos[MAX];
	bool spaceFlag = false;
	for(int i = 0; i < MAX; i++)
		pos[i] = 0;
	while(scanf("%d %d %d", &x, &h, &y) == 3)
	{
		 for(int i = x; i < y; i++)
			if(pos[i] < h)
				pos[i] = h;
	}
	int initH = 0;
	for(int i = 0; i < MAX; i++)
	{
		if(pos[i] != initH)
		{
			if(spaceFlag)
				cout << " " << i << " " << pos[i];
			else
			{
				cout << i << " " << pos[i];
				spaceFlag = true;
			}
		}
		initH = pos[i];
	}
	return 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 »

Print a newline at the end of the line.
Check input and AC output for thousands of problems on uDebug!

SamuelTangz
New poster
Posts: 4
Joined: Wed Jul 31, 2013 11:09 am

The difference in pdf files and the problem webpage

Post by SamuelTangz »

I am a new member in the UVa Online Judge, but after a couple of days I have discovered a problem:

When I am trying to solve problems, I usually checks the .pdf file of the problems instead of the webpage itself.
However the descriptions of the two pages are sometimes different, which makes me confused.

For instance, in problem 105:
The Input
The input is a sequence of building triples. All coordinates of buildings are integers less than 10,000 and there will be at least one and at most 50 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by Li, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.
And in the webpage it saids:
The Input
The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by Li , the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.
Another example is problem 111, the outputs given in sample 2 are different.

There are more examples, but may I ask that which should I follow, the webpage or the pdf file?
Thank you.

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

Re: The difference in pdf files and the problem webpage

Post by brianfry713 »

I'd recommend reading the HTML instead of the PDF. Sometimes the PDF doesn't get updated when changes are made. On 105 if your code works for 5000 buildings it should work for 50 buildings. On 111 the PDF sample output 2 is wrong, the HTML is correct.
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: 105 - The Skyline Problem

Post by brianfry713 »

Try input 1 10 9999
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”