WTommy的无悔青春

There is a sample code from <Thinking in C++, Second Edition>

int d = 1; 
const int e = 2;
int* u = &d;    // OK -- d not const 
// !! int * v = &e ;   // Illegal -- e const

int* w = (int*) &e;     // Legal but bad practice

 //If I change the value of cosnt e, ...

*w = 5;

....

 But when I change the value of const e by pointer w, Kapsersky will regard it as a dangerous program. Actually, it makes an amazing result...

cout << "The address where w points to is: " << w << endl;
cout << "The address where const e saves is: " << &e << endl; // the same as above

 // But the value is different:

cout << "The value of *w is: " << *w << endl ;
cout << "The value of const e is: " << e << endl;

 /**** The results ******/

The address where w points to is: 0x22ff70
The address where const e saves is: 0x22ff70
The value of *w is: 5
The value of const e is: 2
/*******************/

I even don't know how the compiler implement the case: same address with different values.

While in my opinion, the C++ compiler avoids creating storage for a const when it is defined in this way "const int e = 2;" , but instead holds the definition in its symbol table. When I define a int* pointer that points to it, the C++ compiler has to allocate storage to save the const int e whose memory address is 0x22ff70. The value of e for printing out maybe get from its symbol table rather than the real memory, thus it makes the amazing result: same address with different values.

在刚刚结束的2008北京奥运会中，中国健儿们以出色的发挥获得了51金 21银 28铜，共100枚奖牌的佳绩。不知道大家有没有关注过这个数字，如果中国再多夺得一枚银牌，那么这个数字将是如神一样巧合：

51 22 28正好是我国今年汶川地震的时间： 5月12日 2点28分 （14点 下午）

这个世界就是这么巧合：）

The athletes performed a cool Athletics Match at the Bird's Nest -- National Stadium. It was really a wonderful experience for me, and congratulations to Bolt!! 

During the cometition, all the attention was focused on the competitor Usain Bolt who comes from Jamaica. Usain Bolt produced another barely believable performance of dominant sprinting to break Michael Johnson's untouchable world record yesterday and add 200 metres gold to the 100 he won in record time four days ago. At the time he broke the world record, the audience were singing "happy birthday" song to him. All the spectators were celebrating that he became the new world record holder. I was so excited to see that scenario onsite.

Bolt is in line 5:



New World Record:



New World Record Holder: Bolt!!

我很荣幸代表天津大学冲进了今年的ACM/ICPC World Finals，下面是我对这次Final之行的个人总结。

2008年4月5日我们3名队员，2位老师奔赴加拿大的Banff参加2008 ACM/ICPC World Finals， 这次加拿大之行也是我最后一次ACM“演出”，经过了11个小时左右的飞行，我们终于抵达了加拿大的国土 ---- 温哥华(Vancouver)。当时我们没有出机场，而是在机场内部呆了5个小时转机前往了卡尔加里(Calgary)，到达Calgary时已经是当地时间晚上8-9点钟了，我们到事先预定的酒店住下。第二天上午我们由潘老师的同学（在当地工作的天津大学毕业校友）带我们在Calgary游玩了一下，下午2点多钟我们坐上去前往总决赛场地的巴士，这次总决赛在班夫(Banff)举行，它是加拿大的国家公园，一个让人留恋一生的景点，很美很美～

在BANFF的Springs Hotel我们度过了愉快3天，这几天我们去了BANFF小镇闲逛，也参加了一些由举办方举办的活动，例如Cybercafe、前往IceField观看冰原。活动安排的非常紧凑，纪念品也蛮多的，总之Final给了我们不同于任何一场Regional的感受！值得一提的是大家在前两晚的Cybercafe中玩的比较尽兴，Mr. Yu他们一起打牌，我偶然的碰到一个来自waterloo大学的Starcraft Fans，并与他切磋了几把Starcraft。一切都过得很快，在练习赛中我们把能想到的问题都测验了，IBM提供的技术支持真是赞，基本能想到的都做到了。

