返回列表

Silver Medal Solution (15th)

594. Santa 2023 - The Polytope Permutation Puzzle | santa-2023

开始: 2023-12-19 结束: 2024-01-31 数学与计算 数据算法赛

银牌解决方案(第15名)

作者:Kei Harada | 发布日期:2024-02-01 | 协作者:Tomoki Yoshida, sfujiwara

今年我们也在顶尖组别中获得了一枚银牌。你可能想先阅读已发布的 第一名解决方案 以及其他获奖者的解法。
但请允许我公开我的 代码 并写下这份解决方案,以证明我们没有作弊。

立方体(Cubes):

我们可以使用 nxnxn 求解器 来解决常规模式,但该求解器与比赛中的移动计数方式不同,因此直接使用效率较低。例如,在最坏情况下,16Uw2 对求解器(以及人类)来说算作 1 次移动,但在本次比赛中却被计为 32 次移动。

我们首先在 5x5x5 问题上重复使用求解器来对齐边缘和角落。第一种方案中展示了提取带有角落和中心的 3x3x3 子立方体的方法。通过重复 5x5x5 的步骤,我们可以解决所有对角部分(4x4x4 中的 (1,1))、十字部分(5x5x5 中的 (1,2))以及边缘部分(4x4x4 中的 (0,1))。
剩下的任务是对齐内部(6x6x6 中的 (1,2))。我们通过贪心搜索来寻找高效的下一步 3-轮换(3-rots)。(我们称之为“三点交换的魔力” :-))。
使用 5x5 求解器同样效率不高,但我们没有更高效的边缘对齐方法,因此采用了这种方式。

对于 N0;N1;… 这类立方体,通过对其进行着色并执行相同的方法,边缘和角落将会被对齐。其余部分基本相同。

球体(Globes):

我通过将 m × n 简化为多个 1 × n 来解决它。由于自由使用 f_k 会影响其他层,因此我将操作限制在 f_0 和 f_n 上。
在 1 × n 的球体中,也存在“三点交换的魔力”,因此我们能够获得性能充足的解决方案。

花环(Wreaths):

我通过一个简单的启发式方法得到了足够好的解决方案。

@tomokiyoshida 进行的后处理以及 @sfujiwara 采用的不同参数的并行执行显著提高了得分。

同比赛其他方案