Comments

• 
  

  2

  

  PedroPabloAB  commented on April 10, 2021, 11:42 p.m.

  Así mismo es. De verdad que el usuario aniervs da unas explicaciones geniales, muchas gracias por querer compartir tus conocimientos y ayudarnos a aprender más.?

• 
  

  3

  

  Osnielfc_07  commented on April 8, 2021, 11:30 a.m.

  Con el paso del tiempo me he dado cuenta que el 99% de los comentarios que hace el usuaio : //aniervs// sobre la solucion de un problema deberian ser añadidos como editorial para el problema.

• 
  

  3

  

  Bryanm  commented on Nov. 7, 2019, 8:09 p.m.

  alguien podria decirme q tipo de DP podria aplicar en este problema

• 
  

  4

  

  aniervs  commented on April 3, 2021, 3:50 a.m. ← edit 2 →

  Una plastilina representa a un subrango contiguo del arreglo original, y su valor es igual a la suma de dicho subrango. Entonces, la respuesta es la suma de un rango contiguo del arreglo original.

  Solo necesitamos saber cuáles son los rangos que pueden resultar en una sola plastilina (llamémoslos buenos). Eso lo podemos saber con programación dinámica.

  Digamos que ~dp(l, r)~ nos dice si el rango ~[l; r]~ es ~bueno~. Obviamente, los rangos de tamaño ~1~ son buenos, es decir, ~dp(i, i) = true~ para todo ~i\in [1, n]~. Veamos cómo saberlo para rangos de longitud mayor que ~1~.

  Para poder obtener el rango ~[l, r]~ como una sola plastilina podíamos:

  • Haber hecho la primera operación con el rango ~[l, k]~ y el rango ~[k + 1, r]~ para algún ~k \in [l, r-1]~. Podemos elegir un ~k~ si el rango ~[l, k]~ es bueno, el rango ~[k + 1, r]~ es bueno, y además la suma del rango ~[l; k]~ es igual a la suma del rango ~[k + 1, r]~.

  • Haber hecho la segunda operación con el rango ~[l, a-1]~, el rango ~[a, b]~ y el rango ~[b + 1, r]~ para algún par ~a, b: l < a\le b< r~. El rango ~[a, b]~ representa la plastilina intermedia, y los rangos ~[l, a-1]~ y ~[b + 1, r]~ serían las plastilinas de igual tamaño. Podemos elegir un rango ~[a, b]~ si ~[a, b]~, ~[l, a-1]~ y ~[b + 1, r]~ son los tres buenos, y además la suma del rango ~[l,a-1]~ es igual a la suma del rango ~[b + 1, r]~.

  $$\displaystyle dp(l, r) = \left[\bigvee_{a=l}^{r-1}\bigvee_{b=a}^{r-1} dp(l, a-1)\land dp(a,b)\land dp(b+1,r)\land sum(l,a-1)=sum(b+1,r)\right] \vee \left[\bigvee_{k=l}^{r-1}dp(l, k)\land dp(k+1,r)\land sum(l,k)=sum(k+1,r)\right]$$

  El operador ~\vee~ denota el or-inclusivo (|| en C++), y el operador ~\land~ denota el and (&& en C++).

  Código de ejemplo:

      for(int i = 1; i <= n; i++)
          dp[i][i] = 1;
  
      for(int t = 2; t <= n; t++){
          for(int i = 1; i + t - 1 <= n; i++){
  
              int j = i + t - 1;
  
              for(int k = i; k < j; k++){
                  dp[i][j] |= dp[i][k] and dp[k + 1][j] and sum(i, k) == sum(k + 1, j);
              }
  
              for(int a = i; a < j; a++)
                  for(int b = a; b < j; b++){
                      dp[i][j] |= dp[i][a - 1] and dp[b + 1][j] and dp[a][b] and sum(i, a - 1) == sum(b + 1, j);
                  }
  
          }
      }
  

  Ahora, esa solución tiene complejidad temporal ~\mathcal{O}(n^4)~; hay que optimizarla. La parte que necesitamos cambiar es cómo iteramos por los pares ~a, b~.

  Supongamos que ~l, r~ están fijos, a medida que aumentamos ~a~, la suma del rango ~[l, a-1]~ aumenta (ya que los elementos del arreglo son positivos). Y a medida que aumentamos ~b~, la suma del rango ~[b + 1, r]~ disminuye. Como queremos que ~sum(l, a-1) = sum(b + 1, r)~, si aumentamos ~a~, entonces ~b~ no puede aumentar. Podemos, en lugar de iterar por todos los pares ~a, b~, llevar dos punteros: ~a~ inicia en ~l + 1~, y ~b~ inicia en ~r - 1~. ~a~ se mueve de ~1~ en ~1~ hacia la derecha, y cada vez que ~a~ se mueva un paso, movemos ~b~ a la izquierda mientras ~a < b~ y ~sum(l, a - 1) > sum(b + 1, j)~.

  Una vez que ~b~ se movió todo lo requerido, y si ~a \le b~, usamos la misma fórmula.

  Como para ~l, r~ fijos, ~a~ solo se mueve hacia la derecha, y ~b~ a la izquierda, cada posición del rango ~[l, r]~ es visitada una vez por ~a~, y una vez por ~b~. Por tanto, para ~l, r~ fijos, se hacen ~O(r - l + 1)~ iteraciones. Eso quiere decir que la complejidad temporal ahora es ~O(n^3)~.