August 8, 2018 2018 TCO Argentina Regionals Editorial

The two easiest problems are by majk and the hardest problem is by wittyceaser.
ArmySize
For the first problem, we are given a mapping of army sizes to a word that classifies the army size. We are given a list of words describing some units fo the army, and we want to return all possible words that could correspond to the combination of the army.
Since each word describes an interval of army sizes, the addition of two intervals is still an interval, so it suffices to keep track of the smallest and largest possible army sizes.
After extracting this, we can loop through our intervals and check if they intersect with our given interval and output those army sizes in order.
In the code, I parsed out the input rather than manually type it out. It might save a few seconds and is less prone to error (i.e. mistyping numbers).
The runtime of this solution is O(n), where n is the size of the array passed in.
code:

class ArmySize:
	def getSum(self,s):
		qq = """Few: 1-4
Several: 5-9
Pack: 10-19
Lots: 20-49
Horde: 50-99
Throng: 100-249
Swarm: 250-499
Zounds: 500-999
Legion: 1000-9999999999"""
		d = {}
		li = []
		for e in qq.split("\n"):
			b = e.split(":")
			r = b[1].strip().split("-")
			d[b[0]] = (int(r[0]),int(r[1]))
			li.append(b[0])
		lo,hi = 0,0
		for x in s:
			lo += d[x][0]
			hi += d[x][1]
		def intersect(a,b,c,d):
			return intersect(c,d,a,b) if a > c else b >= c
		ans = []
		for s in li:
			if intersect(lo,hi,d[s][0],d[s][1]):
				ans.append(s)
		return ans

Knishop
For the second problem, we are given a special chess piece that can move as both a knight and a bishop, and we want to know the minimum number of moves needed to get from one square to another.
If we color the squares of the board black and white like a chessboard, then we can see that the bishop moves will keep us on the same color square, while the knight moves will flip our color. Also, if two squares are the same color, we can use at most two bishop moves to go from one to the other. Thus, this shows the answer is at most 3.
At this point, we can do some case work. It’s easier to split this based on whether the two squares are the same color or not.
If the two squares are the same color, we never have to do a knight move. This is because we need to do at least two knight moves since each knight move flips our color, but we already know that two bishop moves is sufficient to move to any other square of the same color. In this case, it’s easy to determine if we need 0 or 1 moves (we only need 0 moves if they are the same square, and 1 move if the squares lie in the same diagonal).
If the two squares are on opposite colors, we need to do an odd number of knight moves, and in particular, we only need to do exactly one knight move. Since the order of the moves doesn’t matter, we can initially try all 8 knight moves and take the minimum using the case analysis above.
The runtime of this solution is O(1) since it only considers a constant number of cases.

class Knishop:
	def color(self, x, y):
		return x%2 == y%2
	def getShortestPath(self, x1, y1, x2, y2):
		if self.color(x1, y1) != self.color(x2, y2):
			return 1 + min( self.getShortestPath(x1+dx, y1+dy, x2, y2) for dx in range(-2,3) for dy in range(-2,3) if dx**2 + dy**2 == 5 )
		if (x1, y1) == (x2, y2): return 0
		if abs(x1-x2) == abs(y1-y2): return 1
		return 2

ProbabilisticAlice
For the last problem, we are travelling randomly through a grid with teleporters, and we want to know the expected amount of times we’ll get teleported back to the starting square.
We can instead compute the probability that we’ll reach the ending square without getting teleported back. Then, we know that if the probability of success is p, the expected number of times we need to try before a success is 1/p.
To compute the probability of success, we can use dynamic programming. You can see the code for more details.
The runtime of this solution is O(R*C)

class ProbabilisticAlice:
	def computeExpectation(self,grid,pnum,pden):
		n = len(grid)
		m = len(grid[0])
		nways = [[0 for __ in xrange(m)] for ___ in xrange(n)]
		nways[0][0] = 1
		for ss in xrange(n+m-2):
			for r in xrange(ss+1):
				c = ss-r
				if 0 <= r < n and 0 <= c < m and grid[r] != 'T':
					print ss,r,c
					if r+1 >= n:
						nways[r] += pden * nways[r]
						continue
					if c+1 >= m:
						nways[r+1] += pden * nways[r]
						continue
					nways[r] += (pden-pnum) * nways[r]
					nways[r+1] += pnum * nways[r]
		return -1 if nways[n-1][m-1] == 0 else (pow(pden, n+m-2) / 1.0 / nways[n-1][m-1] - 1)