11908  Skyscraper
Moderator: Board moderators
11908  Skyscraper
i tried to solve this problem using dp but how can i store the dp results in a table?? a N X N array exceeds the memory limit
Re: 11908  Skyscrapper
greedy will do..
Re: 11908  Skyscrapper
Spoiler
I got accepted by implementing O(N) dp. think that when I am thinking from i'th floor, suppose I can place an advertisement that is x floors long and have a profit of p unit. so profit[i+x]=max(profit[i+x],profit[i1]+p);
P.S.: please don't misunderstand,this is copypasted from Topcoder forum. and that post was also by me :p
I got accepted by implementing O(N) dp. think that when I am thinking from i'th floor, suppose I can place an advertisement that is x floors long and have a profit of p unit. so profit[i+x]=max(profit[i+x],profit[i1]+p);
P.S.: please don't misunderstand,this is copypasted from Topcoder forum. and that post was also by me :p
Last edited by Taman on Tue Sep 06, 2011 11:59 am, edited 1 time in total.
Re: 11908  Skyscrapper
after reading taman's post, i looked at my code again and cant decide whether it would be dp or greedy. but i think its a close resembelance to LIS algorithm with a bit of greedy choice. sorry if it makes anyone misguided.
here's my algo,
1. sort (criteria is yours to decide)
2. now, for i'th position you have either two choice(dp)
 place it (how, well greedy comes here, just look back a bit)
 or the previous profit is better
i used N^2 time complexity with N memory, but it can be done in NlogN too.
here's my algo,
1. sort (criteria is yours to decide)
2. now, for i'th position you have either two choice(dp)
 place it (how, well greedy comes here, just look back a bit)
 or the previous profit is better
i used N^2 time complexity with N memory, but it can be done in NlogN too.

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11908  Skyscrapper
this is not good to give the solutions even if no one has asked. please remove your spoilers.
it is quite sufficient when you state the complexity or something like "dp will do"
however, it can be solved in O(n) + O(n lg n) which is in total O(n lg n) time, and O(n) memory.
there are two ways, straight forward dp, or u can also use binary search subroutine. The first one turns out to be faster.
it is quite sufficient when you state the complexity or something like "dp will do"
however, it can be solved in O(n) + O(n lg n) which is in total O(n lg n) time, and O(n) memory.
there are two ways, straight forward dp, or u can also use binary search subroutine. The first one turns out to be faster.
You should not always say what you know, but you should always know what you say.

 Learning poster
 Posts: 62
 Joined: Sat Nov 21, 2009 10:17 pm
 Location: CUET,Chittagong,Bangladesh
Re: 11908  Skyscrapper
Please delete your post.Who have given the solution.It is not good for others to have solution without solving it.I think this is an easy greedy problem.But one have to be careful about the time.
Happy Coding.
Happy Coding.
If you have determination, you can do anything you want....