Desafío Ryckeboer #3: "Buen Kilo de Pan Flauta"

[Guty]

Desafío Ryckeboer 3: “Buen Kilo de Pan Flauta”

Enunciado

La empresa de pan Flauta quiere sacar a la venta un nuevo envase que contiene un kilo de pan (curiosamente, no se trata de pan flauta sino de pan lactal). Como parte del equipo de diseño de envases, les encargaron diseñar una pirámide nutricional acorde a los requerimientos de la empresa. La pirámide nutricional será representada por una grilla triangular de lado L, que es un triángulo equilátero dividido en triángulos unitarios (o sea, triángulos equiláteros de lado uno) trazando paralelas a los lados del triángulo mayor.

Por ejemplo, en la siguiente figura se ven grillas para L = 4, 5, y 6.

Se sabe que hay K tipos de alimentos distintos para mostrar en la pirámide nutricional, cada uno de los cuales será representado por una sección horizontal de la misma. Una sección horizontal es la porción de la pirámide que queda entre dos rectas paralelas a la base de la grilla, trazadas de manera tal que solo toquen triángulos unitarios en sus bordes, sin atravesarlos. En el gráfico a continuación se pueden ver sombreadas tres secciones horizontales válidas de una grilla con L = 5.

Es importante que las K secciones en que quede dividida la pirámide se puedan ver bien, y para ello es necesario que cada una esté conformada por muchos triángulos unitarios. Sin embargo, como el tamaño de la grilla está fijo, hay una cantidad limitada de triángulos unitarios para repartir entre las K secciones. Para asegurarse de que ninguna sección quede desproporcionadamente pequeña, les han pedido que averigüen cuál es la máxima cantidad de triángulos unitarios que pueden conformar la sección más pequeña, si se eligen las secciones óptimamente.

Por ejemplo, a continuación se muestran tres formas distintas de dividir grilla de lado L= 5 en K = 3 secciones.

En la grilla de la izquierda hay dos secciones con 9 triángulos unitarios cada una, teniendo la otra sección 7 triángulos unitarios. En la grilla central, las secciones tienen 12, 9 y 4 triángulos unitarios, mientras que en la grilla de la derecha tienen 16, 8 y 1. De estas tres formas de elegir las secciones horizontales, la mejor es entonces la de la grilla de la izquierda, dado que en ella la sección más pequeña tiene 7 triángulos unitarios, mientras que en la grilla central y de la derecha las secciones más pequeñas tienen 4 y 1 triángulos unitarios, respectivamente. De hecho, la elección de las secciones representada por la pirámide de la izquierda de la figura es óptima, ya que no hay ninguna otra elección posible de K = 3 secciones horizontales en la que la más pequeña de ellas tenga más de 7 triángulos unitarios.

Entrada

Vienen L (lado del triángulo) y K (cantidad de secciones), que cumplen 1 \leq K \leq L \leq 10^6

Salida

Un entero que representa la máxima cantidad de triángulos unitarios que pueden conformar la sección horizontal más pequeña

Link

Link al problema original (en juez SPOJ)
(el enunciado en el link está en Inglés)

Actualización

Acá van dos pistas. Ambas bastante reveladoras (creo).

Pista 1

Pensar primero el siguiente problema: “¿Se puede completar una pirámide de lado L y K secciones si pedimos que cada una de las secciones tenga al menos T triangulitos?”

Pista 2

Ver la Pista 1 y ver cómo hacer encajar una búsqueda binaria en todo esto. ¿Sobre qué podemos hacer una búsqueda binaria?

[michaelszer]

Buenas,

Se me ocurrio primero asignarle a las lineas horizontales los valores mas bajos posibles, esto sería que por ejemplo en el caso de L = 5 y K = 3, K1 = 1 K2 = 3 K3 = 5. Finalmente le vas agragando una linea, un nivel al mas chico, hasta que se hayan utilizado todas las lineas.

Paso por paso para L = 5 y K = 3:

Asignas los valores como se menciono anteriormente: K1 = 1 K2 = 3 K3 = 5.

1. K1 = 4 K2 = 5 K3 = 7.

2. K1 = 9 K2 = 7 K3 = 9.

Al ser el segundo paso y K = 3 quiere decir que todos los niveles en la piramide fueron utilizados.

Código

#include <iostream>
#include <vector>

using namespace std;

vector<unsigned long long> lineas, nivelFinal, nivelBajo;
int k, h, recorrido = 0;
	