在正式比赛过程中，我们三个人稍显紧张，毕竟这次天津大学历史第一次和这么多国外一流强队较量。比赛开始时，三个人不慌不忙的开题，还是和平是一样的顺序读题，FINAL的题目有点长，我们事先有准备，我耐下心来读了前2题，发现都能做。而到了40分钟左右才开始有队伍AC，开始时比较分散，后来发现集中在F题上，由于RoBa对于K题已经有了成熟的思路，所以他先上机了，我主要负责想F题，在思考过程中很快我确定了一些简单的定理，与cnHawk商量过后发现有个更强的性质，我立刻想到了DP的解法并且坚定算法的正确性，我打断了RoBa上机开始敲F题，很快就敲完了（不是很长），发现自己出的一个小case我的程序多了1，后来经检查是因为少考虑了循环重复的情况，很快我们1y了这个题目，当时我们的速度不算太慢，没想到后来我们进入了僵持战，RoBa的K题和cnHawk的A题都有点问题，不过我们三个最了最大的努力，RoBa在给我复述他K题思路时发现了他自己程序的一个错误，经更改确实AC了。我有上机敲了J题，一个不是很难的计算几何问题，经过一段时间为完成了代码，但是Sample一直有一个不对，后来经过几次更改终于对上了Sample，急忙提交返回的是WA。当时已经剩下10分钟时间了，面临我们的是A和J，而B题RoBa有思路但是已经来不及敲了，最后6分钟我冷静思考了我J题代码，发现了一处逻辑错误，把原来的大于号改成小于号，结果又不过Sample了，后来再冷静下来思考发现应该是改成小于等于，结果对上Sample马上提交，那时候大约296分钟，我们稍等了一会儿，没有返回我们J题的结果，但是Staff却把一个J题的气球给我们挂了起来，我们3个询问了下，Staff说是我们的，但还是有些怀疑～

赛后的颁奖，IBM做了一个简单、实用、好看的 Demo演示给我们看，我们看到了最后的J题确实过了，也是这个题让我们没有Mention。整个颁奖晚会很让人激动，看着最后12个学校的名次，不由得让人从心里流露出敬佩。我们5个人还参加了最后的Celebration，两个搞笑演员和一个催眠大师的精彩表演给我留下了深刻的印象。第二天我们返程了，这里省略了很多不爽的事情，例如被大雪困在Calgary机场...

我对整个FINAL的记忆要远远大于上面的文字，那些是永远刻画在我脑里却不能用语言形容给其他人的记忆，2008 FINAL延续了我的ACM生命，也成为了我最后的ACM“谢幕表演”，不管成绩如何，我都要宣布我必须离开了，我大2下学期开始学习编程，进入TJU ACM队，与队友RoBa, goodhorsezxj, cnhawk组队比赛，历经3年从本科到研究生，终于实现了天大在ACM上的历史突破，我很荣幸作为一名TJU ACM一员，感谢Mr. Yu这些年来对我的指导和教育，感谢我所有的队友、队员们这些年来和我一起拼搏，ACM的感情只有ACMers能懂，如今看到了新一批队员，我想我也该退出了，在这里也希望我的队友RoBa在明年中能带领TJU冲进2009 World Finals，希望我们天大的ACM能在Mr. Yu的带领和队员的努力下蒸蒸日上。我永远都会为天大的ACM而感到骄傲和自豪，因为在这里记录了我无悔的青春！

谢谢大家，祝TJU ACM好运～

刚简单看了前一个学期的BLOG，记录了我生活的点点滴滴，最近忙着考GRE的作文，也没有时间再来打理这里～

上了研究生，有时总觉得失去了很多激情，让我多了一些抱怨，实验室的不爽，课题、科研的缓慢进度，还有来自各个方面的压力，真的不知道上了研究生究竟是学到了东西还是把自己磨圆了。。有时看到他人拼搏的劲头意识到了自己的畏缩，前一阵的抱怨我似乎想明白了，确实应该做点实事了，首先要做好的是18号大连的AW考试，其次是4月5日的Wolrd Final，接下来就是研究课题，希望一切顺利～

