reirugan's blog

By reirugan, 7 days ago, In English

(This isn't supposed to be a serious post, but hopefully somebody finds it funny)

Intellegent: are you ok

Intellegent: i think you need some therapy man

Some of my submissions: (all of these were submitted in rated contests and AC'd, and none were intentionally written poorly)

2022C - Gerrymandering:

My submission:

2053C - Bewitching Stargazer:

My submission:

2057C - Trip to the Olympiad:

My submission:

2063D - Game With Triangles:

My submission:

If I can read it, surely it's fine... right? After all, that's all that really matters.

(I would seriously question the judgment of anybody who hires me to write code, ever.)

Full text and comments »

  • Vote: I like it
  • +88
  • Vote: I do not like it

By reirugan, 4 weeks ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +38
  • Vote: I do not like it