*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.