Not much, just my solutions and some comments from my practice contest today :)

Spoiler warning - contains full solutions!

P1: Voronoi Villages

Not much to say about this one; the solution speaks for itself:

#include <algorithm>
#include <iostream>

int v[100];

int main(){
    int n; std::cin >> n;
    for(int i=0; i<n; ++i) std::cin >> v[i];
    std::sort(v, v+n);

    int best = 2e9;

    // edge villages are infinite size so no point in processing
    for(int i=1; i<n-1; ++i){
        int current = v[i+1] - v[i-1];
        if(current < best) best = current;
    }

    // imagine using floating point
    std::cout << best/2 << '.' << (best&1 ? '5' : '0') << '\n';
}

P2: Sunflowers

Another instasolve.. Just needed some specific observations..

// Key observation here is that an arrangement of
// data is only valid if it is sorted in order both
// left -> right and top -> bottom, so we can just
// check the four corners

#include <iostream>

int data[100][100], next[100][100], n;

bool check(){
    return data[0][0] < data[0][n-1] && data[0][0] < data[n-1][0] &&
        data[0][n-1] < data[n-1][n-1] && data[n-1][0] < data[n-1][n-1];
}

void rotate(){
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j)
        next[j][n-1-i] = data[i][j];
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j)
        data[i][j] = next[i][j];
}

int main(){
    std::cin >> n;
    for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) std::cin >> data[i][j];

    for(int i=0; i<4; ++i){
        if(check()){
            // silly io (im lazy)
            for(int i=0; i<n; ++i) for(int j=0; j<n; ++j)
                std::cout << data[i][j] << " \n"[j==n-1];
            break;
        }
        rotate();
    }
}

P3: RoboThieves

Still a very implementation-focused problem.

// BFS spam starting from source, essentially

#include <iostream>

// is square watched by camera?
bool cam[100][100];
char board[100][100];
// length of shortest path
int best[100][100],
    // best bfs method trust
    bfs[10000], *l, *r;

// cycle detection in conveyor loops - consider()
// takes in a cell and figures out if it has a valid
// unvisited endpoint. If so, adds to BFS "queue".

// seen[][] is used while traverse to find cycle
bool seen[100][100];
// return value indicates whether or not hit cycle
bool consider(int i, int j, int d){
    // already processed, do nothing
    if(best[i][j]) return 1;

    // cycle hit; for efficiency we just make the
    // whole trail a wall to avoid future processing
    if(seen[i][j]){
        board[i][j] = 'W';
        return 1;
    }

    // untravelable square
    if(board[i][j] == 'W' || cam[i][j]) return 1;

    // follow conveyors until hit cycle or valid cell
    seen[i][j] = 1;
    switch(board[i][j]){
        case 'L':
            if(consider(i, j-1, d)) board[i][j] = 'W';
            break;
        case 'R':
            if(consider(i, j+1, d)) board[i][j] = 'W';
            break;
        case 'U':
            if(consider(i-1, j, d)) board[i][j] = 'W';
            break;
        case 'D':
            if(consider(i+1, j, d)) board[i][j] = 'W';
            break;
    }
    seen[i][j] = 0;

    // hit valid square; return and add to queue
    if(board[i][j] == '.') best[i][j] = d, *r = i*100 + j, ++r;

    return 0;
}

