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 costC[j+1]-C[j] - for each
k = 1..NI find the smallesthsuch thatdisk[j]attached topin[i]intersects withdisk[h]attached topin[k]and connectuwith(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.
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 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. CodeChef: Practical coding for everyone
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).