Instantly share code, notes, and snippets.

# pdu/ZombieMarch.cpp Created Dec 9, 2012

What would you like to do?
interview street: zombie march, page rank
 /* * https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March * http://www.17sotv.com/ 17sotv电影天堂 */ #include #include #include #include using namespace std; #define MAXN 100000 #define PAGE_RANK_ITERATION_ROUND 50 int n, m, k; vector edges[MAXN]; double val[2][MAXN]; int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m, &k); while (m--) { int i, j; scanf("%d%d", &i, &j); edges[i].push_back(j); edges[j].push_back(i); } for (int i = 0; i < n; ++i) { scanf("%lf", &val[0][i]); } k = min(k, PAGE_RANK_ITERATION_ROUND); int now = 0, next = 1; while (k--) { for (int i = 0; i < n; ++i) { val[next][i] = 0; for (int j = 0; j < edges[i].size(); ++j) { int p = edges[i][j]; val[next][i] += val[now][p] / edges[p].size(); } } now = 1 - now; next = 1 - next; } sort(val[now], val[now] + n); for (int i = n - 1; i >= n - 5; --i) { int j = int(val[now][i]); if (val[now][i] - j >= 0.5) { j++; } printf("%d ", j); } printf("\n"); for (int i = 0; i < n; ++i) { edges[i].clear(); } } return 0; }
 #!/usr/bin/python """ https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March http://www.17sotv.com/ 17sotv电影天堂 """ import sys import random import time page_rank_iteration_round = 50 def main(): # read t line = sys.stdin.readline().strip() t = int(line) while t > 0: t = t - 1 # test time # print "start: %d" % time.time() # read n, m, k line = sys.stdin.readline().strip() (n, m, k) = (int(i) for i in line.split()) # define node degree, and edges degree = [0] * n edges = [[] for i in xrange(0, n)] # read edges for i in xrange(0, m): line = sys.stdin.readline().strip() (p, q) = (int(x) for x in line.split()) degree[p] = degree[p] + 1 degree[q] = degree[q] + 1 edges[p].append(q) edges[q].append(p) # define zombie number num = [[0.0] * n for i in xrange(0, 2)] # read initial zombie number for i in xrange(0, n): line = sys.stdin.readline().strip() num[0][i] = float(line) # end input time # print "end input: %d" % time.time() # enumarate the process k = min(k, page_rank_iteration_round) (now, next) = (0, 1) while k > 0: k = k - 1 for i in xrange(0, n): num[next][i] = 0 for j in edges[i]: num[next][i] = num[next][i] + num[now][j] / degree[j] (now, next) = (1 - now, 1 - next) # sort the result num[now].sort(reverse = True) # end compute time # print "end compute: %d" % time.time() # output the result for i in num[now][0:5]: print int(round(i)), print if __name__ == '__main__': main()
 #!/usr/bin/python """ https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March http://www.17sotv.com/ 17sotv电影天堂 """ import sys import random import time page_rank_iteration_round = 50 def main(): # read t line = sys.stdin.readline() t = int(line) for _ in range(t): # test time # print "start: %d" % time.time() # read n, m, k line = sys.stdin.readline().strip() (n, m, k) = (int(i) for i in line.split()) # define node degree, and edges degree = [0] * n edges = [[] for i in xrange(0, n)] # read edges for i in xrange(0, m): line = sys.stdin.readline() (p, q) = (int(x) for x in line.split()) degree[p] += 1 degree[q] += 1 edges[p].append(q) edges[q].append(p) # define zombie number num = [[0.0] * n for i in xrange(0, 2)] # read initial zombie number for i in xrange(0, n): line = sys.stdin.readline() num[0][i] = float(line) # end input time # print "end input: %d" % time.time() # enumarate the process k = min(k, page_rank_iteration_round) now, next_ = 0, 1 for _ in range(k): for i in xrange(0, n): num[next_][i] = 0 for j in edges[i]: num[next_][i] = num[next_][i] + num[now][j] / degree[j] now, next_ = next_, now # sort the result num[now].sort(reverse = True) # end compute time # print "end compute: %d" % time.time() # output the result for i in num[now][0:5]: print int(round(i)), print if __name__ == '__main__': main()
Owner

### pdu commented Dec 9, 2012

 the cpp code can pass all the test cases, but the python code will fail the 7th test case (Time Limit Exceed), who can help to improve this python code, and give some advise on writing optimized python code.