Kickstart A Round 2020

This year’s round of Kick Start was much easier than in previous years—easy enough that I solved every problem, even though I could not solve yesterday’s LeetCode Problem D.

The strongest people on the leaderboard finished all of them in as little as 16 minutes. After writing these notes, I realised I have been getting worse this year. ^ - ^

Problem link

A. Allocation

Greedy.

std::vector<int> v;
void solve() {
    v.clear();
    int n,d;
    SA(n);
    SA(d);
    REPP(i,1,n) {
        int x;
        SA(x);
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    int cnt = 0;
    REP(i,0,v.size()) {
        if(d >= v[i]) {
            d-=v[i];
            cnt = i+1;
        } else {
            break;
        }
    }
    printf("%d\n", cnt);
}

B. Plates

The problem ultimately becomes a 0/1 knapsack problem; a greedy approach clearly does not work.

int v[55][55];
int dp[55][3005];
void solve() {
    memset(v, 0, sizeof(v));
    memset(dp,0,sizeof(dp));
    int n,k,p;
    SA(n);
    SA(k);
    SA(p);
    REPP(i,1,n) {
        REPP(j,1,k) {
            SA(v[i][j]);
            v[i][j] += v[i][j-1];
        }
    }
    REPP(i,1,n) {
        REPP(s,0,p) {
            dp[i][s] = max(dp[i][s], dp[i-1][s]);
        }
        REPP(s,0,p) {
            dp[i][s] = max(dp[i][s], dp[i-1][s]);
            REPP(j,1,k) {
               if(s + j > p) continue;
               dp[i][s+j] = max(dp[i][s+j], dp[i-1][s] + v[i][j]);
            }
        }
    }
    printf("%d\n", dp[n][p]);
}

C. Workout

Binary search.

ll n,k;
ll val[maxn];

bool check(ll mid) {
    ll now = k;
    for(int i=2;i<=n;i++) {
        if(val[i] - val[i-1] <= mid) {
            continue;
        }
        ll sur = val[i] - val[i-1];
        ll need = (sur - 1 )/ mid;
        if(now >= need) {
            now -=need;
        } else {
            return false;
        }
    }
    return true;
}

void solve() {
    SLLA(n);
    SLLA(k);
    ll le = 1;
    ll ri = 0;
    REPP(i,1,n) {
        SLLA(val[i]);
        if(i > 1) {
            ri = max(ri,val[i]-val[i-1]);
        }
    }

    while(le < ri) {
        ll mid = (le + ri)/2;
        if(check(mid)) {
            ri = mid;
        } else {
            le = mid + 1;
        }
    }
    printf("%lld\n", le);

}

D. Bundling

Use a trie, then apply a greedy strategy.

ll n, k, cnt;
int ch[maxn][30];
int num[maxn], sub[maxn];
ll ans;
char val[maxn];

void insert(char *x, int len)
{
    int now = 0;
    for (int i = 1; i <= len; i++)
    {
        int k = x[i] - 'A' + 1;
        if (!ch[now][k])
        {
            ++cnt;
            ch[now][k] = cnt;
        }
        now = ch[now][k];
        num[now]++;
    }
}

void dfs(int now, int deep, int fa) {
    REPP(i,1,26) {
        if(ch[now][i] != 0) {
            dfs(ch[now][i], deep + 1, now);
        }
    }

    int sz = num[now] + sub[now];
    if(sz < 0) {
    } else {
        ans += (sz/k)*deep;
        if(fa!=-1) {
            sub[fa] += -(sz/k)*k;
            sub[fa] += sub[now];
        }
    }
}

void solve() {
    ans = 0;
    cnt = 0;
    memset(ch,0, sizeof(ch));
    memset(num, 0, sizeof(num));
    memset(sub, 0, sizeof(sub));
    SLLA(n);
    SLLA(k);
    REPP(i,1,n) {
        scanf("%s", val + 1);
        int len = strlen(val+1);
        insert(val, len);
    }
    dfs(0, 0, -1);
    printf("%lld\n", ans);
}