Comments

• 
  

  0

  

  aniervs  commented on Feb. 23, 2019, 1:59 a.m. ← edit 2 →

  El problema 1B es muy parecido al problema Barricades que salió en la competencia Algorithm Engagements 2007, este aparece en el libro Looking for a Challenge? The Ultimate Problem Set from the University of Warsaw Programming Competitions.

• 
  

  1

  

  DGC  commented on Feb. 18, 2019, 8:31 p.m. ← edited →

  oci19day1b

  En este problema hay soluciones que son ~O(K^2/2*N)~ alrededor de ~5*10^8~ operaciones y dan 100 puntos, ¿Si el jurado quisiera permitir estas no deberían poner rangos más pequeños o si la solución esperada era ~O(N^2)~ poner rangos como ~N = K = 5000~ por ejemplo?

• 
  

  -2

  

  aniervs  commented on Feb. 23, 2019, 1:52 a.m.

  Cuáles son esas soluciones que dices? He aquí la mía: rooteamos el árbol en un nodo cualquiera, llevar una Dp[u][j] que dice el costo máximo de un subárbol de tamaño j usando los nodos en el subárbol rooteado en u. Entonces, para computar cada Dp[u][j] se hace como una especie de mochila sobre los hijos de u. Calcular todas las dp[u][] toma tiempo O(~tree[u]^2~), donde tree[u] denota el tamaño del subárbol rooteado en u. Aplicando lo anterior a la raíz del árbol, nos queda el algoritmo en O(~n^2~)

• 
  

  -1

  

  DGC  commented on Feb. 25, 2019, 11:10 p.m.

  No me refería a tu solución, solo decía que puede que alguien con una solución ~O(n^3)~ crea que es muy lenta, mientras hay al menos una solucion con 100 pts así. El problema tiene una demostración corta y simple de que la complejidad final es ~O(n^2)~, "una especie de mochila ... y aplicando esta te queda ~O(n^2)~" eso no dice nada, ni siquiera es un intento de demostración.

• 
  

  -1

  

  aniervs  commented on Feb. 27, 2019, 12:23 a.m.

  Entiendo. Cuando estamos en un nodo u de grado k, donde sus hijos son v1,v2,...,vk, al procesar el hijo v_i hacemos tree[v_i]tree[u] operaciones, entonces calcular las dp[u][] toma tiempo tree[u](tree[v1]+tree[v2]+...+tree[vk])=tree[u]*tree[u]. Espero que esta demostración si sea válida. Disculpa si me expresé mal.

• 
  

  1

  

  DGC  commented on March 1, 2019, 4:46 p.m.

  ~tree[u]*(tree[v1]+tree[v2]+...+tree[vk])=tree[u]*tree[u]~ no dice nada, eso siempre se cumple y no tiene nada que ver con el problema.

  Suponiendo que ~tree[u]~ es el tamaño del subárbol de el nodo ~u~, la idea para demostrarlo es la siguiente:

  Calcular ~dp[u][]~ requiere ~tree[v_1] + tree[v_1]*tree[v_2] + (tree[v_1]+tree[v_2])*tree[v_3] + ... + (tree[v_1]+tree[v_2]+...+tree[v_{k-1}])*tree[v_k]~ operaciones adicionales, si asumimos que el costo de calcular todas las dp en el subárbol de un nodo ~v_i~ toma tiempo ~O(tree[v_i]^2)~ lo cual es verdad en las hojas, usando esto como caso base se puede demostrar por inducción matemática mediante un análisis combinatorio en el paso inductivo que el costo de calcular ~dp[u][]~ es ~O(tree[u]^2)~.

• 
  

  0

  

  aniervs  commented on March 2, 2019, 2:40 a.m.

  Verdad. Era una pura estupidez lo que estaba diciendo.

• 
  

  5

  

  aniervs  commented on Feb. 12, 2019, 9:46 p.m.

  Deberían ser más cuidadosos a la hora de colocar los casos de prueba, porque aunque los arreglen luego de la competencia, los competidores son afectados, pues tratan de buscar un error inexistente en su solución, impidiéndoles dedicarse a otros problemas.

• 
  

  0

  

  Albe  commented on Feb. 13, 2019, 2:42 a.m.

  Yo fui penalizado por tal error ya q estuve 3 horas programando una posible solucion para ese problema donde se solaparan las soluciones, ya q estaba mal la redaccion y eso me penaliza en el concurso en general

• 
  

  0

  

  luismo  commented on Feb. 13, 2019, 3:35 a.m.

  En que problema te ocurrió ?? Fue corregida la redacción ??

• 
  

  0

  

  oci19vc11  commented on Feb. 13, 2019, 1:45 p.m.

  En el tercer problema el decia bbababab y aun esta mal!!!

• 
  

  4

  

  luismo  commented on Feb. 13, 2019, 1:09 a.m.

  Completamente de acuerdo, soy responsable por algunos de los fallos, y pido mis más sinceras disculpas. Mañana no debe ocurrir tal efecto.

• 
  

  1

  

  BrayanD  commented on Feb. 13, 2019, 12:24 a.m.

  Concuerdo contigo

• 
  

  -1

  

  Primervirgen  commented on Feb. 12, 2019, 8:14 p.m.

  Estaban Duros!!!

• 
  

  2

  

  oci19lh3  commented on Feb. 12, 2019, 5:06 p.m.

  suerte a todos

• 
  

  -2

  

  oci19lt1  commented on Feb. 12, 2019, 1:50 p.m. ← edited →

  "Éxitos para todos, la suerte es para los perdedores."

• 
  

  -1

  

  oci19cf10  commented on Feb. 12, 2019, 1:40 p.m.

  Exitos a todos los participantes!!

• 
  

  -6

  

  Rexed02  commented on Feb. 12, 2019, 1:06 p.m.

  A raspar puntos!!!!!

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  1

  

  jorgeAMM  commented on Feb. 5, 2019, 7:41 p.m.

  Buena_Suerte!!!!

  Ready desde Mayabeque!!!

• 
  

  -1

  

  Alvaro  commented on Feb. 5, 2019, 1:05 p.m.

  GLHF