Hello Aabhas, The time limits fixes the time complexity of your program (https://en.wikipedia.org/wiki/Time_complexity). In most problems (not all), the small data set accepts a worse complexity than the large one.
How to grossly evaluate if your program will finish within the time limit given? 1. Compute the complexity of your algorithm (it can depend on one input like O(N^2) or on several like O(N*P), etc. 2. Take the upper limit given by the problem of each variable and replace it in the the complexity formula to evaluate the worse case. 3. Modern computers can execute around 10^9 instructions per seconds. You can evaluate the time that your algorithm will take. It has to be way under the time limit. 4. Be careful that you don't compute the real time but a gross estimation since time complexities only give you the scale. Which means when we have a O(N^3) algorithm, it doesn't mean that it will take exactly N^3 instruction, because in big O notation we get rid of all of the constants and multipliers, a O(N^3) algorithm could actually mean that it takes about 100 * N^3 +10 000 instructions. For example if your algorithm runs in O(N^3), the upper limit of N is 1000, and the time limit is 10 seconds, you cannot say that since 1000^3 / 10^9 = 1 sec, you will finish in time because you might have a factor 10 or 100 or even more. With some experience you easily spot what is possible or not. Example: O(2^N), 1<N<100 => 2^100/10^9 = 1.2*10^21 s => will never finish in time But if for the same issue, you find a better algorithm that works in O(N^3) then: 100^3/10^9 = 0.001s which should be ok unless your constant factor is really huge (in which case you could still optimize you code, by some pruning or such) I hope this helped you. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/7f9f9593-a61c-4abc-a753-d40d1885cc2a%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