int main(){
    int n, m; std::cin >> n >> m;

    for(int i=0; i<n; ++i) for(int j=0; j<m; ++j)
        std::cin >> board[i][j];

    // pointer magic
    l = bfs, r = bfs;

    // compute influence of cameras
    for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) if(board[i][j] == 'C'){
        for(int a=0; a<100; ++a){
            if(board[i+a][j] == 'W') break;
            if(board[i+a][j] == '.' || board[i+a][j] == 'S') cam[i+a][j] = 1;
        }
        for(int a=0; a<100; ++a){
            if(board[i-a][j] == 'W') break;
            if(board[i-a][j] == '.' || board[i-a][j] == 'S') cam[i-a][j] = 1;
        }
        for(int a=0; a<100; ++a){
            if(board[i][j+a] == 'W') break;
            if(board[i][j+a] == '.' || board[i][j+a] == 'S') cam[i][j+a] = 1;
        }
        for(int a=0; a<100; ++a){
            if(board[i][j-a] == 'W') break;
            if(board[i][j-a] == '.' || board[i][j-a] == 'S') cam[i][j-a] = 1;
        }
    }

    // find starting position and push on bfs queue
    for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) if(board[i][j] == 'S')
        if(!cam[i][j]) best[i][j] = 1, *r = i*100 + j, ++r;

    // do the BFS
    while(l != r){
        int i = (*l) / 100, j = (*l) % 100, d = best[i][j]+1; ++l;
        consider(i+1, j, d), consider(i-1, j, d),
            consider(i, j+1, d), consider(i, j-1, d);
    }

    // array initializes with all zeroes and i was too lazy to reinit so
    // just set start node with depth 1 and decrement distances - also
    // removes need for visited array
    for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) if(board[i][j] == '.')
        std::cout << best[i][j]-1 << '\n';
}

Little edge case regarding camera watching start position, but nothing really out of the blue.

P4: Balanced Trees

This one was actually very interesting - immediately saw the DP but couldn't find a good speedup besides sqrt decomp. Ended up moving on to try P5.

// I couldn't find a very good solution in contest,
// so I just moved on - but scraped a couple partials
// with a constructive DP approach: compute for each
// 1 <= i <= n by iterating over all k

#include <iostream>

int out[1000001];

int main(){
    int n; std::cin >> n;

    out[1] = 1;

    for(int i=2; i<=n; ++i){
        // n^2 did not get too far so to steal 2 more
        // partials I used sqrt decomposition - this is
        // actually very similar to the CSES problem
        // "counting divisors" which I did recently
        for(int k=1; k*k<=i; ++k){
            if(k-1) out[i] += out[i/k];
            int l = std::max(k, i/(k+1)), r = i/k;
            out[i] += out[k] * (r - l);
        }
    }

    // 7 points partials :clown:
    std::cout << out[n] << '\n';
}

P5: Maximum Strategic Savings

General approach seemed pretty standard, but working out the actual details took a while. Header comment has better description:

// CCC '18 S5 Maximum Strategic Savings  -  https://dmoj.ca/problem/ccc18s5
//
// This problem reeks of MST :P
//
// We have some sort of graph with patterned edges of certain
// weight, and want to minimize sum of weights. Unfortunately,
// we can't use literal MST because there are something on
// the order of 1e10 edges, so we need to exploit the patterning.
//
// For the sake of understanding, let's use standard MST, and
// see what happens. It turns out it'll be simpler to sort edges
// and then add, kruskal's-style, rather than mantaining a queue.
//
// The first thing we can notice is that all edges of the same
// "type", that being, all flights between same-index cities
// or all portals between same-index planets will be added all
// at once. So, it looks like we can significantly optimize by
// treating all same-type edges as one, and somehow computing
// how many times they will need to be added.
//
// How do we calculate the number of additions? Take for example
// this setup with 2 planets and 4 cities per planet:
//
//   1,1           2,1
//    |             |
//   1,2           2,2
//     
//   1,3           2,3
//    |             |
//   1,4           2,4
//
// Say we can add a portal between planets 1 and 2. How many times
// at minimum do we add this edge?
//
// Here it's easy: both planets have the same "structure" of
// connected components, so we only need to add one portal per
// component. But what if the planets have different structure?
// I claim that all planets will *always* have identical structure.
//
// What if we're adding a flight instead of a portal? Consider:
//
//   1,1 ---- 2,1      3,1
//
//   1,2 ---- 2,2      3,2
//
// Here we're assuming that the portals are of identical structure,
// but I claim that this too will always happen. Anyway, we only
// need to add two edges, as there are only two "connected components"
// in the graph of the planets.
//
// This, if our mirror assumption holds, would be enough to solve the
// problem. Let's try to prove this:
//
// First, why must planets have the same structure? Let's try to prove
// by contradiction: Under what conditions would we *not* add a flight
// uniformly to all planets? We've actually seen this in an example
// before:
//
//   1,1 ---- 2,1      3,1
//    |                 |
//   1,2 ---- 2,2      3,2
//
// Here, we didn't need to add a flight on planet 2 because planets
// 1 and 2 formed a connected component, and so adding a flight on
// only planet 1 was sufficient. But now look: If we want to add
// a portal between planets 2 and 3, the "structure" is still actually
// the same; both planets have city 1 and 2 in the same connected
// component.
//
// The same logic can be applied to show that adding portals mantains
// connected component-ness across planets.

