Anyways, I was upsolving 2061E - Kevin and And from yesterday's round, and my friend Lilypad later upsolved the same problem. My submission (in C++) AC'd in 624ms; his (in Java) TLE'd on test 3. Curious if this was an algorithmic issue or a Java overhead issue, I tried re-implementing my C++ solution into Java, and it AC'd in 1515ms. I also tried re-implementing his Java solution into C++, and it AC'd in 1765ms. So it seemed to be a combination of both Java overhead and an algorithmic issue. But upon examination, it seemed like both of our solutions should have the same runtime— $$$O((m+n)2^m + nm\log{nm})$$$. We both tried to find some constant-factor improvements, but no dice—still TLE on test 3.

But one difference I noticed between our codes is that I like to abuse bitwise operators whenever I can, whereas he tends to use mathematical operations instead. Surely the compiler takes care of that, right? I was under the impression that GCC does this, at least. But seeing as I'm not that familiar with Java, I figured I'd test it. I changed a temp % 2 to a temp & 1 in the $$$O(m2^m)$$$ portion of the code, and lo and behold, it AC's! See 302295478 and 302296599 —the only difference is the above.

I tried making several similar changes, such as changing temp /= 2 to temp >>= 1 in the $$$O(m2^m)$$$ portion of the code, which led to an 141ms improvement, and changing limit *= 2 to limit <<= 1 in the $$$O(m)$$$ portion of the code, which led to another improvement of 31ms. I made these three changes to my C++ implementation of his initial algorithm as well, and the runtime improved from 1765ms to 1624ms. See 302291826 and 302298462 —the only differences are the three above. (The constant-factor improvements mentioned in the first paragraph further improved this to 718ms in C++—as expected, not much different from my initial submission.)

From this, I infer that, contrary to my initial belief, neither GCC nor the Java compiler optimizes mathematical operations involving powers of two to bitwise operators. If somebody has another explanation for this behavior, let me know. In any case, I would advise everybody to use bitwise operators whenever possible, as they seem to be substantially faster than their mathematical counterparts.