Kick Start 2019A

KickStart是谷歌的线上笔试,每年会举办数轮,通过KickStart可以拿到工作面试名额。KickStart的有一定难度,但是又没有用到复杂的数据结构,是比较好的笔试筛选题。

一般来说,一轮比赛有三道题,每道题有小数据和大数据。按照以往的难度,我预计能过A题,BC题小数据。但是没想到这次题目比以往的简单的多,凭借一点运气全部过了,成绩为601名(参赛一万多人,有约一千人全部过,所以相比以前的题确实不算难了),这里记录一下,本次所有题目都在这里

1. Allocation

题目: There are N houses for sale. The i-th house costs Ai dollars to buy. You have a budget of B dollars to spend. What is the maximum number of houses you can buy?

签到题,直接按照价格排序,从最便宜的往最贵的买,复杂度O(Nlog(N))。

using namespace std;

const int N=100010;
int values[N];

int solve(){
    int n, money, ret=0;
    cin>>n>>money;
    for(int i=0; i<n; i++) cin>>values[i];
    sort(values, values+n);
    for(int i=0; i<n; i++){
        if((money-=values[i])>=0) ret++;
        else break;
    }
    return ret;
}

int main(){
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        auto ans = solve();
        cout<<"Case #"<<i+1<<": "<<ans<<endl;
    }
    return 0;
}

2. Plates

题目: 有N摞盘子,每摞有K个,每个盘子都有一个漂亮值,如果想在一摞盘子取一个盘子,那么它上面的盘子都要取,现在想取P个盘子,能达到的最大漂亮值是多少?

这道题如果没有做过类似的得花一些时间想,但非常巧的是我头一天晚上看KickStart2019的C轮题目的Catch Some,比这道题难一些,但也是类似的,从N个东西里选一些出来,在数量限制的条件下,求某种属性的最大值/最小值,所以思路是分组背包问题。

对于一摞盘子,有K+1种选法,分别为从上到下选0,1,…K个盘子,也对应着K+1个漂亮值。所以把选盘子的数量看作背包空间,漂亮值看作物品的价格,就是有N类物品,从每类中选一种物品,求最大价值,也就是分组背包问题,代码如下:

using namespace std;

int values[60][40];
int dp[60][1510];

int solve(){
    int n, k, p;
    cin>>n>>k>>p;
    memset(values, 0, sizeof(values));
    memset(dp, 0, sizeof(dp));

    for(int i=1; i<=n; i++){
        int sum=0, cv;
        for(int j=1; j<=k; j++){
            cin>>cv;
            sum+=cv;
            values[i][j]=sum;
        }
    }


    for(int i=1; i<=n; i++){
        for(int j=1; j<=p; j++){
            for(int sk=0; sk<=j&&sk<=k; sk++)
                dp[i][j] = max(dp[i][j], dp[i-1][j-sk]+values[i][sk]);
        }
    }
    return dp[n][p];
}

int main(){
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        auto ans = solve();
        cout<<"Case #"<<i+1<<": "<<ans<<endl;
    }
    return 0;
}

Google是比较喜欢出背包问题,还有2019B轮的一道Energy Stones也是类似,我刷了2019ABC三轮就遇到两道背包问题,频率还是挺高的。

这里概括一下这种题的特点:一般是从N类/N个物品里选K个,要求某个值最大/最小,如果物品之间选择的顺序是平凡的,那么就可以用背包问题的套路解决。“选择的顺序是平凡的“有两种情况,一种是选择的顺序是不重要的,与最后的值没有关系;另一种情况是,最优解选择物品的先后顺序是确定的,只是不知道是否要选这个物品,Energy Stones就是这样的题。

3. Workout

题目: 小王要上N节体育课,每节体育课都有一个难度系数Ai,小王要从难度最低的上到最高的,但是中间怕有的课之间难度系数相差太大,一下适应不了,所以你可以往其中插入K节课,使得相邻课之间的难度系数相差的最大值最小,问你能优化到多小。

