algorithm - son - ¿Qué número queda después de eliminar repetidamente los cuadrados perfectos?

numeros cuadrados del 1 al 100

Question

Estaba practicando problemas de SRM en Topcoder. Encontré este problema

Afirmación del problema: Hoy es la víspera de Navidad. Personas de todo el mundo celebran esta fiesta. La siguiente historia tiene lugar en la tierra de los renos, donde reside Santa Claus.

El reno ama los caramelos. Tienen n piezas de caramelos. Los dulces están numerados del 1 al n. Dasher es uno de los renos. Quiere comer uno de los dulces. Para elegir el que va a comer, Dasher utiliza el siguiente método: Si bien hay más de una pieza de dulce: deseche todos los dulces que estén numerados con cuadrados perfectos (es decir, los dulces 1, 4, 9, 16, 25, etc.) . Vuelva a etiquetar los k dulces restantes del 1 al k, manteniendo los números en el mismo orden. Una vez que solo queda un pedazo de caramelo, Dasher lo comerá.

Te dan un int n. Su método debe calcular y devolver el número asignado inicialmente a la pieza de dulce que Dasher comió.

Resolví el problema usando ArrayList pero mi solución falla para números muy grandes (Java Heap Sapce Exception). Por lo tanto, estaba pensando si es posible resolver el problema en la complejidad del espacio O (1).

Por favor dé sus sugerencias y enfoque. No quiero que el código explique solo la lógica para resolver este problema.

He reabierto esta pregunta con la declaración del problema para que los maestros en Stackoverflow puedan ayudarme a resolver este problema en O (1) complejidad de espacio

Answer 1

A menos que haya cometido un error tonto, hay una fórmula para esto. Probablemente podría simplificarse, pero este es el primero en el que me topé.

from math import floor, sqrt, ceil
def is_square(i):
sq = int(i**0.5)
return i == sq*sq
def brute(n):
seq = range(1, n+1)
while len(seq) > 1:
seq = [x for i,x in enumerate(seq, 1) if not is_square(i)]
return seq[0]
def dasher(n):
w = lambda i: floor(sqrt(4*i+1))-1
q = lambda i: ceil((i**2+3)/4)
return q(w(n-1)+1)

Y para comprobar:

>>> b = [brute(i) for i in range(1, 10**3)]
>>> d = [dasher(i) for i in range(1, 10**3)]
>>> b[:25]
[1, 2, 3, 3, 5, 5, 7, 7, 7, 10, 10, 10, 13, 13, 13, 13, 17, 17, 17, 17, 21, 21, 21, 21, 21]
>>> b == d
True

Answer 2

Creo que la siguiente solución funciona correctamente y usa la memoria O (1), asumiendo que puede mantener un número entero en el espacio O (1). La idea es intentar ejecutar este proceso hacia atrás hasta que encuentres la posición definitiva de la pieza correcta de dulce.

Vamos a rastrear un ejemplo de este problema donde n = 10. Entonces obtenemos esto:

1 2 3 4 5 6 7 8 9 10
X X X
2 3 5 6 7 8 10
X X
3 5 7 8 10
X X
5 7 10
X
7 10
X
10

Ahora, supongamos que queremos calcular el resultado final para este problema. Sabemos que cuando terminamos, los dulces que se comen están en la posición 1, ya que solo queda una pieza de caramelo. Así que intentemos configurarlo de esta manera:

1

Ahora, sabemos que en la iteración anterior, los dulces en el índice 1 deben haberse consumido. Esto significa que el caramelo final estaba en realidad en la posición 2 la última vez:

? 2

En la iteración anterior a esto, sabemos que desde que comimos los dulces 1, nuestros dulces deben estar en la posición 3:

? ? 3

En este punto, volvemos a pensar una iteración. Sabemos que los dulces 1 se comieron, pero los dulces 4 también se comieron. Esto significa que el índice de nuestros dulces debe haber sido 5 en la iteración anterior, ya que cuando lo movemos a su posición correcta, debe haber omitido un punto para el primer elemento y un punto para el cuarto elemento:

? ? ? ? 5

Repitiendo esta misma lógica, conseguimos que el índice anterior hubiera sido 7:

? ? ? ? ? ? 7

Ahora, para el siguiente paso, sabemos que habríamos movido los caramelos dos posiciones porque habíamos abandonado los elementos primero y cuarto. Sin embargo, esto pondría nuestros dulces en la posición 9, que se habría eliminado. Esto significa que en vez de eso, deberíamos golpear los dulces a la posición 10:

? ? ? ? ? ? ? ? ? 10

