CodeJam Minimum Scalar Produkt Problem

Question

Ich habe dieses Problem geübt, und schnell den richtigen Algorithmus herausgefunden, aber bei der Umsetzung, stieß ich auf etwas seltsam. Zuerst erkannte ich, dass ich vom Überlauf meiner Integer-Typen gebissen wurde, also begann ich mit __int64. Dann bemerke ich das nächste komische Ding. Also zuerst, hier ist mein Code ...

Also, wie Sie sehen können, habe ich zwei Berechnungen auf den beiden Vektoren. Einer benutzt STL inner_product, der andere iteriert nur von Hand. Also, was ist doof, ist, dass für die große Datenmenge in dem Problem, die inner_product-Methode zu den falschen Renditen führt, während der Hand Weg, es zu tun ist richtig. Als ich in den STL-Code trat, sah es ganz sicher so aus, als würde ein Überlauf auftreten, da die Ty-Val-Variable ein int zu sein schien, wo natürlich das Ergebnis akkumuliert ist.

Also, was ich frage mich, ist für Leute, die diese Frage mit inner_product gelöst haben, was denkst du, der Unterschied ist? Ich habe versucht, 0LL für kichern als Init-Parameter zu übergeben, und tatsächlich, es führte zu einer anderen Antwort, aber immer noch nicht die richtige. Seltsamerweise ergab es die gleiche Antwort wie die Handmethode, bevor ich die expliziten __int64-Umwandlungen hinzufügte. Es ist also mit Typen und Überlauf definitiv etwas Seltsames los, nur nicht sicher was. Unabhängig davon, ich habe die richtige Antwort für kleine und große Sets, aber ich habe gerade gesehen, dass einige Leute inner_product, wo ich es nicht zum Laufen bringen konnte. Lassen Sie mich umformulieren, dass ... inner_product für den kleinen Datensatz funktioniert, aber nicht für den großen, wo meine Handlösung sowohl für kleine als auch für große Sätze funktioniert.

Im Folgenden sind die Ausgänge für jeden Fall im Problem (10 insgesamt für den großen Datensatz). Für jeden Fall gibt es drei Ausgänge. Der erste ist mit der Hand berechnet Methode (richtige Antwort), der zweite ist mit inner_product mit einem Init von '0' (falsche Antwort), und der dritte ist mit inner_product mit einem Init von '0LL' (falsche Antwort). Darüber hinaus kompilierte ich auch als x64-Ziel, aber das Ergebnis war das gleiche.

Fall # 1: -7839202227936 Fall # 1: -886.912.736 Fall # 1: -1104693507808

Fall # 2: 7999201712083 Fall # 2: 1972606931 Fall # 2: 1127254038483

Etui # 3: -1313429236847 Fall # 3: 830.755.729 Fall # 3: -175262903407

Case # 4: -3710387739618 Case # 4: 464.004.126 Case # 4: -897 30309090

Case # 5: -3414920765916 Case # 5: -421.765.596 Case # 5: -82026144220

Case # 6: -1271937742993 Case # 6: -627.423.377 Case # 6:

-30692194449

Case # 7: -1964394407029 Case # 7: -1594352757 Case # 7: -40249058421

Case # 8: -1884282427866 Case # 8: 1208215078 Hülle # 8: -101871000026

Case # 9: -4044533757860 Case # 9: 1325434972 Case # 9: -106048747428

Fall # 10: -838.783.451.371 Fall # 10: -1264828651 Fall # 10: -44214501611

Sorry für die lange Post, aber ich dachte, dass war ein interessantes Thema.

Answer 1

CPP reference enthält eine beispielhafte Implementierung inner_product wie folgt:

... 
value = value + *first1 * *first2; 
... 

Es gibt zwei in inner_product beteiligten Typen:

1. Die Art des Akkumulators (von dem Anfangswert in bestanden abgeleitet, zB 0LL)
2. Der Typ der zu multiplizierenden Elemente (abgeleitet vom Typ der Arrays)

Also in Ihrem Fall haben Sie eine int64 für den Akku, aber nur int (was wahrscheinlich ein 32-Bit-Datentyp ist) für die Elemente. Wenn die Multiplikation stattfindet, wird das Ergebnis der Multiplikation in 32-Bit-Genauigkeit berechnet!

Daher gibt es zwei mögliche Überlauforte, einen im + und einen im *. Wenn Sie den Anfangswert ändern, wird der Akkumulator zwar repariert, aber Sie laufen immer noch Gefahr, dass die Multiplikation überläuft.

Der einfachste Weg, dies zu beheben, besteht darin, die Eingabe-Arrays zu Arrays von int64 anstelle von int zu ändern. In diesem Fall wird die Multiplikation in 64-Bit-Genauigkeit durchgeführt.