ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1119. Metro

A better solution
Posted by ComebackSeason 26 Mar 2017 21:00
I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales.

Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j])
where Diag[i][j] is either 100 * sqrt(2) or Infinity.
I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently?
Re: A better solution
Posted by Khanhhuy_19 21 Jan 2018 22:18
But when Diag[i][j] get infinity sir
Re: A better solution
Posted by Milos 14 Jun 2018 17:34
I think the main cause of memory consumption is the matrix of DOUBLES. Even a simple array of doubles consumes a lot of memory.
Even for the solution involving graph and shortest paths would use 'huge' amount of memory, since you would also need a 2 dimensional array of doubles (I suppose).
I managed to solve it using 9360KB.

Edited by author 14.06.2018 17:45
Re: A better solution
Posted by PO 9 Jan 2019 20:32
a better solution is to use dynamic programming to find the longest increasing sequence of diagonals, which there are 100 at most.
min = (n + m - maxDiagonals * 2) * distance + maxDiagonals * diagonalDistance