Codechef July 2013 Galactik

First, to find out where to build the bridges, I had to find out what islands/isolated pockets of planets are there. This can be done by a connected components algorithm, simple enough.

Next step, to choose which islands to build the teleporters on....I had no idea. Dug through the comments on the question page for hints. I found this big one:

qwaker00 @ 5 Jul 2013 07:19 PM

Can GFA create more than one teleport on a planet?

zwolf10003 @ 5 Jul 2013 07:59 PM

Please specify if GFA can construct more than one teleport ending on a planet.

jay_adm @ 5 Jul 2013 10:14 PM

@zwolf10003 ,@qwaker00: yes.

Hence, I could just build one end of all teleporters on the same planet. And of course, that planet would offer the cheapest rate in the galaxy for building one!

The other end would go to each individual island/component. And for each island, the best place to end the teleporter would be the cheapest planet in the island.

With the solution planned out I proceeded to code it out in Python. Code here. Worked perfectly, but when submitted:


Sigh.

Time for port over to C++ again. But before that, I made a search for the fastest I/O operation I can achieve on C++. I landed upon this blog post. Tried the last method, but found that Windows does not have getchar_unlocked(). Replaced it with getchar() instead.

The result:

	#include <iostream>
	#include <stdio.h>
	#include <vector>
	#include <stack>
	#include <map>
	#define MAX_N 100000
	#define MAX_M 1000000
	using namespace std;
	bool travelled[MAX_N] = {false};
	vector<int> islandMinCost;
	int cost[MAX_N];
	int N,M;
	//map<int, vector<int> > edges;
	vector<int> edges[MAX_N];
	void makeIslands()
	{
	for (int n=0;n<N;n++)
	{
	if (!travelled[n])
	{
	int minCost = cost[n];
	stack<int> toVisit;
	toVisit.push(n);
	while (!toVisit.empty())
	{
	int current = toVisit.top();
	//printf("current %d cost %d\n", current, cost[current]);
	toVisit.pop();
	if (travelled[current])
	continue;
	travelled[current] = true;
	if (cost[current] >= 0 && cost[current] < minCost)
	minCost = cost[current];
	if (minCost < 0)
	minCost = cost[current];
	for (vector<int>::iterator iter = edges[current].begin(); iter != edges[current].end(); iter++)
	{
	toVisit.push(*iter);
	}
	}
	islandMinCost.push_back(minCost);
	}
	}
	}
	inline void fastRead(int *a)
	{
	register char c=0;
	bool negative = false;
	while (c<33) c=getchar();
	*a=0;
	while (c>33)
	{
	if (c == '-')
	negative = true;
	else
	*a=*a*10+c-'0';
	c=getchar();
	}
	if (negative)
	*a = *a * -1;
	}
	int main()
	{
	int A,B,C;
	fastRead(&N);
	fastRead(&M);
	// printf("%d %d\n", N,M);
	for (int m=0;m<M;m++)
	{
	fastRead(&A);
	fastRead(&B);
	//printf("%d %d\n", A,B);
	A -= 1;
	B -= 1;
	edges[A].push_back(B);
	edges[B].push_back(A);
	}
	for (int n=0;n<N;n++)
	{
	fastRead(&C);
	// printf("%d\t",C);
	cost[n] = C;
	}
	makeIslands();
	int cheapestIsland = islandMinCost[0];
	int totalCost = 0;
	for (vector<int>::iterator iter = islandMinCost.begin(); iter != islandMinCost.end(); iter++)
	{
	//cout << *iter << " ";
	if (*iter < 0)
	{
	totalCost = -1;
	break;
	}
	if (*iter < cheapestIsland)
	cheapestIsland = *iter;
	totalCost += *iter;
	}
	// cout <<endl;
	if (totalCost >= 0)
	totalCost += (islandMinCost.size()-2) * cheapestIsland;
	if (islandMinCost.size() == 1)
	totalCost = 0;
	cout << totalCost;
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub

It's accepted!