<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/CANxkOGaRdqSyTrkfZyd%2BQDg1mfx6pHXJV221%3DfdD9Mh01B1SeQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
