This program was made by 2009 Mountain View interns to share knowledge together during our internship and will be available to everyone to share also their ideas, give comments and learn more with us.
Problems discussed:
4196 - Series / Parallel Resistor Circuits
4226 - The Heart of the Country
4195 - Lawrence of Arabia
4231 - Worms
4230 - Teleport Out!
Discussions:
Problem 1: Series / Parallel Resistor Circuits
Notice that N maximum = 26 (Number of characters)
Simply our pseudo code will be:
in each iteration
visited = false
if you have a final solution with 2 nodes and 1 resistance
return resistance value
else
choose 2 nodes that are connected in parallel
if found
realize them
visited = true
choose 2 nodes that are connected in series and realize them
if found
realize them
visited = true
if visited = false
return -1
The complexity in this case won't exceed any time limits as the N is small enough.
Problem 2: The heart of the country
We need to find the set of countries that are defensible.
In the beginning for each country we'll keep 2 integers. The number of troops in the country and the total number of troops that may be available in case of an attack.
if available troops in attack < K
Add the country to a queue
For each country in queue
remove this country's troops from all adjacent countries
if any countries available troops are now < K
add to the queue
Now just add the remaining countries that aren't attacked
Problem 3: Lawrence of Arabia
We didn't reach an N^2 solution yet. Still under discussion.
Till now our obvious N^3 solution is simply keeping a 3 dimensional memo for (from, to, bombs) and just fill it using simple recursive calls.
Problem 4: Worms
This problem uses the CYK Algorithm for context free grammar.
Explaining the idea on the example
A -> BCSo basically is to try each rule and get the minimum for this rule.
B -> AC
C -> AB
ACAB
(write a better explanation and write the time complexity)
e.g.
ACAB can be BAB
then get mimimum of (B) + (AB) and () + (BAB)
Keeping a memo with us will make it comfortably run in time.
Problem 5: Teleport Out
We were hungry while reading this problem.
Several ideas came. Linear algebra? Optimization? We couldn't figure them out anyway.
We didn't get a solution for this problem and we went for dinner.
That's all. Comments are welcome to discuss unsolved problems and provide better ideas for solved problems.
Thanks,
Posts
Good problems, but I'd like to chip in my ideas on two problems.
ReplyDeleteProblem 3 Lawrence of Arabia
We define a second list called tracks that'll help us.
tracks[n] is the "value" lost when the track between depots n and n+1 is destroyed.
Here's an algorithm in ugly pythonesque.
def MVTrack(depots)
tracks = list(len(depots)-1)
for fdep in range(1, len(depots)):
for tdep in range(0, fdep):
tracks[tdep] += depots[fdep] * depots[tdep]
return max(tracks)
Now all we have to do is get the total value of the tracks and subtract the amount of value lost by destroying the track with most value.
Problem 5: Teleport Out
It's all about games theory and math. We are playing optimally so the steps are defined.
Consider that we have the "average distance to exit" which is the mean of the number of tiles you'd have to walk to get to the exit. The distance from the exit to the exit is 0, in case you wonder. Distances can also be infinite (if there is no walkable path to the exit), it isn't considered for the average.
So our logic goes as follows
Choose of all walkable tiles (north, east and south) the smallest
If there is a tie, choose anyone.
If the chosen tile's distance to the exit is greater than average:
teleport
else:
go to that tile
Now if we start in a tile that leads to a tile that has a less than average distance we know that the optimal solution is to just walk, since there's a higher risk of teleporting giving us a failure. So the distances is just the distance from the starting position to the nearest Exit.
Teleporting is a bit harder, because it's random. Let us say that there are A tiles with less than or equal distance to the exit to the average, and there are T unblocked tiles. We claim that the probability of falling in a tile were we'd want to start walking would be
p=A/T.
We want to know how many times you'd have to teleport so we use the geometric distribution. The average amount of attempts that are done is
1/p+1
Remember that 1/p is the expect amount of attempts before a success, we also have to add the successful teleport. And the distance? I'd expect it to be the average.
So if we teleport the expected optimal path would be
1/p+1+avg_dist
I'd say we need floyd's algorithm for this one. Though we only need to know the distance of the first 4 tiles to decide if we should walk or teleport, we need to know the distance to exit of all tiles to get the average and the probability of success. Floyd makes the calculations for all tiles once and we don't have to care anymore.
I think I still need to think a bit more about this, but I think I'm going in the right direccion.
Notes:
* In case of more than one exit the distance to exit is the distance to the closest exit.
* A blocked tile is one that has infinite distances to all other tiles, you could just make that row NULL in the list for optimizations (you know it's a block without iterating).
I feel I'm missing something, but I just can't see it.
redoing the pythonesque algorithm because stuff eats my whitespace
ReplyDeletedef MVTrack(depots)
{
tracks = list(len(depots)-1)
for fdep in range(1, len(depots)):
{
for tdep in range(0, fdep):
{
tracks[tdep] += depots[fdep] * depots[tdep]
}
}
return max(tracks)
}
Hi Lobo, Thanks for your comment.
ReplyDeleteWhere about the Lawrence of Arabia problem I really don't know why were we stuck into it.
I think there is no need for the memoization solution of (from, to, remaining bombs) I mean only (from, remaining bombs) are sufficient for our DP solution as simply it's linear.
In this case we'll only need to precalculate an array of [from, to] for the values between each two parts.