Hello codeforces! Some days ago, I solved task which was to optimize $$$O(N^3)$$$, where $$$N \leq 2000$$$. There was a matrix $$$2000 \times 2000$$$. After all optimizations, the following happened:
1) a[2000][2000] got TL
2) a[2048][2048] got TL
3) a[2048][2000] got AC
I understand, that sizes like $$$2^k$$$ are faster slower because of cache and all that jazz. But I can't compare knowledge with the obtained result.
Does anyone know why this is happening?
P.S. Explained to me by the Great and Powerful 'Xellos'.
P.S.S Half of my knowledge of optimizations is [The Lord of the Chairs who wished to stay behind the scenes], I am grateful to him for that. And for the following optimization fact:
If the task requires XOR, then instead of int it is faster to use unsigned int. Why? If the number is positive, then it is stored in int with a bit equal to 1. We all know that 1 XOR 1 = 0. That is, in fact, in the XOR operation code between two ints, we will change this bit separately (informally, with 'if'). In unsigned int, we do not have a bit responsible for the sign, and no bits need to be processed separately. There is intuition! In practice, I've tested it, it speeds up the code a little. (maximum 1.4 times, average 1.1)
The question is, why do we need optimizations that speed up the code by 1.1 times? Idk, it is just very interesting. When you are bored. ,
