posts - 274,  comments - 1258,  trackbacks - 0

Acumon 的长春比赛报告

行程

  • 111 下午~113早上 在火车上度过比较无聊的36 小时
  • 114  试机
  • 11 5  比赛
  • 11 6  在长春游玩,但长春实在没什么好玩
  • 11 6 ~118上午 在火车上度过比较无聊的36 小时

 

比赛

  比赛一开始,我开屏幕调配置。发现试机时的配置全部被保留。大喜,遂去看题。我看 ABC ,基宏看 DEF ,德健看 GHI 。按照之前的作战布署,此时我们首要的目标是找出最水的题并予以消灭。我很快地看完 A ,发现是一条计算几何题,应该不是水题,便先放在一旁,转而看 B B 题大意是给你一个数 n ,要你找出 k 个数 a1~ak ,使得所有 1~n 之间的自然数都可以用 ai, aj-ai, aj+ak-ai 三种方式表示出来,并使得 k 最小。乍看之后像是一条数论构造题,便交给基宏想。此时德健正在看 F H ,前者是一条图论题,后者是一条数据结构题,都不是传说中的最水的题,而且属于德健擅长的类型,我便留给他继续想,继续扫其它题,也帮助基宏一齐想 B ,此时基宏先后找到一些构造的方案,但没能证明它们,而 judge 的返回也说明它们并不正确。

  比赛一小时后,开始有零星的队过 A ,大多数队还是 0 题。于是拉德健一起讨论 A A 题题意是给出 20 个平面上的点,要求你选取其中一些点,连成一个多边形,使得式子周长平方除以面积取得最小值。马上证得最优的多边形是简单多边形,并且是一个凸包,考虑到点数较少,便想枚举所有凸包,但直接枚举复杂度太高,又无法找到一种遍历凸包的算法。稍后,我们发现一种遍历所有简单多边形的算法,复杂度为 n 2n 10s 的限时绝对能过,便交给德健敲,在经历了几次小 bug 带来的 TLE 后,我们终于迎来了第一个 yes 。此时暂时排名十几,很多队过了的 E 题我们还未过,形势看来不错。二队和六队还未过题。为他们祈祷了一下,继续做题。

  E 题又是一道数论题:给出一个复数,判断是否高斯素数。我便和基宏一起想 E ,并写了一个暴力枚举的程序来把小范围的高斯素数打印出来找规律,然后我去想 D D 题目较长,但其实是一个很容易想到的一个 DP 。看完题后不久便想到了算法。但觉得有点繁琐,而且复杂度好像有些高而且不容易算出准确的复杂度,便等到德健过 A 后再交给他敲。另外 E 题我们在《初等数论》上也找到一些结论,可惜我们看不懂证明。后来我写了一个 n2 的水的方法,却水了几次都没有水过。

  这时评委看到 A 题过的人太少,便做了件最令人匪夷所思的事:对 A 题连续多次 rejudge ,最终把时限改为用最强大的布鲁特福斯算法都可以过的题,一下子哗啦啦地过倒一大片,我们一个小时的努力换来的的优势顿时化为乌有。

  不幸中的万幸是,当我用了各种预处理和水的方法都过不了 E 而打算放弃之时,基宏很神奇地修改了其中的一个参数,改大了枚举量,就把 E 过掉了。

  这时德健已经敲了一部分 D 题,但似乎遇到一些困难,却又无法说出来。之后他便去想 F ,然后决定先水一下 F 。这是一个有关最短路的问题,很不幸地我们选择了使用 Floyd 来求最短路,结果无论怎样改都没法水掉道这题(后来六队用对所有点求 Dijikstra 的方式过掉了这题,实在太神奇,膜拜orz~)。在比赛结束前 40 分钟左右,我们终于放弃 F 来继续做 D ,由于此前我已算出准确的复杂度是 O(500*270*12*case ) 左右,所以那时我觉得把 D 过掉的希望还是很大的。这时德健终于说出了他遇到的困难,原来他把我的算法和他之前的一些想法搞混了,结果我们花了很大力气才取得了一致。最后的时间是在我和德健一齐敲 D 题、调 D 题中度过的,可惜最后都没调过。

 

教训

1、  不要以为 g++ 一定会对简单的 inline 函数进行展开。这次比赛的 g++ 对我们测试的所有的简单 inline 函数都不展开。

2、  不要以为题目的标准解法不用打表。本次比赛花了我们很多时间的 B 题的标准解法就是花几个小时去暴力打表。

3、  作为队长,我应该更清楚队员的状态,并且更灵活地调整策略。今次比赛德健明显状态不佳,我应该在更早的时候意识到这个问题。

4、  数论和组合数学是我们队的弱项,这次我们的数论题过得很险,相信随后的成都之战会更加艰苦。必须在接下来的休整时间里尽力恶补一下。

5、  我们队的交流还是做得不够。其实那条花了德健很多时间的 H 题,正是我擅长的线段树题目,而事后也证实那道题真的很容易想出来,但我却因为各种原因没有认真去想。

 

花絮

