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 » Thu Nov 15, 2012 5:18 am

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 » Thu Nov 15, 2012 5:38 am

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 » Thu Nov 15, 2012 11:38 pm

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 » Fri Nov 16, 2012 12:11 am

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 » Wed Dec 26, 2012 12:32 am

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 » Sat Dec 29, 2012 12:21 pm

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 » Sat Dec 29, 2012 6:21 pm

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 » Sun Dec 30, 2012 8:52 am

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 » Sun Dec 30, 2012 10:14 am

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 » Sun Dec 30, 2012 11:33 pm

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 » Tue Mar 19, 2013 3:35 pm

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 » Tue Mar 19, 2013 11:33 pm

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 » Wed Jul 31, 2013 11:21 am

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 » Thu Aug 01, 2013 12:20 am

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 » Tue Dec 03, 2013 2:09 am

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

Post Reply

Return to “Volume 1 (100-199)”