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

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

That's why you got PE~

Try to put a newline character at the end and you will get Accepted.

Pokemonster
New poster
Posts: 10
Joined: Mon Jul 01, 2002 11:15 pm
Location: Germany

Post by Pokemonster »

Thanks alot guys! Works fine now :D

nariini
New poster
Posts: 4
Joined: Tue Jul 16, 2002 12:38 pm

[105]i received Wrong Answer..

Post by nariini »

i don't know why received wrong answer..

sample inputs generate correct outputs.

let me know please

[java]
import java.io.*;
import java.util.*;

class Main
{
static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

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

public static void main(String[] args)
{
Main myWork = new Main();
myWork.Begin();
}

void Begin()
{
String line;
StringTokenizer idata;
int arr[];
int top_pnt[];
int i=0;
int end_pnt = -1;
int cnt=0;

arr = new int[15000];
try
{
while ((line = Main.ReadLn(255)) != null) //input&#44050;&#46308;&#51012; array&#50640; &#51200;&#51109;
{
cnt++;
if (cnt > 5000)
{
System.exit(1);
}
idata = new StringTokenizer(line);
arr = Integer.parseInt(idata.nextToken());
arr[i+1] = Integer.parseInt(idata.nextToken());
arr[i+2] = Integer.parseInt(idata.nextToken());
if (arr<1 || arr>10000 || arr[i+1]<1 || arr[i+1]>10000 || arr[i+2]<1 || arr[i+2]>10000)
{
System.exit(1);
}
i = i + 3;
}
} catch(Exception e){}
for (int j=2; arr[j] != 0; j=j+3) //&#52572;&#45824; &#50864;&#52769;&#44050; &#51200;&#51109;
{
if (end_pnt < arr[j])
end_pnt = arr[j];
}
top_pnt = new int[end_pnt+1]; //creat top_pnt array
for (int j=0; j <= end_pnt; j=j+3) //top_pnt&#47484; top_pnt[]&#50640; &#51200;&#51109;
{
for (int k=arr[j]; k < arr[j+2]; k++)
{
if (top_pnt[k] < arr[j+1])
top_pnt[k] = arr[j+1];
}
}
int temp = 0;
int flag = 0;
for(int j=arr[0]; j<=end_pnt; j++)
{
if (temp != top_pnt[j])
{
temp = top_pnt[j];
if (flag == 0)
{
System.out.print(j+" "+top_pnt[j]);
flag = 1;
} else if (flag == 1){
System.out.print(" "+j+" "+top_pnt[j]);
}
}
}
}
}
[/java]

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja »

Hhm... In fact, I don't know about java. ( I solved this problem in C++ )

So I can't say about your code. ( Perhaps your code has some mistakes. )

But I think that it's one of the easiest problem in valladolid problem set.

How about use this sample test data? Maybe it gives you the opportunity

to solve this problem.

P.S ) Are you Korean? If you are Korean, I strongly recommend

that reading 2001 ACM Taejon problem F, Moving tables. It use very

simuliar solution to this problem. Good luck.

Input
-5 5 1
1 6 2
1 2 7
3 12 10
4 3 5
7 5 20
8 15 12
11 12 13
16 14 19
21 2 22
23 1 30
26 10 28
26 12 27
32 5 36
34 3 38
34 3 40
37 2 42
38 2 44
45 1 46

Output

-5 5 1 6 2 2 3 12 8 15 12 12 13 5 16 14 19 5 20 0 21 2 22 0 23 1 26 12 27 10 28 1 30 0 32 5 36 3 40 2 44 0 45 1 46 0

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn »

I agree, this is a very easy problem. The description has changed some since I solved this, though. At the time, the trick was that some of the coordinates could be less than 0, but always with an absolute value less than 10000. Even though they now promise positive integers, I would allow for 0 as a possible coordinate value.

Try the sample input again, but change the first line to: 0 11 5. The output then should of course also start with 0.

zalileo
New poster
Posts: 2
Joined: Fri Aug 16, 2002 7:08 am

Post by zalileo »

Thanks a lot for soyoja's sample data!


finally, I get it with 0.020 CPU time :)
// .....................................................

chimera
New poster
Posts: 1
Joined: Thu Sep 05, 2002 6:35 am

Post by chimera »

I solved these cases listed above.
But I still got wrong answer.
Who could give me some tips, thanks?

cherlee
New poster
Posts: 1
Joined: Sat Oct 12, 2002 6:23 pm

Post by cherlee »

i don't understand java and i'm having a trouble in solving this problem although it's said to be one of the easiest.. ^^

could someone help me to explain the logic?? i'll try to convert it into c coding by myself.. thx..

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn »

This is probably not the best algorithm -- but it should work.

Create a 20001 integerarray. Set all values to 0 initially.