int lower(){
	
	int _lower = -1;
	unsigned long long _lowerNum = 0;
	
	for(int i = 0; i < h; i++){
		
		if(_lower < 0){
			_lower = i;
			_lowerNum = lineas.at(i);
		}
		
		if(lineas.at(i) < _lowerNum){
			_lower = i;
			_lowerNum = lineas.at(i);
		}
	}
	
	return _lower;
}

void sumLevels(int line){
	
	while(line < h){
		
		lineas.at(line) -= ( nivelBajo.at(line) * 2 ) + 1;
		nivelBajo.at(line)++;
		
		nivelFinal.at(line)++;
		lineas.at(line) += ( nivelFinal.at(line) * 2 ) + 1;
		
		line++;
	}
}

void addLevel(int line){
	
	nivelFinal.at(line)++;
	lineas.at(line) += ( nivelFinal.at(line) * 2 ) + 1;
}

int main(){
	
	cin >> k >> h;
	
	int largo = 1;
	for(int i = 0; i < h; i++){
		
		lineas.push_back(largo);
		nivelFinal.push_back(i);
		nivelBajo.push_back(i);
		
		largo += 2;
		recorrido++;
	}
	
	while(recorrido < k){
		
		// Consigue la linea mas chica de todas
		int n = lower();
		
		// Sube a todos las lineas siguientes a la mas chica un nivel
		sumLevels(n+1);
		
		// Le agrega la proxima linea a la mas chica
		addLevel(n);
		
		recorrido++;
	}
	
	cout << lineas.at(lower());
}

[Guty]

Si no entiendo mal, lo que hacés es lo siguiente:

• Primero que nada, ver que en el nivel i hay 2i+1 triangulitos (indexado en 0 desde la cúspide de la pirámide a la base)
• Generás K bolsas ordenadas, una correspondiente a cada sección. Las voy a llamar C_j en vez de K_j para evitar confusiones.
• Inicialmente, cada sección se corresponde a cada uno de los primeros niveles, entonces la bolsa C_j tiene 2j+1 triangulitos, formados cada uno por un nivel de exactamente 2j+1 triangulitos.
• A partir de ahora comenzás a iterar desde el nivel K+1 hasta L y te fijás en cada paso cuál es la bolsa que menos triangulitos tiene, y para todas las bolsas que le siguen, movés para atrás el nivel más chico. Y además agregás la cantidad de triangulitos del nivel en cuestión a la última bolsa.

Si es así, creo que no es correcto . Fijate qué pasa por ejemplo cuando L = 8 y K = 2. Si no entiendo mal, los pasos a seguir de ese algoritmo sería:

(Arriba de cada caja es el número de iteración y arriba de cada flecha la cantidad de triangulitos en el nivel que se agrega (en amarillo). Además, en verde, la suma de cada bolsa)

\overset{\color{lightCoral}{0}}{\boxed{C_1 = {\color{lime}{1}}, [1], C_2 = {\color{lime}{3}}, [3]}} \overset{\color{yellow}{5}}{\longrightarrow} \overset{\color{lightCoral}{1}}{\boxed{C_1 = {\color{lime}{4}}, [1,3], C_2 = {\color{lime}{5}}, [5]}} \overset{\color{yellow}{7}}{\longrightarrow} \overset{\color{lightCoral}{2}}{\boxed{C_1 = {\color{lime}{9}}, [1,3,5], C_2 = {\color{lime}{7}}, [7]}} \overset{\color{yellow}{9}}{\longrightarrow}

\overset{\color{yellow}{9}}{\longrightarrow} \overset{\color{lightCoral}{3}}{\boxed{C_1 = {\color{lime}{9}}, [1,3,5], C_2 = {\color{lime}{16}}, [7,9]}} \overset{\color{yellow}{11}}{\longrightarrow} \overset{\color{lightCoral}{4}}{\boxed{C_1 = {\color{lime}{16}},[1,3,5,7], C_2 = {\color{lime}{20}}, [9,11]}} \overset{\color{yellow}{13}}{\longrightarrow}

\overset{\color{yellow}{13}}{\longrightarrow} \overset{\color{lightCoral}{5}}{\boxed{C_1 = {\color{lime}{25}}, [1,3,5,7,9], C_2 = {\color{lime}{24}}, [11,13]}} \overset{\color{yellow}{15}}{\longrightarrow} \overset{\color{lightCoral}{6}}{\boxed{C_1 = {\color{lime}{25}}, [1,3,5,7,9], C_2 = {\color{lime}{39}}, [11,13,15]}}

