July 19, 2018 2018 TCO Algorithm Round 3B Editorials

This is the second of round 3s of TCO18 Algorithm Round, and an additional 50 people from this round will move onto round 4, for one last chance to move onto the onsite finals. Competitors who get a non-zero positive score in either 3A or 3B can also win a t-shirt.
This round, the easy and hard are authored by [misof], while the med is by [lg5293]. The editorials are all written by [lg5293].

Easy: SquareCutout

In this problem, you are given a partial view onto an infinite grid, and your job is to determine if there could be a square in the overall image and if so, what is its smallest possible size.
First, we can determine easy cases. If there are no black squares in our view, the answer is 1.
Otherwise, there are some black squares. We can see that these must form an axis aligned rectangle in our view if they are part of a square in the bigger grid (this condition is necessary, but not sufficient).
To check if the black squares form an axis-aligned rectangle, we can compute the number of black squares, the max x-coordinate of a black square, the min x-coordinate, the max y-coordinate, and the min y-coordinate. Then, we have an axis-aligned rectangle if (max x – min x + 1) * (max y – min y + 1) = number of black squares.
Let dx = max x – min x + 1, and dy = max y – min y + 1. If dx == dy, then this is already a square, so we can just return dx.
Otherwise, WLOG, let’s say dx < dy. If we were to form a square with this partial rectangle, we must be able to extend the x-coordinates to the left or right. That means we must have this rectangle touch the left or right side of our grid. This can be checked by looking at the min x and max x coordinate
This leads to a solution that is $$O(n m)$$, which is needed to iterate through the grid squares initially. Afterwards, we just check a constant number of conditions each of which take constant time to evaluate.
This leads to the following implementation:

class SquareCutout:
        def verify(self, cutout):
                n = len(cutout)
                m = len(cutout[0])
                x1 = n
                x2 = -1
                y1 = m
                y2 = -1
                c = 0
                for i in range(n):
                        for j in range(m):
                                if cutout[i][j] == '#':
                                        c += 1
                                        x1 = min(x1, i)
                                        x2 = max(x2, i)
                                        y1 = min(y1, j)
                                        y2 = max(y2, j)
                if c == 0:
                        return 1
                dx = x2-x1+1
                dy = y2-y1+1
                if dx * dy != c:
                        return 0
                if dx == dy:
                        return dx
                if dx < dy and (x1 == 0 or x2 == n-1):
                        return dy
                if dy < dx and (y1 == 0 or y2 == m-1):
                        return dx
                return 0

Medium: TestProctoring

In this problem, we are given several geometric random variables, and we want to find the expected value of their maximum.
Let’s go over a $$O(3^n)$$ solution using bitmask dp (see https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/ for some reference).
Let $$dp[mask]$$ be the expected time that Bob needs to wait if the students still taking the test are 1 bits in $$mask$$.
To compute $$dp[mask]$$, we can iterate through a submask of mask and compute the probability that only this submask finishes the test in the next second, and use the value of dp[mask^submask] to get the expected time the rest of the students need to finish. Remember it’s also possible that none of the students don’t finish this second, so we need to be careful about looping back to our current dp state.
In particular, we want dp[mask] = (1 + sum{p[F1] * p[F2] * .. * p[Fk] *(1-p[G1]) * (1-p[G2]) .. DP[{G1, G2, ..}]}) / (1 – prob of all finished) over all ways to have {F1,F2..}+{G1,G2,..} = mask.
Where we can rewrite p[F1] * p[F2] * .. * p[Fk] *(1-p[G1]) * (1-p[G2]) into (1-p[G1])/p[G1] * (1-p[G2])/p[G2] * … * X where X only depends on mask.
So let t[{G1, G2, ..}] = (1-p[G1])/p[G1] * (1-p[G2])/p[G2] * .. * DP[{G1, G2, ..}]. Then what we want is sum{t[x] | x is a subset of mask}. We can maintain this subset sum in O(2^n * n).
See the following code for more details:

