Breaking the 100 point barrier for IOI 2010 Maze

Правка en4, от maomao90, 2023-07-31 12:34:25

After 21 days and 56 submissions on IOI 2010 Maze, I finally broke the 100 point barrier and achieved a score of 100.081 / 100.

Score distribution Page 3 of submissions

Page 2 of submissions

Page 1 of submissions

Methodology

It's just simulated annealing + a lot a lot of time.

The neighbour function to generate a new state was just randomly choosing one cell to change from '$$$\text{#}$$$' to '$$$\text{.}$$$' or from '$$$\text{.}$$$' to '$$$\text{#}$$$'. Remember to take care that there must be exactly one '$$$\text{.}$$$' at the edge of the maze at all times.

The energy function that we are optimizing is the question itself, which is the maximum shortest path.

The acceptance probability function is the classic exponential function based on the Boltzmann probability distribution.

Finally, the initial temperature I used was $$$t_0 = 2.5$$$ and the geometric temperature reduction $$$t' = t\cdot \alpha$$$

Теги ioi2010, maze, simulated annealing, output-only

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский maomao90 2023-08-02 09:34:59 9743 (published)
en6 Английский maomao90 2023-07-31 18:02:42 1902
en5 Английский maomao90 2023-07-31 12:45:22 499
en4 Английский maomao90 2023-07-31 12:34:25 770 Tiny change: 'm '.' to '\s{#}'.' -> 'm '.' to '$\s{#}$'.'
en3 Английский maomao90 2023-07-31 10:19:03 4 Tiny change: '3de1a.png)' -> '3de1a.png)\n\n'
en2 Английский maomao90 2023-07-31 10:18:16 159 Tiny change: '5e8.png)\n[cut]\n![ ](/pr' -> '5e8.png)\n\n[cut]\n\n![ ](/pr'
en1 Английский maomao90 2023-07-31 10:17:22 475 Initial revision (saved to drafts)