11790 - Murcia's Skyline

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

11790 - Murcia's Skyline

Post by suneast » Sun May 16, 2010 4:18 am

I really don't know why my solution is always getting WA...
Is it a simply LIS questions...

Can any one who got AC gives some hints :wink:

Thx in advance.

p.s. If is necessary I will post my code here, but I don't want to waste your time to read it...

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11790 - Murcia's Skyline-WA

Post by suneast » Sun May 16, 2010 3:43 pm

finally got AC...

I really don't understand....
I just changes my ini method from "ans=0" to "ans=wid[0]" and got Accepted...

can a building's width be a negetive?
unbeliievable...

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11790 - Murcia's Skyline(TLE)

Post by saiful_sust » Thu May 20, 2010 4:24 pm

Hi...Ithink this is an Easy problem..But i got TLE...
My algorithmn Complexity is N^2
I do not Understand What is wrong with my code...
PLZ some one help me.... :oops: :oops:

Code: Select all

CUT AFTER ACCC.......
Last edited by saiful_sust on Fri May 21, 2010 7:10 am, edited 1 time in total.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11790 - Murcia's Skyline(TLE)

Post by suneast » Thu May 20, 2010 4:38 pm

saiful_sust wrote:
u can just asume that N is not larger than 10000 :D
I solved this PRO use O(N^2) BRUTE FORCE...

and I don't know what's wrong with my O(NlogN) LIS...
maybe there is some stricky input I havn't considerd... :oops:

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11790 - Murcia's Skyline(TLE)

Post by saiful_sust » Thu May 20, 2010 8:10 pm

Thanks for ur Quick reply...suneast

But now i got WA:
i don't understand why?????? :oops: :oops:
just change array size in my code:

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11790 - Murcia's Skyline(TLE)

Post by suneast » Fri May 21, 2010 2:23 am

saiful_sust wrote: Reply to saiful_sust
Hi, saiful_sust .
I just change you INI method to

Code: Select all

int Data[10001],n,DP[10001],a[10001],DP1[10001];         // I change you array size to 10001

