预告: Oɪᴏᴊ 在线评测系统

这个项目构思于大概三年前。我希望能够设计一种安全、高效、可扩展、基于xNIX的在线评测系统。但一直无法构思出一种合适的框架。最近幸运地遇到了 Eureka moment,便着手设计。项目继承了当年取的名字 OIOJ,代表 OIOJ Instructional Online Judge (受 lipeiqian 神牛思想影响)

基本结构功能

系统分Web服务器和评测服务器两部分。评测服务器用 C++ 撰写,运行在 Linux 上,但应该可以比较容易地移植到 BSD;Web 服务器使用 php,可以运行在 Windows 上,但显然毫无必要。

两类服务器之间使用 Socket 通信,每次评测传送程序和题目 ID 号码,数据预先存放在每台评测服务器上。

支持屏幕或文件输出(屏幕输出时把stdin和stdout重定向到文件)
支持交互式问题(每个题可指定依赖文件)
支持 special judge(Cena 格式)
支持提交答案类问题(传送 zip 压缩包)
支持多CPU(选手程序只允许使用1个CPU),可设置同时评测多个程序(每个程序一个CPU,或每个CPU多个程序也可以,但可能影响公正性)
每个评测服务器可设置时间限制乘数以平衡高性能和低性能服务器的差异

通过限制程序的系统调用、设置专门帐号调用程序、程序在 chroot 环境里运行的方式最大程度保障安全。

在 Web 服务器上添加题目,题目自动传送到每台评测服务器:题目基本信息由专有格式通过 socket 传送,数据使用 FTP 协议传送(为了防止阻塞评测服务器)。添加评测服务器相对简单,只要把已有服务器上的数据传送到新服务器上就行了。

服务器之间通讯安全由防火墙和 Token 来保护。

未来设想

考虑增加 Amazon EC2 支持,由 EC2 云计算平台提供评测服务。

完成时间

争取在十月内部署到学校,为今年的联赛培训服务。在学校进行测试后部署到互联网。

Stanford Summer Session 2011

After one year and a half, I'm going to step on this continent again, flying all the way over Pacific.

Excitement. Anxiety. Curiosity.

Wish me a splendid journey.

In Memorial of Jack Murray

Jack Murray
Principal of Perfect English
Resident of Changchun City, People's Republic of China, Citizen of the United States of America
deceased in this much-beloved land this morning, possibly of heart attack.
May Him Rest in Peace

杰克.莫瑞
佩尔英语校长
长春市居民, 美国公民
今晨离开这片他深爱的土地
原他的灵魂安息

SAT On Sale Booklist

如果你是互联网上无辜的旁观者,请略过这篇日志。
以下是我用过/不用的SAT2和AP辅导书籍,成色非常好,现3-5折出售。限同校。

注:PR = Princeton Review; Barron = 巴朗

原版
PR AP Physics B 60

引进版
Barron SAT2 Math 2 20
Barron SAT2 Physics 20
McGraw-Hill SAT2 Literature 20
McGraw-Hill SAT2 US History 30

国内影印版
Barron SAT US History 60
Kaplan Physics 35
Kaplan US History 35
PR Physics 35

国内复印版
PR Cracking SAT US & World History 25

附赠SAT2原版答题纸若干

F1 Visa in Shenyang

申请了斯坦福大学暑期学校计划,打算去呆两个月。3月21办签证。看到互联网上很少有在沈阳面签的经历,在这里写一下我自己的吧。
iPad 非常方便,不沉,电池还耐用。这篇日志就是在火车上写的。

