ACM

北京之行 – Snoopy简略篇

Posted on by snoopy

北京之行 – Snoopy简略篇

Nov.9 周四

买好吃的去火车站, 到火车站后迅速找到 HUST 两伙人, 打个招呼就分别上车了, 一个在车头一个在车尾…

晚上在火车上拍了 KO 的裸照, 同时半夜发生了集体翻身事件, keke…

Nov.10 周五

到达清华, 小见识了一下北京的堵车, 不过很遗憾, 没遇上传说中的特能侃的出租司机. 等 DeathDecay 一队人到达后去报道, 看见了复活赛正在进行中, 暗暗 wish 了一下 Gardon. 搞定住宿. 中午在 KO 带领下沿着清华校车的路线兜了个大圈然后到达清华西门想寻找传说中的西门鸡翅, 无果, 找了半天依然无果, 累的半死的一群人饥不择食的随便进了个地方吃完搞定.

下午去参观 Google, 路上去清华东主楼看了看复活赛结果, Gardon 领军的 HFUT 两个半小时搞定全部六题, 昂首阔步迈入决赛(事实证明我们应该好好 wish 自己的). 去 Google 的路上一群人在互相认识, Sempr 在和无数人拿着 DC 对拍后到达 Google, 在里面转了一圈. Google 果然是一个极好的去处, 环境非常好, 到处是 24/30 的 LCD, 还有 ThinkPad X60. 在大厅拍了一个很恶的东西, 顺路一群人在 Google 大厅里上网 ip 留念, 顺了一袋纪念品和一堆吃的后跑路.

晚上无聊, 看电视, 睡觉.

Nov.11 周六

上午开幕式, 其实也没什么, 惯例的领导讲话和鼓励, 很快就完了. 中间清华的系主任在很坦白的挖人, 我才跟 Sempr 说不是这么明目张胆的吧, 然后上面就说 “我这不是在挖人啊”, ft. 我们回去后董老师和 KO 去参加教练会, 快中午的时候回来告诉我们抽签结果, Moonmist -> Team15, DeathDecay -> Team41.

下午去练习赛, 清华把所有队伍分在了4个机房, 我们和 DeathDecay 在斜对面房间. 题目质量不错, 我们过两题的速度还不错, 第三题有一个很巧妙的地方, 到完的时候都没过. 中间去上厕所的时候发现 ACRush 在 DeathDecay 那个房间送打印纸, 小 ft 了一下, 最后完的时候只有 PKU_RPWT 过了, 去问 frkstyc 的时候把讲题的任务推给了 ACRush, 然后一群人围着听完讲解, 不过貌似最关键的地方被带过去了, ft. 练习赛的时候居然可以上网, 在 PC^2 上问了一下这个, 估计还是练习赛没注意吧, 系统是 FC1 而不是传说中的 FC4, 有些奇怪, 不过对我们没影响, gEdit 能高亮和自动缩进还有括号匹配我们已经很满足了. 因为不放心, 在 PC^2 上问了特别多问题, 几乎 1/4 都是我们问的, 也测了很多地方, 比如 longlong 还有 gets() 什么的.

晚上打牌, 睡觉.

Nov.12 周日

比赛, 比赛过程在赛事总结写.

下午比赛完了合影, 有听 Kaifu Lee 的报告的活动, 我们没去, 直接回宿舍休息了.
晚上晚宴, 无数人对灌, RC 很快就被 KO 放倒了, 有关 OOXX 的事略过不提.

晚上颁奖晚会, Moon 和 KO 扶 RC 回去了, 剩下 Tank, mmd, catcat 还有我一起去拿两块铜牌, 不过听张一飞很比较仔细的点评了题目, 还是比较值得的.

Nov.13 周一

相对晚点起来, 一群人争论了半天最后决定去香山玩, 在香山上兜了个最大的圈盘旋到顶, 中间多次抄道走, RC 手划伤后就一直在大路上了. 坐缆车下山, 因为实在是饿了并且不想走了. 到山下后一群人开始买纪念品, 我只是随便看看, 什么都没买. 吃面闪人, 在此特别提醒香山脚下不要吃大碗的牛肉面, 虽然是大碗, 不过面少并且只有3-4块牛肉, 相比较而言 RC 选的刀削面是很赞的.