2008年是鼠年，虽然没有过春节呢，但是马上就到我的本命年啦：） 人家都说本命年会很不走运，结果第一天果然如此劳累的度过。替天津市小学组出任技术支持，评测他们的程序，真的是累翻了。从早上到现在刚回来休息，晚饭都是拖到晚上9点多吃的。

今天给小学生评测，发现了90后小朋友的现实，太TMD现实了，几个经典的话语：

1. 老师，我都六年级了，您就给我点儿分吧。。。。

2. 学生： 老师，我都写了这么多了，您就给点分吧。
    我： 不行啊，得按程序办事啊，不是我说给就给的！
    学生： 给不给分还不是您说的算啊。。。

3. 怎么的，我交钱了，您就得给我复测出分来。。。。

4. 老师，这不是我的程序，肯定有人给我改程序了。。。。。

5. 学生： 您能给我点儿分吗？
    我： 不行，因为你的程序不对
    学生： 但是我有钱啊。。。。

什么也不多说了，我小的时候都会认为作弊的人可耻，现在的小朋友动不动就上升的金钱上，这帮孩子的家长们也该反省反省了，可不能给自己的孩子都培养成拜金主义者啊>_<~~~~

不过还是赞扬那些能够靠着自己实力拿到高分甚至满分的同学，我的2008年第一天是这么过了，接下来大后天的人工智能考试可迎头劈来了，希望这两天好好复习一下，能过就行，我上大学考试从来就是突击，真的已经厌烦了，什么时候也能让我好好复习一段时间并且充满自信的走入考场啊：）

Bless 最近考AI的人和IBM认证的朋友们～～～  大家期末RP++

昨天从朋友那里听到了这条消息，很震惊，百度的CFO王湛生先生在新年假期期间发生意外不幸离开了人世。

王湛生先生的介绍就不多说了，网上都可以查到，他对百度美国上市和发展的贡献是不可磨灭的。之所以特意写一篇日志去悼念他是因为我和他有过一面之缘，在百度2007年AStart决赛的赛场上，第一天晚宴的时候他给我们全体选手讲过话，给我一个很和蔼，很稳重的印象。就在他人生的顶峰时期离开了这个世界，真的让人很痛心。经过查阅网上资料，才知道原来他和我还是老乡，都是沈阳人，在这里更要祝他一路走好，在天堂安息。

前天得到这个消息，还是很激动，感谢教练，感谢队友，天津大学ACM队的梦想终于实现了。
TJU Wizard会继续努力，在Final比出水平，赛出风格:)  愿天大的ACM再创佳绩！
仅此留念～

由于一直忙着写paper，做实验，也没有时间练习了～
赶上一次Topcoder SRM 384，就凑巧做了做，果然失败了，赛后做了做总结，记录一下！

250分题目：
很简单的一个题目，基本所有人都做对了，除非把题目读错的（我开始是没注意doc是要唯一的）。这题就不多说了！

500分题目：
一个很不错的状态压缩DP，之所以有点难度，因为他状态转移方程的特殊性。
简单回顾一下题目：
设有n个小朋友围成一个圈玩球，顺时针编号0到n-1。他们按顺时针的顺序轮流拿球去打其他人，每次轮到某人打击时，他都会选择另一个人去打，对于第i个人打中的概率是给出的，记为pro[i]%。一个人打完以后，不管打中没打中都要把球传给顺时针的下个人，被打中的人要离开这个游戏。这个游戏直到只剩下一个人终止，请问这个游戏期望要打多少轮才能结束？
题目中有个重要的提示是：所有的小朋友并不在乎自己在这个游戏中能存活多长时间，而是很想快速的结束这个游戏，可见他们选择打谁是有目的的。

题目的数据范围很小，n最大只有6，所以很容易想到用状态压缩DP。
即用dp[1<<n][i]表示状态，dp[mask][i]表示还剩下mask状态人时，该第i给人打，期望还会继续多少轮终止游戏。

很容易的列出状态转移方程：

dp[mask][i] = 1 + (min{ dp[mask^(1<<hit)][(i+1)%n] }*pro[i] + dp[mask][(i+1)%n]*(100-pro[i])) / 100.0   --> 其中hit是枚举被打的人

