OJ Board

I have a problem from the Waterloo CCC from 2000: Given the HTML source code for N websites (N < 100), each of which can contain K links (K < 100). At the end of input, you're also given the URL of two websites and asked to see if you can get from the first website to the second just by using links.

My problem with this is that since URL can be up to 80 characters long, and each page can link to 100 links, this means you'd need to store 80*100*100 characters, or 800K in memory! Isn't that too much, considering you'd also have to have some sort of a way to store the actual graph of the websites? How is it possible to solve this problem?

Also, does anybody know of any websites that explain generic, typical algorithms, like Dynamic Programming, etc.?

Any help would be appreciated.

First of all, 800K doesn't sound too bad for me

Then, I'd suggest to use a map<string,int> to convert a URL to a number. Whenever you have a URL, get its number from the map or if not existent, insert it with a new number. Then never work with the URL, but instead with its number. This will also speed up the whole thing.

For DP etc: Get yourself the book "Introduction to Algorithms" of Cormen, Leiserson, Rivest and Stein. You'll not regret it. For sure, you'll find someone to borrow it from, if you'd first like to have a look at it.

Stefan

Another excellent book that describes general techniques is "The Algorithm Design Manual" of Steven S. Skiena. It doesn't have much (pseude)code, but is very enlightening and a great reference. The first part of the book is about general stuff, the second is a catalog of problems. You can get an idea of what's in the second part here:

http://www.cs.sunysb.edu/~algorith/

Stefan

Thanks!

I'm waiting for that book to come to my library... Unfortunately I doubt it'll be there by the time of the contest I'm training for