Link to the problem on UVa Online Judge
Link to the pdf version
In my opinion this is a classic Dynamic Programming problem which can be solved with a top-down approach. The most important part of this problem is that it explicitly states that there are no cyclic dependencies between cells, a key part in a dynamic programming solution.
The fact that we can solve a problem with a top-down approach shows that there are no cyclic dependencies between subproblems. Actually it's a DAG, Directed Acyclic Graph, in which larger subproblems are dependent on smaller subproblems.
The tricky part which requires more attention is parsing input and calculating row number and column number correctly.
Link to the pdf version
In my opinion this is a classic Dynamic Programming problem which can be solved with a top-down approach. The most important part of this problem is that it explicitly states that there are no cyclic dependencies between cells, a key part in a dynamic programming solution.
The fact that we can solve a problem with a top-down approach shows that there are no cyclic dependencies between subproblems. Actually it's a DAG, Directed Acyclic Graph, in which larger subproblems are dependent on smaller subproblems.
The tricky part which requires more attention is parsing input and calculating row number and column number correctly.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
private static int convertToColumn(String s) { | |
int result = 0; | |
int p26 = 1; | |
for (int i = s.length() - 1; i >= 0; i--) { | |
result += p26 * (s.charAt(i) - 'A' + 1); | |
p26 *= 26; | |
} | |
return result - 1; | |
} |
This is my code for converting a string like A, AAB, AZ ... to column number.
The rest is a simple function which memoizes the answer to each cell, if it has been calculated before, it doesn't calculate it again and only returns the result.
The rest is a simple function which memoizes the answer to each cell, if it has been calculated before, it doesn't calculate it again and only returns the result.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
private static int calc(int i, int j) { | |
if (mat[i][j] != -1) return mat[i][j]; | |
if (input[i][j].charAt(0) != '=') { | |
mat[i][j] = Integer.valueOf(input[i][j]); | |
return mat[i][j]; | |
} | |
String[] all = input[i][j].split("[=+ ]"); | |
mat[i][j] = 0; | |
for (String s : all) { | |
if (s.length() > 0) { | |
int firstDigit = indexOfFirstDigit(s); | |
int colIndex = convertToColumn(s.substring(0, firstDigit)); | |
int rowIndex = Integer.parseInt(s.substring(firstDigit)) - 1; | |
mat[i][j] += calc(rowIndex, colIndex); | |
} | |
} | |
return mat[i][j]; | |
} |