Google Code Jam Round 1A 2008

Problem link and source code

At first I only wanted to write down problem C, but problem B turned out to be worth noting too.

A Minimum Scalar Product

Given two $n$-dimensional vectors, permute their coordinates to minimize their scalar product ($x_1y_1+x_2y_2+…+x_ny_n$). Find that minimum.

Sort one vector ascending and the other descending.

B Milkshakes

There are $n$ products, each assigned either 0 or 1, and $m$ customers. Each customer has $T$ requirements, where “$X\ Y$” means product $X$ must be $Y$ ($Y$ is 0 or 1); each customer has at most one requirement with $Y=1$. Satisfy at least one requirement for every customer while minimizing the number of zeroes; print “IMPOSSIBLE” if it cannot be done.

Check every product currently set to 0 against each customer. If a customer already has a satisfied requirement, move on. Otherwise record its requirement for 1 and change that product to 1 on the next pass. If all relevant products are already 1 while a customer only needs 0-valued products, print “IMPOSSIBLE”.

void solve()
{
	memset(state, 0, sizeof(state));
	memset(num, 0, sizeof(num));
	memset(chan, 0, sizeof(chan));

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &num[i]);
		for (int j = 1; j <= num[i]; j++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			chan[i][j][0] = u;
			chan[i][j][1] = v;
		}
	}
	int fini = 0;
	int imp = 0;
	while (!fini)
	{
		fini = 1;
		for (int i = 1; i <= m; i++)
		{
			int k = -1;
			int j = 1;
			for (j = 1; j <= num[i]; j++)
			{
				if (state[chan[i][j][0]] == chan[i][j][1])
				{
					break;
				}
				if (chan[i][j][1] == 1)
				{
					k = j;
				}
			}
			if (j > num[i])
			{
				if (k == -1)
				{
					fini = 1;
					imp = 1;
					break;
				}
				fini = 0;
				state[chan[i][k][0]] = 1;
			}
		}
	}
	if (imp)
	{
		puts("IMPOSSIBLE");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (i > 1)
		{
			printf(" ");
		}
		printf("%d", state[i]);
	}
	printf("\n");
}

C Numbers

The statement is simple: find the last three digits of the integer part of $(3+\sqrt{5})^n$.

This is a classic problem, so it is worth recording.

Let $a=3+\sqrt{5}$, $b=3-\sqrt{5}$, and $x_n=a^n+b^n$.

$x_n$ is an integer. Moreover, since $b^n<1$, it is the first integer greater than the desired value. So it is enough to compute $x_n$.

For $x^{n+1}$, $(3+\sqrt{5})(a_n+b_n\sqrt{5})=(3a_n+5b_n)+(3b_n+a_n)\sqrt{5}$, so $a_{n+1}=3a_n+5b_n$ and $b_{n+1}=3b_n+a_n$.

This can be written in matrix form:
$$
\begin{pmatrix}
a_{n} \
b_{n+1}
\end{pmatrix}=A\begin{pmatrix}
a_{n-1} \
b_{n-1}
\end{pmatrix}=A_{n}\begin{pmatrix}
a_{0} \
b_{0}
\end{pmatrix}
$$
where
$$
A=\begin{pmatrix}
3&5 \
1&3
\end{pmatrix}
$$
Because $a_0=1$, we have $(a_0,b_0)=(1,0)$.

Too tired—I’ll finish this tomorrow.

Now fast matrix exponentiation does the job.