领事馆门口居然没有排队的。我预约的两点,一点半就让我进去了。进去前遇到了点生理问题,虽说我知道里面有个条件很好的洗手间,但为了保险我还是在外面找地方解决了,要了一块钱,非常黑暗。
门口一个武警把守,我一个很小的挎包也不让带,只能带文件袋。把包送走后,查验了护照就放我进去了。
PS, 领事馆门口对面有个老大爷提供存包服务,很明显要钱。
放进去后直接看到一个窗口。他会向你索要护照和身份证。没带身份证不要紧,告诉他信息也可以(似乎是地址和身份证号)我前面的黑龙江MM就是如此。
然后向左走,最左边的门的左边的窗口交验护照和DS160。然后在那个门过安检。
有人说成绩单需要封好盖戳,实际上如果你这么干了的话,安检你都过不去。未开封的信件不让带(怕是恐吓信或夹带不明物质?)黑龙江MM也是如此。
然后在那个门过安检。安检的同志说那个看上去比我大好几届的黑龙江MM居然只有15岁??!!(不好意思黑龙江MM,这篇文章你会贯穿始终。谁都知道办签证时所有人都会观察前一个人的待遇,嘿嘿),然后说我看上去不像18岁而要更小(orz…对比的力量)
安检和机场差不多,就是严格了很多而已。
从安检的小房间另一头出来,被指示走类似无障碍斜坡的通道而不能走右边宽敞的台阶,没想明白原因。也许是监控吧。
进到签证大厅,第二次安检。然后就可以从一个小走廊进入一个类似银行营业大厅的地方。
首先到6号窗口交材料。什么照片、I20、DS160啥的一股脑递上去。他们会给你一个号,数字比较大(600多)。然后你可以去休息了。
经过漫长的等待,你会被叫到(去5或6号窗口),他们把那堆东西装袋后都还给你,让你去按指纹(4号窗口)你把那堆东西给指纹工作人员。那个工作人员很搞笑:"你是不是很喜欢打video games""no…?""sorry。我就是随便猜…总猜不对…"似乎是因为…我按指纹时手是弯的,活像拿鼠标…他在文件袋里放上一个新号(比较小,1xx),又还给你了(而不是直接给签证官)。听到黑龙江MM去读私立高中。(去美国读公立高中比较麻烦,需要支付所有产生的费用,因为人家的高中是义务教育…可是谁知道你到底产生了多少费用…)
漫长的等待…幸好带了本书…人比较少只开了一个窗口。但迫近我的时候,又开了一个窗口,167号过去了,一个坐在我边上的F1哥哥。只见老窗口一个一个通过,他还没有回来。我的心一沉,不会摊上他吧…
幸运的是(对他不幸的是),叫到我时他还在谈…
早就听右边签完的女孩说2号签证官很好,胖胖的可爱的女的,果然名不虚传。不过之前没听说过她(之前去沈阳都知道那里的签证官凑齐了三大人种,一个白人一个黑人一个韩裔)她先用中英文说你好,然后切入正题。问的就是最基本的问题,不用我说你也知道是什么﹣
你为什么去?
你去上什么课?
谁掏钱?
当然都是英语。
因为我去过美国,她还问我那次去干什么、多久。
"Your visa application is approved"
可以算水过吧,我的材料都没看。
她听我去学数学,把我夸了一通。
看我下周一过生日,还祝我生日快乐。
非常好的人,好人一生平安~
她把护照留下、I20和SEVIS收据还给我,给我邮寄回执。至此,签证申请完成。

如果有经验可言的话,自信是最重要的。反正你也不想移民…

2011情人节: 密码学和暗恋

没有情人的情人节...更新一下blog好了,写一点应景的东西——一种利用密码学解决暗恋问题的方法

我们知道,暗恋的关键在于“暗”字。这意味着出于某种原因,你不愿意把你所喜欢的对象公诸于众。这带来的问题就是,你无法知道你所暗恋的对象是否在暗恋你。假如真的如此,那么一段美好的姻缘岂不是就此展开?然而信息的不对称使得你不敢采取进一步的行动。这大概是电视剧、电影中非常经典的桥段了,例如《加菲猫》。

非对称加密系统的出现为这一问题的解决带来了希望。假定你不知道我刚才说的是什么意思,下面我做一点简单的解释。如果你知道,越过下一段(大概可以越过全文了吧?)

