TopCoder-How to find a solution

Posted on | In |

Top Coder: How to find a solution

BFS

Question Features:

  • ask to find the fewest number of steps(or the shortest path) needed to reach a certain end point(state) from the strarting one
  • certain ways of passing from one point to another one offered, （state transfer）all of them having the same cost of 1(or another number)
  • Format: N*M tables, certain cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end point from the start one.
  • Such tables may represent maze,maps,cities, and other similar thing.

Time complexity:

Linear or NlogN.

Summary:

The most revealing hint about the BFS solution is the cost of 1 for any jump.

Flood Fill

What’s this? flood fill is a technique that uses BFS to find all reachable points. Difference between BFS and Flood Fill is that: minimum path/cost is not needed

This kind of problem can also be solved using DFS, but DFS might meet Stack Overflow problems.

Brute Force and Backtracking

Both of them are similar, try all possible cases and choose the best one.

Backtracking is more advanced and optimized than BF. It usually uses recursion and is applied to problems having low constrains.

Brute Force

Question Features:

  • You need to find all possible situations that satisfy a certain rule
  • The limits are very low.

Backtracking

Question Features:

  • Every possible configuration of items. These configurations should respect some given rules
  • The best configuration that respects some given rules

Dynamic Programming

Question Features:

  • Usually a DP problem has some main integer variables(N), which are neither too small, nor too big. Because its time complexity is N[^2] or N[^3] . If N is very small less than 30 then it’s likely the problem is not a DP problem.
  • Exist states and one or more ways to reach one greater state from another lower one.
  • Greater state should depend only upon lower state.

The most difficult part in identifying a DP problem statement is observing the state with the properties described above.

Maximum flow

Question Features:

  • The constraints are appropriate for a N[^3] or N[^4] solution. N should’t be greater than 500, usually it’s less than 100
  • There should be a graph with edges having capacities given, or you should be able to define/create it from data given in the statement.
  • You should be finding a maximum value of something.

Linear Programming

  • Collection of items having different costs/weights. There is a certain quantity of each item that must be achieved.
  • A list of sets
  • Goal is to find optimal combination.