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
asif_iut
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

11908 - Skyscraper

Post by asif_iut » Sun Feb 06, 2011 7:36 am

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

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

Re: 11908 - Skyscrapper

Post by crip121 » Sun Feb 06, 2011 3:28 pm

greedy will do..

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

Re: 11908 - Skyscrapper

Post by Taman » Tue Feb 08, 2011 7:07 pm

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

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

Re: 11908 - Skyscrapper

Post by crip121 » Thu Feb 10, 2011 1:51 pm

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.

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

Re: 11908 - Skyscrapper

Post by zobayer » Thu Feb 10, 2011 8:27 pm

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.

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11908 - Skyscrapper

Post by naseef_07cuet » Wed Mar 09, 2011 1:54 am

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

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

11908

Post by amin__ » Fri May 13, 2011 10:38 pm

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