Stop
On Sat, Mar 29, 2014 at 12:46 PM, <[email protected]> wrote: > Today's topic summary > > Group: http://groups.google.com/group/google-code/topics > > - Code performance concerns <#1450d724993e640a_group_thread_0> [2 > Updates] > - Maintaining Max/Min Heap to get a sorted > array<#1450d724993e640a_group_thread_1>[1 Update] > > Code performance > concerns<http://groups.google.com/group/google-code/t/fbad932ab9884bd5> > > Shivang Gupta <[email protected]> Mar 28 10:43AM -0700 > > 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! :) > > > > > Carlos Guia <[email protected]> Mar 28 01:20PM -0700 > > <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 > > > > Maintaining Max/Min Heap to get a sorted > array<http://groups.google.com/group/google-code/t/f6e501843f806593> > > Leopoldo Taravilse <[email protected]> Mar 28 03:23PM -0300 > > http://en.wikipedia.org/wiki/Heapsort > > > > > > -- > 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/001a11c2f4764afabe04f5bc86e3%40google.com<https://groups.google.com/d/msgid/google-code/001a11c2f4764afabe04f5bc86e3%40google.com?utm_medium=email&utm_source=footer> > . > 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/CAKMwf80PVvfeS%2BM-qvExoizZrTV4fjD%3Dd-Hs-VH2gMr15KxTog%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