#include <algorithm>
#include <iostream>
#include <array>

using LL = long long;

// flights are "internal" and portals are "external"
std::array<int, 3> in[100000], out[100000];
// combine all edge types together and sort
std::array<int, 4> all[200000];

// DSU to store components formed by cities (inroot) as well
// as components formed by planets (outroot), and also their
// count of components
int inroot[100000], outroot[100000], incomps, outcomps;

int find(int *root, int i){
    if(root[i] < 0) return i;
    return root[i] = find(root, root[i]);
}

int main(){
    int n, m, p, q; std::cin >> n >> m >> p >> q;

    // input everything.. so messy
    for(int i=0; i<p; ++i)
        std::cin >> in[i][1] >> in[i][2] >> in[i][0], --in[i][1], --in[i][2];
    for(int i=0; i<q; ++i)
        std::cin >> out[i][1] >> out[i][2] >> out[i][0], --out[i][1], --out[i][2];

    for(int i=0; i<p; ++i)
        all[i][0] = in[i][0], all[i][1] = in[i][1], all[i][2] = in[i][2], all[i][3] = 1;
    for(int i=0; i<q; ++i)
        all[i+p][0] = out[i][0], all[i+p][1] = out[i][1], all[i+p][2] = out[i][2];

    // init DSU structures (store size in same array)
    for(int i=0; i<n; ++i) outroot[i] = -1;
    for(int i=0; i<m; ++i) inroot[i] = -1;
    outcomps = n, incomps = m;

    std::sort(all, all+p+q);

    // maximum saved - assume everything can be removed, and then add
    // back the cost of edges we use, multiplied by their occurance
    LL max = 0;

    for(int i=0; i<p+q; ++i){
        // edge is a flight
        if(all[i][3]){
            // like mentioned before we assume we use this flight
            max += (LL)all[i][0] * n;

            // check if these city types are already in the same
            // component, and if so, do nothing
            int a = find(inroot, all[i][2]), b = find(inroot, all[i][1]);
            if(a == b) continue;

            // occurances of this flight is precisely equal to
            // the number of components formed by planets
            max -= (LL)all[i][0] * outcomps;

            // update components
            if(a < b) inroot[a] += inroot[b], inroot[b] = a;
            else inroot[b] += inroot[a], inroot[a] = b;
            --incomps;

        // edge is a portal
        }else{
            // identical, but with the other variable set
            max += (LL)all[i][0] * m;

            int a = find(outroot, all[i][2]), b = find(outroot, all[i][1]);
            if(a == b) continue;

            max -= (LL)all[i][0] * incomps;
            if(a < b) outroot[a] += outroot[b], outroot[b] = a;
            else outroot[b] += outroot[a], outroot[a] = b;
            --outcomps;
        }
    }

    // it is really that easy
    std::cout << max << '\n';
}

I ended up actually not finishing within my semi-official window, submitting a correct solution ~7 minutes after time, but Richard said to prioritize solve ability rather than time (another bad CF practice?)

Great contest overall, interesting problems. Also, shoutout to my code formatting script, which saved me tons of time while writing this post.

tags: programming ccc contest-logs