Extended 366E [Inquiry]

Revision en1, by BL7A., 2018-11-14 13:49:15

original problem
(http://codeforces.me/contest/366/problem/E)
Here we have the complexity of a way to play a song is defined as the maximum of complexities of moving between adjacent pairs of the sequence. so we can redefine it as the maximum mxDIS(s[i], s[i+1]) for each i (0 <= i < n-1) where mxDIS(n, m) is the maximum (|x1-x2| + |y1-y2|) among all cells in which a[x1][y1] = n and a[x2][y2] = m.

I've already solved the original problem and now my question is:
How can we solve the problem if the complexity of a way to play a song is defined as the sum of complexities of moving between adjacent pairs? For example, the input: 3 3 3 3
1 2 3
1 2 3
1 2 3
2 1 3
should print the answer 7.
Explanation: we will start at cell (1, 2) and move to cell (3, 1) with complexity of 3(|1-3| + |2-1|) then to cell (1, 3) with complexity of 4(|3-1| + |1-3|) so the final answer is 4 + 3 = 7.
any help would be appreciated :D and thanks in advance.

Tags 366e, inquiry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English BL7A. 2018-11-14 13:49:15 2029 Initial revision (published)