大入力のポイントは何ですか？

Question

Google Code Jamでは、大きな入力の問題を解決できる場合は、小さな入力を解決するポイントを2倍または3倍にします。

しかし、私はこの点を理解していません。正の数のケースを処理できるプログラムを作成すると、10個の入力ケースと10000個の入力ケースを処理できます。

小さな入力の問題を解決するときは、コードを変更せずに大きな入力も解決できるはずです。

何か不足していますか？

Answer 1

何か不足していますか？

はい - 期限がありません。しばしば、小さな入力（例えばO(n^2)アルゴリズム、さらにはO(2^N)アルゴリズム）でうまく動作するアルゴリズムは、入力が大きくなるには時間がかかり、実質的に異なるアプローチを必要とします。

たとえば、最長の昇順サブシーケンスを見つける手法は、4行のコードで1つの配列でコード化することができ、数百項目の入力には問題ありません。しかし、その方法は何十万もの項目で失敗するため、ツリーまたはバイナリ検索を使用する高度な方法が必要です。異なるアプローチはコード作成に時間がかかりますので、多くのポイントでそれを報酬するのは当然です。

Answer 2

これらの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 ^{フィボナッチ数について誤った結果を取得します32}（Limitが非常に大きい場合に行われる）intとlong intはC.

4バイト（32ビット）になるように、あなたの正しいアルゴリズムが原因Cのデータ型の欠乏のため失敗ソリューションについては、独自のデータ構造を実装する必要があります。

Answer 4

Google Code Jam small &の違いは、主にケースの数ではありません。実際には、大きい入力はが小さいものより小さいケースを持つかもしれません。しかし、大きな入力の場合は困難です。 （これは多くの場合、名前を説明するより大きい意味です）入力数が2倍の場合は、解決策を見つけるのに2倍の時間がかかることがありますが、これは問題ではありません。しかし、入力が2倍になると、2倍以上の時間が必要になることがあります。