DCL2015D | Editorial

Contest Link: Problem Link Contest

Problem Link: Practice peer section problem link

Author and Editorialist: Prateek Kumar

Problem Title : Sheldon and the mission


PREREQUISITES:

Graph algorithm- Djkstra’s algorithm (Shortest path algorithm for single source to destination) .


PROBLEM:

We are given a coordinate system. Sheldon is standing at (0,0,0,0). The problem is only concerned with the first 2 dimensions. This gives us a plane, a x-y plane.
Sheldon is standing at (0,0). He needs to get to another point on this plane, (x1,y1). He can use n intermediate points on the plane to get to the destination point.
To move S units in this coordinate system, sheldon has to spend S*S Cal of energy.
He wants the energy used to be minimum, to move from (0,0) to (x1,y1).

Your task is to find the path that uses Sheldon’s minimum energy in going from (0,0) to (x1,y1) and then print this energy.

EXPLANATION:

1.Let us form a graph out of the n points, the source (0,0) and the destination (x1,y1).

2. We store this graph having n+2 nodes and some edges in an adjacency matrix.
3. Sheldon can go from any one point to any other point, there is no restriction on that in the problem statement.
4. We form an edge from each point to every other point. The weight of the edge is the square of the distance between these points (because we want S*S[energy] to be minimum not S[ the distance]).
5. For (a,b) to (c,d), the edge weight is (a-c) * (a-c) + (b-d) * (b-d).
6. We can calculate the edge weight from any one point to any other point using brute force as the constraint on number of points is only 1000. Store all these edge weights from one node to any another node as an adjacency matrix.
7. To calculate minimum energy from single source to single destination we use the Dijkstra’s algorithm on the graph stored as adjacency matrix.



POINTS TO NOTE:

  1. There are many shortest point algorithms that can be implemented on graphs. Like, Floyd–Warshall algorithm, Bellman–Ford algorithm, Dijkstra’s algorithm and a few more.
  2. Dijkstra’s algorithm helps to find the shortest distance from a single source to a destination.
  3. Adjacency matrix stores a graph in a 2-D matrix g[][], g[i][j] is the weight of the edge from i to j.

Please add this problem to practice section.

1 Like

@rishabhprsd7, all problems of DCL2015 have been moved to practice peer section.
The link of this problem in the practice section is: http://www.codechef.com/problems/DCL2015D