En este punto, dado que quedan 10 caramelos, sabemos que hemos revertido completamente el proceso y hemos terminado. Ya que el lugar de reposo final de nuestros dulces fue la posición 10, sabemos que la respuesta es que el décimo dulce es el que se comió, ¡lo que encaja perfectamente con nuestro trabajo anterior!

El truco detrás de este enfoque es que no necesitamos mucha memoria para que funcione. En particular, en cada paso necesitamos hacer un seguimiento de solo algunas cosas:

• ¿En qué índice se encuentra la última pieza de caramelo actualmente? Necesitamos esto para saber dónde parar.
• ¿Cuántos cuadrados hay debajo de ese índice? Necesitamos esto para saber cuántos elementos se eliminan en cada paso.
• ¿Cuál es la siguiente plaza perfecta? Necesitamos esto para saber cuándo aumenta el número de cuadrados que se eliminan cada vez.
• ¿Cuál fue el último índice que exploramos? Este algoritmo funciona ejecutando el proceso hacia atrás, por lo que en algún momento nos daremos cuenta de que lo hemos ejecutado una vez demasiado. Cuando esto sucede, debemos poder "respaldar" un paso para llegar al último índice que no se excedió.

Dado esto, tenemos el siguiente algoritmo:

• Establezca el índice actual en 1.
• Establece el número de cuadrados perfectos más pequeños en 1.
• Establecer el siguiente cuadrado perfecto a 4.
• Establezca el último índice más pequeño en 1.
• Mientras que el índice actual es menor que n:
  • Establezca el último índice más pequeño para que sea el índice actual (recuerde la solución hasta ahora).
  • Establezca el índice actual + = el número de cuadrados perfectos más pequeños (ejecute el proceso hacia atrás un paso)
  • Si el índice actual es igual al siguiente cuadrado perfecto, agrégale uno (un caso extremo de ejecutarlo hacia atrás; si encontramos un cuadrado perfecto, deberíamos estar un paso más allá)
  • Si el índice actual es mayor que el siguiente cuadrado perfecto (ahora hay más números que se eliminan en cada paso):
    • Establecer el cuadrado perfecto para ser el próximo cuadrado perfecto.
    • Agregue uno al número de cuadrados perfectos más pequeños que el índice.
• Devuelve el último índice más pequeño.

Esto requiere solo memoria O (1) para contener todos los valores.

¡Probemos un ejemplo! Con n = 20, si trabajamos a través del proceso formal, obtenemos esto:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
X X X X
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20
X X X X
3 5 7 8 10 11 13 14 15 17 18 19
X X X
5 7 10 11 13 14 17 18 19
X X X
7 10 13 14 17 18
X X
10 13 17 18
X X
13 17
X
17

Si ejecutamos nuestro algoritmo, obtenemos

 Current Index Next Square Smaller Squares
1 4 1
2 4 1
3 4 1
5 9 2
7 9 2
10 16 3
13 16 3
17 25 4
21 25 4

Desde 21> 20, el último índice más pequeño es 17, por lo que devolvemos 17, que es la respuesta correcta.

Escrito como código C, asumiendo que no hay desbordamiento de enteros:

int EatenCandyIndex(int n) {
int currIndex = 1;
int numSmallerSquares = 1;
/* Rather than tracking the next square, track the root of the next
* square. We can just square this to get the next square.
*/
int rootOfNextSquare = 2;
/* The last spot where the candy would be before we had Too Much Candy. */
int lastIndex = 1;
while (currIndex <= n) {
lastIndex = currIndex;
currIndex += numSmallerSquares;
if (currIndex == rootOfNextSquare * rootOfNextSquare)
++currIndex;
if (currIndex > rootOfNextSquare * rootOfNextSquare) {
++numSmallerSquares;
++rootOfNextSquare;
}
}
return lastIndex;
}

Sin embargo, como está escrito, este algoritmo no es particularmente eficiente. Específicamente, observe su comportamiento en el ejemplo donde n = 20. Tenga en cuenta que tenemos tres rondas en las que el tamaño del paso es uno, dos con el tamaño del paso dos y tres, etc. En lugar de que esas rondas se produzcan explícitamente, en lugar de eso, podemos calcular ¿Cuántas rondas van a tener que ocurrir con ese tamaño de paso, entonces simplemente ejecute todos esos pasos a la vez? De esta manera, siempre tenemos una ronda con tamaño uno, una ronda con tamaño dos, una ronda con tamaño tres, etc. Para hacer esto, en cada paso tendremos que ver cuál es nuestro próximo objetivo; este será el número n o el siguiente cuadrado perfecto. Una vez que hayamos encontrado nuestro objetivo, debemos ver cuántos pasos se requieren para llegar allí. Si el índice actual es i y nuestro objetivo es t, y si nuestro tamaño de paso es k, entonces debemos tomar ⌈ (t - i) / k⌉ pasos para llegar allí. Usando un lindo truco con división entera, podemos calcular esto como

