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

Ovro
New poster
Posts: 12
Joined: Mon Nov 11, 2013 8:30 am

Re: 105 - The Skyline Problem

Post by Ovro » Tue Dec 10, 2013 7:44 pm

Getting WA. Can someone plz help me?

Code: Select all

#include<stdio.h>
int main()
{
    int a1[20100],a2[20100],h[5100],height,ara[20100],i,count=0,j;
    while((scanf("%d %d %d",&a1[count],&h[count],&a2[count])==3))
        count++;
    for(i=0;i<20100;i++)
        ara[i]=0;
    int k;
    for(k=0;k<count;k++)
    {
        if(a1[k]==a2[k])
            continue;
        for(j=2*a1[k];j<=2*a2[k];j++)
        {
            if(ara[j]<=h[k])
                ara[j]=h[k];
        }
    }
    height=ara[0];
    for(i=0;i<20100;i++)
    {
        if(ara[i]>height)
        {
            height=ara[i];
            printf("%d %d ",i/2,height);
        }
        if(ara[i]<height)
        {
            height=ara[i];
            printf("%d %d ",(i-1)/2,height);
        }
    }
    printf("\b\n");
    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 Dec 10, 2013 9:40 pm

Don't print a space or a '\b' at the end of the line.
Check input and AC output for thousands of problems on uDebug!

Ovro
New poster
Posts: 12
Joined: Mon Nov 11, 2013 8:30 am

Re: 105 - The Skyline Problem

Post by Ovro » Wed Dec 11, 2013 6:00 am

Thanks a lot sir. It is AC now. :)

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 105 - The Skyline Problem

Post by just_yousef » Wed Jul 23, 2014 8:05 pm

A lot of WA,, Please Help :/

Code: Select all

AC :D
Last edited by just_yousef on Wed Jul 23, 2014 11:07 pm, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 105 - The Skyline Problem

Post by lbv » Wed Jul 23, 2014 9:18 pm

just_yousef wrote:A lot of WA,, Please Help :/
Try reading the previous messages from the forums. For example, brianfry713's post from around Mar 19, 2013 has advice that applies to your code.

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 105 - The Skyline Problem

Post by just_yousef » Wed Jul 23, 2014 11:07 pm

lbv wrote:
just_yousef wrote:A lot of WA,, Please Help :/
Try reading the previous messages from the forums. For example, brianfry713's post from around Mar 19, 2013 has advice that applies to your code.
6 WA Only Because Of New line :evil: :evil: Thanks lbv

azisak
New poster
Posts: 4
Joined: Wed Aug 20, 2014 6:09 pm

Re: 105 - The Skyline Problem

Post by azisak » Thu Sep 04, 2014 6:59 pm

Help please, i got WA on this, and i got tired to find where's the failure :(

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;

int pos[10001]={0};

main()
{
    int l,h,r;
    //freopen("0tes.txt","r",stdin);
    while (cin>>l>>h>>r)
    {
        for (int i=l;i<r;i++){
            if (h>pos[i])
                pos[i]=h;

        }

    }

    bool notfirst=false;
    int hnow=0;
    
    for (int i=0;i<1000;i++)
    {
        if (pos[i]!=hnow)
        {
            if (notfirst)
                cout<<' ';
            else
            notfirst=true;
            cout<<i<<' '<<pos[i];
            hnow=pos[i];
        }
    }
    cout<<endl;

}

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 » Sat Sep 06, 2014 7:14 am

Change line 25 to:
for (int i=0;i<=10000;i++)
Check input and AC output for thousands of problems on uDebug!

BD_Star
New poster
Posts: 1
Joined: Fri Oct 17, 2014 4:22 am

Re: 105 - The Skyline Problem

Post by BD_Star » Fri Oct 17, 2014 4:55 am

Why my code gone failed with verdict Wrong answer. My Source code is following:-

Code: Select all

/* Problem:  105 - "The Skyline Problem" */

#include <iostream>
using namespace std;
 
int	main(){
int	data[10002]; 
int	l,h,r;
int start=1,end=0;
 
for(int	i = 0; i < 10002; i++) data[i] = 0; 

while(cin >> l >> h >> r){
	if(l<=0) l=1;
	for(int	i = l; i < r; i++){
		if(h > data[i]){
			data[i] = h;
			if(i<start){
				start=i;
			}
			if(i>end){
				end=i;
			}
		}
	}
}

int x=start;
cout<<x<<" "<<data[x]<<" ";
for(int i=start;i<=end+1;i++){
	if(data[i]!=data[x]){
		x=i;
		cout<<x<<" "<<data[x]<<" ";
	}
}

return	0; 
}

I have check following input and output
Input #1:
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

Output(for input set #1):
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
Input #2:
3 2 4
3 1 7
5 2 6

output(my code output for input set #2):
1 0 3 2 4 1 5 2 6 1 7 0

Also, form http://www.udebug.com/UVa/105
i got output for input set #2
1 0 3 2 4 1 5 2 6 1 7 0
Input #3:
-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
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 <=[my code output for input #3]
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 <=[output from http://www.udebug.com/UVa/105]
So what is the problem??? For what types of input it got WA? Or give me some critical input.
Please anyone help me

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 » Fri Oct 17, 2014 10:20 pm

Print a newline char at the end of the line. Don't print a space at the end of the line
Check input and AC output for thousands of problems on uDebug!

4dummies
New poster
Posts: 1
Joined: Sat Jan 28, 2017 5:18 pm

Re: 105 - The Skyline Problem

Post by 4dummies » Sat Jan 28, 2017 5:40 pm

I finally got accepted. I used a max-heap to keep track of the highest current building, along with its end x. At each event, I discard any tall buildings that are past x; what's left on top of the heap is the tallest.

This way the algorithm only looks at actual start and ending x values. I wanted working heap code anyway, so I'm happy.

Post Reply

Return to “Volume 1 (100-199)”