Cow Camp

Solución

Podemos restar $1$ de $T$ porque siempre obtenemos el caso de prueba de ejemplo y lo sumamos a nuestra respuesta final.

Sea $E_x$ el valor esperado después de a lo sumo $x$ envíos. Buscamos $E_K$ . Para obtener el valor esperado del envío final, podemos hallar la relación entre $E_x$ y $E_{x - 1}$ .

Para esto podemos expresar $E_x$ en términos de $E_{x -1}$ y $p_i$ , que es la probabilidad de obtener exactamente $i$ casos de prueba.

Después de $x-1$ envíos, se espera obtener $E_{x-1}$ casos de prueba. Hay tres posibilidades si se decide reenviar.

Caso 1: Si se obtienen menos casos de prueba que $E_{x-1}$ , no se quiere reenviar.

Caso 2: Si se obtienen más casos de prueba que $E_{x-1}$ , sí se quiere reenviar.

Caso 3: Si se obtiene el mismo número de casos de prueba que $E_{x-1}$ , no importa si se reenvía. En este caso no perjudica reenviar o quedarse igual, así que podemos combinarlo con el Caso 1 (o el Caso 2).

La probabilidad de obtener a lo sumo $E_{x-1}$ casos de prueba es ${\sum_{i=0}}^{E_{x - 1}} p_i$ . Podemos multiplicar esto por $E_{x-1}$ para obtener el valor esperado de $E_x$ si nos detenemos antes del $x$ -ésimo envío y obtenemos $E_{x-1} \cdot {\sum_{i=0}}^{E_{x - 1}} p_i$

La probabilidad de obtener más de $E_{x-1}$ casos de prueba es ${\sum_{i=\lfloor E_{x-1} \rfloor + 1}}^T p_i$ . El valor esperado de obtener más de $E_{x-1}$ casos de prueba es la suma de $i$ desde ${\lfloor E_{x-1} \rfloor + 1}$ hasta $T$ de la probabilidad de obtener $i$ casos de prueba multiplicada por $i$ , o ${\sum_{\lfloor E_{x-1} \rfloor + 1}}^T p_i i$ .

Además, estas fórmulas para ambos casos pueden ayudarnos a demostrar matemáticamente que se puede fusionar el Caso 3 con el Caso 1 o el 2. La única diferencia entre ambos casos es si $i = E_{x-1}$ pertenece a la primera o a la segunda suma. Si lo fusionamos con el Caso 1, el término de la suma será $E_{x-1} \cdot p_{E_{x-1}}$ . Si lo fusionamos con el Caso 3, también será $E_{x-1} \cdot p_{E_{x-1}}$ . Esto ocurre porque $p_i \cdot E_{x-1} = p_i \cdot i$ solo se cumple cuando $i=E_{x-1}$ .

Sumar las dos partes da nuestra expresión final para el valor esperado:

E_x = E_{x -1} \cdot \sum_{i=0}^{\lfloor E_{x - 1} \rfloor} p_i + \sum_{i=\lfloor E_{x - 1} + 1 \rfloor}^{T} i p_i

Podemos resolver el problema simulando cada caso de prueba y recalculando las sumas para cada caso de prueba en $O(TK)$ . Sin embargo, esto se puede acelerar fácilmente a $O(T^2 + K)$ precalculando $p_i$ usando la identidad de Pascal y precalculando las sumas de prefijos tanto de $p_i$ como de $p_i i$ para obtener los valores de las sumas en $O(1)$ en lugar de $O(T)$ . Esto nos da los primeros $9$ casos de prueba pero no es suficiente.

Para resolver el problema por completo, necesitamos quitar el factor $O(K)$ . Podemos hacerlo si somos capaces de procesar varios valores de $E_x$ en un solo paso.

Afirmación: Podemos procesar varias consultas si los valores de ${\sum_{i=0}}^{\lfloor E_{x - 1} \rfloor} p_i$ y ${\sum_{i=\lfloor E_{x - 1} + 1 \rfloor}}^{T} i p_i$ no cambian entre consultas.

Demostración: Sea $a = {\sum_{i=0}}^{\lfloor E_{x - 1} \rfloor} p_i$ y $b = {\sum_{i=\lfloor E_{x - 1} + 1 \rfloor}}^{T} i p_i$ . Entonces nuestra fórmula queda

E_x = E_{x - 1} \cdot a + b

Como $a$ y $b$ son constantes, podemos extender esta fórmula y obtener

E_x = a \cdot (a \cdot ... (a \cdot E_{x - k} + b) ... + b) + b

Simplificando obtenemos una sucesión geométrica.

E_x = a^k \cdot E_{x - k} + a^{k - 1}b + a^{k - 2} + ... + b

Podemos reescribir del segundo al último término usando la fórmula de una serie geométrica.

E_x = a^k \cdot E_{x - k} + \frac{b(a^k - 1)}{a - 1}

Aquí hay más información sobre series geométricas .

Sin embargo, los valores de $a$ y $b$ no siempre permanecerán iguales. Podemos hacer búsqueda binaria sobre el número máximo de envíos que Bessie puede hacer antes de que cambien los valores de $a$ y $b$ . $a$ y $b$ cambiarán cuando cambie el valor de ${\lfloor E_x \rfloor}$ . Las condiciones de la búsqueda binaria se cumplen porque $E_x$ es una función no decreciente.

