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.
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

3237 - Bob and Multi-Function Prime-Lock

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

ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

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

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.

Posts: 13
Joined: 8 years ago
Location: CUJAE
Gender:

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

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

isaac
Posts: 83
Joined: 4 years ago
Gender:

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

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.

alurquiza
Posts: 54
Joined: 4 years ago
Gender:

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

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

ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender:
Contact:

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

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.