----------------------------------- klopyrev Thu Feb 15, 2007 12:40 am Contest Problems ----------------------------------- Maybe I am wrong, but I don't see any recent posts about Contest Problems! Doesn't anyone here enjoy contest problems as much as I do? Here is one problem I found interesting. It is called the Skyline Problem and can be found on UVA Problem Set 1: You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple where and are left and right coordinates, respectively, of building i and is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) the skyline, shown on the right, is represented by the sequence: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0) DIAGRAM MISSING! If you like solving this problem, as well as others, you should post some of them here along with their sources so I can submit my solution. ----------------------------------- Hikaru79 Thu Feb 15, 2007 12:44 pm Re: Contest Problems ----------------------------------- Just as a note, if you're a big fan of algorithms contests, you should check out http://www.topcoder.com/tc . They have thousands of problems and weekly live competitions. If you're over 19, you can even make some mad amounts of money. :) ----------------------------------- PaulButler Thu Feb 15, 2007 3:04 pm RE:Contest Problems ----------------------------------- Thanks for the link, Hikaru79. I've been doing any problem I could get my hands on this week for practice. I would do the one in this thread, but I don't understand what is being asked. ----------------------------------- zylum Thu Feb 15, 2007 10:30 pm RE:Contest Problems ----------------------------------- hey i love doing contest problems. i also do topcoder though i haven't had the time lately to compete in an srm. the problem you posted seems pretty easy but a lot of it is missing so its sort of hard to give a formal solution. Hikaru79, why haven't you competed in any of the srms? i see you already have an account :) ----------------------------------- bugzpodder Fri Feb 16, 2007 11:54 am Re: Contest Problems ----------------------------------- If you like solving this problem, as well as others, you should post some of them here along with their sources so I can submit my solution. wtf? http://acm.uva.es/problemset/usersnew.php?user=11918 you solved the skyline problem already... my id is 28684 if you are curious ----------------------------------- klopyrev Fri Feb 16, 2007 7:35 pm Re: Contest Problems ----------------------------------- I have no idea what you mean by that wtf? and the comment on me having solved it already! I found the SkyLine problem to be quite interesting. I remember reading it several months ago on UVA and thinking: Whoa. How the hell do you do this? That was before I decided to complete all of the USACO training along with a lot of the problems on TopCoder. Now, I was forced to try to solve it again for http://www.osix.net/ as one of the Challenge problems. Looking back at it, the simplicy of the solution hit me. I was amazed that the problem which I had no idea how to solve turned out to be solvable by an algorithm that only takes a few lines. I love that about Computer Science. Anyway, for people who like solving problems, here are two very interesting websites: http://www.osix.net/