As you read in each triplet, add 10000 to the starting and ending coordinates in the triple. This takes care of any cases where buildings are specified with negative start or end values. A negative height doesn't happen since it wouldn't make sense anyway. You wouldn't notice a hole in the ground as you look at a skyline.

For each of the locations from the altered beginning coordinate to the altered ending point (include the starting point, exclude the ending point), check the current height. If the new height is more than the current height -- save the new height in the array. This takes care of overlapping buildings. Only the tallest building becomes part of the skyline.

Once all triples have been read in, scan the array. Starting from the beginning of the array, scan until you find some height other than 0. At that point, subtract 10000 from the array index and print that location number, then give its current height, then scan until the height changes again. Then keep alternating printing new coordinates and new heights. Just remember to subtract 10000 from the array index each time for the coordinate.

David

Olorin
New poster
Posts: 8
Joined: Sun Nov 03, 2002 3:39 pm

p105 (and others): C++ detect end of file..argh..of stream ?

Post by Olorin »

So, p 105 is an example, but not the only one.
In many problems we have to read input until the end of the stream. Now, if this was a file (for ex named infile), we could have loops that check on infile.fail, or loops while(infile) (depending).
Since this is cin, not a filestream, how do you keep on reading till there is input?

For instance, p105 has the input made up of triplets of integers.
So, I have the following (ok, with cuts and removals :-):
[cpp]
#include <cstdlib>
#include <cmath>
#include <climits>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void main()
{
int n;
vector<Bld> buildings;
int maxR=-1;

while(cin>>n)
{
// read two more integers with
// cin>>myInt;
// and do stuff with them
}//WEND
// Do more stuff

}
// End main
[/cpp]

Of course, when I try to test it,
I enter the numbers I wish, press Enter, enter 3 more numbers, and so on. However, the program cannot understand when I am done with my entering data and move out of that while loop to Do More Stuff.

Ehr... how do you people do it?

Thanks in advance.
-- Elen Sila Lumenn' Omentielvo --

Olorin
New poster
Posts: 8
Joined: Sun Nov 03, 2002 3:39 pm

Detecting end of file...ehr...of stream (sigh)

Post by Olorin »

Well, I did post this in the Volume I forum, but maybe it is more appropriate here in C++. ANyhow, the question makes explicit reference to P105, but disregard that, since it is really a generic problem I'm having because the inputs here come from cin rather than a filestream.

=================================

So, p 105 is an example, but not the only one.
In many problems we have to read input until the end of the stream. Now, if this was a file (for ex named infile), we could have loops that check on infile.fail, or loops while(infile) (depending).
Since this is cin, not a filestream, how do you keep on reading till there is input?

For instance, p105 has the input made up of triplets of integers.
So, I have the following (ok, with cuts and removals :

[cpp]

#include <cstdlib>
#include <cmath>
#include <climits>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void main()
{
int n;
vector<Bld> buildings;
int maxR=-1;

while(cin>>n)
{
// read two more integers with
// cin>>myInt;
// and do stuff with them
}//WEND
// Do more stuff

}
// End main

[/cpp]

Of course, when I try to test it,
I enter the numbers I wish, press Enter, enter 3 more numbers, and so on. However, the program cannot understand when I am done with my entering data and move out of that while loop to Do More Stuff.

Ehr... how do you people do it?

Thanks in advance.
-- Elen Sila Lumenn' Omentielvo --

Fresh
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

...

Post by Fresh »

Try this - Store the sample input in a file, let's say input.txt. Make executable file (p105.exe) and at command prompt, test the output by typing 'c:\p105 < input.txt'. You can print the output to a file with 'c:\p105 < input.txt >output.txt'

-novice :wink:

zorbathut
New poster
Posts: 16
Joined: Tue Nov 05, 2002 6:31 am

Post by zorbathut »

For submission, the code you've got there will work beautifully - it'll hit end-of-stream and go into More Stuff.

For testing purposes, I recommend coming up with a sentinel value to indicate "end of stream" - if( n == -2 ) break; - and then write -2 to end it. Just remember to pull it out before submitting, if -2 is valid input ;)

EZE
New poster
Posts: 4
Joined: Wed Nov 06, 2002 2:34 am

Post by EZE »

Yeah... the while(cin >> blah) works well for the submissions. However, when reading from standard input that isnt re-directed, you have to tell cin that it's at the end of the stream. This is done by hitting ctrl-d (^d) then enter. I'm not sure if this works under dos (or windows)... but who uses them anyways? Hope that helps!

ciao
EZE

Olorin
New poster
Posts: 8
Joined: Sun Nov 03, 2002 3:39 pm

Post by Olorin »

Thanks EZE, and Zorba. I'll try to submit it as-is and come up with a testing scheme using files or sentinel values.
-- Elen Sila Lumenn' Omentielvo --

Post Reply

Return to “Volume 1 (100-199)”