Signal Strength: Difference between revisions
imported>Plg5 Created page with "= Introduction = *midatl2008 This problem asks to find the maximum signal strength in a non-cyclic graph. There are "servers" which have gain, and a "connections" from a..." |
imported>Plg5 No edit summary |
||
| Line 8: | Line 8: | ||
Mild. The theory is pretty straightforward and doesn't necessitate a fast algorithm. | Mild. The theory is pretty straightforward and doesn't necessitate a fast algorithm. | ||
==Implementation== | ==Implementation== | ||
Moderate. Parsing the information and putting them into the relevant data structures is annoying. | |||
= Solutions= | = Solutions= | ||
== Solution | ==Solution using recursion== | ||
=== Idea === | === Idea === | ||
Create a function that will recursively determine the signal strength at any server. It will find the strength of all the parent servers, and return the strongest one. Implement memoization for speed | |||
=== How to === | === How to === | ||
Your program needs 3 layers | |||
*Initial setup layer | |||
*Case layer | |||
*Recursive layer | |||
The recursive function should be called initially on the LAST server, and should work its way up to the FIRST server. Thus, base case is when server #0 is hit. | |||
= Tags = | = Tags = | ||
*[[ | *[[DFS]] | ||
Revision as of 04:03, 25 April 2015
Introduction
This problem asks to find the maximum signal strength in a non-cyclic graph. There are "servers" which have gain, and a "connections" from a server to another, witch also have a gain.
Difficulty
Algorithmic
Mild. The theory is pretty straightforward and doesn't necessitate a fast algorithm.
Implementation
Moderate. Parsing the information and putting them into the relevant data structures is annoying.
Solutions
Solution using recursion
Idea
Create a function that will recursively determine the signal strength at any server. It will find the strength of all the parent servers, and return the strongest one. Implement memoization for speed
How to
Your program needs 3 layers
- Initial setup layer
- Case layer
- Recursive layer
The recursive function should be called initially on the LAST server, and should work its way up to the FIRST server. Thus, base case is when server #0 is hit.