回清华后就准备去北京西了, 路上被堵了个半死, 在火车站草草吃了点东西就上车了. 火车上看了看相机里的照片, 看到最后一张定格在 Ranklist 上, 难过的睡着了.

Back with no medal

Posted on by snoopy

36 hours early we got off from Z11, and with no medal, although there is two copper, but in my eyes, they are nothing.

We’ve hoped to win a qualification to the final, but at last only a copper, with too many stupid mistake. I still don’t know why we didn’t code the H, sigh.

Hope for Shanghai, hope that won’t be my last show. Good Luck, we are the Moonmist, we are the future.

出发去北京

Posted on by snoopy

Nov. 9th
武昌 Z12 到北京西, 晚上 20:49 发车, 离开武汉.
Wish our Moonmist, wish DeathDecay, wish our WHUACM.

Nov. 10th
早上 7:14 Z12 到达北京西, 去清华园, 报到, 安排住宿. 也许我们会去 Google 玩, 看看所谓的极尽奢华, 看看那个万人追捧但是我觉得越来越只是个伪图腾的 KaifuLee.

Nov. 11th
上午教练会, 下午我们会去试机, 记得看看 vim 的配置, 记得改好 gEdit 的显示, 记得看看 long long 等乱七八糟的细节问题, 还有键盘. Java Challenge, 可以考虑玩玩 :P

Nov. 12th
正赛, 没什么好说的, 好好发挥就是了, 希望晚上我们能是获得最多闪光灯的队伍, 希望我们是笑的最灿烂的队伍.

Nov. 13th
准备归程, 一天的空闲时间说不定还是 WHU 的保留节目去故宫玩. 晚上 20:49 北京西 Z11 回武汉.

Get Ready for the Regional Beijing

Posted on by snoopy

This Thursday evening we will travel to Beijing, then we need to do a extra work on this weekend. Tsinghua offered 10 Gold, 15 Silver, 20 Copper medals for the teams, more than Chengdu and Hangzhou last year, and less than Beijing last year, but I think that’s enough, and we’d better to win a Gold medal to prove us, and prove our Wuhan Univ. be strong. For Fudan Univ. got the qualification to the Final on Dhaka, Peking Univ. and Sun Yat-Sen(ZhongShan) Univ. got the qualification on Seoul, Shanghai Jiao Tong Univ. got the qualification on Yokohama, there is no more teams need to get the qualification, and according to the new rules, Tsinghua can’t join in the contest on their own site, I agree that if a team can get a Gold on this weekend then they’ll get the qualification, there is a chance for us, fighting for it~

Oct.21th, Preliminary of Shanghai

Posted on by snoopy

Shanghai Univ. did a lot of work on the OnlineJudge System, but there is still many bugs, because so many team tried to submit and refresh the page, but Shanghai Univ. did a lot of remedies to fix it, by delayed a hour to finish, all the contestants praised the hard work of repair.

I updated my signing messages before the contest, said "Oct.21th, Wuhan, Sunny, Wish our Moonmist, Wish our WHUACM~", then updated it with "Oct.21th, Rainy, We got 7/35 Accept and got a ticket to Shanghai~". It’s the day we have a good job, I’ve got 5 AC of our team’s, with many fearless guesses, they all thought that I must crazy, but actually I’m right :P

We’ll have two teams to Shanghai on November, wish our Moonmist and Silence, we are the best!

Good Luck for This Weekend

Posted on by snoopy

I’ve received the invitation from Tsinghua University yesterday, and filled the table to check. We have two team to join the on site contest, our Moonmist and the DeathDecay, good luck, wish them win a prize on Nov.12th.

Preliminary contest of Shanghai will be taken on this weekend, but it looks like there is still many bugs on the OJ of Shanghai University, wish them to fix them up before the preliminary. We’ll win a ticket to Shanghai by a good standing, Nov.22th, we’ll see Moonmist and Silence on Shanghai.

