April 21, 2018 2018 TCO Algorithm Round 1A Editorials

This round’s author was Nickolas.

2018 TCO Algorithm Round 1A Easy: RedDragonInn

In this problem, you are playing a board game where a player distributes their coins evenly to the other players after leaving the game according to a specified scheme.
The steps in the directions are:
1) The player gives half of their money to the inn, rounded down if it is odd.
2) The player divides money as evenly into N piles, and distributes this money into N piles.
3) Any leftover coins are given to the inn.
We want to know what the maximum amount of money is that’s consistent with the directions given that in step 2 the player was able to divide their money into N piles with exactly X coins in each pile.
Now let’s work backwards.
At step two, the player needs at least N * X coins. They could have at most (N-1) extra coins (if they had N extra coins, the piles would have size
At step one, let’s suppose we want to end the step with exactly K coins. Then, we can start with at most M coins, where floor(M/2) = K. We can solve this equation to find that M = 2*K+1.
Thus, we know the maximum amount of coins that the player starts with is equal to 2*(N*X+N-1)+1, which we can print and return.
This approach takes constant time, since we are just evaluating a constant sized formula.
Sample code here:
Code

class RedDragonInn:
	def maxGold(self,n,x):
		return 2*n*(x+1)-1

2018 TCO Algorithm Round 1A Medium: Resistance

In this problem, you are playing the game of Resistance.
There are a total of S spies in the game, P people playing the game, and there are M missions. For each mission, you know the set of people that went on that mission and whether the mission passed or failed. You would like to compute the probability that each person is a spy.
Since the bounds of this problem are small, we can iterate through all ways to choose S spies out of the people and then check if this set of spies is consistent with the results of the game. Thus, this problem reduces to finding out whether the results are consistent with a fixed set of spies.
Since spies can either vote success or fail, we don’t need to look at any mission that passes since this gives us no information on where the spies could be.
Thus, it suffices to check that for each failed mission, there is at least one spy on that mission. This can be done naively as well.
If a set of spies is consistent, we can increment our total count of the valid arrangement of spies and also increment the number of consistent sets of each spy in this set by one.
At the end, if there are no valid arrangements of spies, we can return the empty array. Otherwise, we can return the sum of counts for each spy divided by the total number of arrangements to get the desired probability.
Here, we can use bitwise operations to make iterating through assignments of spies to people easier. For instance, we can loop through 0 to (2^p) – 1, and the one bits in the number correspond to the indices of the spies. The time complexity of this solution is O(2^p * p * m). We need 2^p for iterating through all the spies, and each set of spies takes O(p * m) time to check. Note, that we can speed up the 2^p factor to (p choose s) if we only iterate through bitmasks with exactly s set bits (we can do this by starting with the array {0,0,0,…,1,1,1}, where there are p-s 0s at the beginning and 1s at the end and calling next permutation on this array).
Take a look at the Python solution below:
Take a look at the Python solution below:

class Resistance:
	def spyProbability(self,P,S,missions):
		tot = 0
		counts = [0 for __ in xrange(P)]
		for spies in range(1<<P):
                # this set of spies is valid if the number of spies is exactly S and for each mission, it is a success, or there is a spy on it.
			if str(bin(spies)).count("1") == S and all(m[0] == 'S' or int(m[1:], 2) & spies for m in missions):
				tot += 1
				for i in range(P):
					counts[i] += (spies>>i)&1
		if tot == 0: return []
		return map(lambda x : 1.0 * x / tot, counts)[::-1]

2018 TCO Algorithm Round 1A Hard: DeadFish

In this problem, you start with the number zero and you want to reach the number n using only three available operations:
1) increment the number
2) decrement the number
3) square the number
4) sort the digits in non-increasing order (i.e. biggest to smallest)
n can be up to 200,000.
Here, we can think about this as a graph problem instead. For each number, we have up to four outgoing edges. However, this graph currently has an infinite number of vertices (one for each natural number). Instead, we can limit the range of numbers we need to consider from 0 to 2*n. We never need to go above 2*n for example, since we need at least n decrements to go from 2*n to n (and decrementing is the only way to decrease our number), and we can already get from 0 to n in n increments.
The time complexity of this is proportional to the number of vertices and edges in this graph, which is at most (2*n) * 4 = 8*n= O(n), thus BFS will also run in O(n) time.
You can see the Python code below for some more details:

class Deadfish:
	def shortestCode(self, N):
		dist = {}
		dist[0] = 0
		Q = [0]
		qs = 0
		while qs < len(Q):
			x = Q[qs]
			qs += 1
			s = int(''.join(sorted(str(x))[::-1]))
			for y in [x+1,x-1,x**2,s]:
				if y < 0: continue
				if y > 2 * N: continue
				if y in dist: continue
				dist[y] = dist[x] + 1
				Q.append(y)
		return dist[N]