GridGraph 师兄的文章. 主要 idea 是把邻接矩阵切成块 (p*p) 放到磁盘上顺序读来提升 io 性能. 单机. GraphChi disk-based, parallel sliding windows, single consumer-level computer. metis 不 work (???) 解决出入边都要考虑和写的问题. 按出边分块 shard. 入边按序存放, 在每个 shard 中为连续一段. 可加载进来. 解决了一些比较麻烦的问题比如数三角形.

因为在 LA 爬了俩月坡, 感觉自己功率有所长进, 所以这场比赛以为自己能站个台. 然而事实是刷出了 pw. 这个经历再次验证了 flag 学三大定理 lyzy, 2016. 起源和准备阶段 赛前两周才听说重庆有比赛. 本来下半年没有比赛计划的, 自己的公路车也还没组装好, 但考虑到可以中秋回趟成都过节, 就还是毅然决然地被报名了. 在成都老车迷租到了一台 Trek Emonda 的入门铝公路车, 是前段时间某个比赛的赞助车, 虽然套件轮组辣鸡, 但总之能骑, 而且比在 LA 骑的那台上古 Allez 强. 甚至感觉自己能刷 pb. 回北京第一周早晨倒时差起床跑步, 发现跑六分配速都喘. 三天跑了11km. 游泳训练是和洞pro约在陈明讨论学术顺便划了300米. 赛前 发现20-24被重邮移通铁人队占了绝大多数. 有点方. 听尘尘和红红说他们很菜. 我竟然信了. 去车店取了车准备骑回家, 一路在三环辅路上飙到40kph非常爽. 然而骑了 6km 胎就被扎了. 回家看了半天才发现胎里扎了个钉子. ovo 开自家车带着爹妈和自行车从成都开了四个半小时到长寿湖. 一路定速巡航还挺爽. 审体检报告的时候果然又被短pr间期的问题卡了. 不过这次赛会医疗组很人性化地带了心电图设备, 直接现场复查了. 赞. 看赛道的时候让我爹开车跟着, 体验了一把后援车跟拍. 发现有一段颠颠颠颠的下坡. 以及发现这车变速不太准. 当场调变速. 晚上去吃奇怪的水库鱼, 然后鱼一直没上, 饭都吃完了, 就把鱼退了. 游泳 第一次遇到水下出发. 第一圈还将就就是有点慢. 第二圈下水就游偏了, 被裁判船吹哨赶了回去. 上岸的时候发现岸边有石头甚至差点划破了脚. 到 T1 发现只有我和另一台自行车了....

看上去很复杂的一个题. 然而数据范围 ( n \leq 50 ) 基础知识0: python 里面 list 可以做 dict 的 key. 基础知识1: python 里面 list 可以直接比较大小, 比较方式就是元素的字典序. 做法是先按照 username 对记录进行归类 (dict of list). 然后把每个 username 对应的所有记录按 timestamp 进行排序. (sorted(…, key=lambda …)) 然后枚举每个用户的所有访问页面三元组并扔进 list 里面. 因为要求一个用户只算一次, 所以要去除 list 里面重复的元素. 所以把 list 转换成 set (集合) 就好了. 也可以直接用 set. 然后把 set 里面的元素都用一个 dict 做一下记数. 最后从记数的 dict 里面挑出次数最多且字典序最小的就可以了. 代码链接

