昨天我尝试去做这道提答题,写了一个随机调整,能把除了 task4 之外的所有点在 10min 内求出答案。然后我又尝试用 SAT-Solver 来求解 task4(用的是 cryptominisat5 和 kissat),可是它们都未能在 6h 内跑出答案,一直卡在 87%。
然后我考虑二进制拆位把点数从 8n 拆成 3n,然后再挂了俩 SAT-solver 求解。
到了今天早上我后台一共有四个程序,俩跑了接近 14h,俩跑了 9h,这四个程序跑了一晚上,一个得出结果的都没有!
我认为造数据人造这个 task4 的方式就是,先生成一个答案序列,然后随机加限制,如果限制和答案不冲突就加上,知道加满 123456 个条件。这样就有个后果就是可行答案数非常少。随机调整啥的很容易陷入一个「满足大部分条件但是正确答案相差非常大」的解,这就能解释为啥我 sat-solver 会卡在 87% 了。
然后我看了下提交记录,目前所有未隐藏的提交里,没有一个提交是能过 task4 的(那个 AC 的应该是出题人测试),现在我就想问一下,究竟有没有一种算法,能在比赛要求的 8 小时内跑出 task4。
出题人 w33z 对 task4 的题解是:「给更优秀贪心或者剪枝」,但是他说他根本没写 std,也就是说,至少目前,没有一个程序是能够满足上述条件的。
我已经在这题上卡将近一天了,如果有人能提供关于 task4 的信息,比如 task4 的数据生成器,一种可行解或者是能过 task4 的程序,请私聊我,万分感谢。