Y por lo tanto la respuesta del algoritmo sería 25. Pero podemos conseguir 28 con:

• C_1 = {\color{lime}{36}}, [1,3,5,7,9,11]
• C_2 = {\color{lime}{28}}, [13,15]

Por lo tanto el algoritmo no sería correcto. Además (aunque menos importante que lo anterior), fijate que la implementación más simple de esta idea toma tiempo cuadrático, y las cotas del problema son 1 \leq K \leq L \leq 10^6.

Ya que estoy, en el código falta un fin de línea, ya sea un \texttt{endl} o \texttt{"\n"} al imprimir la respuesta.

Así que a seguir intentando

En unos días se viene una pista dos pistas

[michaelszer]

Se me ocurrió una solución complejidad(n), no la probé con muchos casos pero creo que anda bien .

Nos fijamos el promedió, y en base a eso empezamos a rellenar cada linea, empezando desde la parte de abajo, hasta que ( contenido en la linea >= promedio ). Después pasamos a la siguiente, hasta que recorrido (variable con la que recorremos los escalones en la pirámide) >= L .

Si estamos recorriendo la pirámide y nos quedan la misma cantidad de niveles por recorrer que lineas pendientes para asignar, asignamos cada linea a cada nivel restante.

Código

#include <iostream>
#include <vector>

using namespace std;

vector<unsigned long long> lineas;
unsigned int k, l, recorrido = 0;
unsigned long long promedio;

int main(){
	
	cin >> l >> k;
	
	promedio = ( (l*(l-1)) + l) / k;
	
	lineas.push_back(0);
	
	while(recorrido < l){
		
		if(k - lineas.size() == l - recorrido){
			
			while(recorrido < l){
				lineas.push_back((recorrido*2) + 1);
				recorrido++;
			}
			break;
		}
		
		if(lineas[lineas.size()-1] >= promedio){
			lineas.push_back(0);
		}
		
		lineas[lineas.size()-1] += (recorrido*2) + 1;
		
		recorrido++;
	}	
	
	unsigned int minNumber = 0;
	
	minNumber = lineas[0];
	
	for(unsigned i = 0; i < lineas.size(); i++){
		if(minNumber > lineas[i]){
			minNumber = lineas[i];
		}
	}
	
	cout << minNumber << endl;
}

[Guty]

No creo estar entendiendo bien lo que decís, pero no me convence .

No veo una intuición clara de por qué esa elección de llenar en base al promedio sea correcta. (Estoy suponiendo que le estás llamando “promedio” a \frac{L^2}{K} que sería la cantidad de triangulitos totales dividido la cantidad de secciones)

Fijate que actualicé el primer post y puse un par de pistas que guían a la solución esperada del problema.

Actualización:

Fijate que en el caso de L = 6 y K = 2 el código responde 11 cuando debería responder 16.

[sebach]

Siguiendo las pistas de Guty en su “Actualización”:

Pista 3

Si sabemos que podemos formar las secciones de manera que la más chica tenga M triangulitos, tiene sentido ver si podemos armar las secciones para un número menor a M?

Si no se entiende alguna pista, o se les ocurrió alguna idea y no saben cómo seguir, pueden preguntar.
Y si tienen una solución o creen que podrían tenerla, comenten también así vemos lo que pensaron y si quieren les damos más pistas (o 1 punto si está bien!)

[Guty]

Quizá sirva repasar el tema:

Tema

Búsqueda Binaria

Pueden hacerlo aquí:

Wiki de OIA

Charlas Nacional de OIA 2017

[IvoP]

Tiro una solucion aunque paso bastante tiempo del post:

Solucion

#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
int main(){
long long n,m,l,h,impar,k,sum,r,mid;
bool b=false;
while(cin>>n>>m){
l=0;
h=(n*n)+1;
while(h-l>1){
	sum=0;
	mid=(h+l)/2;
	r=m;
	impar=1;
	for(int i=0;i<n;i++){
		sum=sum+impar;
		if(sum<mid){
			
		}
		else{
			sum=0;
			r--;
		}
		impar=impar+2;
		if(r==0){
			b=true;
		}
		
	}
	if(b){
		l=mid;
	}
	else{
		h=mid;
	}
	b=false;
}
cout<<l<<endl;
}
return 0;
}

[Guty]

No importa cuánto tiempo pasó de la creación de un post. Siempre es bienvenido que compartan ideas, códigos o soluciones

¡Ahí va la merecida Insignia Ryckeboer !