Contest Problems

klopyrev · **Posted:** Thu Feb 15, 2007 12:40 am

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 · **Posted:** Thu Feb 15, 2007 12:44 pm

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

PaulButler · **Posted:** Thu Feb 15, 2007 3:04 pm

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 · **Posted:** Thu Feb 15, 2007 10:30 pm

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 Smile

bugzpodder · **Posted:** Fri Feb 16, 2007 11:54 am

Quote:

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 · **Posted:** Fri Feb 16, 2007 7:35 pm

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/ <- FUN problems (Stuck on Challenge 8)

http://projecteuler.net/ <- FUN math related problems (I got up to 54% genius having solved all the easy problems. Then I just gave up Razz

)

bugzpodder · **Posted:** Sat Feb 17, 2007 1:01 pm

its short for "what the fuck are you talking about?" (woah, what happened to sensors)

klopyrev · **Posted:** Sat Feb 17, 2007 2:31 pm

lol... What I meant by post the sources so I can submit my solution is if someone posts another problem, I want to be able to submit my solution to that problem to some judge. I know what wtf means...

Just a curious question. What university do you go to, bugz? (That is if you go to university)

bugzpodder · **Posted:** Sat Feb 17, 2007 9:25 pm

waterloo... im too lazy to do challenge 3 (the file iO one... maybe you could tell us what challenge 8 is?)

klopyrev · **Posted:** Sat Feb 17, 2007 10:50 pm

Do you mean challenge 4? Where you are given a file and you have to do some bit operations on it? That challenge is hilarious! It teaches you to read all the instructions before you start, because you would be wasting your time. The second last instruction asks you to take the XOR of every value with itself. I only read that after I already programmed the first few steps. What a waste of time that was. Anyway, Challenge 8 is a Reverser Challenge. You are given a executable file. In the file, you have to enter a login and a password. You are also told the MD5 checksum of the password. You have to basically reverse engineer the executable file. Since I have no idea how to do that and no time to learn, I stopped at that challenge. I just don't have the time with the CCC coming up soon.
Anyway,bugz, since you go to waterloo, maybe you could help me out. I am another one of those people trying to decide whether I should go to Computer Science or to Software Engineering. On one hand, Computer Science offers problem solving, etc. I love problem solving. On the other hand, Software Engineering could more likely lead to a more profitable career because it teaches you how to be a manager and such. I was wondering: what is your opinion on this?

bugzpodder · **Posted:** Sat Feb 17, 2007 11:07 pm

o.O xor with itself... duh! I dont like that geek challenge. I prefer the euler project more

probably software...
in cs you get to do a *lot* of math (maybe a good or a bad things) and some bad courses, as well elective options are ridiculous (depth+breadth). I think softeng would be better, albeit its more boring (more engineering, less math).

klopyrev · **Posted:** Sun Feb 18, 2007 12:41 am

Softeng was my initial choice. I've got my whole family going through that program now. My brother graduated last year and he's working at google now. Got two cousins in the second year. Maybe you've met them. They are Anton and Artem. What year are you in anyway?
Anyway, I like Euler Project more too. I got addicted to it for a couple days. Such fun problems.

Naveg · **Posted:** Sun Feb 18, 2007 1:16 pm

Speaking of Project Euler, i'm trying to think of the "clever method" for problem 18.

http://projecteuler.net/print.php?id=18

If someone could point me towards a branch of math or algorithms that i should investigate without giving away the solution that would be great!

klopyrev · **Posted:** Sun Feb 18, 2007 6:42 pm

Dynamic Programming! Problems 67, 81 and 82 are very similar! If you need more of a hint, reply to this again.

PaulButler · **Posted:** Sun Feb 18, 2007 6:49 pm

Naveg @ Sun Feb 18, 2007 1:16 pm wrote:

Speaking of Project Euler, i'm trying to think of the "clever method" for problem 18.

http://projecteuler.net/print.php?id=18

If someone could point me towards a branch of math or algorithms that i should investigate without giving away the solution that would be great!

Just got it. You are probably over-thinking it, the solution isn't too difficult. Let me know if you want a hint.

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members