public class TestProctoring {
    public double expectedTime(int[] p, int[] q) {
        int n = p.length;
        double[] prob = new double[n];
        for (int i = 0; i < n; i++) {
            prob[i] = p[i] * 1.0 / q[i];
        }
        double[][] t = new double[n+1][1<<n];
        double[] dp = new double[1<<n];
        for (int mask = 1; mask < 1 << n; mask++) {
            double fail = 1;
            double mult = 1;
            double am = 1;
            for (int j = 0; j < n; j++) { t[j+1][mask] = t[j][mask]; if (((mask>>j)&1) == 1) {
                    t[j+1][mask] += t[j][mask^(1<<j)];
                    fail *= (1 - prob[j]);
                    mult *= prob[j];
                    am *= (1 - prob[j]) / prob[j];
                }
            }
            dp[mask] = (1 + mult * t[n][mask]) / (1 - fail);
            for (int j = 0; j <= n; j++) {
                t[j][mask] += dp[mask] * am;
            }
        }
        return dp[(1<<n)-1];
    }
}

Hard: Alchemy

In this problem, we are given a single lead coin, and several experiments that take a single lead coin and produce a certain number of lead and gold coins. We would like to determine if it’s possible to make a specific number of gold coins.
First, let’s try to transform our experiments to a form where they take in a single lead coin, and either produce a single lead coin and some gold coins, or don’t produce any lead and some gold coins. We’ll call these “one-lead” experiments and “zero-lead” experiments, respectively.
The only “zero-lead” experiments are given as input. Now, let’s see how to transform our other experiments to one-lead experiments. The only way we can reduce our lead coins is to perform zero-lead experiments. So, let’s say an experiment makes L lead coins and G gold coins. Then, we can combine this with L-1 zero-lead experiments to make a new one-lead experiment.
This can be computed by the following code snippet:

  ex = sorted(zip(lead,gold))
  make = set([0])
  curl = 0
  zero_lead = set()
  one_lead = set()
  for l,g in ex:
          if l == 0:
                   zero_lead.add(g)
                   continue
          while curl+1 < l:
                  make = set(m+s for m in make for s in zero_lead)
                  curl += 1
          one_lead.update(g+m for m in make)

At the end of this loop, one_lead will contain all the gold we can make from a single one-lead experiments, and zero_lead will contain all the gold we can make from a single zero-lead experiment.
Now, there are a few cases. If one_lead is empty, then that means we can perform at most one zero-lead experiment, so we can just check if goal is in zero_lead.
Otherwise, our strategy will look like perform some one_lead experiments several times, then perform a single zero-lead experiment.
Let’s see what values we can get from doing one_lead experiments.
Let M be the smallest non-zero value in one_lead.
We can do this by creating a graph with M nodes labeled from 0 to M-1. Then, for each element x in one_lead, we can add an edge from node i to node (i+x)%M with weight x.
The shortest path from node 0 to node i represents the smallest amount of gold we can make with that has value i mod M (and we can always add M to this number).
After computing the shortest paths by running Dijkstra, we can iterate through our last zero-lead experiment we do, and check if it works.
The value of M is bounded by the (max value of gold in experiments) * (max value of lead in experiments), which is 100^2. The number of elements in one_lead is also bounded by this number. So, we have a graph 100^2 nodes and 100^4 edges, which we run dijkstra’s on.
See the complete code below

import heapq
class Alchemy:
	def leadToGold(self, lead, gold, goal):
		return "Possible" if self.can(lead, gold, goal) else "Impossible"
	def can(self, lead, gold, goal):
		sp = sorted(zip(lead,gold))
		make = set([0])
		curl = 0
		zero_lead = set()
		one_lead = set()
		for l,g in sp:
			if l == 0:
			 	zero_lead.add(g)
			 	continue
			while curl+1 < l:
				make = set(m+s for m in make for s in zero_lead)
				curl += 1
			one_lead.update(g+m for m in make)
		if 0 in one_lead: one_lead.remove(0)
		if not one_lead:
			return goal in zero_lead
		print one_lead, zero_lead
		mod = min(one_lead)
		dist = [1 << 60 for __ in xrange(mod)]
		dist[0] = 0
		used = [False for __ in xrange(mod)]
		x = [1 << 60 for __ in xrange(mod)]
		for a in one_lead:
			x[a%mod] = min(x[a%mod], a)
		while True:
			mn = -1
			for i in xrange(mod):
				if not used[i] and (mn == -1 or dist[i] < dist[mn]):
					mn = i
			if mn == -1 or dist[mn] == 1 << 60:
				break
			used[mn] = True
			for j in xrange(mod):
				nn = (mn+j)%mod
				dist[nn] = min(dist[nn], dist[mn]+x[j])
		return any(goal >= k and (goal-k) >= dist[(goal-k)%mod] for k in zero_lead)