What is the meaning of big input?

Question

In washing Google Code, it gives you 2 or even 3 times the points that solve the small input, if you can solve the problem for large input.

But I do not understand the meaning of this. If you create a program that can handle any positive number of cases, it can handle 10, as well as 10,000 cases of input.

So, when you solve the problem for small input, you can also solve for large input, without any code changes.

Did I miss something?

Answer 1

Did I miss something?

Yes - you do not have enough time limits. Often, an algorithm that works great for small inputs (for example, the O(n^2) algorithm or even the O(2^N) algorithm) takes too much time at the large inputs, requiring a significantly different approach.

For example, the O(n^2) approach for finding the longest ascending subsequence can be encoded in four lines of code with one array, and it will work fine for inputs of several hundred elements. However, this approach would not succeed for hundreds of thousands of elements requiring an advanced approach that uses a tree or binary search. Since this other approach takes a lot more time to encode, it is natural to reward it with a lot more points.

Answer 2

These two inputs may differ in the following fields:

• Input Disadvantages For example, you can probably solve a small problem input using an algorithm with O(n^2) complexity, but you should solve a big input using a better algorithm with O(log n) complexity.

• Number of test cases. This can also be important when choosing an algorithm.

• Hardness of test cases Typically, a large input has more complex test cases, such as boundary conditions, etc.

Answer 3

You are wrong. Programming languages ​​use certain types of data to store data. Often often a data type cannot contain large data values. Therefore, you need to modify your code to include these large data values.

For example, if you print Fibonacci numbers using C, then you have simple code like

 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 very large), since int and long int are 4 bytes (32 bits) in C.

Thus, your correct algorithm fails due to a lack of data type in C. For the solution, you need to implement your own data structure.

Answer 4

The differences between the small and large entries in the Google Code Jam are not basically the number of cases. In fact, a large entrance may have less than the one that it has. But cases of large input are more complicated. (this often means more, which explains the name). If you have twice as much input, you may need twice as much time to find a solution, and this may not be a problem. But if the entrances are twice as complex, you may need much more than twice as much time.