1、  在去长春的火车上,大家都在努力看书和论文,还讨论一些以前的题目,其间我发现某题可以用 O(n(nlogn)1/2 ) 的复杂度过。这是我想过的题中“最复杂”的一个复杂度。

2、  去长春的路上大家都没有打太多牌,怕伤 RP 。很不幸地我连胜了几局,赶紧收手去睡觉。回广州的路上终于可以放手打牌了,大败而归。

3、  由于是第一次在深秋时节跑到北方去(假如前几天飞去北京面微软不算的话,但显然长春要比北京冷多了)所以大家都准备了很多御寒衣物。去到后发现其实也没有想像中那么冷,我的围巾和最厚的绵袄都没有用过。

4、  王磊在火车上开玩笑地说他在实验室研究“布鲁特福斯”( brute force )算法。我们的德健更号称“系数之王”。很不幸地,这次我们遇上了更加暴力的评委,方知“强中还有强中手”。

5、  在去长春火车上的第一晚,我接连推掉了百度、网易和腾讯的面试,当时感觉心痛无比。不过很幸运地,最终我还是赶在百度团队飞回北京前获得了面试的机会,并很顺利地拿到了 offer ^_^

6、  比完赛后二队和郭老师随即飞回了广州,剩下六个大男人在长春逛沃尔玛,囧。

7、比赛服装的size除了印的码数不同外几乎没有什么差别,导致我们的基宏同学选了件XXL,而肥东师兄却选了件M。

发现

1、  东北有很多西南菜,尤其是云南过桥米线。

2、  在北方千万不要乱点“清淡”的菜,它可能辣得令你无法下咽。一个较好的做法是叫师傅“绝对不放辣椒”,但这时师傅很可能会跟你说那道菜他不会做了。

3、  坐火车千万不要坐车厢两边,除非你不介意车上那帮烟鬼们日夜不停地轮番轰炸。

4、  一个城市的空气和饮用水质量真的很重要的,为了这两个原因我打死都不会到长春去生活。

5、  长春的轻轨很慢,而且车站很密,一两分钟就停一次站,使我们怀疑步行是否会比坐轻轨更快。

6、  原来在手机 QQ 上是看不到对我可见的密友的,由于大家都习惯隐身,结果我经常觉得 Q 上一片冷清。


鸣谢

  • 谢谢郭 老师给了我代表中山大学到长春比赛的难得的机会。
  • 谢谢队友德健和基宏给了我这个菜鸟队长许多支持和帮助。和你们一起并肩奋斗是我毕生难忘的一段经历。
  • 谢谢嘉慧借给我手机,使我没有错过任何一个重要的面试电话,并且在旅途中可以一直用 QQ跟大家 聊天。我那只肥猪仔现在经常“智能悭电”了。
  • 谢谢在这次旅程中帮助过我、关心过我的所有人,谢谢你们。
posted on 2007-11-12 02:10 踏雪赤兔 阅读(1114) 评论(9)  编辑 收藏 引用 所属分类: 玩转编程岁月如歌

FeedBack:
# re: Acumon的长春比赛报告
2007-11-12 21:30 | 小bug
B公司offer....好米啊....

苟富贵,毋相忘啊.....~~~>_<~~~  回复  更多评论
  
# re: Acumon的长春比赛报告
2007-11-12 21:35 | 小bug
PS. 嘉慧借左部机比你甘她用乜...?  回复  更多评论
  
# re: Acumon的长春比赛报告
2007-11-12 22:08 | 踏雪赤兔
新手机啰~  回复  更多评论
  
# re: Acumon的长春比赛报告
2007-11-12 22:09 | 踏雪赤兔
忘边个都唔会忘肥虫啦  回复  更多评论
  
# re: Acumon的长春比赛报告
2007-11-13 01:36 | Week
不论猪富贵,狗富贵,勿相忘就是了  回复  更多评论
  
# re: Acumon的长春比赛报告
2007-11-13 01:39 | 踏雪赤兔
哈哈~  回复  更多评论
  
# re: Acumon的长春比赛报告
2007-11-14 22:23 | 阿姐
看上去很不错哦!!!!~~~~~  回复  更多评论
  
# re: Acumon的长春比赛报告[未登录]
2007-11-15 09:07 | 星星
长春的空气应该同广州差不多吧  回复  更多评论
  
# re: Acumon的长春比赛报告
2008-11-29 20:55 | iStone
好文,我就是长春的,这边的空气还可以,就是水有问题  回复  更多评论
  
只有注册用户登录后才能发表评论。

百度空间| 见闻日记| 编程感悟
我的twitter


LOGO

自我介绍:百度厂基础平台车间的一名挨踢民工。擅长C++、算法、语言设计、分布式计算,也用过Java,Python, PHP,JS/AS等语言开发。请关注我的twitter (免翻墙版) 发QQ消息


添加到收藏夹 Locations of visitors to this page

常用链接

随笔分类(300)

随笔档案(274)

文章分类(38)

相册

收藏夹(54)

与博主互动

博客手拉手

搜索

  •  

积分与排名

  • 积分 - 380407
  • 排名 - 10

最新评论

阅读排行榜

评论排行榜