int numSteps = ((t - i) + (k - 1)) / k;

Esto nos da el siguiente algoritmo actualizado:

int EatenCandyIndexFaster(int n) {
int currIndex = 1;
int numSmallerSquares = 1;
/* Rather than tracking the next square, track the root of the next
* square. We can just square this to get the next square.
*/
int rootOfNextSquare = 2;
while (true) {
/* Figure out what our target is. */
int target = min(n, rootOfNextSquare * rootOfNextSquare);
/* See how many steps are required. */
int numSteps = ((target - currIndex) + (numSmallerSquares - 1)) / numSmallerSquares;
/* See where we''d end up if we took one fewer than this many steps forward. */
int lastIndex = currIndex + (numSteps - 1) * numSmallerSquares;
/* Take that many steps forward. */
currIndex += numSmallerSquares * numSteps;
/* There is an edge case here: if we hit our number but it''s a perfect square,
* we want to return the previous value.
*/
if (currIndex == n && n == rootOfNextSquare * rootOfNextSquare)
return lastIndex;
/* Otherwise, if we hit the target number exactly, return it. */
if (currIndex == n)
return currIndex;
/* Otherwise, if we overshot the target number, hand back where we''d be if we
* took one fewer step.
*/
if (currIndex > n)
return lastIndex;
/* Oh well; didn''t make it. If we hit a perfect square, skip it. */
if (currIndex == rootOfNextSquare * rootOfNextSquare)
++currIndex;
++numSmallerSquares;
++rootOfNextSquare;
}
}

Esta versión optimizada del algoritmo se ejecuta en tiempo O (√N) y utiliza espacio O (1). La razón del límite de tiempo es que cada paso del algoritmo se mueve al siguiente cuadrado perfecto, y solo hay O (√N) cuadrados perfectos menos que N.

¡Espero que esto ayude!

Answer 3

Creo que podría estar en algo aquí.

f(n) = 1 if n = 1
f(n) = f(n-floor(sqrt(n))) + floor(sqrt(n)) if n is not a perfect square
f(n) = f(n-1) if n is a perfect square

El caso base es claro. El caso del "cuadrado perfecto" proviene de la observación de que si n es un cuadrado perfecto, se eliminará cuando elimines los cuadrados perfectos, por lo que resolverlo es equivalente a resolver uno menos que eso. El último proviene de la observación de que después de quitar los cuadrados perfectos del piso (sqrt (n)) y volver a numerar, ha desplazado algunos de los números a la izquierda (pero las respuestas son las mismas). Podemos comprobar esto para los primeros casos ...

 n Answer f(n)
1 1 1
2 2 f(2-1) + 1 = f(1) + 1 = 1 + 1 = 2
3 3 f(3-1) + 1 = f(2) + 1 = 2 + 1 = 3
4 3 f(4-1) = f(3) = 3
5 5 f(5-2) + 2 = f(3) + 2 = 3 + 2 = 5

Probar esto, si es correcto, debería ser una extensión directa, y hasta que lo complete, lo dejo como un ejercicio. Debe verificarlo en una gran cantidad de casos y ver si funciona; Si no funciona, lo quitaré.

EDITAR:

Creo que la tendencia que estoy notando, y la razón por la que esto funciona, es que para n no cuadrada, la respuesta nunca puede ser menor que el cuadrado más grande menos que n. Creo que la razón de esto es que nunca puedes eliminar m ^ 2 + 1 antes de eliminar todo menos o igual que m ^ 2. Dado lo anterior, las relaciones de recurrencia anteriores son casi trivialmente ciertas.

Answer 4

Otra variante de la misma:

a = floor(sqrt(N-1))
b = min((N-1)/a, a+1)
solution = a*b+1

O, dicho de otra manera,

unsigned long long eats(unsigned long long N) {
unsigned long long r = (unsigned long long)sqrt(N-1);
while(r*r >= N) --r;
while(r*(r+2) < N) ++r;
if (N <= r*(r+1)) {
return r*r+1;
}
return r*(r+1)+1;
}

La prueba se desprende del análisis de la next función que da la siguiente posición de cualquier dulce, next(n*n) = 0 , de modo que no es una función parcial. Si a*a < N < (a+1)*(a+1) , tenemos a next(N) = N - a . Así que un número de la forma n = a*(a+1) + 1 viaja

