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
