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由C，J，?三者组成，其中每出现一个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%的要求了。
Round1A
赛程回顾
这场国内在周六早上，正好可以做一下。两个半小时3个题，top1500晋级。看到只有3个题时觉得应该稳了。一上来搞了第一题，结果出了一些小状况卡了不少时间，最后快50min才ac。第二题受第一题卡题的影响，脑子锈逗算错了复杂度，把本来可以水大数据的题硬生生做成了只能过两组小数据的题。。。第三题又次锈逗虽然想出了正解，但写了半天没写对，还发现答案会爆long long，最后评估了一下水了一下小数据，比赛结束。。。rank 1448 = =！勉强卡过。
赛后整理了一下思绪，草稿纸上演算了一把，才勉强把2,3的大数据过了。感觉比赛有个4小时应该能做完~~
2.5小时还是有一定难度的。
A） Append Sort
问题大意:
一些十进制的数，排成一行。需要你将该序列修改成递增的序列。操作不准挪位置，可以做的操作就是在每个数的末尾添加若干个数字（0~9）。没增加一个数字，花费为1.求完成排序的最小花费是多少？
思路:
显然贪心是对的。依次通过修改 A[i+1]` 让 `A[i] < A[i+1]` 成立，且保证`A[i+1]
rule需要耐心一些分析，原则就是能不多一位就不多一位。主要考察细心吧。
B） Prime Time
问题大意:
M个不大于500的质数，M<10^15
思路:
其实这是个乍一看很难，其实分析一下不难的问题。
暴力：设SUM是M个质数的和，那么和的那组最后的和X一定0<X<SUM`，枚举X for X in range(SUM), 对X质因分解。分解后就知道另一组的元素有哪些了（因为M个数都是质数所以有唯一的集合）。然后看看这个集合的和是不是等于 `SUM-X
但显然不能枚举10^15这个数量级。但我们知道2^64 > 10^15` 所以积的那组不会超过64个元素，所以 `SUM-X < 500 * 64
B） Hacked Exam
问题大意:
（未完待续）