¿Cómo podemos abordar para resolver el problema de ‘Infinite House of Pancakes’ de Google Code Jam 2015?

Suponiendo que ya leyó la declaración del problema.

ordene la lista en orden creciente y luego repita a través del 2 hasta el valor máximo del número presente en la lista y luego encuentre la mejor respuesta posible generando todos los estados posibles (La función entumecida en el código a continuación).

tomemos el ejemplo para 4 6 8

observado:-
1er minuto especial 4 6 4 4
2do minuto especial 4 4 2 4 4
luego déjalos comer por 4 minutos
respuesta total 2 especial + 4 ordinario = 6 minutos.

pero cómo encontrar el mejor número posible para obtener este tipo de descanso,
generando todos los estados posibles y luego seleccionando el más pequeño.

Procedimiento algorítmico: –
el más grande es 8
entonces nuestro ciclo va de 2 a 8 para verificar.
para 2 = 1 + 2 + 3 + (2 en sí toma 2 minutos para ser comido) = 8
para 3 = 1 + 1 + 2 + (3 en sí) = 7
para 4 = 0 + 1 + 1 + (4 en sí) = 6
para 5 = 0 + 1 + 1 + (5 en sí) = 7
para 6 = 0 + 0 + 1 + (6 en sí) = 7
para 7 = 0 + 0 + 1 + (7 en sí) = 8
para 8 = 0 + 0 + 0 + (8 en sí) = 8

mínimo de todo lo anterior 6.

Código aceptado en el atasco de código para entradas pequeñas y grandes.

#include
#include
#include
#include
#include
#include
#include
#include
usando el espacio de nombres estándar;

int numbuti (valor int, int n)
{
/ * cout << "n" << n << endl;
cout << "valor" << valor << endl;
cout << "n% value" << (n% value) << endl;
cout << "n / value" << (n / value) << endl;
cout << "n / 2" << (n / 2) << endl;
cout << "n / 2 -1" << ((n / 2) -1) << endl; * /
if ((n% value) == 0)
retorno ((n / valor) -1);
más
retorno n / valor;
}

