A better solution

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

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.

then

```

min = (n + m - maxDiagonals * 2) * distance + maxDiagonals * diagonalDistance

```