11790 - Murcia's Skyline

[suneast]

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

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]

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]

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....

Code: Select all

CUT AFTER ACCC.......

[suneast]

u can just asume that N is not larger than 10000
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...

[saiful_sust]

Thanks for ur Quick reply...suneast

But now i got WA:
i don't understand why??????

just change array size in my code:

[suneast]

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 .

Hard to believe ...isn't ?

Maybe there is something wrong with OJ's datasets.

PLZ delete U code after got AC.

[saiful_sust]

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

[tajbir2000]

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]

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.

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).

Yes,I mean that, your code can't have the correct output while NEGETIVE width exist...

Hope I am help to you...

[sreejond]

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]

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

[sohel]

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]

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

[anis_cuet016]

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...
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]

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

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...