micah.stairs's blog

Longest Path Problem in Special Sparse Graph
By micah.stairs, history, 8 years ago, In English

Hello,

I have spent considerable time thinking about this NENA ICPC Regional problem from a few years ago and have not been able to come up with a solution: https://open.kattis.com/problems/hopper

I have also scoured the internet for an editorial or a solution and have not come up with anything (although there is one accepted solution on Kattis).

Any thoughts?

-Micah

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Say you have the longest path. Now, say you only look at the subgraph if it induced by the first i incides. How would that look? That could lead you to a dynamic programming solution, that is similar to that of hamiltonian / longest paths in general line graphs. If you didn't manage to solve it, I will give you some more insight to the idea. Good luck!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply! But how would this work in a case like:

    [1,9,2,8,3,7,4,6,5], D=2, M=1

    Because we're not necessarily processing the array from left to right. We might go back and forth a few times.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      If you consider a prefix [1..i] of the sequence, any induced subgraph of a path will be composed of a number of disjoint paths (components). Each of these paths have an entry-point and an exit-point. Given the constraints, these cannot be smaller than i - d (because they have to be connected, either now, or in the "future"). There can also be a starting path (it has no entry point) or an end path (with no exit point). A state in your dp should somehow code the entry and exit points of all the paths. Now every new node could either form a new path, unite two paths, or be appended to an existing path. Note that, by using some symmetries (given the fact that the graph is undirected), you can reduce the number of states (paths encoding) by a rather large factor. You would also have to find the transitions of your dp function, which could be tricky, depending on the implementation.

      → Reply