my solutions for couple CSES tasks

CSES has two very similar by description tasks but with completely different solutions: "Critical Cities" (218 accepted solutions at time when I writing this) and "Visiting Cities" (381 accepted solutions)

Critical Cities

We are given an directed unweighted graph and seems that we need to find it`s dominators for example using Lengauer-Tarjan algo (with complexity O((V+E)log(V+E))

Then we could check each vertex in this dominators tree to see if it leads to target node, so overall complexity is O(V * (V+E)log(V+E))

 

This looks not very impressive IMHO. Lets try something completely different (c) Monty Python's Flying Circus. For example we could run wave (also known as Lee algorithm) from source to target and get some path with complexity O(V+E). Note that in worst case this path can contain all vertices. Lets mark all vertices in this path

Next we could continue to run waves but at this time ignoring edges from marked nodes and see what marked vertices are still reachable. For example on some step k we run wave from Vs and reached vertices Vi and Vj. We can conclude that all vertices in early found path between Vs and Vj are NOT critical cities. So we can repeat next step starting with Vj

This process can be repeated in worst case V times so overall complexity is O(V*(V+E))

 

My solution is here

 

Visiting Cities

At this time we are given an directed weighted graph and seems that simplest solution is to find all K-th shortest paths (for example with Yen algo) and make union of their vertices. Because I'm very lazy I decided to reuse some ready and presumably well-tested implementation of this algo. You can read about fabulous results here
 

After that I plunged into long thoughts until I decided to count how many paths of minimal length go through each vertex - actually we could run Dijkstra in both directions: from source to target and from target to source, counting number of paths with minimal length. And then we could select from this path vertices where product of direct counts with reverse equal to direct count on target (or reverse count on source) - it`s pretty obvious that you can`t avoid such vertices in any shortest path. Complexity of this solution is two times from Dijkstra algo (depending from implementation O(V^2) or O(V * log(V) + E * log(V)) using some kind of heap) + in worst case V checks for each vertices in first found shortest path

My solution is here

kssp library, part 2

Previous part 

I was struck by the idea of how to reduce size of graph before enumerating all K-th shortest paths. We can use cut-points. By definition if we have cut-point in some shortest path it must be visited always - otherwise you can`t reach the destination. So algo is simple

1. find with Dijkstra algo first shortest paths for whole graph
2. find all cut-points in whole graph
3. iterate over found shortest path - if current vertex is cut-point - we can run brute-force from previous cut-point till current

Results are crazy anyway - on the same test 7

• Yen: 13.86s, 29787, 3501 cycles
• Node Classification: 118.4s, 30013, 3501 cycles
• Postponed Node Classification: 104.95s, 30013, 3501 cycles
  
• PNC*: 120.33s, 30013, 3501 cycles
  
• Parsimonious Sidetrack Based: 4.66s, 29980, 3501 cycles
  
• Parsimonious Sidetrack Based v2: 4.79s, 29980, 3501 cycles
  
• Parsimonious Sidetrack Based v3: 4.85s, 29980, 3501 cycles
  
• Sidetrack Based: 4.18s, 29980, 3501 cycles
  
• Sidetrack Based with update: 4.34s, 29980, 3501 cycles
  

At this time all algos worked to completion and again gave different results...
Source code

kssp library

I`ve tried to solve CSES task "visiting cities"

Looks like you can use kind of brute-force - get 1st shortest paths, then all remained with the same cost and make union of cities in each path - nor elegant nor smart algorithm, just to estimate if this approach works at all

I remember from my university course "graph theory" about Yen`s algo to get K-th shortest path so choosed to use some ready (and hopefully well-tested) implementation - kssp library from INRIA (yep - famous place where OCaml was invented)

And then happened real madness - different algos gave me different result and moreover - they didn't match with "correct" results from CSES! Lets see what I got (all results for test 7, compilation options -O3 -DTIME -DNDEBUG):

• Yen - 470s, 30157 cities
• node classification - 4.37s, 30140 cities
• postponed node classification - 3.83s, 30140 cities
• postponed node classification with star - 3.76s, 30140 cities
• sidetrack based - consumed 13Gb of memory and met with OOM killer
  
• parsimonious sidetrack based - OOM again, perhaps bcs not enough parsimonious :-)
  

Source code