3237 - Bob and Multi-Function Prime-Lock

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3237 - Bob and Multi-Function Prime-Lock

Post by ymondelo20 » 3 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3237 - Bob and Multi-Function Prime-Lock

Post by ymondelo20 » 3 years ago

Solution:

First you need to pre-compute all prime numbers with 6 or less digits (i.e. between 2 and 999999): ---> Eratosthenes Method.

If you try to solve the problem using recursive backtracking, looking for possible combinations, you will probably (almost sure) get TLE.

The correct/safe solution is to use BFS starting with initial state-code; commons implementations should pass but even if not there are multiple optimizations than can be done to this solution to reach better performances.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
padrinoIJ
Posts: 13
Joined: 7 years ago
Location: CUJAE
Gender: None specified

Re: 3237 - Bob and Multi-Function Prime-Lock

Post by padrinoIJ » 3 years ago

En la competencia nos dio TLE en el 8 usando backtracking, nunca vimos la via de usar bfs... :shock:

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: 3237 - Bob and Multi-Function Prime-Lock

Post by isaac » 3 years ago

Me da mala espina el bfs ahi. No tengo ni la remota idea de como se puede usar el bfs en ese caso. Está fula eso.

User avatar
alurquiza
Posts: 54
Joined: 4 years ago
Gender: Male

Re: 3237 - Bob and Multi-Function Prime-Lock

Post by alurquiza » 3 years ago

A mi el BFS todavia me da TLE. Pero la idea es que para un numero crear todos los posibles nuemeros que se forman con un solo movimiento, o con 2 movimientos, etc.
Por ejemplo para:
309
tienes en 1 movimiento a estos numeros:
300
308
399
319
409
209

User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3237 - Bob and Multi-Function Prime-Lock

Post by ymondelo20 » 3 years ago

Es muy común usar BFS en este tipo de problemas. Y las optimizaciones son importantes; desde seleccionar el tipo de estructura de datos adecuada, hasta cuidar por el uso de la memoria utilizada. Por ejemplo, un error común suele ser declarar las estructuras dinámicamente cada vez que se invoca el BFS, en lugar de hacerlo de manara global una sola vez, lo cual lleva a un TLE seguro.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

Post Reply

Return to “Problem set”