传统的加密算法在影视剧中被反复渲染。需要秘密通讯的两个人维护一个密钥(比如说密码本),一个人按照某种规则利用密钥作为参数将信息编码,另一个人则如法炮制反过来将信息解码。比如,凯撒移位密码(介绍在线加解密器),把每个字母用其后的t个代替。这种代替便是规则,参数t就是密钥。任何一个知道t和密文的人都能解开。然而,这样有一个弊端:为了通讯安全(比如,潜入我军内部的特务),任意两个人通讯的密钥应该是不一样的。这样,假设有n个人,总共有n(n-1)/2个密钥需要维护,这无疑是很大的负担——随n呈抛物线形增长。而非对称加密则解决了这一问题:每个人维护一对密钥,分别用于加密和解密。用于加密的密钥公开,称作公钥。这样,想发送信息给你的人用你的公钥加密后传给你。而你使用解密用的密钥,称为私钥,就可以把信息还原。这乍看以来很难实现,怎样做到公钥只能用于加密而不能用于解密而维持信息的完整呢?幸运的是,目前有许多算法可以做到这一点,最早、最著名的是RSA,除此以外还有椭圆曲线等算法。

我们假设 Jessie 暗恋 Charles。Jessie 可以把自己的情书用 Charles 的公钥加密,然后公开。其他人呢?只能看着干瞪眼,完全不知道 Jessie 所暗恋的对象是谁或者写了哪些肉麻的语句。而如果幸运的是,Charles 也喜欢 Jessie,而又看到了Jessie 写的情书,他便可以试探性地用自己的私钥解密。Bingo!让我们祝福幸福的他们俩。

如果 Jessie 是个万人迷,碰巧 Fidel 也喜欢她。看到 Jessie 的情书,他满怀希望地用自己的私钥解密,可惜什么也没有得到。沮丧的他只好放弃幻想。

Shaelyn 对爱情心灰意冷,因此没有任何兴趣暗恋谁。然而,看到他没有公开宣布暗恋某个男生,许多对她早有好感的男生都主动献殷勤。于是,Shaelyn 自己生成了一对密钥,把《数学竞赛章程》加密了一下然后公布了出去。

Fanny 很害羞,问能不能在只有对方喜欢她的情况下才让对方知道自己喜欢他。可惜这不可能,因为喜欢是一种主观的、无法测量和鉴别的东西。对于她,被动地等待他公布情书然后去解密大概是唯一的选择了

暗恋说穿了是经济学上低效率经济的代表。所以多数攻略建议大家主动出击。可惜,如果所有人都袒露胸襟的话,暗恋这个词就不存在了。至少我不敢

只能说有情人终成眷属吧,不管是明恋还是暗恋~

Hackindroid

最近异想天开准备学习Android开发,因为上手容易,成本低廉(苹果的会费居然要199美金,最重要的是不交会费不能在真机上开发,Android不存在这个问题)。可惜没有Android手机,又不能特意买一个。幸好我找了一台Touch Diamond和一台iPhone 3G,都可以装Android

懒人直接看结论:这两个都能装Android,但都不适合搞开发

首先,安装颇费一番周折。经试验,Touch Diamond上最好使用connect-utb.com的作品,iPhone则是iDroid的Bootlace.具体如何操作,都非常简单,在此不赘述。大体来说,Diamond的话,把压缩包解压到手机内存里,把andboot\STARTUP CONFIG\DIAMOND100\里的txt文件放到andboot根目录,重命名为default.txt,在手机上运行haret.exe,看着Linux启动,然后校准下触摸屏,等android启动搞定。iPhone 3G更简单,下载Bootlace(在bigboss源里),启动,按照提示装好里面的两个组件,再重启就是双系统了

但是,虽然声称支持,我没能在任何一台机器下USB成功连接电脑。这样的话何谈开发?经过一番研究,这是可以的,诀窍是在WM里设成ActiveSync,然后在USB连接的情况下启动android

其次,系统不太稳定。尤其是iPhone-扬声器不断发出怪响,好似要爆炸;不能待机,所以极其耗电;WiFi不太正常...

再次,速度比较慢,虽然也在容忍范围(但比模拟器好一点)

结论?想搞开发的人,要么买一台机器,要么...洗洗睡吧

New Journey

2010.会考

班级后黑板写着一句话,余很以为然:

再多说该和谐了,我就此打住吧

Mark of a New Beginning