第四名解决方案
主要解决方案
我们的主要解决方案是以下循环（ILS）。由 @daiwakun 提供的带 Kick 策略的 Beamsearch。
-
插入优化 (Insert optimize)
- 随机删除 N 个单词并使用 beam search 重新插入它们
- 随机删除 N 个单词并使用 beam search 重新插入它们
-
局部优化 (Local optimize)
- 重复以下步骤直到没有改进 (No Improvement)
- 打乱子部分 (Shuffle Subsections)
- 交换单词 (Swap Words)
- 移动单词 (Move Words)
- 排除相同排列 (Exclude Identical Arrangements)
- 移除重复项 (Remove duplicates)
| id | 单词长度 (len words) | 分数 (score) | 时间 (time) | 可能分数 (Possible score) |
|---|---|---|---|---|
| 0 | 10 | 469.77 | 3 分钟 | 469.77 |
| 1 | 20 | 424.38 | 10 分钟 | 424.38 |
| 2 | 20 | 298.93 | 10 分钟 | 298.93 |
| 3 | 30 | 198.93 | 10 小时 | 191.73 |
| 4 | 50 | 74.33 | 1 天 | 67.54 |
| 5 | 100 | 36.58 | 1 天 | 28.52 |
发现 1 (Finding 1)
这些单词增加了 valid_length。将它们放在开头我们会获得优势。（粗体是 id3）
- reindeer jingle sleigh gingerbread peppermint decorations ornament wreath magi stocking chimney fireplace
关于 id3，如果你以"magi"开头，我们的算法可以在大约 3 小时内发现最优解。
供参考，id0 和 id1 以 reindeer 开头，id2 以 sleigh 开头。
我们还发现，将这些功能词（停用词）集中在一处并放在开头往往会导致更低的 loss。id4 的最优答案是 功能词 + 内容（其他）词。
- 功能词：and as from have in is it not of that the to we with you
Id4: 50! → 14! + 36!
Id5: 100! → 20! + 80!
| id | 单词长度 (len words) | 分数 (score) | 时间 (time) | 可能分数 (Possible score) |
|---|---|---|---|---|
| 3 | 30 | 191.73 | 3 小时 | 191.73 |
| 4 | 50 | 67.54 | 6 小时 | 67.54 |
| 5 | 100 | 32.4 | ??? | 28.52 |
发现 2 (Finding 2)
关于 id5，我们还发现：
- 内容单词按字母顺序排列会降低 loss
- 拆分字母顺序的内容单词会降低 loss
所以我们认为 id5 的最优形状大致是 功能词 + 排序 (内容 1) + 排序 (内容 2)
顺序将是 20! + 80C40？
32.41 → 28.574555 (排行榜 LB 246.82532)
最后，我们发现 and 应该从功能词中移除。
28.574555 → 28.529695 (排行榜 LB 246.81784)
