Что такое большой вход?

Question

В застревании в Google Code он дает вам 2 или даже 3 раза точки решения для малого ввода, если вы можете решить проблему для большого ввода.

Но, я не понимаю смысла этого. Если вы создаете программу, которая может обрабатывать любое положительное число случаев, она может обрабатывать 10, а также 10000 случаев ввода.

Итак, когда вы решаете проблему для малого ввода, вы также сможете решить проблему с большим входом, без каких-либо изменений кода.

Я что-то упустил?

Answer 1

Я что-то не хватает?

Да - вам не хватает сроков. Зачастую алгоритм, который отлично работает для небольших входов (скажем, алгоритм O(n^2) или даже алгоритм O(2^N)), занимает слишком много времени на больших входах, требуя существенно другого подхода.

Например, подход к поиску самой длинной восходящей подпоследовательности может быть закодирован в четырех строках кода с одним массивом, и он будет работать нормально для входов нескольких сотен элементов. Однако этот подход не удался бы для сотен тысяч элементов, требующих расширенного подхода, который использует дерево или двоичный поиск. Поскольку этот подход требует гораздо больше времени для кодирования, естественно вознаградить его гораздо больше очков.

Answer 2

Эти два входа могут быть разными в этих областях:

1. вход Проблема ограничения Например, может быть, вы можете решить небольшой вход проблемы с использованием алгоритма с O(n^2) сложности, но вы должны решить большой вход с использованием лучшего алгоритма с сложностью O(log n).

2. Количество проверок Это может быть важно и при выборе алгоритма.

3. Твердость тестов Обычно большой вход имеют более сложные тестовые случаи, такие как граничные условия и т.д.

Answer 3

Вы ошибаетесь. Языки программирования используют определенные типы данных для хранения данных. Часто часто тип данных не может содержать большие значения данных. Поэтому вам нужно изменить свой код, чтобы включить эти большие значения данных.

Например, если вы печатаете чисел Фибоначчи с помощью C, то у вас есть простой код как это,

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++; 
} 

Этот код является правильным, но вы получите неправильные результаты для чисел Фибоначчи> 2 (Случается, если Limit очень большой), так как int и long int составляет 4 байта (32 бита) в С.

Так ваш правильный алгоритм не удается из-за дефицита типа данных в C.Для решения вам необходимо реализовать свою собственную структуру данных.

Answer 4

Различия между Google Code Jam small & Большие входы не являются в основном количеством случаев. Фактически, большой вход может иметь меньше случаев, чем маленький. Но случаи большого ввода сложнее. (это часто означает большее, что объясняет название). Если у вас в два раза больше вводимых данных, вам может понадобиться в два раза больше времени, чтобы найти решение, и это может и не быть проблемой. Но если входы в два раза сложнее, вам может потребоваться гораздо больше, чем в два раза больше времени.