RIVPILE - approach

How did u guys solve RIVPILE? I was thinking of having n*m vertices where each vertex i,j represented reaching pile i with disk j. I used dijkstra to find min cost to reach such a vertex. But the problem was that there were O(nm) edges for each vertex, making the complexity O(m^2 * n^2 * log(nm)) which obviously got TLE.

2 Likes

I was managed to optimize this solution to O(M * N * (M + N)).

Of course we can delete useless disks and assume that
R[0] < R[1] < ... < R[M-1]

C[0] < C[1] < ... < C[M-1]

The first idea is to reduce number of edges.
For each vertex u = (pin[i], disc[j])

  • I connect it with vertex (pin[i], disk[j+1]) with the cost C[j+1]-C[j]
  • for each k = 1..N I find the smallest h such that disk[j] attached to pin[i] intersects with disk[h] attached to pin[k] and connect u with (pin[k], disk[h]) with the cost C[h].

Thus I have only O(N * M * N) edges.
Clearly my graph is equivalent to yours one, since every your edge (pin[i], disk[j]) -- (pin[k], disk[l])
is equivalent to the path
(pin[i], disk[j]) -- (pin[k], disk[h]) -- (pin[k], disk[h+1]) -- ... -- (pin[k], disk[l])
in my graph

The first my attempt was to find the smallest h by binary search and run Dijkstra.
This leads to complexity O(E * log E), with E = N * M * N.
But such solution got TLE.

Next I calculate this h for all triples in advance using method of two pointers in O(N * M * N) time. But still Dijkstra was getting me TLE.

So the final thing I did was my old idea - Dijkstra can be implemented in O(E + V * sqrt(V)) time using sqrt decomposition for array of shortest distances. In this problem this can be made even more naturally since number of vertexes is already factored as N * M with close factors in worst case.

Namely, in addition to the array of shortest distances for all pin-disc pairs, for each i I store minj[i] that minimizes shortest distance over all pairs (pin[i], disc[j]) for this i, that is
d[i][minj[i]] = min { d[i][j] : 1 <= j <= M },
where d[i][j] is the current shortest distance to vertex (pin[i], disc[j]).

Then when I need to take the vertex with smallest distance I simple iterate over this array of auxiliary minima in O(N) time. When either vertex (pin[i], disc[j]) is marked as visited or its shortest distance is updated we simple recalculate minimum for pin[i] in O(M) time by the above formula.

After making this optimization I get AC instantly, though timing is quite bad compared with others.
So I believe there exists a better approach.

9 Likes

For me the “standard” Dijkstra algorithm with heap (STL priority queue) worked in time. However, I initially inserted in the heap all the nodes intersecting (or touching) y=0 and I stopped the algorithm as soon as I extracted from the heap a node which intersected (or touched) y=W.

2 Likes

@mugurelionut Thanks for the comment i have been dying to hear someone confirm this. I just could not think of inserting all the start nodes at once into the heap :frowning: (and was checking for all the start nodes ahem) Apart from that i had the same ideas. But still i could not implement this in time. May be my implementation sucks http://www.codechef.com/viewplaintext/2383092 ?

@mugurelionut, what’s your complexity in terms of m,n?

@mugurelionut I tried doing almost the same thing using a priority queue, but apparently there were too many states and i kept running out of memory. RTE was all I could get. Did you prune the states at some point?

“Next I calculate this h for all triples in advance using method of two pointers in O(N * M * N) time. But still Dijkstra was getting me TLE.” – I got AC using this method. Coded in JAVA. http://www.codechef.com/viewsolution/2372056

1 Like

@anton_lunyov can you give me some link for the tutorial of E+V*sqrt(V) implementation of dijkstra? Thanks!

@anunay_arunav I invented it by myself. I don’t know whether it is available elsewhere. But I guess I’ve described it more or less clearly in my answer.

@coder245: The time complexity of my solution is exactly what you would expect when using Dijkstra with heaps. There are O(M * N) nodes and O(M * N^2) edges, so the theoretical time complexity is O(M * N^2 * log(M * N)). The solution presented by @anton_lunyov has a better time complexity (because of a different way of implementing Dijkstra).

@anton_lunyov Great Solution! Thanks Man! Filled with a lot of things to learn!