首先弄清楚中序遍历是什么意思. 中序遍历是一个序列 (list). 不存在的节点的中序遍历是空序 ([]). 以 u 为根的二叉树的中序遍历 = u 的左儿子的中序遍历 + u + u 的右儿子的中序遍历 其中加号就是连接两个序列的意思. 题目里说只考虑叶子节点的中序遍历, 就是把所有非叶子从中序里扔掉就好了. 然后考虑从随便一个序列构造一个满足条件的二叉树. 其实这个二叉树上的任意一个点会对应原序列中的连续一段, 而这个点的值就是这一段的所有数的最大值. 我们考虑自底向上的建树. 也就是说最开始是 n 个单独的点, 然后每次建一个新点, 它的两个儿子分别是原来的两个点. 然后用这个新点代替原来的两个点. 重复 “挑选, 替代” 的过程直到只剩一个点, 就建成了一棵完整的树. 每次挑选的两个点一定代表原数组上相邻的两个区间. 合并后建成这棵树的 最小 代价为 左儿子的最小代价 + 右儿子的最小代价 + 左边最大值 * 右边最大值. 而我们的最小化目标是根的 最小 代价. 自然想到用 f[l][i] 代表以 i 为第一个数的长度为 l 的区间所代表的点为根的树 的 最小 代价. 首先 f[1][i] == a[i], 而我们的目标是 f[n][0]. 进一步想, 最小化 f[l][i] 就是在所有该点的左右儿子分配方式 (就是各有多长, 总之加起来是 l) 中挑一个最小的....

很基础的 BFS 题目. BFS 和 DFS 是相对应的两种算法. 其区别在于对于新发现的可能性, BFS 将其放入队列末尾, 稍后进行探索, 而 DFS 立即探索这种新情况, 等探索完之后再回到之前的状态继续枚举. 对于这道题目来说, 具体来讲, 状况可以用 (位置, 距离, 颜色) 这么一个 tuple 来表示. 最开始的时候, 有 (0, 0, blue) 和 (0, 0, red) 这两种情况. 假设 0到1 有一条蓝边, 0到2 有一条红边, 那么新的情况是 (1, 1, red) 和 (2, 1, blue). 如果我们使用 DFS, 那么当新发现 (1, 1, red) 这个状态的时候, 我会立即以 (1, 1, red) 为起点, 继续探索 1 号点的邻居, 比如找到了 (3, 2, blue) … 直到找完所有通过 (1, 1, red) 可以达到的状态之后, 再继续以 (2, 1, blue) 为基础进行枚举....

先预处理一下, 把 >8h 的变成 +1, <=8h 的变成 -1 现在问题就变成了: 找最长的连续一段使其和 >0 使用前缀和数组, 要求 i~j 的和, 公式是 sum[j] - sum[i - 1]. 枚举左端点 i. 对于某个确定的 i, 要找以 i 为左端点的最长一段符合要求的区间, 即找满足条件 sum[j] > sum[i - 1] 的最大的 j 注意到 sum 数组的取值为 [-n, n], 故使用值域数组 values. value[k] 表示 sum[j] == k 的最大的 j. 该数组可以在求 sum 数组时一并求出. 满足条件 sum[j] > sum[i - 1] 的最大 j 即求 values[sum[i - 1] + 1], values[sum[i - 1] + 2], values[sum[i - 1] + 3], …, values[正无穷] 中的最大值....

状压动态规划. dp[x] 表示 x 状态下的最少人数. 其中 x 是二进制数, 第 i 位表示第 i 项技能是否有人已经拥有. 例如 ( x = (10010)_2 ) 从右往左第 1, 4 位是 1, 表示技能 1, 4 已有人掌握, 而 0, 2, 3 无人掌握. 假设一个人的技巧是 p, 现在的状态是 x, 则加入后的状态是 x|p. 其中 | 即 python/cpp 中的 | 运算符, 意义是取二进制或. 运算过程为最初时只有 dp[0] = 0. 对于每个人的技能集合 p, 可以更新 dp 数组 dp[x | p] = min(dp[x | p], dp[x] + 1) 最后的答案是 dp[((111\dots 1)_2)] 即 dp[(1 « len(skills)) - 1]...

