You are not logged in. Please login at www.codechef.com to post your questions!

×

SPSHORT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey

DIFFICULTY:

Medium-Hard.

PREREQUISITES:

Dijkstra Algorithm, STL uses.

PROBLEM:

You are given a graph, you need to find the shortest walk in the graph from src to snk which satisfies the following property: Let the shortest path from src to snk goes from edges $E_{1} -> E_{2} -> \cdots -> E_{k}$ , then $Weight(E_{1}) > Weight(E_{2}) < Weight(E_{3}) > Weight(E_{4}) \cdots$ and so on.

QUICK EXPLANATION:

The given problem can be solved using few modification in Dijkstra Algorithm.

EXPLANATION:

First Subproblem:

Given a graph, You need to find the shortest path in the graph from $\text{src}$ to $\text{snk}$, without any condition. This problem can be solved using Dijkstra Algorithm. In Dijkstra Algorithm, We initialize distance of the $\text{src}$ with $0$, and distance of other vertices as $ \infty$ and add $\text{src}$ into a priority queue, and we do it in following manner.

     while Q is not empty:    
          u ← vertex in Q with min dist[u]  // Source node in first case   
          remove u from Q             
          for each neighbor v of u:           // where v has not yet been removed from Q.    
              alt ← dist[u] + length(u, v)    
              if alt < dist[v]:               // A shorter path to v has been found    
                  dist[v] ← alt     
                  prev[v] ← u     
              end if   
          end for   
     end while

The given pseudo-code calculates the shortest path for each of the vertex. The shortest path for the $\text{snk}$ can be reported easily. Implementation of the Dijkstra Algorithm can be looked here.


Second Subproblem:

You are given a graph, you need to find the shortest wak in the graph from src to snk which satisfies the following property: Let the shortest path from src to snk goes from edges $E_{1} -> E_{2} -> \cdots -> E_{k}$ , then $Weight(E_{1}) < Weight(E_{2}) < Weight(E_{3}) < Weight(E_{4}) \cdots$ and so on.

In sub-problem 1, we kept a visited array. Once a node has been visited, we get the shortest path for that particular node and there is no need to visit the same vertex again. We can do it in a different manner, at the moment we are exploring vertex $v$, and pushing all neighbour of $v$ in the priority queue, we can delete all neighbouring edges of vertex $v$ just after pushing them in priority queue.

So, for solving subproblem 2, Consider we have arrived at vertex $V$ by an edge having weight $W$. when removing the vertex $V$ from the priority queue, push all neighbour $X$ of $V$ if $ W_{VX} > W$, and delete all those edges from the edge-list . This algorithm guarantees that each edge is processed at most once. hence, algorithm will terminate. We may visit a vertex more than once.

The proof of correctness of the given algorithm can be understood in following way. If we arrived at vertex $V$ with cost $C_{1}$, and later we arrived at same vertex with cost $C_{2}$, then $C_{1} < C_{2}$, cost of last explored edge in both cases are the same .

Implementation details:

Preprocess the graph by sorting outgoing edges from each node (by weight). Keep a pointer at each vertex, which will tell edges having higher weight should not be considered.

Original Problem:

To solve the original problem, where edge length is increasing and decreasing alternatively. We need to make a few changes in second subproblem. We will keep two copies of the graph in as the edge list, Call them $GL$ and $GS$. A $ \text{counter}$ should be kept, $ \text{even counter}$ will denote that we are looking for a smaller edge and $ \text{odd counter}$ will tell that we are looking for a larger edge than previous one.While we are looking for a larger edges we will delete those larger edges after pushing them in the priority queue.This deletion will happen only in larger copy of the graph which is edge-list $GL$, and similarly in other case.

The reason for keeping two copies of graph is that if edge $E$ has been taken and it is larger than last one, then later it can considered again(as shorter than last one).

Now see the reason of keeping two copies of graph, edge having length $10$ is being considered twice. During execution of the algorithm, first it will be deleted from the smaller copy of the graph i.e. $GS$(while traversing from length $200$ to $10$)and later it will be deleted from the larger copy of the graph i.e. $GL$(while traversing for length $8$ to $10$).

As the deletion can be costly or can have linear complexity, we can keep counters which will tell range in which edge list need to be considered. Time Complexity of the above approach will be $O(ElogE + ElogV)$, $O(ElogE)$ will appear due to sorting edge list, and $O(ElogV)$ due to Dijkstra.

Solutions:

Setter's solution can be found here.
Tester's solution can be found here.

asked 11 Feb '15, 00:50

amitpandeykgp's gravatar image

4★amitpandeykgp
2591322
accept rate: 0%

edited 11 Feb '16, 19:14

admin's gravatar image

0★admin ♦♦
15.9k347484508


Nice problem, too bad $O(E^2 \log E)$ solution passes tests.

link

answered 16 Feb '15, 00:23

mmaxio's gravatar image

7★mmaxio
81128
accept rate: 0%

1

Thanks @mmaxio for the appreciation on problem. I should have coded the E^2 log E solution :( . Will take care in near future for sure :)

(16 Feb '15, 01:26) devuy11 ♦♦4★

1 st test case is wrong. there is no path from 1 to 4 it should be 4 to 1 6. then only answer is possible.

link

answered 16 Feb '15, 18:40

vishalgupta94's gravatar image

1★vishalgupta94
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×932
×801
×138
×109
×98
×41
×1

question asked: 11 Feb '15, 00:50

question was seen: 2,474 times

last updated: 11 Feb '16, 19:14