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
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
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
It makes sense that the native Python
count is the fastest. This
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.