Como hay a lo sumo $T$ valores de $E_x$ , $a$ y $b$ pueden cambiar a lo sumo $T$ veces, así que la complejidad temporal resultante será $O(T^2 + T \log K)$ .

Implementación

Complejidad temporal: $\mathcal{O}(T^2 + T \log K)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = double;
 
const int MAXT = 1000;
 
db prob[MAXT + 1][MAXT + 1];
db pref_prob[MAXT + 1];
db pref_exp[MAXT + 1];
 
// Función para saltar x envíos con constantes a y b y el valor
// esperado actual igual a E.
db skip_submissions(db a, db b, db E, ll x) {
	return pow(a, x) * E + b * (pow(a, x) - 1) / (a - 1);
}
 
int main() {
	int T;
	ll K;
	cin >> T >> K;
 
	// Restamos el caso de prueba de ejemplo
	T--;
 
	// Precomputamos la probabilidad de elegir exactamente i casos de prueba usando
	// la identidad de Pascal.
	prob[0][0] = 1;
	for (int i = 1; i <= T; i++) {
		prob[i][0] = prob[i - 1][0] / 2;
		for (int j = 1; j <= T; j++)
			prob[i][j] = (prob[i - 1][j] + prob[i - 1][j - 1]) / 2;
	}
 
	// Creamos suma de prefijos de probabilidad
	pref_prob[0] = prob[T][0];
	for (int i = 1; i <= T; i++) pref_prob[i] = pref_prob[i - 1] + prob[T][i];
 
	// Creamos suma de prefijos de valor esperado
	pref_exp[0] = 0;
	for (int i = 1; i <= T; i++) pref_exp[i] = pref_exp[i - 1] + prob[T][i] * i;
 
	db E = 0;
	while (K != 0) {
		/*
		 * Hallamos el piso del valor esperado actual
		 * que actúa como el límite de cuántos envíos podemos saltar hacia adelante.
		 */
		ll cross = (ll)floor(E);
 
		// Hallamos las constantes a y b
		db a = pref_prob[cross], b = pref_exp[T] - pref_exp[cross];
 
		// Búsqueda binaria para hallar cuántos envíos podemos saltar
		ll lo = 1;
		ll hi = 1e9;
		while (lo < hi) {
			ll mid = (lo + hi + 1) / 2;
			// Revisamos si 'mid' envíos cruzan el límite 'cross'.
			if (floor(skip_submissions(a, b, E, mid)) == cross) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		/*
		 * Saltamos 'lo' envíos o la cantidad restante de envíos
		 * si quedan menos de 'lo' envíos.
		 */
		lo = min(lo, K);
		E = skip_submissions(a, b, E, lo);
		K -= lo;
	}
	cout << fixed << setprecision(20);
	cout << E + 1 << endl;
}


import math
 
 
def skip_submissions(a: float, b: float, e: float, x: float) -> float:
	"""
	Función que salta x envíos hacia adelante
	con constantes a y b y valor esperado actual e
	según la fórmula de la serie geométrica
	"""
	return pow(a, x) * e + b * (pow(a, x) - 1) / (a - 1)
 
 
t, k = map(int, input().split())
 
# Restamos el ejemplo
t -= 1
 
# Precomputamos la probabilidad de obtener i casos de prueba usando la identidad de Pascal
prob = [[0 for i in range(t + 1)] for j in range(t + 1)]
prob[0][0] = 1
for i in range(1, t + 1):
	prob[i][0] = prob[i - 1][0] / 2
 
	for j in range(1, t + 1):
		prob[i][j] = (prob[i - 1][j] + prob[i - 1][j - 1]) / 2
 
# Sumas de prefijos de probabilidad
pref_prob = [0 for i in range(t + 1)]
pref_prob[0] = prob[t][0]
for i in range(1, t + 1):
	pref_prob[i] = pref_prob[i - 1] + prob[t][i]
 
# Sumas de prefijos de valor esperado
pref_exp = [0 for i in range(t + 1)]
pref_exp[0] = 0
for i in range(1, t + 1):
	pref_exp[i] = pref_exp[i - 1] + prob[t][i] * i
 
e = 0
while k != 0:
	"""
	Hallamos el piso del valor esperado actual
	que también es el límite de cuántos envíos podemos saltar hacia adelante
	"""
	cross = math.floor(e)
 
	# Hallamos a y b usando las sumas de prefijos precomputadas
	a = pref_prob[cross]
	b = pref_exp[t] - pref_exp[cross]
 
	# Búsqueda binaria para ver cuántos envíos podemos saltar
	lo = 1
	hi = 10**9
	while lo < hi:
		mid = math.floor((lo + hi + 1) / 2)
		if math.floor(skip_submissions(a, b, e, mid)) == cross:
			lo = mid
		else:
			hi = mid - 1
 
	"""
	Saltamos lo envíos hacia adelante
	Si el número restante de envíos es menor que lo,
	saltamos los envíos restantes
	"""
	lo = min(lo, k)
	e = skip_submissions(a, b, e, lo)
	k -= lo
 
print(e + 1)