NWERC 2005 Unequalled Consumption

Posted on by snoopy

以下内容引用自frkstyc’s Blog, 原文地址:
http://www.blog.edu.cn/user2/frkstyc/archives/2006/1180760.shtml

——————————————————-我是分隔线——————————————————

有人曾经在POJ webboard上声称生成函数是“没用的东西”。但这个题却是利用生成函数解决问题的一个很好的例子。

题目的大意是有不超过5种重量在10以内的糖果（不同的糖果可以有相同重量），给一个整数P<= 1015，要求一个最小的重量w，只得做一个重量为w的糖果盒的不同方法数至少是P。

看到P的规模就可以立即否决普通的动态规划解法。容易联想到的算法是二分法，但这个题乍看之下没有明显的单调性。尝试用生成函数解决。为描述方便，以下直接用一个实例来说明。

假设有3种糖果，重量分别为2, 3, 5。用生成函数中xn项的系数表示做重量为n的糖果盒的方法数，那么对应的生成函数就是

f(x) = 1 / ((1 – x2)(1 – x3)(1 – x5))。

这个形式是没有办法直接利用的，因为里面三个因子的展开式都有无穷项，要直接找系数的通项公式也不容易。但是利用一个很简单的技巧就可以解决这两个问题。（应当说明，这个技巧虽然看起来很简单，但的确是要费一番思考的。）注意到2, 3, 5的最小公倍数[2, 3, 5] = 30，因此将上面的式子改写一下，变成

g(x) = ((1 – x30) / (1 – x2)) ((1 – x30) / (1 – x3)) ((1 – x30) / (1 – x5))，
h(x) = 1 / (1 – x30)3，
f(x) = g(x) h(x)。

这样，g(x)是一个一般的多项式，h(x)虽然有无穷项但形式很规整，f(x)只是g(x)和h(x)的乘积。

g(x)只需直接展开即可，展开的结果是一个次数小于3 * 30 = 90次的多项式。对于h(x)，为方便起见，作一个换元，记

h’(y) = 1 / (1 – y)3。

通过计算或者查阅工具书可以知道h’(y)中yn项的系数为组合数C(3 – 1, n + 3 – 1)，其中的3就是h’(y)的解析式中1 – y的次数。因此h(x)中x30 n的次数也是C(3 – 1, n + 3 – 1)，而其他项的系数都是0。

综合上面的讨论，可以得到计算f(x)中xn项的系数的方法。记p(x)中xn项的系数为c(p, n)。对于n< 90，c(f, n)可以直接利用动态规划或者限制次数地直接展开f(x)得到。（注意：这个不是c(g,n)！）对于n >= 90，记n = 30 k + r，其中0 <= r < 30，那么根据f(x) = g(x) h(x)，有以下公式

c(f, n) = C(2, k + 2) c(g, r) + C(2, k + 1) c(g, r + 30) + C(2,  k) c(g, r + 60)。

和f(x)直接相关的计算已经基本解决。剩下求最小的问题，方法还是二分法。虽然从整体看，c(f,n)关于n不一定是单调的，但是假如把n写成n = 90 k + r，其中0 <= r < 90，就可以发现对固定的r，c(f, 90 k + r)关于k是单调的。因此只需枚举r，对k应用二分法，然后从所有候选的n = 90k + r中选取最小的即可。

Mid-Autumn day

Posted on by snoopy

The day for family to get-together and for a celebration in Chinese custom, I spent 2 hour to write a code for the practice contest of ACM/ICPC Asia Regional 2006, Beijing, Internet Preliminary Contest in the eve, but I feel happy because these things I did are what I’d like to do.

 Oct. 6th is also the birthday of my father, so I wanna say "Happy Birthday, My Lovely Daddy!" now, but it’s too late, so I’ll give a call tomorrow(or the next daytime?) and send my blessing to my dad, who is the most important person and the best teacher in my life.

Happy Mid-Autumn day! Wish everyone can have a nice moon at this night.