Qualification Round

赛程回顾

最开始其实记错了资格赛的日期,原以为今年和往年一样是周六或周日早上开始,所以周五晚上睡觉前确认了一下日期,结果发现比赛已经开始了。。。
于是瞄了一眼题目,发现还蛮简单,准备水几个再睡觉,结果一做就到凌晨2点。还好没太卡题,不然可能就到第二天早上了。
总体来说,今年资格赛题目水准依旧不错,中等题不需要太多冷门数学知识,就可以解出,非常良心。

A) Reversort

问题大意:
一种反转排序的方法:

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

定义: 一次Reverse(list)操作的cost=len(list).
求给定原始序列L,计算Reversort(L)总操作成本是多少?(len(L) <= 100)

思路
这个方法和冒泡排序类似,很容易发现O(N^2)不是很大。暴力模拟+统计即可。

B) Moons and Umbrellas

问题大意:
一个字符串S由CJ?三者组成,其中每出现一个CJ子串需要花成本cj_cost,每出现一个JC子串需要花成本jc_cost。问合理安排?(将?换成C或J),使最后S的总成本最小。输出这个最小成本。

思路
这里如果cj_cost和jc_cost都是非负数,那么是有贪心方法的,因为连续的?(如?????)最优时一种分配方法就是全替换为C或J。那么枚举各个连续?构成的子串就可以求解。
不过这里有一个价值1分的测试集表示cost可能为负数。
那就只能DP了,f(i, suffix)表示s[:i]最后一位是suffix字符时,最小cost前缀的cost。然后O(N)的dp可解。

C)Reversort Engineering

问题大意:
问题A)Reversort的逆向工程问题,输出一个序列L,使其在长度是N的同时恰好Reversort(L)总操作成本是C.

思路
首先比较容易发现如果我们知道全过程中N-1步每一步操作了多长的子序列,那么我们只要逆着操作N-1次过程,我们就能从{1,2,3,..., N}还原出排序前的L了。
那么如何构造一个合法的操作序列OP呢?(定义:OP[i]为第i步翻转了OP[i]长度的子序列)
首先sum(OP) = C, 然后满足1 <= OP[i] <= N-i.
很容易想到贪心的策略去构造OP。
有了思路下面coding就很简单了。

D)Median Sort

问题大意:
说有N个对象需要排序,但是现在只有一个识别机器来辅助你完成这个事情。
这个识别机器它能做的Query只有一种:
你输入3个对象给它,然后它会告诉你这三个对象中谁应该排在中间。
显然只靠这个机器你是没法完成排序的,但是又显然如果你排好的序列只要是单调的(即无所谓它是递增序列还是递减序列)就算合法的话,那么你可以完成这个任务。
现在要求你设计一个算法,尽可能用最少的Query去完成这个任务。
要求: N = 50, 一个任务平均Query次数不超过170次。

思路
这个问题其实已经不是简单题的范畴了,首先可以先想一个暴力的方法。
假设已经给定一个已经拍好K个对象的子序列list(这个序列是单调的),那么如何加入一个新的对象e?
最简单的想法就是从i=0到i=k-2依次去检查(list[i],list[i+1],e), 显然有O(K/2)的暴力方法找到e的位置。那么这个方法的总复杂度大约是O(N^2/4).
对于170来说成本太大了一些。
不错你很快会想到二分的方法把复杂度降到O(N * log2 N)。对这题依然是不够的,因为一旦K大于16每次添加就变成4 ~ 5次超过32时就变为5 ~ 6次,这让算法能平局稳定在170次内基本不可能。
但是由于一次query输出结果可能是三个,那么理论上信息有效利用的话,编码应该是能在O(log2 K)上完成的。受这个启发比较容易想到新的编码方法:
把当前串等分为3个区域和2个交界[****A****]X[****B****]Y[****C****]每次我们query(X,Y,e)那么能得到e落在A,B,C中的哪个。然后再递归这个思路,最终得到O(N * log3 N)的算法。这样就能平局在170下了。
实现上需要仔细一些,因为O(log3 N)被哪怕不小心写成O((log3 N) + 1)最后也是致命的。

E) Cheating Detection

问题大意:
100个选手,10000道题。每个人都要回答全部的题目。
每个人player[i]有一个能力数值S[i]; 每个题目question[j]也有一个难度数值Q[j].
一个选手i 能回答对 问题j的概率是 prob(i, j) = 1 / (1 + exp(- S[i] + S[j])).
已知:S[i]Q[j]都是在区间[-3.0, 3.0]上随机均匀采样的。
但是在100个选手中有且只有一人选择了作弊,作弊的策略是:
对每一道题0.5的概率采用正常方法作答prob(i, j)是其答对的概率,或者0.5的概率作弊那么答对的概率直接变成100%。
现在给你每个人10000题的对错结果(即你有100x10000的表格记录着全部的结果)。
问题:从这个记录中分析出作弊者是谁? (该程序需要有86%的准确率)。

思路
这题让人有点摸不着头,迷失探索的方向。
这时不如从分析prob(i, j) = 1 / (1 + exp(- S[i] + S[j]))开始:
首先一个题很简单Q[j]=-3,然后这个人很强S[i]=3那么答对的概率几乎接近1.0。最弱的人S[i]=-3,只有0.5。
但如果很难的题Q[j]=3,即使最强的人S[i]=3,那么正确也只有0.5.最弱的人s[i]=-3,接近0。
所以,作弊到底改变了什么?
大致可以看到最弱的人,可以把最难的题水平直接拔高到最强的人一个水平0.5,如果最强的人还作弊,最难的题他甚至能达到远超过期望0.5的0.75这个大小。

此时你可能已经找到一个非常不错的策略去查作弊了。
就是观察一个人对最难问题的回答情况,如果他能达到0.6的准确率,基本上是作弊无疑了。
但可惜这离86%的准确率要求还差不少。但似乎已经很接近了。

如果一个维度不能分别,那就再加一个维度。很容易想到另一个极端,最简单的题目:一个很强的人无论作不作弊,最简单的问题都是几乎100%完成的,但一个很菜的人即使作弊也只能达到75%的完成度,而这与其作弊后最难题的0.5完成度构成鲜明的反差。

那么只需要统计每个人的2个特征,几乎可以完成判断。对每个人来说:

  • feature 1: 最难5%的问题的准确率,hard[i]
  • feature 2: 最易5%的问题的准确率,easy[i]
    那么用feature=(hard[i], easy[i])去做识别。
    (最难最易的题怎么得到?直接统计答对的人数,排序呀。毕竟总是99个正常人和一个异常人,那么期望的排序顺序是不变的。)

如果强写rule去区分这个二维空间,还是稍微恶心了一些。我们定义一个距离来降低这个难度:
我们把正常人可能的得分期望曲线找到,即S[i]从-3到3离散枚举,计算(hard[i], easy[i]),然后连起来,得到曲线L1;再把作弊者的得分期望曲线找到,即S[i]从-3到3离散枚举,计算(hard[i], easy[i]),然后也连起来,得到L2。
然后对每个人的实际统计的feature计算到两条曲线的距离为d1和d2. (距离可以定义为到最近点的距离)
然后用softmax去计算排序的指标(类似一个0~1的概率),获得最大概率者,输出为作弊者。
softmax=exp(d2)/(exp(d1) + epx(d2))

这样其实已经远远超过86%的要求了。

(未完待续)