11908 - Skyscraper

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

Moderator: Board moderators

Post Reply
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

11908 - Skyscraper

Post by asif_iut »

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

New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 11908 - Skyscrapper

Post by crip121 »

greedy will do..

New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

Re: 11908 - Skyscrapper

Post by Taman »

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[i-1]+p);

P.S.: please don't misunderstand,this is copy-pasted 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.

New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 11908 - Skyscrapper

Post by crip121 »

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.

Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh

Re: 11908 - Skyscrapper

Post by zobayer »

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

Post by naseef_07cuet »

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. :)
If you have determination, you can do anything you want....:)

New poster
Posts: 10
Joined: Thu Jul 01, 2010 10:44 am


Post by amin__ »

hello I am getting wa in this problem and need some critical cases..Can anyone help me??

Post Reply

Return to “Volume 119 (11900-11999)”