# 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 (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!

//