很多人（比赛时的我），都会想整个DP过程枚举的顺序可能会有问题，dp[mask][i]和dp[mask][(i+1)%n]是循环制约的，也许要解方程。

其实因为我们用mask作为阶段，那么dp[mask^(1<<hit)][?]都是已经求过的了，那么就可以很容易的把转移方程转化成：
在某一个特定的mask下：

dp[mask][i] = c * dp[mask][(i+1)%n] + f             (*)

注： |c| <= 1 并且 f是常数，是因为mask^(1<<hit)一定比mask小，所以是计算过的。

那么很容易证明这个方程(*)是收敛的，那么我们可以采用雅可比或者高斯-塞德尔迭代法求解，整个题目就解决了。

天大的ACM队伍保持在国外赛区比赛，已经比到第四个年头了，这与于老师的争取和学校学院领导的支持分不开，在这几次比赛中我们有过进步，有过激动，也有过很多次遗憾，在总结这次比赛之前，我想说说国外赛区的比赛到底对于我们ACM队有什么意义？

首先不得不承认的是参加国外赛区花费确实很大，从学校到学院都做了很大努力，我们在全国各个高校里面应该算是幸运儿。但是我们可以看得出来，出国比赛是有很大作用的，可以让我们队员体会另一种ACM氛围（完全不同于国内），可以看到更强的队伍，可以增大我们冲进总决赛的几率。

这几年在国内，也不知道是POJ月赛带来的风气，还是大陆水平的迅速增长，国内的题目有些偏，而且有时可以用“扣”来形容，好多都是论文性、结论性或者固定成熟解法的题目，对于中等或者中上等的队伍在5个小时以内都是不可做的，并且从解题的数量上可以看到，前三名有时都不能及格（没有做出超过60%的题目），在国内出线对于一般的队伍确实需要RP，从目前比完的各个赛区结果可以看出，每个赛区在4到10名的队伍和学校都是很随机的，和现场的发挥有很大关系。看完上交队员在南京的总结，我很同意他们的观点，这样的方向已经与WORLD FINAL相违背了。但是近些年来，亚洲国外赛区的题目有些还是很赞的，例如韩国、日本、越南等，至少他们题目大部分都是可做的。

鉴于这种形式，我觉得我们ACM队要针对国内和国外的不同特点来分别准备比赛。我同意于老师的意见，“我们并不是为了旅游，去更多的国家，我们出国是为了更好的成绩，更大的进步”，所以我建议ACM队以后盯住一些每年都举办比赛的国外赛区，每年都去，积累经验，总结失误的地方，最后能在国外拿到出线名额。

关于越南DANANG赛区的比赛过程，RoBa和cnHawk都已经写的很详细了。不能说我们在越南是失败的，但是确实是很遗憾，我们输给了好多强队。从整体上看我们并不和他们差的那么多，但只看那天的成绩，我们确实输了。

关于比赛的成绩不太理想，我想最重要的三点原因是：

1.       南京的好成绩使我们有些松懈。

2.       对于越南的题目难度预估计是错误的，根据越南去年的题目把今年的题目想的过于简单，其实都是不怎么好做的。

3.       场上被卡后协调不够好，作为队长当时确实没有做到合理安排任务，自己也被两个破题缠住了。

其实第二条就是我们要积累的，对于每个赛区都有他出题的风格，我们要善于总结，积累经验，才能取得更好的成绩。没有一个大学不需要积累的，目前全国的6大强校也都是积累起来的，想当年浙大需要6-7年积累冲进了FINAL，我们学校今年也是第6年，所以我们要保持住这个劲头。

通过这次比赛对中山大学队伍体系有了一定的了解，可以看得出我们和他们还有很大的差距，小队员还需要很多努力，我们要保持自己的节奏去进步，总有一天天大的ACM队会成为国内的前几强。如果我们这次能够幸运的去World Final，希望从这一年开始，靠着一届又一届辛勤的努力来托起天大ACM队，并走向更高的顶峰。