Leia o enunciado antes de continuarmos.
A primeira versão que li deste problema tinha como limite máximo uma dimensão de 10000. Vamos considerar inicialmente que este era o limite.
Se eu pretender saber qual é o ciclo máximo (maxCycle) entre i e j, preciso conhecer todas as dimensões dos ciclos entre i e j incluídos. Por exemplo, o maxCycle(1,1000) precisa calcular-se 1001 ciclos, de 1 a 1000. A seguinte função calcula a dimensão de um ciclo:
static int cycleLength(int n) {
int result = 1;
while (n!=1) {
n = n%2==0 ? n/2 : 3*n+1;
result++;
}
return result;
}
Isto pode fazer-se com rapidez, mas se a seguir pedir-se maxCycle(100,500) será escusado estar a repetir cálculos que já foram realizados.
Se quisermos abordar do ponto de vista da programação dinâmica (DP) temos de decompor o problema em subproblemas, e verificar se os subproblemas partilham sub-subproblemas.
Ora, uma abordagem recursiva diz-nos o seguinte: para calcular maxCycle(1,1000) se eu souber maxCycle(1,500) e maxCycle(501,1000), eu já sei a solução (é o maior dos dois).
Nesta abordagem, porém, não há partilha de sub-subproblemas. Isto não significa que não se possa pensar numa solução com esta estratégia, mas estamos à procura de uma solução 100% DP.
Uma outra alternativa de formulação é dizer que maxCycle(1,1000) é o máximo entre maxCycle(2,1000) e maxCycle(1,999). Estes dois subproblemas partilham sub-subproblemas (por exemplo, maxCycle(2,999)).
Para concretizar esta solução precisamos de uma matriz triangular para guardar todas as combinações de maxCycle(i,j) entre 1 < i <= j < 10000.
static final int SIZE = 10000, UNKNOWN = 0;
static int[][] computeMatrix() {
int[][] sols = new int[SIZE+1][];
// make a triangular matrix, since maxCycle[i][j] is valid only for i<=j
// notice that rows and cols were flipped, since we made a lower triangular matrix
for(int i=1; i<=SIZE; i++)
sols[i] = new int[i+1]; // init to zero, ie, UNKNOWN
computeMaxCycles(SIZE, 1, sols); // compute max cycle lengths
return sols;
}
A função computeMaxCycles (que vai preencher a matriz) é invocada com pedido máximo de 1 a 10000. De reparar que damos o j no 1º argumento, dada a forma como a matriz é construída (os j's são as linhas da matriz).
static void computeMaxCycles(int j, int i, int[][] sols) {
if (i==j && sols[j][i] == UNKNOWN) // base of recursion
sols[j][i] = cycleLength(i);
else {
if (sols[j-1][i] == UNKNOWN)
computeMaxCycles(j-1, i, sols);
if (sols[j][i+1] == UNKNOWN)
computeMaxCycles(j, i+1, sols);
sols[j][i] = Math.max(sols[j-1][i], sols[j][i+1]);
}
}
Quando este processamento termina, obtemos uma matriz com todas as soluções maxCycle(i,j). O início dela (não esquecer: as linhas são os j's):
1
2, 2
8, 8, 8
8, 8, 8, 3
8, 8, 8, 6, 6
9, 9, 9, 9, 9, 9
17, 17, 17, 17, 17, 17, 17
17, 17, 17, 17, 17, 17, 17, 4
20, 20, 20, 20, 20, 20, 20, 20, 20
...
Qual é o problema desta solução? Se executarmos para o limite de 10000 obtemos esta mensagem:
Exception in thread "main" java.lang.StackOverflowError
As invocações recursivas são demasiado profundas!
Quando temos este problema é altura de procurar uma solução iterativa!
Se olharmos para a linha
sols[j][i] = Math.max(sols[j-1][i], sols[j][i+1])
reparamos que um dado valor da matriz acima é calculado pelo máximo dos valores que lhe estão acima e à direita. Isto dá-nos uma pista de como fazer uma função iterativa: começar a preencher a matrix linha a linha, de cima para baixo, e em cada linha começar pela direita, ie, pelo último elemento (que é a diagonal com os valores cycleMax(j,j)).
static void computeMaxCyclesIter(int[][] sols) {
// compute cycle length from naturals 1 to SIZE
for(int i=1; i<=SIZE; i++)
sols[i][i] = cycleLength(i);
// compute remaining solutions
for(int j=2; j<=SIZE; j++) // for each row, starting 2nd:
for (int i=j-1; i>0; i--)
sols[j][i] = Math.max(sols[j-1][i], sols[j][i+1]);
}
E agora já conseguimos calcular a matriz correctamente sem erros de runtime.
Mas...
O problema no site da UVa tem limite 1000000 (!!).
Esta segunda solução também não serve, dado que uma matriz triangular destas dimensões teria meio trilião de valores, o que rebenta com a memória disponível...
Para resolver este caso temos de largar a solução DP e tentar outra coisa (bem, isto é um tutorial de como modelar problemas com programação dinâmica mas, já que apresentámos o problema, vamos resolvê-lo).
A solução sugerida a seguir é para cada par de valores i, j, percorrer todos os valores intermédios e calcular os seus ciclos.
Mas para ser mais rápido usamos memorização, a tal técnica também usada na DP que guarda as soluções encontradas até então. Desta forma, há medida que são calculados os cycleMax(i,j), o vector de soluções vai ficando preenchido e o tempo de cálculo dos restantes valores fica progressivamente mais rápido.
Notem que temos memória para criar um vector de um milhão de posições (a matrix é que não dava).
Um exemplo:
static final int SIZE = 1000000, UNKNOWN = 0;
static int[] sols;
static int computeCycle(int k) {
if (k <= SIZE && sols[k] != UNKNOWN)
return sols[k];
int result = 1 + (k%2==0 ? computeCycle(k/2) : computeCycle(3*k+1));
if (k <= SIZE) // only keep values <= SIZE
sols[k] = result;
return result;
}
No main() fazemos as inicializações e respondemos a cada um dos pares de input:
public static void main(String[] args) {
sols = new int[SIZE+1];
sols[1] = 1;
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int i = sc.nextInt(),
j = sc.nextInt();
int from = Math.min(i, j),
to = Math.max(i, j),
result = 0;
for(int k=from; k<=to; k++)
result = Math.max(result, computeCycle(k));
System.out.println(i + " " + j + " " + result);
}
sc.close();
}
Referência: http://www.algorithmist.com/index.php/UVa_100