oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

08年中南赛--失意后的反思

Posted on 2008-04-28 11:06 oyjpart 阅读(2229) 评论(10)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

    08年中南赛如期举行。
    废话不多说,先贴成绩。
Rank School-Name Solved Time     A         B         C         D         E         F         G         H         I     Total att/solv
1 csyali(hs)-Yali-1 6 973 3/59 1/-- 5/189 3/278 1/6 2/109 0/-- 0/-- 3/112 18/6
2 tongjiu-三喜馄饨 4 761 2/114 0/-- 5/-- 4/226 1/13 8/-- 0/-- 0/-- 3/288 23/4
3 csyali(hs)-Yali-2 4 856 6/185 6/-- 6/101 0/-- 1/13 6/257 0/-- 0/-- 5/-- 30/4
4 whu-GCC 3 376 6/-- 0/-- 1/85 0/-- 1/18 7/153 0/-- 0/-- 7/-- 22/3
5 cssyz(hs)-一中队1 3 497 5/169 0/-- 1/-- 1/-- 1/9 0/-- 0/-- 0/-- 2/219 10/3
6 csyali(hs)-Yali-3 3 516 5/67 0/-- 2/-- 0/-- 1/22 4/287 0/-- 0/-- 5/-- 17/3
7 hust-Struggle2008 3 655 5/245 2/-- 2/-- 0/-- 1/11 4/259 0/-- 0/-- 0/-- 14/3
8 hku-T1 3 680 7/266 0/-- 18/-- 0/-- 1/9 3/245 0/-- 0/-- 0/-- 29/3
9 whu-Eternal_Arbiter 3 896 19/254 0/-- 27/-- 6/-- 1/13 5/189 0/-- 0/-- 0/-- 58/3
10 hust-Excalibur 2 106 2/-- 0/-- 0/-- 1/94 1/12 7/-- 0/-- 0/-- 0/-- 11/2
11 whu-BFS 2 126 0/-- 0/-- 3/61 0/-- 1/25 0/-- 0/-- 0/-- 0/-- 4/2
12 whu-R2 2 158 13/-- 0/-- 1/142 0/-- 1/16 0/-- 0/-- 0/-- 0/-- 15/2
13 hnu-Footman 2 209 1/-- 0/-- 0/-- 2/-- 1/6 0/-- 0/-- 0/-- 3/163 7/2
14 csyali(hs)-Yali-4 2 219 46/-- 0/-- 0/-- 0/-- 2/17 2/162 0/-- 0/-- 0/-- 50/2
15 cscj(hs)-CscjBBT3 2 226 3/178 0/-- 1/-- 0/-- 1/8 5/-- 0/-- 0/-- 8/-- 18/2
16 cscj(hs)-CscjBBT2 2 229 6/-- 0/-- 0/-- 1/-- 2/13 3/-- 0/-- 0/-- 1/196 13/2
17 alpc-alpcT1 2 269 0/-- 0/-- 44/-- 5/172 1/17 0/-- 0/-- 0/-- 0/-- 50/2
18 hnu-sword 2 305 0/-- 0/-- 14/-- 5/202 1/23 0/-- 0/-- 1/-- 0/-- 21/2
19 hfut-EarthShaker 2 343 0/-- 0/-- 0/-- 2/-- 1/9 4/274 0/-- 0/-- 0/-- 7/2
20 gzhu-MayChord 2 368 0/-- 8/-- 2/-- 2/-- 1/19 5/269 0/-- 0/-- 0/-- 18/2
21 cscj(hs)-CscjBBT1 2 397 6/273 3/-- 0/-- 7/-- 1/24 3/-- 0/-- 0/-- 6/-- 26/2
22 hku-T2 2 446 0/-- 0/-- 3/-- 2/275 4/91 4/-- 0/-- 0/-- 0/-- 13/2
23 csu-III.D 2 517 11/298 0/-- 2/-- 0/-- 1/19 0/-- 0/-- 0/-- 0/-- 14/2
24 alpc-alpcT2 2 520 1/-- 0/-- 9/-- 11/298 1/22 3/-- 0/-- 0/-- 0/-- 25/2
25 alpc-alpcT5 1 7 0/-- 0/-- 2/-- 0/-- 1/7 4/-- 0/-- 2/-- 0/-- 9/1
26 hfut-RP_GAO 1 9 0/-- 0/-- 1/-- 0/-- 1/9 4/-- 0/-- 0/-- 0/-- 6/1
26 whu-novices 1 9 0/-- 0/-- 18/-- 0/-- 1/9 2/-- 0/-- 0/-- 0/-- 21/1
28 ecust-SURE 1 10 2/-- 0/-- 8/-- 0/-- 1/10 1/-- 0/-- 0/-- 0/-- 12/1
29 alpc-alpcT8 1 11 0/-- 0/-- 5/-- 0/-- 1/11 1/-- 0/-- 0/-- 0/-- 7/1
30 alpc-alpcT15 1 12 2/-- 0/-- 1/-- 0/-- 1/12 1/-- 0/-- 0/-- 0/-- 5/1
30 alpc-alpcT3 1 12 6/-- 0/-- 1/-- 0/-- 1/12 3/-- 0/-- 0/-- 0/-- 11/1
32 alpc-alpcT12 1 13 0/-- 0/-- 0/-- 2/-- 1/13 0/-- 0/-- 0/-- 0/-- 3/1
32 ccnu-tower_rush 1 13 0/-- 0/-- 0/-- 1/-- 1/13 2/-- 0/-- 0/-- 0/-- 4/1
32 hnu-FM2008 1 13 1/-- 2/-- 0/-- 0/-- 1/13 1/-- 0/-- 0/-- 0/-- 5/1
35 alpc-alpcT7 1 14 3/-- 0/-- 41/-- 0/-- 1/14 0/-- 0/-- 0/-- 0/-- 45/1
36 alpc-alpcT14 1 15 0/-- 0/-- 1/-- 0/-- 1/15 0/-- 0/-- 0/-- 0/-- 2/1
36 alpc-alpcT4 1 15 0/-- 0/-- 1/-- 0/-- 1/15 3/-- 0/-- 0/-- 0/-- 5/1
36 cug(wuhan)-Three_Up 1 15 9/-- 0/-- 9/-- 0/-- 1/15 2/-- 0/-- 0/-- 0/-- 21/1
39 alpc-alpcT13 1 17 0/-- 2/-- 2/-- 0/-- 1/17 0/-- 0/-- 2/-- 0/-- 7/1
39 hnu-zealor 1 17 0/-- 0/-- 2/-- 0/-- 1/17 0/-- 0/-- 0/-- 7/-- 10/1
41 alpc-alpcT6 1 18 0/-- 8/-- 5/-- 0/-- 1/18 0/-- 0/-- 0/-- 0/-- 14/1
41 whu-Slash 1 18 4/-- 0/-- 0/-- 8/-- 1/18 0/-- 0/-- 0/-- 0/-- 13/1
43 cssyz(hs)-一中队2 1 20 7/-- 0/-- 4/-- 0/-- 1/20 6/-- 0/-- 0/-- 0/-- 18/1
43 hust-Apollo 1 20 0/-- 0/-- 1/-- 1/-- 1/20 14/-- 0/-- 0/-- 0/-- 17/1
45 alpc-alpcT9 1 21 0/-- 0/-- 1/-- 5/-- 1/21 0/-- 0/-- 0/-- 0/-- 7/1
46 xtu-Pursuer 1 22 0/-- 0/-- 4/-- 6/-- 1/22 0/-- 0/-- 0/-- 0/-- 11/1
47 ccnu-Athena 1 23 0/-- 0/-- 0/-- 0/-- 1/23 0/-- 0/-- 0/-- 0/-- 1/1
48 ccnu-Redligt 1 26 0/-- 0/-- 0/-- 0/-- 1/26 0/-- 0/-- 0/-- 0/-- 1/1
49 ccsu-希望2队 1 27 1/-- 0/-- 0/-- 0/-- 1/27 0/-- 0/-- 0/-- 0/-- 2/1
50 xtu-Opera 1 33 0/-- 0/-- 2/-- 0/-- 1/33 0/-- 0/-- 0/-- 2/-- 5/1
51 hnbc-雏鹰 1 35 0/-- 0/-- 0/-- 0/-- 1/35 0/-- 0/-- 0/-- 0/-- 1/1
52 alpc-alpcT11 1 39 0/-- 0/-- 3/-- 0/-- 1/39 0/-- 0/-- 0/-- 0/-- 4/1
52 ccnu-FollowDream 1 39 0/-- 0/-- 8/-- 0/-- 1/39 0/-- 0/-- 0/-- 0/-- 9/1
52 csu-RedFox 1 39 0/-- 0/-- 3/-- 0/-- 1/39 1/-- 0/-- 0/-- 0/-- 5/1
55 tongjiu-囧 1 42 3/-- 0/-- 0/-- 0/-- 2/22 2/-- 0/-- 0/-- 0/-- 7/1
56 hnbc-龙 1 57 0/-- 0/-- 0/-- 0/-- 2/37 0/-- 0/-- 0/-- 0/-- 2/1
57 csu-BlueWhale 1 59 0/-- 0/-- 0/-- 0/-- 1/59 1/-- 0/-- 0/-- 1/-- 3/1
58 ccsu-希望1队 1 64 0/-- 0/-- 6/-- 0/-- 1/64 0/-- 0/-- 0/-- 1/-- 8/1
59 ecnu-KOP 1 65 0/-- 0/-- 3/-- 0/-- 2/45 0/-- 0/-- 0/-- 0/-- 5/1
60 alpc-alpcT10 1 75 0/-- 0/-- 1/-- 0/-- 3/35 10/-- 0/-- 0/-- 0/-- 14/1
61 hnbc-楚风 1 76 0/-- 0/-- 3/-- 0/-- 2/56 0/-- 0/-- 0/-- 0/-- 5/1
62 ccnu-Sky 1 80 0/-- 0/-- 0/-- 0/-- 2/60 0/-- 0/-- 0/-- 0/-- 2/1
63 ccsu-希望3队 1 92 0/-- 0/-- 0/-- 0/-- 2/72 0/-- 0/-- 2/-- 0/-- 4/1


