Intuitively, long as primitive type should be faster in case of multiplication or other arithmetic operations than Long as object type. However, my recent submissions to a CF problem 439B - Devu, the Dumb Guy disproved this intuition.
15307785 using long, the primitive type got TLE, whilst 15307798 using Long, the object type got Accepted, and has a large timely improvement over the previous one by like 10 times.
Does anyone have any idea why this happened?
Here is another problem :285C - Building Permutation
Auto comment: topic has been updated by safarisoul (previous revision, new revision, compare).
Primitive types use a type of sort which can go to O(N^2) in the worst case. ( I think it's quick sort).
Wrapper classes ( Objects ) for Primitive types use an O(NLogN) worst case running time algorithm for sorting. ( Merge sort ).
It has nothing to do with the Object (Wrapper class ) being faster. It's mainly because of sorting.
Before sorting, shuffle your array for the "long" submission, and you will get AC.
UPDATE: Here is AC with "long" in 156 MS and faster than Long.
http://mirror.codeforces.com/contest/439/submission/15340014
Thanks!
Auto comment: topic has been updated by safarisoul (previous revision, new revision, compare).