Hey, First of all _many, many_ thanks for taking the time and effort to explain this; really appreciate it. :)
You make a good point about recognising the complexity of the algorithm I'm implementing. That should definitely help in dealing with the large datasets. And I think another reason why it's important, is that if I can't estimate the complexity, it's more than likely I don't have a complete idea of the algorithm itself, in which case it may or may not be the right approach for the given problem. And conversely, if I understand the problem correctly, and have come up with an idea for an algorithm, I _should_ be able to have a good estimate of the complexity. If not, perhaps I didn't understand the problem correctly in the first place. So, understanding / estimating the complexity not only helps me get a better idea about whether the algorithm will work within the constraints or not, but also whether it will work _correctly_ when it indeed does. As you said, "practice" is the key word here. I'm trying to do that more - qualification rounds and Round 1s only, for now. _Hopefully_, I'll improve. ;) It's very nice and helpful for us beginners when the seasoned guys can share their experience and knowledge. Thanks again for that. :) Wish you the best, Shivang On Saturday, March 29, 2014 1:50:14 AM UTC+5:30, Carlos Guia wrote: > <warning>Long email ahead</warning> > > > It's hard to have much before hand because you don't know the problems yet. I > usually do everything, in the case generating department, during the contest; > but you could have some template with some utility functions if you feel your > language is lacking something you will use many times. > > > > > About creating them manually or automatically, it also depends on the > problem. For example, sometimes the input is two numbers, say, N and M, and > you know the worst case is for example N = 10^ and M = 10^3. In those cases > it's pretty easy to generate it manually by copy pasting, assuming your code > doesn't benefit from the fact the input is the same always this may be good > enough. But many times is not that easy, so I'd create a simple generator. > > > > > Most of the times is rather easy to know how a worst case for algorithm is, > so a very simple generator might take only a few minutes to write. But it > depends on your algorithm and you need insight into it. As an oversimplified > example, the basic quicksort is slowest with an already sorted sequence, you > won't be implementing quicksort in a constest, but for whatever you implement > you'll be better off knowing how the worst case looks like for your > algorithm. So ideally, you should study your algorithm enough to know its > complexity, average behavior and worst case behavior, you should also have a > good idea of how the worst case looks like. Even before you write your first > line of code, you should know this. The only way this will happen is with > practice, both writing algorithms and studying them. > > > > > Other times is harder to know exactly how the worst case looks like, for > example in a graph problem maybe the worst case is not having a maximum > number of nodes and edges, but a certain pattern of connectivity actually > hits the sweet spot but you're not sure which is it. For those cases I > usually over generate random cases, say twice the maximum T with random cases > where I think the worst case might appear, like N = MAX_N and M = MAX_M / 2, > but is really problem/solution dependent. Note that when I find myself in > this situation, it usually means I'm not completely sure about my algorithms > complexity and whether is the best option or not. > > > > > I never write an algorithm that I don't know how the worst case looks like as > a first option, it usually means I haven't fully grasped the idea. However, > sometimes I can't come up with anything better in a reasonable time so I have > to go with the algorithm I'm not completely sure how it behaves in real > problems. These are the moments where I do more worst case testing than > normal, I'll generate many random input cases and try to measure the worst > case of those random ones and then try an input full of those or something > like that. But remember, not knowing is a last resource, when you know the > worst case and your algorithm's complexity, you're usually in the right track > to find the intended solution. > > > > > Also, a lot of times experience is enough to know it will be ok, so I don't > do this for every problem. After you have practiced a lot, there will be many > cases where you simply know your solution will be fast enough, but this you > will only acquire with practice. Since you still need to practice a lot to be > effective and keep improving your skills, that practice will also help you > know what to do with the large cases. Even before you start thinking, just > looking at the constraints will give you an idea of what type of complexity > is expected. > > > > > Many first timers will read a problem and jump to writing the first idea that > comes to mind, this isn't necessarily the best option, sometimes spending a > little more time thinking, writing, drawing or whatever; will make the coding > easier and will discard wrong ideas early on. If you see a very successful > contestant reading a statement and starting to code right away, it usually > doesn't mean they jumped to their first idea without thought but their > experience allowed them to think it trough while reading the statement. So > they usually already know the behavior in worst case given the constrains and > are pretty confident the solution is correct without any deeper thoughts. > > > > > So it's possible to be almost sure without thinking more, but those guys have > a lot of experience. Since you're starting, I recommend thinking it trough, > find a reasonable estimate of complexity. It doesn't have to be a tight bound > or prove is tight even if it is, just good enough to convince yourself it > will be fast enough and will fit in memory for the constraints. Also, try to > prove is correct, usually you don't need a formal proof, but you should try > to sketch an idea for a proof, think why and when wouldn't be correct and > convince yourself (by logic and not faith) that it is in fact correct. If all > fails and you have no idea of it's complexity nor correctness, well, it might > be worth trying it out if your out of ideas, but this should be a last > resource. Probably looking at another problem first is a better idea than > coding in such darkness. > > > > > To wrap up, the main advice any contestant will ever give you is: practice a > lot. Solve as many problems from past contests as you can, try to solve them > yourself and if you can't check the contest analysis. However, many people > practice only writing the code, you should also practice thinking about the > solution, analyzing complexity and proving correctness. Never underestimate > the power of understanding what you will write before you write it, when you > do that, most of the times you will know how to test the worst case without a > problem. > > > > > Good luck and have fun, > Carlos Guía > > > > On Fri, Mar 28, 2014 at 10:43 AM, Shivang Gupta <[email protected]> wrote: > > > > On Tuesday, March 25, 2014 1:34:17 AM UTC+5:30, Shivang Gupta wrote: > > > Hi, > > > > > > Are the solutions judged for performance as well, in terms of lines of > > code, or execution time, or memory footprint, etc.? Has anybody ever run > > into a problem where they had to be careful about this aspect, specially > > with the large inputs? > > > > > > Thanks M.H. and Stanislav. > > > > Carlos, I really like your idea about preparing my own test files for the > large input, consisting of as many worst-case as scenarios as possible. 2 > questions: > > > > - This will have to be done programmatically, correct? I'm not even sure how > we could do it manually. > > > > - I'm not sure if there'll be enough time within the contest window to do > that (I'm new to this; and it doesn't look like a cakewalk ;). If you don't > mind me asking, do you do that during the contest or prepare some sort of > "template" beforehand and somehow use that? What about the particular > problem's description and limits to customize the test? > > > > > > Care to share more of your tricks? And thanks for such a detailed and helpful > answer! :) > > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/f0f1f644-d89c-4a92-9e1a-e4b068d17e5b%40googlegroups.com. > > > > > > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/7f3ac3ad-fc96-4ddb-a18e-914c522dfb24%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
