扒一扒某人的美本申请材料

发布时间 2023-09-15 07:22:22作者: DDG-1000

https://www.zhihu.com/question/270879035/answer/1632803651 这是该人的知乎回答,此人的申请材料看上去非常nb,然而仔细看还是能发现一些问题。

1.首先,作者声称提出计算斐波那契字符串前缀和的O(1)算法,然而这是学术造假。
来看一下作者的论文:http://www.yau-awards.com/uploads/file/20210817/20210817113608_48184.pdf
作者定义字符串\(f(n)=f(n-1)+f(n-2)\),+是拼接,\(f(1)='0',f(2)='1'\),斐波那契字符串\(F(n)=f(1)+...+f(n)\),要求出\(F(\ inf)\)的前\(k\)项和
有个暴力算法可以在\(O(\log_2k)\)的时间复杂度内算出\(F(\inf)\)的前\(k\)项和
作者声称,公式\(a_n=ceil(\frac{\sqrt{5}-1}{2}*n)\)导出了斐波那契字符串前\(n\)项和的公式。
作者的实现的代码如下:

#include<iostream>
using namespace std;
const long long G[3]={61803398,87498948,48204587},P=1e8;
long long n,f[3],A[5];
int main()
{
  cin>>n;
  f[0]=n/P/P,f[1]=n/P%P,f[2]=n%P;
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
      A[i+j]+=f[i]*G[j];
  for(int i=4;i>0;i--)
    A[i-1]+=A[i]/P,A[i]%=P;
  cout<<A[0]*P+A[1];
  return 0;
}

这个代码在做什么呢?

G[3]={61803398,87498948,48204587}$

事实上是存储了黄金分割比的小数部分,下面的代码事实上做了一个压位高精度乘法(可以视为\(O(1)\)
然而求出\(\sqrt(5)\)事实上需要二分/牛顿迭代,时间复杂度还是\(O(字长)\),与暴力算法无异。
当数据范围一大\((2^1000)\),则论文内的算法需要求出\(\sqrt(5)\)精确到\(1000\)位的结果,时间复杂度是\(O(1000^2)\)
暴力算法只需进行\(1000\)次加减法,判断大小,时间复杂度也是\(O(1000^2)\)
(以后补写这个暴力算法)
paper作者作为OIer不可能知道时间复杂度的概念,所以只能说作者造假。
2.星际争霸2国服宗师锦标赛冠军:几乎不可能,除非那篇文章的作者是sc2职业选手,否则不可能水平比国内的职业选手还高。
3.设计AI为炉石传说竞技场选卡,73%胜率
但是没说谁打了选出的卡组,以及此人的水平高低,没有参考价值。
4.USACO2020公开赛铂金组全球第8,Codeforces等级分2433,Grandmaster
现在线上比赛都可以造假,所以也是没有什么参考价值。
5.NOIP2018一等奖/NOI2020铜牌/APIO2020银牌
作者事实上是D类铜牌,而不是正式铜牌。
而且作者的分数除去笔试只有157,在所有正式选手中只排行210多名。
USACO 白金组的题目至少也有中等省份省选难度,在这场比赛中拿到917分(大概相当于省选270分)的实力在国赛也至少能拿到银牌前100名(拿到简单100+48+52+45+28+5)。这说明作者大概率在USACO中作弊了。
综上所述,作者因为材料造假才导致申请结果相当不好。