Day 0

因为去年就参加过 CodeCraft 2021,但是当时和一些比赛及其他事情冲突了,因此初赛甚至都没提交就而结束了。今年本想着来拿个手环呢,妹想到啊~~~啥也没捞着啊

关于队名我倒还觉得挺有意思,baseline这个名字被官方 ban 掉了,去年参加的时候就用的 --baseline--,今年相较去年认识到了很多 Unicode,本想着找个字符替换,妹想到啊,应该是只支持 ASCII,试了一下 baseIine,在那个名单中的无衬线字体是没有 I 上下的横线的,看起来跟baseline一毛一样,估计官方也没想到有人这么起名吧 hhhhh

练习赛

整个赛题比较简单,有一些服务器(边缘节点)和客户(客户节点),每个时刻(把一段时间抽象成一个时间节点)客户有需求,服务器要分配带宽给客户以满足需求,但是服务器和客户的链接要满足延迟需求,最后成本是带宽序列的 95 计费。

一开始 95 计费没搞清楚,还以为是每个时刻的 95 计费呢,随便写了个贪心交上去居然有分,开门 134w,自己写 judger 的时候才发现搞错了。

另外就是写贪心的时候,我拿 pandas 嘎嘎就写完了,不到 20min,交上去一直运行错误,后来才意识到根本没 pandas tnnd,改成 numpy 直接读入 txt,逗号划分就可以了。但是代码里用的 pandas 的索引全寄了啊,无奈只能重写部分内容。

还有一个坑就是数据读入要从根目录开始,麻麻了。

然后我当时以为就是负载均衡问题,于是写了个平均的方法,反而比贪心拉了?然后就是觉得是选择顺序问题,魔改了几个排序,甚至都不如我第一次交贪心跑的高(第一次交贪心也是排过序的,按照带宽和能够处理的 Client 节点数量排序,先使用高带宽少节点的服务器)

中间还考虑过二分答案,限制最高阈值看看能否可行,再套一个网络流来试试。

这可能根本不是负载均衡问题,然后就从 95 计费出发,去白嫖那 5%,果然,效果嘎嘎提升。只需要考虑需求顺序,对于每个边缘节点单独处理 5% 的需求,随便改改大概就有 60w,最后改改了参数什么的就到了 40w,然后就一直躺平,交了第 2,寻思差不多也能进复赛了,但是最后几天从第 2 一直跌倒了第 20,此时的我还没意识到问题的严重性 - -。

初赛

初赛第一天有点事就鸽了,回来交了一下之前最好的结果,发现不保证客户节点的顺序了,麻了,改改交了也只有 40 来名的样子,随后试了几个自己想法,提升不大,终究是算法问题。之前练习赛的时候就写过网络流和费用流,无奈 Python 跑太慢了,确实是搞不过,我是觉得二分答案 + 网络流的做法还挺科学的。

开摆,搞我自己毕设去了,浪费时间。

写在最后

说实话,虽然自己懒了,但是参赛体验还是很差的,前面练习赛还好,大家都是正常问提交问题,到后面开始不同的人交流思路,搁这分苹果是吧?就练习赛最后几天,大家一下子都变聪明了呢,嘻嘻。初赛了,聪明人又变得更多了,嘻嘻,好多练习赛都没见过的呢,嘻嘻,真棒啊。

后话

喜提粤港澳 64 强,混了个证书 hhhh

明年不会再参加了。