Z. Extras

Competitive ProgrammingWeek 06
  1. Cycle Finding (CSES). You are given a directed graph, and your task is to find out if it contains a negative cycle, and also give an example of such a cycle. You can use this to test your Bellman-Ford implementation.
  2. Special Shortest Walk (Codechef). You are given a graph, you need to find the shortest walk in the graph from src to snk which satisfies the following property:
  3. Weight(E1) > Weight(E2) < Weight(E3) > Weight(E4)...

    and so on, where E1, E2, E3, etc. are edges on the walk from src to snk in their order of appearance. The solution here involves modifying Dijkstra's algorithm appropriately.

  4. Okabe and City (Codeforces). A non-trivial BFS application, watch out for the limits here.
  5. Frogger (UVa 534). This defines the cost, or the quality, of a path as the weight of the heaviest edge on it. One way to solve this is using a natural adaptation of Floyd-Warshall - when you describe the recursion, instead of adding up the lengths of the shortest paths, just register the maximum of the costs instead.
  6. The Tourist Guide (UVa 10099). Again a problem where the cost of the path is defined as the lightest edge on it.
  7. MPI Maelstrom (UVa 423) Another APSP practice problem.
  8. ProfTrip (Codechef). You are given cities, (bidirectional) roads, and the cost, in terms of fuel, of traveling over these roads — all sounds standard so far, except that you want to stock up on fuel and fuel prices are different in different cities. One key hint for this problem, stolen from the editorial, is to run APSP twice.