codechef MAR14 challenge

其实接触cc的challenge是 很早之前 的事情了,去年8月是第一次打challenge。
后来几个月的challenge都有参加。
每次参加的时候都是斗志满满地想干个⑨题啥的……但是每次都是做五道水题就弃疗了。
最近一次是冬令营回来之后,刚好是FEB14 challenge的最后一天。
因为做过那道COT5……感觉最难的那道都会做了, 似乎是完成那个⑨题成就的最好机会了。
然后就花了一个上午切了前五道通过率最高的水题,结果遇到了第六道就不会做了,就弃疗了。(后来发现第六道也是大水题)
以上就是我打cc的辛酸血泪史
直到这个月的challenge……我才完成了成功出⑨题的成就……但是感觉这次的题目……呵呵

situation

3月8日愉快地补觉到中午十二点,接下来刷人人发现zhonghaoxi在这场cc刷到了rank1。
然后想起cc刚好在3月七日开始,不算太晚。
接下来看到榜上fancycoder/zhonghaoxi/huzecong等人都切得飞起。
然后就恰好没什么事情做……就决定来搞一搞了。
花了两三个小时搞掉了通过率最高的前七题。
然后看了一下Chef and Graph Queries这题。
发现不怎么会做,然后凭着以前做hnoi那道城市建设和ahoi那道连通图的经验,感觉可以用cdq分治。
又随便yy了一下发现我想的分治方法可以很轻易地构造数据卡到单组数据
但是不死心的我坚信出题人是不会卡这么乱搞的做法的,然后写了不到一小时写出来了。
接下来就测试了一下发现这乱搞做法在随机数据下都比暴力慢不知道多少倍,但是我还是勇敢地交上去了,结果自然是怒收获一个tle。感觉不能更,b。
然后就想分块,接下来又想了一个时间复杂度极其不靠谱的乱搞方法。
结果分析了一下复杂度,感觉时限8s的话…… 似乎乱搞没啥希望
但是我还是写了一下,花了半小时搞完代码之后。测试了一下时间,发现本机单个随机数据用时12s。
我觉得是自己没开o2所以这么慢,然后开了o2。发现o2效果拔群。
上图你们感受一下。


开o2后12秒变成了15秒……当时非常想说wtf。
然后抱着大胆提交,放弃治疗的心态,面对这题单点时限8s而本机12s的现实,我还是交了上去...
结果居然过了……不吐槽……
然后接下来看了一下The Street这题。
发现出题人完全是在骗钱,把两道经典题揉在一起,然后把n稍微出大了一点就变成他的题了……
然后也懒得搞了,就出去玩了。
到了今天(3月⑨日),早上起来和同年级的六百多人抢选修课……感觉略逗。
抢完之后随手搞了一下,查了个傻逼错误交上去就过掉了……然后就达成了cc⑨题的成就了233

所以接下来几天的时间就是来战sereja了!

sol

比赛还没结束……题解就算了……

Comments

comments powered by Disqus