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 costC[j+1]-C[j]
- for each
k = 1..N
I find the smallesth
such thatdisk[j]
attached topin[i]
intersects withdisk[h]
attached topin[k]
and connectu
with(pin[k], disk[h])
with the costC[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).