I was solving this problem and was getting TLE (3s) when using vector<vector<ll>> as my 2x2 matrix, then I converted it to array<ll,4> and I passed in 500 ms. Why is it so much faster?
Update: 2D vector TLE code, array AC code
Some notes: I wasn't sure why I was TLE so at first I tried using int instead of long long. I also stopped maintaining 2 versions of the matrices per node and did the flip transform mentioned in the editorial. Both of these optimizations didn't work, so I then tried converting my 2d vector to 1d array. I remember that trick working on some other matrix problem on CF that I solved from long time ago, but I can't remember which one it is.
A vector has some overhead, so for small sizes it's better to use arrays than vectors.
So I guess
array<array<ll,2>,2>will be fine as well? In other words, the speed-up is due to predefined sizing?I would guess so but you can check.
I’ve seen a lot of reds use vectors easily without getting TLE. And whenever i use them i get TLE and after changed it to array it becomes AC. how can we figure out if we get TLE by using vectors?
If you use a lot of small vectors then they are slow.
WHAT DO YOU MEAN? I've heard this answer thousand times... please replace the words (a lot of) and (small) and (slow) by integers!
That's a general rule of thumb. If you want to know numbers you can try doing some benchmarks.
Just a guess, you night be passing your vectors to functions by value instead of by reference.
Array of such small size can be allocated and manipulated on the call stack efficiently.
But vectors causes heap allocation, construction, possibly initialisation, destruction, heap deallocation. That sounds like too much overhead but isn't unless you repeatedly create vector.
Can you post your submissions? There might be something slightly specific regarding how you are using the arrays/vectors.
Sure, I updated the post.
Ah yeah, so as retrograd mentioned there will be many heap allocations and the rows of the matrix will not necessarily be next to each other. The performance hit from this is actually multiplied by the fact that you are doing matrix multiplication, which will probably incur many cache misses.
Why are the submissions to this problem are not viewable? Submissions to 1252K
I think for some ICPC contests, they set submissions and/or test cases to not-viewable.
Not sure how the latest compilers do their magic, but most of yhe times 2d data structures like
std::vector<std::vector<T>>allocate on heap. On top of that, they do not necesarily allocate contiguous memory for the elements on different rows (although it should be the case with malloc in practice). Now, heap allocations are expensive. And the overhead is seen more and more as you copy vectors arround. On the other hand, small arrays are probably kept on the stack, therefore allocation and copying is almost of zero cost, due to cache locality of the stack.If you are allocating a vector for 2x2 matrix a lot, you could declare it once and reset entries everytime you need to use it. This should be just as fast as
array. Also I think evenvector<ll>(4)should be fast enough to pass in most cases.Auto comment: topic has been updated by limabeans (previous revision, new revision, compare).