Algorithm Kick Start

Google Kick Start 2020 A轮题解

查阅更多的题解,请点击
github传送门

建议首先阅读:

update: 这一轮通过了,但是ml intern的面试流程也没有更新(貌似可能因为疫情凉凉),感觉kick start失去了意义

先对本轮做个小结吧:这轮参加人远多于之前,总共有10000+人参加,规则也有所改变:

  • 题目由原来的3道改为了4道,感觉整体变简单了。
  • 没有隐藏的test set

这也是第一次全部AC,不过等结束了去统计了下,有917人满分。感觉意义也不是很大。而且比较难受的是,博主是21届毕业的学生,咨询HR发现仅2020年的成绩对校招有效,去年过了的不算。今年还得重打orz。

A. Allocation

题目地址

Solution

解法

这道题很简单,升序排序,然后从小到大取就可以了。(没想到kick start也有这么简单的题,我多看了好几分钟,都没敢直接写答案)

复杂度分析

瓶颈主要在排序: O(nlogn) time.

代码

code

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.

代码

code

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

代码

code

D. Bundling

题目地址

Solution

解法

从题目描述来看,和字符串前缀相关,字符串又特别多,比较容易想到trie树,trie树的设计思想就是尽可能利用共同前缀,节省存储空间:当我们的trie树构建完成之后,实际上已经得到了最优解的组合情况,注意在构建树的时候,在每个节点,记录节点child的个数num_i

遍历整个trie树,最优解的值为:\sum_{i\in {tree node}}num_i/K

代码

code

发表评论

电子邮件地址不会被公开。 必填项已用*标注