Submitted/1st Yes/Total Yes

185/59/11 32/--/0 282/61/5 75/94/7 76/6/63 133/109/10 0/--/0 7/--/0 54/112/5 844/101
School Abbr.
中国地质大学 cug(wuhan)
华中师范大学 ccnu
同济大学 tongjiu
香港大学 hku
合肥工业大学 hfut
华东理工大学 ecust
华中科技大学 hust-
华东师范大学 ecnu
广州大学 gzhu
武汉大学 whu
湖南大学 hnu
湖南商学院 hnbc
长沙学院 ccsu
湘潭大学 xtu
中南大学 csu
长沙市第一中学 cssyz(hs)
长沙市雅礼中学 csyali(hs)
长沙市长郡中学 cscj(hs)
PART I 比赛过程概览:
    基本上整场比赛处于一种郁闷中。分题是我ABC,李佳鑫DEF,王要得GHI。E题发现的比较晚,好像是我把ABC都读完了(都否决掉了简单题的嫌疑)之后看到蓝气球之后叫李佳鑫赶紧给我讲E题题意。按照计划,我准备把前面1-2道简单题留给新人王要得来敲,我来敲后面的题。所以我又给王要得说了题意,然后把关他的程序过掉E。过掉E之后我对D题有信心,主要考察的是字符串的离散化(stl::map)和双端优先队列(stl::set),想了想,这个题目给王要得估计不行。他对STL不熟,不可能现场教他STL吧。中间我和王要得讨论了C题,因为MS很多人扎堆做C题。我估计n^3的算法过不去,惯性地想了想凸包+二分。是王要得讨论了下,是根本错误的。王要得喜欢数学,我要他想想能不能找到n^2或者n^2 logn的算法。当然,场上最后大家都是预处理对点距离+n^3算法水过去的,这是后话。于是我就抢了机器开始敲D。敲D,我认为策略并没有错,但是我没敲好。敲第一行const int N = 10010;的时候,隐患就买下了。我没有细想任务数有多少,迷糊中以为题目中的最大同时下载任务数就是任务数。后面的代码也敲错好些地方,改来改去的。好不容易过了样例和李佳鑫给我的数据,交上去一个WA,心都凉了。打印代码,查错。既然过了那么多数据,肯定程序是没有大错的。又仔细读了题,果然发现一个漏掉的地方:Waiting & Downloading Task can both be paused.我以为只有Downloading。改了重交还是WA。发现自己没有改完,后面有一段也要改。再改再WA.中间还有一次莫名奇妙的TLE,迫使我当时优化了一遍代码。到那之后我就再也找不到错了。王要得觉得F题有规律,我也没管了,让他去敲。我则一遍一遍的看程序,给李佳鑫讲程序,都没有发现逻辑上的问题。我火了,等自己拿到机器,就开始测官方数据(就是在可能出错的地方写大量的debug语句如while(1),一个个来测试)因为题目中有很多东西是Assumed,不知道数据有没有错。测试的时候果然发现数据有问题,因为我的程序检测到一个已经pause的任务再次被pause掉!我仔细看了我的程序,不可能发生这种问题!顿时就崩溃了,终于我觉醒了,放下了D题,放下了机器,伤心地离开了键盘。王要得看到场上C题过得人过,示意要 n^3水一下。这个时候我没报任何希望,我认为n^3能过的话,场上应该全是C题气球了。下到场上,他们敲C,我开始审视A题。我心里明白,这场比赛肯定要丢人了。而我现在能做的,就是尽可能少丢点人!心里虽然些许不安,可是我还是很清醒的分析了A题。很快发现一个简单的2次DFS的树形DP就可以搞定。等他们C题TLE之后我上去敲了A。很高兴的过了测试数据之后,Runtime Error。立即意识到爆栈了。说实话,树形DP爆栈,人生第一次。我当时想都没想BFS的做法,就只记得去人工模拟栈了。现在回想起来,还不如改成 BFS。人工模拟栈我还真不会写,而且我觉得我那个DFS还是以边做DP的,更复杂了,压栈还得压点。我就只记得压栈弹栈了,磨蹭了半天,就没写出个像样的模拟栈出来!说我弱也好,说我烦也好,比赛还剩下最后的30分钟,我丢下了A题。在王要得的建议下,用随机去水C题,水啊水,就是水不过(已经沦落到这个地步了,有什么办法呢)到了最后5分钟的时候,我心不死,再次翻出D题。砸头一看就是一个const int N = 10010,心里一惊,怎么是10010呢!靠!不是100010吗!马上改了重新交,怕交不上,反复交了几次。同时又把C题的程序交了几次。就在那静静的等待死亡。过了又如何,不过又如何?已经很丢人了,也罢也罢。但是看到D题YES之后还是兴奋了一下的。就这样,结束吧结束吧,化悲痛为食量吧。。。

