Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Se te da un arreglo de $n$ enteros entre $1$ y $n+1$. Es posible que algunos de los enteros aparezcan múltiples veces en el arreglo. Aun así, está claro que al menos uno de los enteros entre $1$ y $n+1$ falta en el arreglo. Tu tarea es encontrar cualquiera de esos enteros. Normalmente sería fácil, pero hay un problema desafortunado: no hay suficiente memoria en tu computadora para representar todo el arreglo.

Por lo tanto, se te pide producir un algoritmo de flujo (streaming algorithm) en su lugar. Informalmente, los elementos del arreglo se te entregan uno por uno sin forma de acceder a ellos aleatoriamente. Sin embargo, hay un consuelo: después de recibir el último elemento del arreglo, puedes reiniciar su lectura desde el principio. Idealmente, te gustaría evitar tal situación y resolver todo el problema en una sola pasada. Sin embargo, a veces (incluyendo este mismo problema) pueden ser necesarias múltiples pasadas sobre la entrada para evitar usar demasiada memoria. Necesitas equilibrar ambas preocupaciones y, simultáneamente, no usar demasiada memoria ni hacer demasiadas pasadas sobre el arreglo (el problema es trivial si se te permite almacenar $n$ bits de memoria o usar $n$ pasadas).

Sin embargo, todavía hay una trampa. Por razones técnicas, debes producir un autómata finito determinista (DFA) sobre el alfabeto $\{0, 1, \dots, n + 1\}$ que implemente la lógica de tu algoritmo. Los caracteres del alfabeto corresponden a la información que recibes al leer el flujo: los números de $1$ a $n+1$ representan leer el entero correspondiente del arreglo, mientras que el número $0$ representa el hecho de que has llegado al final del arreglo. Después de las primeras 7 veces que hayas llegado al final del arreglo, el arreglo se te dará nuevamente en el mismo orden que antes, terminando siempre con un carácter $0$ que representa el final del arreglo. Por lo tanto, tu DFA recibirá la cadena $a_1, a_2, \dots, a_n, 0$ un total de 8 veces (aquí, $a_1, a_2, \dots, a_n$ es el arreglo oculto). Finalmente, en cualquier momento de la ejecución, tu autómata puede "decir" que ya conoce alguna respuesta correcta al problema; en ese caso, la ejecución se detiene. Si tu DFA no lo ha hecho para cuando haya leído todo el flujo (incluyendo el carácter $0$ al final) 8 veces, no se acepta como solución. De manera similar, si se detiene pero con una respuesta incorrecta, tampoco se acepta como solución.

Enunciemos el problema formalmente. Hay un arreglo oculto $a_1, a_2, \dots, a_n$ de $n$ enteros entre $1$ y $n+1$. En el ejemplo, $n = 4$, y en todas las demás pruebas $n = 250$. Debes especificar una máquina de estados finitos con a lo sumo 4000 estados, numerados de $0$ a $q - 1$, donde $q \le 4000$ es el número de estados. Para el estado $i$ ($0 \le i \le q - 1$), debes especificar $n + 2$ números $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. El número $\delta(i, j)$ representa el comportamiento de tu DFA cuando está en el estado $i$ y lee el número $j$ de la entrada. Debe ser un entero desde $-(n + 1)$ hasta $q - 1$ inclusive. Los enteros negativos corresponden al hecho de que la ejecución se detiene y se da una respuesta; específicamente, $-s$ corresponde a que tu DFA afirma que $+s$ es una respuesta correcta al problema. Los enteros no negativos corresponden al hecho de que la ejecución continúa y el estado del autómata cambia de $i$ a $\delta(i, j)$. La ejecución del autómata comienza en el estado $0$.

Se considera que tu DFA funciona correctamente en el arreglo $a_1, a_2, \dots, a_n$ si se detiene con una respuesta correcta en algún punto de la lectura de la cadena $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$, donde el arreglo se repite 8 veces. Se considera que tu DFA funciona correctamente en general si funciona correctamente en todos los arreglos posibles $a_1, a_2, \dots, a_n$ de enteros entre $1$ y $n+1$ (por lo tanto, se desaconsejan las soluciones probabilísticas).

Para $n = 4$, verificaremos tu DFA en todos los arreglos posibles. Para $n = 250$, no tenemos medios para verificarlo en todos los arreglos, por lo que lo verificaremos en menos de 5000 arreglos especialmente seleccionados. Hay dos pruebas en el problema; ambas pruebas comprueban de forma efectiva que tu enfoque funciona correctamente en muchos arreglos simultáneamente.

Entrada

Un entero $n$, que es igual a $4$ o a $250$.

Salida

En la primera línea, imprime un solo entero $q$ ($1 \le q \le 4000$) que denota el número de estados en tu DFA.

En la $i$-ésima de las siguientes $q$ líneas, imprime $n + 2$ enteros $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Todos ellos deben estar entre $-(n + 1)$ y $q - 1$ inclusive y corresponder a las transiciones del autómata. Ten en cuenta que todos los números deben estar en este rango: incluso si alguna combinación del estado $i$ y el número de entrada $j$ nunca puede alcanzarse en ninguna entrada válida, el valor de $\delta(i, j)$ que especifiques debe seguir estando en el rango $[-(n + 1), q - 1]$.

Ejemplo

Entrada 1

4

Salida 1

8
-3 0 0 1 0 0
2 1 1 1 1 1
-1 3 2 2 2 2
4 3 3 3 3 3
-5 4 4 4 4 5
6 5 5 5 5 5
-2 6 7 6 6 6
-4 7 7 7 7 7

Nota

La respuesta del ejemplo es un autómata muy aburrido que utiliza cuatro pasadas para comprobar si el arreglo incluye los números 3, 1, 5 y 2 (en ese orden). Cada una de las pasadas utiliza en la práctica solo dos estados que corresponden a si ya ha encontrado el número que está buscando en la pasada actual. Si llega al final del arreglo (el carácter 0) sin encontrar el número necesario, se detiene inmediatamente diciendo que dicho número efectivamente falta. De lo contrario, procede a usar la siguiente pasada para buscar el siguiente número. Finalmente, si ha encontrado los cuatro enteros necesarios, entonces el número 4 tiene que faltar. Por lo tanto, no hace una quinta pasada buscando el número 4 (aunque podría haberlo hecho sin violar las restricciones sobre el número de estados del autómata y las pasadas utilizadas).

Por supuesto, este enfoque ingenuo no tiene ninguna posibilidad de funcionar para $n = 250$, y se necesita algo mucho mejor. La razón principal de la existencia del ejemplo es ilustrar el formato de salida.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1213EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.