void LIS()
{
	int i,j,s,x=0;
	memset(DP,0,sizeof(DP));
	memset(DP1,0,sizeof(DP1));
	DP[0] = DP1[0] = a[0];
	maxv = maxd = a[0];
	for(i=1;i<n;i++)
	{
		s = 0;
		DP[i]=DP1[i]=a[i];            //be care of here !!! the width maybe negetive...or am I misunderstand it?
		for(j=i-1;j>=0;j--)

and got Accepted . :D

Hard to believe ...isn't ?

Maybe there is something wrong with OJ's datasets.

PLZ delete U code after got AC.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11790 - Murcia's Skyline(TLE)

Post by saiful_sust » Fri May 21, 2010 7:12 am

Thanks "suneast" for ur help:)
hw width can be negative...i don't understand???????????? :wink: :wink:

tajbir2000
New poster
Posts: 19
Joined: Fri Sep 05, 2008 6:39 pm
Location: bangladesh
Contact:

Re: 11790 - Murcia's Skyline-WA

Post by tajbir2000 » Wed Jun 09, 2010 7:28 pm

WA need critical input

Code: Select all

#include<stdio.h>

#define size 10001
typedef struct{
	long index;
	long a;
}data;
data I[size],D[size];
int main(){
	long i,j,n,T,cas=1,height[size],temp[size],max_i,max_d,max;
	
	//freopen("i.txt","r",stdin);
	
	scanf("%ld",&T);
	while(T--){
		printf("Case %ld. ",cas++);
		
		
		scanf("%ld",&n);
		for(i=0;i<n;i++){
			scanf("%ld",&height[i]);
		}			
		for(i=0;i<n;i++){
			scanf("%ld",&temp[i]);
			I[i].a=D[i].a=temp[i];			
			I[i].index=D[i].index=1;
		}
		max=temp[0];

		for(i=1;i<n;i++){
			if(max<temp[i])
				max=temp[i];
		}
		max_i=max_d=max;
		
		for(i=0;i<n-1;i++){
			for(j=i+1;j<n;j++){
				if(height[j]>height[i]){					
					if(I[i].index+1>I[j].index){
						I[j].index=I[i].index+1;
						I[j].a=I[i].a+temp[j];
						if(max_i<I[j].a)
							max_i=I[j].a;
						
					}					
					else if(I[i].index+1 == I[j].index){						
						if(I[i].a+temp[j]>I[j].a)
							I[j].a=I[i].a+temp[j];
						if(max_i<I[j].a)
							max_i=I[j].a;
						
					}
				}				
				else if(height[j]<height[i]){					
					if(D[i].index+1>D[j].index){
						D[j].index=D[i].index+1;
						D[j].a=D[i].a+temp[j];
						if(max_d<D[j].a)
							max_d=D[j].a;
						
					}
					else if(D[i].index+1 == D[j].index){						
						if(D[i].a+temp[j]>D[j].a)
							D[j].a=D[i].a+temp[j];
						if(max_d<D[j].a)
							max_d=D[j].a;
						
					}
				}			
			}
		}		
		if(max_i>=max_d)
			printf("Increasing (%ld). Decreasing (%ld).\n",max_i,max_d);
		else
			printf("Decreasing (%ld). Increasing (%ld).\n",max_d,max_i);
		}
		return 0;
}



suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11790 - Murcia's Skyline-WA

Post by suneast » Thu Jun 10, 2010 3:45 am

tajbir2000 wrote: Hi,tajbir2000...
even though I have solved this problem long long...ago...
But I still can't understand why the judge data has such TRICKY case just below. :evil:

Code: Select all

1
3
1 2 3
1 -10 2
and my ac code generate the output

Code: Select all

Case 1. Increasing (3). Decreasing (2).
:wink: Yes,I mean that, your code can't have the correct output while NEGETIVE width exist...

Hope I am help to you...

User avatar
sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

Re: 11790 - Murcia's Skyline

Post by sreejond » Thu Jul 08, 2010 1:50 pm

I got WA several time. I handle the negativity problem also.
Kindly anybody please check my code or give any critical I/O.
Thanks in advance.
Here is my code:

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 10001

long A[MAXN],N,B[MAXN];
long L[MAXN],P1[MAXN],P2[MAXN],waitSum1[MAXN],waitSum2[MAXN],last1,last2,lis,lds,D[MAXN];

void doLIS() 
{
	long i, j;
	long longest1 = 0,longest2=0;
	lis=lds=last1=last2=0;
	for(i = 1; i<=N; i++) 
	{
		long max1 = 0,max2=0;
		long parent1 = -1,parent2=-1;
		for(j = i-1; j>=0; j--) 
		{
			if(B[i]<0)	break;
			if(A[i] > A[j]) 
			{
				if(L[j] > max1) 
				{
					max1 = L[j];
					parent1 = j;
				}
				else if(L[j]==max1 && parent1!=-1)
				{
					if(waitSum1[j]>waitSum1[parent1])
						parent1=j;
				}
			}
			else if(A[i] < A[j])
			{
				if(D[j] > max2) 
				{
					max2 = D[j];
					parent2 = j;
				}
				else if(D[j]==max2 && parent2!=-1)
				{
					if(waitSum2[j]>waitSum2[parent2])
						parent2=j;
				}	
			}
		}

		L[i] = max1+1;
		P1[i] = parent1;
		D[i]=max2+1;
		P2[i]=parent2;
		if(parent1==-1)
			waitSum1[i]=B[i];
		else
		{
			waitSum1[i]=B[i]+waitSum1[parent1];
		}
		if(parent2==-1)
			waitSum2[i]=B[i];
		else
		{
			waitSum2[i]=B[i]+waitSum2[parent2];
		}

		if(lis<waitSum1[i])
			lis=waitSum1[i];
		if(lds<waitSum2[i])
			lds=waitSum2[i];

		if(L[i] > longest1) 
		{
			longest1 = L[i];
			last1 = i;
		}
		else if(L[i]==longest1)
		{
			if(waitSum1[i]>waitSum1[last1])
				last1=i;
		}
		if(D[i] > longest2) 
		{
			longest2 = D[i];
			last2 = i;
		}
		else if(D[i]==longest2)
		{
			if(waitSum2[i]>waitSum2[last2])
				last2=i;
		}
	}
}

int main() 
{
	long i,kase=1,T;
	cin>>T;
	while(T--) 
	{
		cin>>N;
		A[0] = 0;
		for(i = 1; i<= N; i++) 
		{
			cin>>A[i];
		}
		for(i = 1; i<= N; i++) 
		{
			cin>>B[i];
		}
		cout<<"Case "<<kase++<<". ";
		doLIS();
		if(lis>=lds)
			cout<<"Increasing ("<<lis<<"). Decreasing ("<<lds<<").\n";
		else
			cout<<"Decreasing ("<<lds<<"). Increasing ("<<lis<<").\n";
	}
	return 0;
}

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

Re: 11790 - Murcia's Skyline

Post by anis_cuet016 » Thu Aug 05, 2010 5:51 am

hlw ol, frm the problem i could figure out that it is weighted lis/lds. Guyz cn any1 cn help me how to handle the weight along with lis. I mean what was ur approach. Thankz in advance

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11790 - Murcia's Skyline

Post by sohel » Thu Aug 05, 2010 11:43 am

Hello Anis,
We usually avoid writing in SMS style in the forums. There are many whose mother tongue isn't English and would find it difficult understanding the message. :)
Good luck and keep solving.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11790 - Murcia's Skyline

Post by suneast » Thu Aug 05, 2010 11:45 am

Yes... :wink:
I really don't understand what he want to express...

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

Re: 11790 - Murcia's Skyline

Post by anis_cuet016 » Fri Aug 06, 2010 9:18 pm

hlw .......

I thought this are the common terms in the algorithm, as i often see + hear the people expressing in this shortcut forms, and i guess abbreviation form is not really the SMS form, as SOHEL brother mentioned... anywayz i will try to rewrite my statement what i wrote earlier with explanation....

From the problem statement i can understand is that it is longest increasing subsequence(lis) and longest decreasing subsequence(lds) along with weight.. but i cant find gud algorithm myself to handle the weight ... along with finding the longest increasing subsequence(lis) or longest decreasing subsequence(lds). example ..

for input : 10 100 50 30 80 10
50 10 10 15 20 10

i can find the longest increasing subsequence as 10 -> 50 -> 80. this sums up to 80; but it should be 10 -> 30 -> 80. this sums up to 85;
now can any1 please help me about sharing some ideas.... i thought of finding all the subsequence and then find the maximum weight from there, but failed to do that, Suppose there are common length for the subsequence's, like there are two subsequence of length 3.. 10-> 50->80 and 10->30->80. how can i find all the subsequence's. i hope my problem is understood....
Yes... :wink:
I really don't understand what he want to express...
I didn't realize this sentence's i wrote at my previous post are harder to understand ...... anywayz sorry for my poor english, and next time i will keep this in mind while posting is that everyone's mother tounge is not english .......

Anis

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11790 - Murcia's Skyline

Post by suneast » Sat Aug 07, 2010 5:26 am

[quote="anis_cuet016"][/quote]
I'm sorry ,anis_cuet016...
I don't meant to hurt you... :wink:
just forget it :roll:

I think this problem is just a O(n^2) brute force lis/lds
you should initial your array to -INF...
because I think the width of a building maybe negetive...
just do it ,and got AC... :D

Post Reply

Return to “Volume 117 (11700-11799)”