PART II 失败的原因
    整体上来说,这次alpc是全军覆没。部分原因是我们的主力们都分散到各个队伍中了,可是这不是理由。即便是个人赛,我们的主力们也决不能赛成这个样子啊!我是典型重犯,所以分析我的失败原因亦是很有借鉴意义的。
    经过我自己的反思,我把失败的原由按照大小排序如下:
    1.D题我的敲题错误和反复修改延误了队伍。影响了我思考其他题目,严重限制了我对其他题目的发挥,场上GHI我都不知道题目。
    2.题目没有读完。实际上他们俩读了题,但是我深陷D题,我没有去读GHI。如果D题早些过掉,有时间看看F,I题,形势会好过很多。
    3.没有问过他们敲得C的细节,F的做法,因为贯彻2人负责制。但是实际上我应该对较难题目的算法全权负责,把关时间复杂度。
    4.根本原因:自己代码能力下降了。敲题不在状态。上两个星期发生了太多无奈的事情,有少许影响。

PART III 失败后的反思
    1。也许自己思维还过得去,但是不得不正视的是,我们和真正的高手比起来,代码能力已经差了一大截。对于Regional,我对于自己的定位可能仍然是敲题手,至少得先成为单挑很强的敲题手,才能很好的把握队伍的动向(from dwyak,戴文渊,world final冠军)。下个阶段的训练可能主要针对的是自己的敲题能力,因为我觉得自己在比赛的时候敲代码脑袋不清楚。tomek(world final冠军,poland)是这样说的:being forced to work on paper with no terminal access, I found I would solve the problems quicker。显然,我会在以后加强纸上的训练,让自己的手在键盘上的时候成为反射而不是边想边敲。或者至少也要敲得时候想清楚。
    2。正视ACM。如果真的喜欢ACM,要在ACM里面做出一番成绩,不努力是不实际的。生活中总是有很多不顺意的事情,你有他也有,他能化解,你也得学会化解。有时候会很累,可是为了自己喜欢的东西,又有什么关系。前段时间做web开发方面的事情很是分心,恋爱的事情也很分心,考试的事情还是很分心。前段时间答应教授研究NP基础理论方面的东西,现在连论文都没看完,sigh。人总是进步就好。ACM啊ACM,只有你才能让我感觉得到自己的灵魂还在,而不是一个机器。

PART IV 祝愿
    祝愿alpcs今年能取得好的成绩!alpcs开心最重要!
    特别祝愿alpc62早日完成心底的夙愿!




Feedback

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-04-28 14:31 by alpc55
也祝你今年取得好成绩吧,不过你的总结也不见得怎么不是傻呼呼的哈~~~

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-01 15:17 by 金今哲
祝你们成功.

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-01 22:57 by haha
和55的总结都是傻乎乎的

我的不傻乎,因为我没写

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-02 10:23 by ecnu_zp
+U
alpc 很强大~~

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-02 19:51 by oyjpart
@ haha
这还不够傻啊。。。哈哈

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-04 16:09 by oyjpart
@ecnu_zp
你也加油!

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-06 01:36 by Calvin Kwok
祝你成功!

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-05-06 13:06 by oyjpart
@Calvin Kwok
也祝你成功!

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-06-03 16:41 by DenoFiend
谢谢,你的这句话:ACM啊ACM,只有你才能让我感觉得到自己的灵魂还在,而不是一个机器。我喜欢。
开开心心做acm

# re: 08年中南赛--失意后的反思  回复  更多评论   

2008-06-03 17:42 by oyjpart
@DenoFiend
呵呵 搞ACM的喜欢自己感慨下子

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理