11790  Murcia's Skyline
Moderator: Board moderators
11790  Murcia's Skyline
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...
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...
Re: 11790  Murcia's SkylineWA
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...
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...

 Learning poster
 Posts: 97
 Joined: Fri Aug 22, 2008 10:18 pm
 Location: CSE.SUST.SYLHET
Re: 11790  Murcia's Skyline(TLE)
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.......
Last edited by saiful_sust on Fri May 21, 2010 7:10 am, edited 1 time in total.
Re: 11790  Murcia's Skyline(TLE)
u can just asume that N is not larger than 10000saiful_sust wrote:
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...

 Learning poster
 Posts: 97
 Joined: Fri Aug 22, 2008 10:18 pm
 Location: CSE.SUST.SYLHET
Re: 11790  Murcia's Skyline(TLE)
just change array size in my code:Thanks for ur Quick reply...suneast
But now i got WA:
i don't understand why??????
Re: 11790  Murcia's Skyline(TLE)
Hi, saiful_sust .saiful_sust wrote: Reply to 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=i1;j>=0;j)
Hard to believe ...isn't ?
Maybe there is something wrong with OJ's datasets.
PLZ delete U code after got AC.

 Learning poster
 Posts: 97
 Joined: Fri Aug 22, 2008 10:18 pm
 Location: CSE.SUST.SYLHET
Re: 11790  Murcia's Skyline(TLE)
Thanks "suneast" for ur help:)
hw width can be negative...i don't understand????????????

 New poster
 Posts: 19
 Joined: Fri Sep 05, 2008 6:39 pm
 Location: bangladesh
 Contact:
Re: 11790  Murcia's SkylineWA
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<n1;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;
}
Re: 11790  Murcia's SkylineWA
even though I have solved this problem long long...ago...tajbir2000 wrote: Hi,tajbir2000...
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
Code: Select all
Case 1. Increasing (3). Decreasing (2).
Hope I am help to you...
Re: 11790  Murcia's Skyline
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:
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 = i1; 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;
}

 New poster
 Posts: 15
 Joined: Thu Jul 08, 2010 8:28 am
Re: 11790  Murcia's Skyline
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
Re: 11790  Murcia's Skyline
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.
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.
Re: 11790  Murcia's Skyline
Yes...
I really don't understand what he want to express...
I really don't understand what he want to express...

 New poster
 Posts: 15
 Joined: Thu Jul 08, 2010 8:28 am
Re: 11790  Murcia's Skyline
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....
Anis
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....
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 .......Yes...
I really don't understand what he want to express...
Anis
Re: 11790  Murcia's Skyline
[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...
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...