建议首先阅读:
update: 这一轮通过了,但是ml intern的面试流程也没有更新(貌似可能因为疫情凉凉),感觉kick start失去了意义
先对本轮做个小结吧:这轮参加人远多于之前,总共有10000+人参加,规则也有所改变:
- 题目由原来的3道改为了4道,感觉整体变简单了。
- 没有隐藏的test set
这也是第一次全部AC,不过等结束了去统计了下,有917人满分。感觉意义也不是很大。而且比较难受的是,博主是21届毕业的学生,咨询HR发现仅2020年的成绩对校招有效,去年过了的不算。今年还得重打orz。
A. Allocation
Solution
解法
这道题很简单,升序排序,然后从小到大取就可以了。(没想到kick start也有这么简单的题,我多看了好几分钟,都没敢直接写答案)
复杂度分析
瓶颈主要在排序: O(nlogn) time.
代码
B. Plates
Solution
解法
该题是一道典型的动态规划问题,所求的是n堆plates中,取k个plate,所能得到的最大值
那么可以定义子问题:令dp[i][j] 代表前i堆plates里取j个plates得到的最大值,得到状态转移方程:
dp[i][j]=max\\{dp[i-1][j-m]+ sum_{i}(m)|for\ m\in[0,min(k,j)]\\}
其中的sum_{i}(m)代表在第i堆取m个plates的结果。注意,这里类似童年游戏汉罗塔,只能从上向下依次取,所以可以用前缀和来加速
复杂度分析
- 前缀和:n\times k
- dp: n\times p\times k
总计:O(npk) time.
代码
C. Workout
这道题,会用到一个有意思的算法技巧:优化问题转决策问题,知道这个技巧,问题就比较简单了。
Solution
解法
题目要求在插入k个session的情况下,所能得到的最小难度,从问题来看是一个的优化问题;而难度等于整个program中,两个连续session时间差的最大值。那么可以直接求出不加任何session的情况下,运动的难度,记作d,设所求解为res,那么一定有res \in[1,d]
问题就可以从优化问题,转化为决策问题:对于m \in[1,d],在至多插入k个session的情况下,是否成立?
同时该过程可以用二分搜索加速
复杂度分析
O(N*log(d)) time
代码
D. Bundling
Solution
解法
从题目描述来看,和字符串前缀相关,字符串又特别多,比较容易想到trie树,trie树的设计思想就是尽可能利用共同前缀,节省存储空间:当我们的trie树构建完成之后,实际上已经得到了最优解的组合情况,注意在构建树的时候,在每个节点,记录节点child的个数num_i;
遍历整个trie树,最优解的值为:\sum_{i\in {tree node}}num_i/K
请问有【优化问题转决策问题】的资料么,搜索了下没有发现什么有用的
暂时木有~