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.

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.

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.

@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 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

@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).