ISC'19. 一场大概是退役失败的超算比赛. 我负责的 part 是 AI, 还有万年大锅 HPL, 以及神秘应用. 还有就是订保险订酒店联系赞助商blabla. 本来想帮忙搞 HPCC 的但是没有精力搞不动 ovo AI AI 题是去年的 GB 论文 + 精调模型. 在解决了组委会提供的脚本里的一些性能上的 bug 之后顺利地训了起来. 而且按照原文里在上千个节点上并行训还能收敛来讲, 是可以在现有机器条件下随便数据并行的. (事实证明直接把整个训练集切成 10 个batch 也没有问题) 因为最终要求是精度, 所以请教了一些人, 得到的思路是 数据增强, ensemble. 数据增强不太写得动, 于是改脚本做了 ensemble 的 inference, 效果还不错. 比原文高了几个点. 但也没有特别闪亮的突破性进展. 唯一发现是 bn 用的是 training mode. (原因应该是 tf 的 bn 一直自带 bug, 如果用推理模式精度就是会炸掉) 于是推理的时候也应该 bs 越大越好. 于是就有了 dummy sample inference + unique 的一个脚本. 然后因为没有处理好 “//” 于是组委会还怀疑了半天为什么我的脚本有锅. 哭. 然后就是现场出了一个锅: unseen dataset 发下来一看居然是事前给出的 test set....

前段时间遇到 mac 微信出了一个锅. 部分微信群和联系人在电脑上收不到消息, 可以发消息, 但发出去一直显示转圈圈 (其实对方已经收到了), 切换窗口再切回来就连之前自己发的消息都不见了ovo 然而因为不太影响使用(可以在手机上看消息, 电脑盲回) 所以没太管. 但是作为一个强迫症还是不太能忍, 于是过了好久还是决定动手修一下. mac下微信的本地数据文件在 /Users/laekov/Library/Containers/com.tencent.xinWeChat/Data/Library/Application Support/com.tencent.xinWeChat/2.0b4.0.9. 初步估计是本地文件出锅了, 于是对它动手. 首先在mac端不上线的情况下手机拉了一个不影响别人的群, 然后用mac登录, 果然这个群属于bug群. 把 Message 目录移动为 Message_bak, 重新登录, 失去了所有聊天记录. 再次尝试使用上面那个群, 发现可以正常使用. 定位到问题文件在 Message 目录里. 发现 Message 目录下有 msg_[0-9]十种前缀的文件, 估计是对聊天记录进行了分桶. 大胆猜测是某个桶坏了. 于是等了一分钟后在群里发了一条消息, 发现只有 msg_6 开头文件被更新了. 大胆猜想是 msg_6 这个桶炸了. 另有有一个 MessageTemp 目录较大, 目测是数据文件. (比如消息, 图片, 视频) 猜想这里放的是元数据. 于是把旧的 MessageTemp 先拷回来. 然后恢复了 msg_1 开头的几个文件, 发现果然聊天记录回来了一部分. 挨个恢复除了 msg_6 以外的所有 msg_x 文件, 于是除了之前炸掉的记录以外, 聊天记录都回来了. 坏掉的文件就确实没法修了. 鬼知道.data格式是啥玩意. 完结撒花....

许久没写过博客了. 看到 harry 写了赛记才想起我还有个博客. 随便写一点东西吧. ASC19. 拿了 “大满贯” 之后第一场比赛, 拿了个亚军. @大连理工 Sec 0 赛前给自己的定位大概就是, 学学配机器和benchmark这种看上去比较底层的东西. 应用上就划划水好好干别的事. 于是初赛成为了写 proposal 选手 + 装机器选手. 最初装机器闹了很多笑话 比如在R730上把 V100 的挡板拆了然后导致显卡悬空. 感谢戴尔和 NVIDIA 的 PCIe 槽足够结实没有直接坏掉让我赔20万的机器的卡. 然后 proposal 也是写到崩溃 ovo. 然后跑 HPL 发现各种玄学, 以及 32G 的 V100 性能和 16G 的不太一样. 单卡跑不上去, 多卡也有各种问题. 然后 P, Q, NB 有很多玄妙的组合. (后来知道 N 也有很多玄学). 以及连续跑和单独跑是不一样的. 这还是不考虑功耗在四台 R730 上插上 8 张卡裸跑的情况. HPCG 单卡不压功率也只有 125 的样子. 另一个神奇的情况是直接跑HPL会报 MPI Error: Illegal address. 解决它的方法是, 跑一次HPCG....