interview street: Zombie March

zombie-march.cpp

// https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef int node_t;

void print(map<node_t, vector<node_t> >& ny_graph) {
	map<node_t, vector<node_t> >::const_iterator iter = ny_graph.begin();
	while (iter != ny_graph.end()) {
		node_t current_node = iter->first;
		const vector<node_t>& neighbor = iter->second;
		cout << "Node: " << current_node << " has ";
		for (int i = 0; i < neighbor.size(); i++) {
			cout << neighbor[i] << " ";
		}
		cout << endl;
		iter ++;
	}
}

void print_result(const vector<pair<node_t, double> >& result) {
	for (int i = 0; i < result.size(); ++i) {
		const pair<node_t, double>& p = result[i];
		cout << "node: " << p.first << " = " << p.second << endl;
	}
}

void rounding(vector<pair<node_t, double> >& result) {
	for (int i = 0; i < result.size(); ++i) {
		pair<node_t, double>& p = result[i];
		double rem = p.second - static_cast<int>(p.second);
		if (rem < 0.5f) {
			p.second = static_cast<int>(p.second);
		} else {
			p.second = static_cast<int>(p.second) + 1;
		}
	}
}

bool comparator(const pair<node_t, double>& p1, const pair<node_t, double>& p2) {
	return p1.second < p2.second;
}

int main(int argc, char* argv[]) {
	int totalcase;
	cin >> totalcase;
	while (totalcase) {
		int node, edge, k;
		cin >> node >> edge >> k;

		map<node_t, vector<node_t> > ny_graph;	// building block
		map<node_t, double> ny_zombie;				// building block

		int edge_tmp = edge;
		while (edge_tmp) {
			int start, end;
			cin >> start >> end;
			edge_tmp -= 1;
			ny_graph[start].push_back(end);
			ny_graph[end].push_back(start);
		}
		int node_tmp = node;
		while (node_tmp) {
			int zombie_num;
			cin >> zombie_num;
			ny_zombie[node - node_tmp] = static_cast<double>(zombie_num);
			node_tmp -= 1;
		}
		// start the k time seg processing
		while (k) {
			map<node_t, vector<node_t> >::const_iterator iter(ny_graph.begin());
			map<node_t, double> new_popu;
			while (iter != ny_graph.end()) {
				const node_t& current_node = iter->first;
				const vector<node_t>& neighbor = iter->second;
				for (int i = 0; i < neighbor.size(); ++i) {
					new_popu[current_node] += ny_zombie[neighbor[i]] / ny_graph[neighbor[i]].size();
				}
				iter ++;
			}
			// TODO: note here we copy from a map to a map
			ny_zombie = new_popu;
			k--;
		}
		vector<pair<node_t, double> > result;
		// TODO: note here we copy a map to a vector of pairs, then we can sort it
		copy(ny_zombie.begin(), ny_zombie.end(), back_inserter(result));
		sort(result.begin(), result.end(), comparator);
		rounding(result);
		for (int i = result.size() - 1, n = 0; n < 5; --i, n++) {
			const pair<node_t, double>& p = result[i];
			int out = static_cast<int>(p.second);
			cout << out << " ";
		}
		cout << endl;
		totalcase -= 1;
	}
}

Have you passed all the test cases?

When submitted, the code causes all tests TLE...T_T

Sorry guys, not noticed there are comments here. Yeah, it is TLE. But there is only minor fix needed. That is when several iterations the situation will be stablized. I have quite a period of time not coming back for this problem but I am sure the fix for it is to add a check for every iteration see if the zombies become more and more stable till some very small threshold.