Editorial for Secuencias Buenas

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

Primera Subtarea:

La idea principal es DP. Definamos $dp [i]$ ~dp [i]~ como el valor máximo de la longitud de la secuencia buena cuyo último elemento es $a [i]$ ~a [i]~.

La transición de esta DP es la siguiente:

$dp[i] = max_{j<i}(dp[j]+1)$ ~dp[i] = max_{j<i}(dp[j]+1)~ tal que $gcd(a[i], a[j]) != 1$ ~gcd(a[i], a[j]) != 1~.

Se puede implementar intuitivamente en $O(n^2)$ ~O(n^2)~ lo cual es suficiente para la primera subtarea.

Segunda Subtarea:

Definamos $dp [x]$ ~dp [x]~ como el valor máximo de la longitud de la secuencia buena cuyo último elemento es $x$ ~x~.

Definamos $d [i]$ ~d [i]~ como el (valor máximo de $dp [x]$ ~dp [x]~ donde $x$ ~x~ es divisible por i).

Debe calcular $dp [x]$ ~dp [x]~ en el orden creciente de $x$ ~x~. El valor de $dp [x]$ ~dp [x]~ es (valor máximo de $d [i]$ ~d [i]~ donde $i$ ~i~ es un divisor de $x$ ~x~) $+ 1$ ~+ 1~. Después de calcular $dp [x]$ ~dp [x]~, para cada divisor $i$ ~i~ de $x$ ~x~, también debe actualizar $d [i]$ ~d [i]~ .

Este algoritmo funciona en $O (nlog(n))$ ~O (nlog(n))~ porque la suma del número del divisor de $1$ ~1~ a $n$ ~n~ es $O (nlog(n))$ ~O (nlog(n))~.

Comments

There are no comments at the moment.