a*(a+1)+1 -> a*a + 1 -> (a-1)*a + 1 -> ... -> 2*3 + 1 ->2*2 + 1 -> 1*2 + 1 -> 1*1 + 1 -> 0*1 + 1

Vemos que también los números de la forma a*a +1 alcanzan 1. Los números de cualquier otra forma alcanzan un cuadrado mayor que 1 en algún punto:

a*(a+1) -> a*a -> eliminated
a*(a+1) + r -> a*a + r -> (a-1)*a + r

para 2 <= r <= a . Si r = a , (a-1)*a + r = a*a es un cuadrado, lo que resulta en la eliminación inmediata. Si r < a , el número alcanzado después de dos pasos tiene la misma forma con el mismo r . Continuando, se deduce que el número alcanza.

(r+1)*(r+2) + r -> (r+1)*(r+1) + r -> r*(r+1) + r -> r*r + r -> r*r -> elimination.

Así que hemos visto

• Un número llega al punto 1 en el proceso si y solo si tiene la forma n*n + 1 o n*(n+1) + 1

El último número para alcanzar el primer lugar que comienza con N caramelos es, por supuesto, el mayor número de esa forma que no exceda de N QED.

Answer 5

Sabe que el último número se eliminará con el número especial 1. Si genera todos los números eliminados con 1, tendrá un conjunto que contiene el número especial. Así que todo lo que tienes que hacer es generar esos números.

Así que veamos si hay un patrón.

Sea n ser 150

Números eliminados por 1

r = [1, 2, 3, 5, 7, 10, 13, 17, 21, 26, 31, 37, 43, 50, 57, 65, 73, 82, 91, 101, 111, 122, 133]

Array de r [i + 1] -r [i]

[1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11]

Números eliminados por 2

r = [4, 6, 8, 11, 14, 18, 22, 27, 32, 38, 44, 51, 58, 66, 74, 83, 92, 102, 112, 123, 134, 146]

Array de r [i + 1] -r [i]

[2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12]

Números eliminados por 9 Sabemos que los números eliminados por 9 diferirán en los primeros 2 elementos en 3 y el primer elemento es 9. A partir de eso, podemos generar los números que se eliminarán siguiendo este patrón de 3,3,4. 4,5,5 [9, 12, 15, 19, 23, 28, 33, 39, 45, 52, 59, 67, 75, 84, 93, 103, 113, 124, 135, 147] [3, 3 , 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12]

import math
def getSpecial(n):
sp = list()
s = 1
while((s * s) <= n):
sp.append(s*s)
s += 1
return sp
def bruteForce(n):
nu = range(n+1)
nu.pop(0)
while(len(nu) > 1):
sp = getSpecial(len(nu))
removed = list()
for x in sp[::-1]:
removed.append(nu.pop(x-1))
return nu[0]
def fancyMathWitchCraft(n):
sp = getSpecial(n)
oneset = [1]
j = 0.0
while(oneset[-1] <= n):
oneset.append( oneset[-1] + int(1 + 1 * math.floor(j/2)) )
j = j + 1.0
if(oneset[-1] <= n):
return oneset[-1]
if(oneset[-2] <= n):
return oneset[-2]
if(oneset[-3] <= n):
return oneset[-3]
def main():
for x in range(1,2000):
if(bruteForce(x) != fancyMathWitchCraft(x)):
print(x, bruteForce(x), fancyMathWitchCraft(x))
print("Done")
if __name__ == "__main__":
main()

La prueba detrás de esto está probablemente en el hecho de que el último cuadrado perfecto solo eliminará 1 número, por lo que el número final provendrá del segmento continuo más grande que no se verá afectado después de la primera iteración, y ese será el último segmento. Si REALMENTE desea una prueba matemática para esto, deberá llevar esta pregunta a meta.

Answer 6

n=1, eats=1
n=2, eats=2
n=3, eats=3
n=4, eats=3
n=5, eats=5
...

¿Ves un patrón emergente? Cree una fórmula y demuestre que la fórmula es correcta utilizando la inducción matemática

Aquí está el código c ++:

#include <iostream>
#include <cmath>
using namespace std;
bool is_perfect_square(int value)
{
return pow( static_cast<double>(static_cast<int>(sqrt(static_cast<double>(value)))), 2.0) == value;
}
int EatEm(int n)
{
while (is_perfect_square(n))
{
n -= (static_cast<int>(sqrt(static_cast<double>(n)) - 1));
}
return n;
}
int main()
{
int res = EatEm(25);
cout << res << endl;
return 0;
}