I've been doing some HackerRank challenges for
fun lately. Their platform has support for pretty much every language under
the sun, so users are free to use what they're most comfortable with.
Python's been my language of choice for the problem sets since they're not too
complicated (at least the warmups) and the solutions typically require only
coding up a quick function or two.
Submissions have time/memory limitations
based on language, which obviously makes sense since performance will vary
depending upon language. But I never really gave language much weight and
concentrated on making sure my algorithm had good to decent Big O computational
run time complexity (where good to decent means polynomial times of O(n2)
or O(n3) or less).
But after spending a bit of time on a particular problem
whose straightforward solution had a cubic running time and consistently went over
HackerRank's 10 second time limit (for python programs), I decided to poke around the
discussion boards and see if I could find out what I was doing wrong and how others
were approaching the problem.
To my surprise one of the moderators commented that another poster's C++ solution
was `correct' and simply required 3 nested loops over the input; pretty much exactly
what I was doing, except in a different language.
I was a bit surprised, and so I translated my python solution to vanilla C and
low and behold run times went from ~16 sec to under 1 sec. I'll now concede that
language choice does in fact matter for `hot' pieces of code or systems requiring
realtime or near-realtime performance. In such cases it probably makes sense to
optimize and/or rewrite critical pieces in a more close-to-the metal language like
assembly, C, or C++.
But obviously correctness trumps all and gathering data/metrics via profiling and
instrumentation should be done first to see which parts may benefit most from an
optimized rewrite.
For reference the programs and their associated running times are below. And here
is the problem description and one of the
sample inputs.
$ time cat input/acm_icpc_team.txt | python acm_icpc_team-v1.py
467
1
real 0m16.264s
user 0m16.176s
sys 0m0.045s
$ time cat input/acm_icpc_team.txt | python acm_icpc_team-v2.py
467
1
real 0m16.954s
user 0m16.874s
sys 0m0.045s
$ time cat input/acm_icpc_team.txt | ./acm_icpc_team
467
1
real 0m0.465s
user 0m0.461s
sys 0m0.005s
# acm_icpc_team-v1.py
import sys
if __name__ == '__main__':
line = sys.stdin.readline()
N, M = [int(n) for n in line.split()]
buf = [line.strip() for line in sys.stdin]
max_ = 0
count = 0
for i in range(N-1):
for j in range(i+1, N):
bits = 0
for k in range(M):
if buf[i][k] == '1' or buf[j][k] == '1':
bits += 1
if bits == max_:
count += 1
elif bits > max_:
max_ = bits
count = 1
print "{0}\n{1}".format(max_, count)
# acm_icpc_team-v2.py
import sys
if __name__ == '__main__':
line = sys.stdin.readline()
N, M = [int(n) for n in line.split()]
buf = [line.strip() for line in sys.stdin]
max_ = 0
count = 0
for i in range(N-1):
for j in range(i+1, N):
v = int(buf[i], base=2) | int(buf[j], base=2)
bits = 0
while v:
v &= (v-1) # clear the least significant bit set
bits += 1
if bits == max_:
count += 1
elif bits > max_:
max_ = bits
count = 1
print "{0}\n{1}".format(max_, count)
/* acm_icpc_team.c */
#include <stdio.h>
int main(int argc, char** argv)
{
int N, M;
scanf("%d %d\n", &N, &M);
char buf[500][500];
for (int i = 0; i < N; ++i) {
scanf("%500s\n", buf[i]);
}
int max = 0;
int count = 0;
for (int i = 0; i < N-1; ++i) {
for (int j = i+1; j < N; ++j) {
int bits = 0;
for (int k = 0; k < M; ++k) {
if (buf[i][k] == '1' || buf[j][k] == '1') {
bits += 1;
}
}
if (bits == max) {
count += 1;
}
else if (bits > max) {
max = bits;
count = 1;
}
}
}
printf("%d\n%d\n", max, count);
return 0;
}
