Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
interview street: zombie march, page rank
/*
* https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
* http://www.17sotv.com/ 17sotv电影天堂
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define PAGE_RANK_ITERATION_ROUND 50
int n, m, k;
vector<int> 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()
@pdu
Owner
pdu commented

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.