This was my first attempt at CodeJam. Followed it last year but was unable to actually participate then. I wanted to us AS3 (I currently work in AS3 thats Adobe's programming language for FLASH and FLEX). But since its not free couldn't use it here. So i reverted back to C which i hadn't worked with since college and that was like a year back. I am new to dynamic programming. I am currently opening the wikipedia link to it, but can some one give me a more short answer as to what it is.
I am not sure whether i used DP in any of the problems but i got all problems right somehow. Most of the time i spent recalling all the basics of file handling in C. Check out my solutions for really confusing and weird ways of reading input files.(username - vipulvpatil). My algorithms were based on simple analysis. For A, I first tried creating every possible word for each test case and match it with the dictionary entries, but it seemed to take something around 20 minutes even for small input. (I use C, so i have proved once and for all, that a good algo will run fast in any language and vice versa). Then to make it faster i just did a simple char by char comparison. i.e. for every word in dictionary i checked whether it can be made from the given test case (one char at a time). This made the program fast enough to even run the large input in like 1 second. For problem B, i went through all the cells and first marked each sink. Once all sinks were marked, i went through the grid to mark every cell that flowed into the marked cell. I repeated this process continuously until all cells were marked. What i m not sure is that is this a shabby way of doing DFS? For problem C, for which every one seems to have used DP, I used a system of simple weights. Starting from W all the way to M (including spaces), I calculate the weight of each occurence of a character as follows The Search order is WELCOME TO CODE JAM The weight of each W is 1. The weight of every other character is equal to the sum of weights of each occurence of the previous character that occurs before the current character. It seems to do the job pretty fast. Is this DP? Thank you and best of luck to all. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
