HackerRank: ACM ICPC Team

Posted: 24 November 2018

Starting to do HackerRank again. The objective is to do a small problem each day at least, with the option of spilling over to the next day if it is too hard.

This question is really simple. N is less than 500, and 500C2 is in the order of O(N^2). 250000 pairs in the worst case. We can also use bit operations, which should definitely make things a lot faster. M is less than 500, which means that for each pair, the counting of the subjects they know should take O(M). We need to count the number of digits that have value 1 in the binary string. Given this, the solution can be seen as O(N^3) with N<500. Turns out that I had a TLE.

The line that caused a TLE was taking a really long time to compute the number of digits that have value 1 in the binary string. The native Python method of count was of course the fastest, followed by a simple loop, bit shifts, and then the method I initially did. More information can be found here.

It makes sense that the native Python count is the fastest. This SO explains it well. It’s written in C!

The lesson learnt here is that native methods should be used as much as possible. I did that initially, but it was all native methods combined together in an inefficient manner. I should start writing in C++. Those are the rules of ICPC after all - guaranteed solvable in C++ but not in Python 2/3.