这道题leetcode有类似的题,大意是一条线上有N个邮局,要再建K个邮局,问所有相邻邮局的最大距离的最小值是多少。一样的思路,二分可以解决,距离的最小是是0,最大值是最初始的最大相邻距离,然后取中点做二分。

using namespace std;

int times[100010], inters[100010];

bool valid(int target, int n, int k){
    for(int i=0; i<n-1; i++){
        int ci = inters[i];
        if(ci>target){
            int demand = (ci-1)/target;
            k -= demand;
            if(k<0) return false;
        }
        else break;
    }
    return true;
}

int solve() {
    int n, k;
    cin>>n>>k;
    for(int i=0; i<n; i++) cin>>times[i];
    for(int i=0; i<n-1; i++) inters[i]=times[i+1]-times[i];
    sort(inters, inters+n-1, greater<>());
    //for(int i=0; i<n-1; i++)cout<<inters[i]<<" ";
    //cout<<endl;

    if(inters[0]==0) return 0;
    int l=1, r= inters[0]+1;
    while(l!=r){
        int mid = (l+r)/2;
        if(valid(mid, n, k)) r=mid;
        else l = mid+1;
    }
    return l;
}

int main(){
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        auto ans = solve();
        cout<<"Case #"<<i+1<<": "<<ans<<endl;
    }
    return 0;
}

Google出的二分题也多,2019A的Parcels题也是二分,思路比较巧。这样的题一般也是求最大值/最小值,能够初始确定值的范围,而且对于每个值,可以比较快速地核实能够优化到这个值(通常为O(N)),这时候用二分就很方便了。

4. Bundling

题目: 给N个字符串,让我们把它分组,每组K个字符串(K整除N),每一组的共同前缀的长度为该组的得分,求所有组得分总和最大为多少。

这道题之前没见过,需要按照固定的思路想一下。首先看到看到前缀,想到的方法肯定是前缀树(字典树),把字符串存到前缀树中,每个节点可以记录前缀在这里的字符串有多少;然后再想有没有贪心的组团方法,可以先找公共前缀最长的组团,把组团中的字符串删掉,再继续这样找,可以想到,这样找确实是最优的。结合两种想法,就是先建立字典树,在每个节点存字符串的数量,然后从下往上对树做层次遍历,遇到够组团的,就把字符串删掉,一直遍历到树根就可以了。

整个算法的时间复杂度为O(N),空间复杂度也为O(N),N是字符的数量。

using namespace std;

struct Node{
    int count;
    int need_remove;
    Node* child[26];
    Node *parent;
}nodes[2000010];
int S;
unordered_map<int,vector<Node*>> umap;

void insert(Node* node, string& s, int i, int level){
    node->count++;
    if(i==s.size()) return;
    int index = s[i]-'A';
    if(!node->child[index]){
        Node* c = &nodes[S++];
        umap[level+1].push_back(c);
        node->child[index] = c;
        c->parent = node;
    }
    insert(node->child[index], s, i+1, level+1);
}


int solve() {
    int n,k;
    cin>>n>>k;

    umap.clear();
    S=0;
    memset(nodes, 0, sizeof(nodes));
    Node* root = &nodes[S++];

    string s;
    for(int i=0; i<n; i++){
        cin>>s;
        insert(root, s, 0, 0);
    }

    int level=0, ret=0;
    for(auto &pair: umap) level=max(level, pair.first);
    while(level>0){
        for(Node *node: umap[level]){
            int true_count= node->count - node->need_remove;
            ret += (level*(true_count/k));
            node->need_remove += (true_count-true_count%k);
            node->parent->need_remove += node->need_remove;
        }
        level--;
    }
    return ret;
}

int main(){
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        auto ans = solve();
        cout<<"Case #"<<i+1<<": "<<ans<<endl;
    }
    return 0;
}

没想到这道题代码写起比较顺利,写完、运行、提交、Pass、舒服。