What is the point of Large Input?

Question

In Google Code Jam, it gives you 2 or even 3 times the points solving for small input if you are able to solve the problem for large input.

But, I don't understand the point of this. If you make a program that can handle any positive number of cases, it could handle 10 as well as 10000 input cases.

So, when you solve the problem for the small input you should be able to solve for the large input as well, without any code changes.

Am I missing something?

Answer 1

Am I missing something?

Yes - you are missing the time limits. Oftentimes, an algorithm that works fine for small inputs (say, an O(n^2) algorithm or even a O(2^N) algorithm) takes too long on larger inputs, requiring a substantially different approach.

For example, an O(N^2) approach of finding a longest ascending subsequence can be coded in four lines of code with a single array, and it would work fine for inputs of several hundred items. However, that approach would fail for hundreds of thousands of items, requiring an advanced approach that uses a tree or a binary search. Since that different approach takes a lot longer to code, it is natural to reward it with a lot more points.

Answer 2

These two inputs could be different in these fields:

1. Problem input limitations For example maybe you can solve the small input of a problem using an algorithm with O(n^2) complexity, but you should solve the large input using a better algorithm with O(log n) complexity.

2. Number of test cases This could be important too in choosing algorithm.

3. Hardness of test cases Usually the large input have harder test cases, like boundary conditions and etc.

Answer 3

You are wrong there. Programming languages use specific data types to store data. Many often the data type will not be able to hold large data values. So you need to modify your code to incorporate these large data values.

For example if you are printing the Fibonacci numbers using C, then you have a simple code like this,

long int first,second,third;
first=1;
second=1;
ct=0;
while(ct < Limit)
{
   third=first + second;
   first = second;
   second = third;
   printf("\n%d",third);
   ct++;
}

This code is correct, but you will get incorrect results for Fibonacci numbers > 2³² (Happens if Limit is very large) since int and long int is 4 bytes (32 bits) in C.

So your correct algorithm fails because of the deficiency of the data type in C. For a solution you need to implement your own data structure.

Answer 4

The differences between Google Code Jam small & large inputs are not mainly the number of cases. Actually, the large input may have less cases than the small one. But the cases of the large input are harder. (this often means larger, which explains the name) If you have twice the number of inputs, you may need twice the time to find a solution, and this may not be a problem. But if the inputs are twice harder, you may need much more than twice the time.