UOJ Logo matthew99的博客

博客

关于“鏖战表达式”错误复杂度算法水过现象的看法

2016-02-27 21:42:39 By matthew99

WC2016鏖战表达式一题,松爷(王逸松,鏖战表达式出题人)在WC上讲了复杂度为每次操作$O(k + \log n)$的做法,即所谓的树(套树)$^*$。然而民间流行一种直接用treap维护的,并把优先级比较定为比较运算符,运算符相同则根据子树大小用概率比较的做法,复杂度为$O(k\log n)$,为什么呢,因为我们先加入一堆1,再加入一堆2,一直到一堆k,每一次新加入一堆运算符,不能改变前面运算符的形态,因此复杂度是$O(k \log n)$,直接提交会得到七十到八十的分数,由于此题数据强度不大,因此稍微根据数据进行修改一些实现细节即可水过。

松爷与我曾多次提到过此事,我也认为此事十分不妥,作为一个很好的数据结构题,留下的却是一堆的水过,以及不断的有新人抱着以为这是正确的做法的心态去写,最后却死活过不去而只能跟着水过的事情。幸运的是考场上并没有人水过。

本题作为一道特殊的题,难以像现在大部分UOJ上的题一样支持hack和extra test,甚至考场数据和grader都使用了特殊的方法加密,因此想要阻止这种现象只要两条路,一是通过@vfleaking等管理员来手工添加一些extra tests强行卡掉复杂度错误的算法,二是靠大家的理解和自觉,理解这种算法的不正确性,并自觉不使用这种算法。

这里我提醒一下大家不要再陷入错误做法的泥潭中。

对于那个$O(k \log n)$的做法,本人也进行了一些改进,可以参见http://uoj.ac/submission/50137注意,提交统计里面显示的我的提交是我之前跟着大家水过的程序,并不是这份代码。

我大概是在merge和split的时候进行了一些rotate,具体复杂度无法给出详细证明,但是感觉是$O(k + \log n)$的可能性还是比较大的(当然也有可能是$O(k\log n)$,或者甚至$O(\sqrt{k}\log n)$, $O(k \log k + \log n)$, $O(k \log \log n + \log n)$这些鬼畜的复杂度233,大家还可以继续脑洞),大家可以感受一下我改动的地方。如果觉得我的做法也不靠谱可以学习松爷std程序的做法。如果有谁卡掉了我的做法或者是证明了我的做法的复杂度的确是$O(k + \log n)$,欢迎与我讨论。

评论

Recursion
我一直以为那个做法复杂度是一样的[捂脸熊]
mxh1999
雾。。。 感觉能水过的题大家应该都会去水过? <del>人就是这样一种生物。。</del> 以上个人观点,说错轻喷。。 = =还是提倡大家使用正确算法吧。。
dwjshift
资瓷加数据!感觉hack功能就是为了这个而存在的呀 (以上口胡 (我就是那个跟着水过去的新人
bzoj
我觉得能过的算法就是合理的,单纯形复杂度都不是多项式,但实际表现非常好。一个题并不是标程是唯一正解,能通过数据的算法就是好算法。
CJCJLLL
我是第一个尝试水过(刚加题时那一坨95分)、第二个成功水过的人(第一个是猪猪侠)。 我感觉这个算法并没有什么特别大的问题,只是“操作次数常数”较大。 举例:如果在build的时候使用merge,只能70分,第19个点要3kw次操作。但如果使用基于绽的表达式解析,并O(n)建树,单点修改时不使用split、merge而是专门写操作,能拿95分,第19个点大约只要1.1kw的操作次数。就算构造了类似111112222233333.....100100100100这样的数据,不停的修改很小的区间,操作次数也不会超过1.2kw。 这样,初始建树虽然高度是klogn的,但似乎后来会变小。 松爷有说一种神奇的时间nlogn操作数线性的建树,但我并不知道。。
sxy_cnyali
%%%%%%%%%%%%%%%%%%

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。