Hola Buenos dias… Consulta sobre el OIA Juez, sucede que este tiene un filtro de busquedda en el cual esta la catgoria Fenwick-Seg Tree, y hay un problema “Aventureros” que sinceramente no le encuentro la vuelta para resolverlo con Fenwick. Muchas Gracias.
1 me gusta
Buenas! No suelo usar Fenwick Tree porque me acostumbré a Segment Tree, pero lo que importa que es podamos hacer las operaciones “obtener suma en un rango” y “actualizar un valor”.
La solución que se me ocurre esa la siguiente:
Solucion
Lo que queremos saber es a partir del actual lugar el mate, hasta dónde llego si me muevo “x” posiciones.
Si tenemos un array de N posiciones que inicializamos con un “1” en cada lugar, representando “la persona que comienza en la posición i-ésima está todavía en la ronda”, y vamos actualizando estos valores a un 0 cuando alguien se va de la ronda, entonces la cantidad de personas que haya entre los lugares a y b será la suma de los valores del array en esas posiciones.
Entonces lo que podemos hacer es una binaria para buscar el lugar en el que termina la pava después de moverse a_i lugares. Primero, si a_i es más grande que la cantidad de personas que quedan, simplemente tomamos a_i módulo la cantidad de personas que quedan en la ronda (que sabemos que será n - i).
Ahora sí, una vez que nos tenemos que mover un número menor que la cantidad de personas que quedan, hacemos una binaria y nos fijamos "cuántas personas hay entre el lugar en donde está el mate y m". Si es más grande que la cantidad de lugares que debemos mover el mate, entonces en ese intervalo estará la persona que terminará con el mate, si no no.
Acá entra Fenwick/SegTree entonces, calculamos la suma de esos intervalos y actualizamos la binaria hasta encontrar la posición del número 1 en donde termina el mate. Actualizamos esa posición a 0, y después “darle el mate a la persona de la derecha” es simplemente la operación “mover el mate 1 lugar”, entonces con la misma operación (pero sin actualizar a 0 porque no estamos sacando a nadie de la fila) ya tenemos en donde comienza el mate en la siguiente ronda.
Si querés intentá implementar esto y cualquier cosa lo seguimos hablando por acá.
Y si tenés alguna solución sin usar Fenwick/SegTree, comentala!
1 me gusta