ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования
вернуться в форум

Обсуждение задачи 1119. Метро

A better solution
Послано ComebackSeason 26 мар 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
Послано Khanhhuy_19 21 янв 2018 22:18
But when Diag[i][j] get infinity sir
Re: A better solution
Послано Milos 14 июн 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
Послано PO 9 янв 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