Điểm đầu vào lớn là gì?

Question

Trong Google Code Jam, nó cung cấp cho bạn 2 hoặc thậm chí 3 lần các điểm giải quyết cho đầu vào nhỏ nếu bạn có thể giải quyết vấn đề cho đầu vào lớn.

Nhưng, tôi không hiểu điểm này. Nếu bạn tạo một chương trình có thể xử lý bất kỳ số trường hợp dương nào, nó có thể xử lý 10 cũng như 10000 trường hợp đầu vào.

Vì vậy, khi bạn giải quyết vấn đề cho đầu vào nhỏ, bạn sẽ có thể giải quyết cho đầu vào lớn là tốt, mà không có bất kỳ thay đổi mã nào.

Tôi có thiếu gì đó không?

Answer 1

Tôi có thiếu gì đó không?

Có - bạn thiếu các giới hạn thời gian. Thông thường, một thuật toán hoạt động tốt cho các đầu vào nhỏ (giả sử thuật toán O(n^2) hoặc thậm chí là thuật toán O(2^N)) mất quá nhiều thời gian cho các đầu vào lớn hơn, đòi hỏi một cách tiếp cận khác nhau đáng kể.

Ví dụ, cách tiếp cận O(N^2) tìm kiếm một chuỗi tăng dần dài nhất có thể được mã hóa thành bốn dòng mã với một mảng duy nhất, và nó sẽ hoạt động tốt cho đầu vào của hàng trăm mục. Tuy nhiên, cách tiếp cận đó sẽ thất bại cho hàng trăm nghìn mặt hàng, đòi hỏi một cách tiếp cận nâng cao sử dụng cây hoặc tìm kiếm nhị phân. Vì cách tiếp cận khác nhau này mất nhiều thời gian hơn để viết mã, nên tự nhiên thưởng cho nó với nhiều điểm hơn.

Answer 2

Hai đầu vào có thể khác nhau trong các lĩnh vực:

1. hạn chế vấn đề đầu vào Ví dụ có thể bạn có thể giải quyết đầu vào nhỏ của một vấn đề sử dụng một thuật toán với O(n^2) phức tạp, nhưng bạn nên giải quyết đầu vào lớn sử dụng thuật toán tốt hơn với độ phức tạp O(log n).

2. Số lượng trường hợp kiểm tra Điều này cũng quan trọng trong việc chọn thuật toán.

3. Hardness trường hợp thử nghiệm Thông thường các đầu vào lớn có trường hợp kiểm tra khó khăn hơn, như điều kiện biên và vv

Answer 3

Bạn đang sai ở đó. Ngôn ngữ lập trình sử dụng các kiểu dữ liệu cụ thể để lưu trữ dữ liệu. Nhiều loại dữ liệu thường sẽ không thể chứa các giá trị dữ liệu lớn. Vì vậy, bạn cần phải sửa đổi mã của bạn để kết hợp các giá trị dữ liệu lớn này.

Ví dụ, nếu bạn đang in những con số Fibonacci sử dụng C, sau đó bạn có một mã đơn giản như thế này,

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

Mã này là đúng, nhưng bạn sẽ nhận được kết quả không chính xác cho số Fibonacci> 2 (xảy ra nếu Limit là rất lớn) kể từ int và long int là 4 byte (32 bit) trong C.

vì vậy, thuật toán chính xác của bạn bị lỗi vì sự thiếu hụt của các kiểu dữ liệu trong C.Để có giải pháp, bạn cần triển khai cấu trúc dữ liệu của riêng mình.

Answer 4

Sự khác biệt giữa Google Code Jam nhỏ & đầu vào lớn không chủ yếu là số lượng trường hợp. Trên thực tế, đầu vào lớn có thể có số trường hợp ít hơn so với trường hợp nhỏ. Nhưng các trường hợp đầu vào lớn thì khó hơn. (điều này thường có nghĩa là lớn hơn, mà giải thích tên) Nếu bạn có hai lần số lượng đầu vào, bạn có thể cần gấp đôi thời gian để tìm một giải pháp, và điều này có thể không phải là một vấn đề. Nhưng nếu đầu vào khó gấp đôi, bạn có thể cần nhiều hơn gấp đôi thời gian.