Just to clarify, the times are actually 4 minutes for small and 8 minutes for large. In that time you have to download the input, run your code against it and upload the output + source code.
You can read more about it here: https://code.google.com/codejam/faq.html#submissions However, other than those constrains there will be no other performance considerations, if you take 1 minute from download to upload for the large is practically the same as if you take 3 minutes. There's potentially a small difference because ties are broken on penalty time, which includes the time of your last successful submission ( https://code.google.com/codejam/faq.html#mechanics) but in general you might be better off taking a little extra time there to verify the output file and see it makes sense. For example, when expecting non-negative integers seeing some negative numbers might indicate you have overflown somewhere, you may be able to fix your solution fast within the submission window to avoid extra penalties on a small input or complete loss on a hard input. In general, if you have solved the problem using the right approach, you'll be well within those limits without crazy optimizations or extra concerns; and if you have an inefficient algorithm (when compared to the intended solution) you won't be able to generate the input no matter how many micro optimizations you do. Therefore, most of the time you should only focus on having the correct algorithm and not have other concerns in mind. Also, is good to know how much your computer can handle, for example, you might test how big of an N you can have for an O(N) algorithm, since big O hides the constants is not an exact science, but will most likely find some numbers to use as a guide. Maybe, something like N <= 10^6 works easily, N <= 10^9 is acceptable sometimes and N >= 10^12 is too slow to even consider for small inputs (remember you need to download, run and upload in the 4 minutes window); these numbers are educated guesses for me and you're extremely encouraged to try and find where your boundaries lie as those depend on your programming language of choice, computer, connection speed, etc. Since you only have one shot at large, I highly recommend you generate a test input file that could resemble the worst input file you could get. As many cases as the constrains allow and make them of the worst case possible for your algorithm. If the constrains say N <= 10^6, expect cases for which N is 10^6; the real input will probably have many non worst case scenarios in it, but a correct solution is expected to solve an input file of all worst case instances, and since you might have missed which is the actual worst-case, this will help you be in a better position. Then run your code against it and see if you'll be able to fit that running time in the 8 minutes window. You could do this for the small cases too, but I usually only do it for small inputs if I have already failed because of timeout or I'm really unsure, like when the constrains lie in my expected boundary of what is achievable. Carlos Guía On Tue, Mar 25, 2014 at 11:05 AM, Andrey Ponomarev <[email protected]>wrote: > You have some very limited time frame (2 minutes for a hard and half a > minute (?) for an easy input) to produce an output and upload it. The > problems are designed in such a way that you won't be able to produce an > output for hard input with an inefficient algorithm. So, yes, execution > time matters. > > > 2014-03-25 0:04 GMT+04:00 Shivang Gupta <[email protected]>: > > 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? >> >> -- >> 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/83edd317-3326-4920-880a-f4d34e03691f%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/CANBUrM-es-QPjPS93%3Dvu-n5qZ9jbX54%3DqrWJJrA_prDnLm69Yw%40mail.gmail.com<https://groups.google.com/d/msgid/google-code/CANBUrM-es-QPjPS93%3Dvu-n5qZ9jbX54%3DqrWJJrA_prDnLm69Yw%40mail.gmail.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/CANxkOGbpt46S0StseOJ12-4CtDOdJinWBUXAF9cJJKNX039%3Dxg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
