On Thu, Aug 13, 2009 at 11:45 PM, Hawston LLH<[email protected]> wrote: > Anyone with experience, please advice. The naive solution to this question > is obviously O(n^2), now my question is: (1) usually naive solution can work > within time limit ? (2) if it can work for small data set, do you go ahead > with the large data set or you will spend some time try to optimize it > first, which would mean you have less time for other questions? (3) or all > the questions in code jam is designed in such a way that naive approach will > fail, thus we must always strive for more efficient algorithm, e.g. > O(n*log(n))?
(1) The O(n^2) naive algorithm will work for the small dataset, but won't work for the large input. (2) Just read the problem statement. It says that K will go as far as 1000000 in the large input, an O(n^2) algorithm is always a bad choice for such a high limit. I would try to optimize it, but your choice might depend on your skills and familiarity with the problem subject. (3) Not always, but most of the time. For instance, there are some questions where a brute force or backtracking algorithm will do the job, but you'll have to prune the search space or something to get it on time. -- Luiz Ribeiro http://luizribeiro.org/ --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