int numb (vector a, valor int)
{
int temp = 0;
// cout << "valor" << valor << endl;
para (int i = 0; i {
temp + = numbuti (valor, a [i]);
// cout << numbuti (valor, a [i]) << endl;
}
temp + = valor;
// cout << "valor" << valor << endl;
temperatura de retorno;
}

int main ()
{
int t, d;
scanf (“% d”, & t);
para (int ii = 1; ii <= t; ii ++)
{
scanf (“% d”, & d);
vector n;
int temp = 0, max;
para (int i = 0; i {
scanf (“% d”, & temp);
n.push_back (temp);
}
sort (n.begin (), n.end ());
max = n [n.size () – 1];
int ans = max, te;
para (int i = 2; i <= max; i ++)
{
te = entumecido (n, i);
// cout << endl;
// cout << "te" << te << endl;
if (ans> te) ans = te;
}
printf (“Caso #% d:% d \ n”, ii, ans);
}
devuelve 0;
}

Descomentar algunas líneas lo ayuda a comprender el flujo del código.

La complejidad del algoritmo es O (t * (max en d) * d).
los límites superiores de tyd se dan en la declaración del problema

La estrategia óptima es distribuir primero todos los panqueques de comensales vacíos a vacíos o no vacíos tomando los minutos especiales, y luego dejar que el cliente coma los panqueques.

Por lo tanto
[matemáticas] T_ {min} = T_ {sp} + T_ {maxpancake} [/ matemáticas]

[matemáticas] T_ {min} [/ matemáticas]: TIEMPO MÍNIMO
[matemáticas] T_ {sp} [/ matemáticas]: NÚMERO TOTAL DE MINUTOS ESPECIALES
[matemáticas] T_ {maxpancake} [/ matemáticas]:
MAX PANCAKES EN CUALQUIER CENA DESPUÉS DEL ÚLTIMO MINUTO ESPECIAL TOMADO (se requiere 1 minuto para terminar el pastel de pan individual)

El número total de minutos especiales dependerá de cuál sea el máximo de todos los panqueques en cualquier restaurante.

Entonces, si nos movemos a través de todos los valores posibles de [math] T_ {maxpancake} [/ math] Y calculamos los minutos especiales correspondientes al valor de [math] T_ {maxpancake} [/ math]. Podemos obtener el tiempo mínimo.

El siguiente es un algoritmo [matemático] O (m * n) [/ matemático] para hacer esto
(m es el número máximo de panqueques en cualquier restaurante inicialmente yn es el número total de comensales no vacíos)

1. Almacene el número de panqueques en comensales no vacíos en la matriz p
2. Calcular max = el número máximo de panqueques en cualquier restaurante inicialmente
3. min [math] \ leftarrow [/ math] max
4. para i [math] \ leftarrow [/ math] 1 a max
5 do Tsp [matemáticas] \ leftarrow [/ matemáticas] 0
6 para j [matemáticas] \ leftarrow [/ matemáticas] 0 a la longitud [p]
7 hacer si (i> = p [j]) continuar
8 k [matemáticas] \ leftarrow [/ matemáticas] p [j] / i
9 if (p [j]% i = 0) k [matemáticas] \ leftarrow [/ matemáticas] k-1
10 cucharaditas [matemáticas] \ leftarrow [/ matemáticas] k

11 T [matemáticas] \ leftarrow [/ matemáticas] Tsp + i
12 if (min> T) min [matemáticas] \ leftarrow [/ matemáticas] T

13 Imprimir min

Mi código que se basa en el primer enfoque.

import java.io. *;
import java.util. *;

Panqueque de clase pública {
public static void main (String args []) lanza Exception {

BufferedReader br = new BufferedReader (nuevo FileReader (“c: /gcj2015/B-large.in”));
PrintWriter pw = new PrintWriter (“c: /gcj2015/B-large.out.txt”);
int tc = Integer.parseInt (br.readLine ()) + 1;
StringTokenizer sts = null;
int i = 0, j = 0, k = 0, cuenta = 0, i1 = 0, suma = 0, len = 0, l = 0, d = 0, p [] = nulo, st [] = nulo, máx. = -1, min = 0, tiempo = 0, w_time = 0, mt = 0;
para (i1 = 1; i1 {d = Integer.parseInt (br.readLine ());
max = -1;
p = nuevo int [1001];
st = nuevo int [1001];
sts = new StringTokenizer (br.readLine ());
para (i = 0; i {p [i] = Integer.parseInt (sts.nextToken ());

max = max

}
min = max;
para (i = 1; i <= max; i ++)
{w_time = 0;
para (j = 0; j {if (i> = p [j]) continuar;
k = p [j] / i;
si (p [j]% i == 0)
k = k-1;
w_time = w_time + k;
}

tiempo = w_time + i;
min = min> tiempo? tiempo: min;
}
System.out.println (“Caso #” + i1 + “:” + min);
pw.println (“Caso #” + i1 + “:” + min);

}

pw.close ();

}

}

Cuando me acerco a problemas como estos, trato de encontrar invariantes , o patrones implícitos, en el problema. Después de pensar en el problema durante unas horas, llegué a algunas ideas clave:

1. Dar panqueques a un restaurante vacío es mejor (o no peor) que dárselos a alguien que ya tiene comida, ya que reduce la “altura máxima” tanto como sea posible.
   => Dividir siempre en un plato vacío.
2. Dividir panqueques al principio es mejor que hacerlo más tarde. Digamos que dividimos un plato de 4 en 2. Luego, cada plato se reducirá en 1 en la siguiente ronda, lo que equivale a reducir en 2 en general (en lugar de solo 1 si dividimos más adelante).
   => Haga una cadena de divisiones antes de comenzar la secuencia de alimentación.
3. Siempre tomará un número fijo de pasos para dividir una pila de tal manera que las subpilas sean <= some max_height. Esto implica que dividir 8 en pilas <= 2 siempre tomará al menos 3 pasos, independientemente de cómo lo hagamos.
   => Forma simple de dividir un plato de 8 en 3 platos: sigue tomando 3 del plato de 8 hasta que solo queden 2. Generalice este ejemplo a cualquier placa n.

Entonces, a partir de estos patrones, vemos que siempre queremos dividir un montón de veces antes de dejar que los comensales terminen su comida, por lo que el tiempo total sería (num_divides + max_new_height). Resulta que no puedes dividir con avidez (es decir, a la mitad cada vez): 9 es un caso así, ya que dividir en 3 pilas de 3 es mejor que dividir de otra manera. Por lo tanto, vemos que tenemos que iterar sobre posibles “max_new_height” en lugar de iterar sobre “num_divides”, lo que conduce a la misma solución que hizo Eliot.

Con fines de aprendizaje, quería escribir una solución más detallada que tratara de explicarse por sí misma, y ​​que se inclinara hacia la FP más que imprescindible. Puede que no sea el más eficiente, pero me ayudó a convencerme de que funciona.
(el idioma utilizado es Scala si alguien se lo pregunta)

objeto IHOP {
def main (args: Array [String]) {

val fileName: String = …
val outFileName: String = …

val pw: PrintWriter = nuevo PrintWriter (nuevo archivo (outFileName))
val s: escáner = nuevo escáner (nuevo archivo (nombre de archivo))
val testCases: Int = s.nextInt

para (i <- 1 para testCases) {
val numPancakes = s.nextInt ()

val pancakePerPlate = for (i <- 0 hasta numPancakes) produce s.nextInt ()

// 1) cuál es el costo de simplemente sentarse y no hacer nada (es el plato máximo en la lista de platos)

val costOfDoingNothingAndLettingThemAllEat = pancakePerPlate.max

// 2) para cada posible “tamaño máximo de placa”, calcule el costo.

val costToDivideAllPlatesToLessThanMaxStackSize = para (targetMaxStackSize <- 2 a 1000) rendimiento {
// el costo es: el tamaño de pila máximo objetivo (después de dividir, la gente todavía necesita comer) + el número si la división necesita llegar allí
targetMaxStackSize + numDividesNeededToMakeMaxStackSize (targetMaxStackSize, pancakePerPlate)
}

// 3) la respuesta es el mínimo de: el costo mínimo si se hace una división (la llamada a la función .min), o el costo de no hacer nada

val answer = Math.min (costToDivideAllPlatesToLessThanMaxStackSize.min, costOfDoingNothingAndLettingThemAllEat)
val message = s “Caso # $ i: $ respuesta”
println (mensaje)
pw.println (mensaje)
}
pw.close ()
}

// método auxiliar: para una altura de pila determinada (tamaño), ¿cuántas divisiones (también conocido como “especiales” minutos) necesitamos?
def numDividesNeededToMakeMaxStackSize (tamaño: Int, pancakePerPlate: IndexedSeq [Int]): Int = {
// resumiéndolo “la forma funcional” (no la forma más eficiente, pero una variable menos mutable)
(para (curStackSize <- pancakePerPlate) rendimiento {
if (curStackSize> size) numDividesNeededToMakeMaxStackSize (size, curStackSize) más 0
}).suma
}

def numDividesNeededToMakeMaxStackSize (size: Int, stack: Int): Int = (stack – 1) / size

// NOTA – con respecto a (stack – 1) / size – puede que no sea obvio, pero si juegas con él, verás que para pasar de una pila de altura X a
// múltiples pilas de altura Y (que es menor que X) necesita (X-1) / divisiones Y
// por ejemplo, un plato con 10 panqueques y una pila máxima de 3 – necesitas
// 1ra división – 7, 3
// 2da división – 4, 3, 3
// 3ra división – 3, 3, 3, 1
// (10-1) / 3 = 9/3 = 3.

// por ejemplo, un plato con 9 panqueques y una pila máxima de 3 – necesitas
// 1ra división – 6, 3
// 2da división – 3, 3, 3
// (9-1) / 3 = 8/3 = 2. // scala, al igual que las divisiones int de Java Floor automáticamente

// por ejemplo, un plato con 8 panqueques y una pila máxima de 3 – necesitas
// 1ra división – 5, 3
// 2da división – 3, 3, 2
// (8-1) / 3 = 7/3 = 2.

}

EDITAR: una solución un poco menos detallada, pero con suerte se explica por sí misma. (también me di cuenta de que no hay necesidad de iterar para todos los 1000, solo necesitamos verificar hasta la altura máxima, por supuesto …)

(esto todavía pasa el juez en línea para entradas pequeñas y grandes)

objeto IHOP {
def main (args: Array [String]) {
val pw: PrintWriter = nuevo PrintWriter (nuevo archivo (outFileName))
val s: escáner = nuevo escáner (nuevo archivo (nombre de archivo))
val testCases: Int = s.nextInt

para (i <- 1 para testCases) {

val numPancakes = s.nextInt ()
placas val = para (i <- 0 hasta numPancakes) producir s.nextInt ()

// el costo de dejarlos comer y no hacer nada es el tamaño máximo de la pila
val noOpCost = plates.max

// todos los costos posibles de dividir primero todas las placas por encima de targetMaxSize
// luego dejándolos pegar

val divideCosts =
para (targetMaxSize <- 2 to noOpCost) rendimiento {
targetMaxSize + numDivisions (targetMaxSize, placas)
}

// +: antepone un elemento a una colección,
// min solo devuelve el min de una colección

val minDivideCost = (noOpCost +: divideCosts) .min

respuesta val = Math.min (minDivideCost, noOpCost)
val message = s “Caso # $ i: $ respuesta”
println (mensaje)
pw.println (mensaje)
}
pw.close ()
}

def numDivisions (maxPancakes: Int, placas: IndexedSeq [Int]): Int = {
divisiones val = para (numPancakes <- placas
if numPancakes> maxPancakes)
rendimiento (numPancakes – 1) / maxPancakes
divisiones.sum
}

}

No lo intenté hasta ahora, pero aquí está mi proceso de pensamiento.

Primero, si divide los panqueques, debe ponerlos en un plato nuevo, ya que es una persona nueva que come panqueques, y aumentar la tasa de consumo de panqueques siempre es bueno. Dado que cada minuto especial aumentará la tasa de consumo de panqueques, debe hacerlos todos al principio. No hay ningún beneficio en esperar, en el mejor de los casos puede encontrar una solución equivalente.

Ahora que hemos establecido que todos los minutos especiales ocurren al comienzo, deberíamos averiguar qué hacer con ellos.
Como objetivo general, queremos que los panqueques se dividan equitativamente. si me toma menos tiempo distribuir mis panqueques y luego comerlos que simplemente comerlos, vale la pena dividirlos.
Entonces, hay algún umbral x donde me tomará x tiempo comer todos los panqueques, y necesito dividir todas mis pilas en un tamaño de x o menos.
Cualquier pila mayor que x puedo sacar de x panqueques y hacer una nueva pila, repitiendo hasta que esté debajo de x.
Entonces necesitamos encontrar x.
me llevará tiempo dividir mis pilas al tamaño x.
entonces, necesitamos minimizar s + x.

x estará en algún lugar entre el tamaño de mi pila más grande y 2. (2 porque una sola pila de 2 cuesta la misma cantidad de tiempo dividir que comer y comer, y nada más que eso no valdrá la pena dividir una pila de 2 )

para comenzar, ordenaría mis pilas por su tamaño.
entonces recorrería x = tamaño máximo a x = 2;
para cada ciclo, pasaría por cada pila de tamaño mayor que x.
s + = techo (pila / x) -1; Se necesitarán tantas divisiones para moverlo.

esto es O (s * n), donde s es el tamaño de la pila más grande yn es el número de pilas.

Esta es una búsqueda lineal para x. Si x está en un gradiente, será más fácil de encontrar, podríamos hacer una búsqueda binaria para obtener O (lg (s) * n)
Entonces, ¿está en un gradiente? En otras palabras, si disminuyo x, ¿alguna vez aumentará mi costo si reducir más x será beneficioso?
Nuestro costo es s + x. la parte x es lineal, disminuirá en 1 cada vez que disminuyamos x (porque es x). ¿y qué hay de s?
S = Suma (techo (p1 / x) -1)
o = suma (techo (p1 / x)) – número de placas
El número de platos es una constante.
suma (techo (p1 / x))
Esto siempre aumentará a medida que x disminuya.

Entonces, a medida que disminuimos x, el costo disminuirá y luego comenzará a aumentar. Este punto de inflexión es lo que necesitamos encontrar. Por lo tanto, la búsqueda simple puede provocar un cortocircuito tan pronto como aumente el costo. También podemos usar una búsqueda binaria modificada
Para cada punto en nuestra búsqueda, podemos calcular el valor en la x actual yx + 1. Si esto está aumentando, necesitamos buscar hacia atrás. Si está disminuyendo, tenemos que buscar hacia adelante. Esto nos permitirá concentrarnos en x. en tal caso, también podemos usar una conjetura educada para el punto de partida de x; Yo diría que una x en algún lugar como el sqrt (panacakes totales) sería una suposición decente.