Western European Olympiad in Informatics 2024 Editorial

Here is a quick editorial for the problems from WEOI 2024, in order from easiest expected problem to hardest, along with my solutions.

You can attempt these problems on the mirror contest page on Codeforces.

Mazes (mazes)

Full Solution

From subtask $4$ , we can come up with a pattern to solve for all powers of two. The construction I used created the following pattern for $K = 8$ and is easily generalisable for all powers of two:

...#####
.#.#####
......##
###.#.##
###...##
#####...
#####.#.
#####...

We can add an “early-exit” for powers of $2$ that are used in the binary representation of $K$ , and bring them directly to the end of the maze.

For example, for $K = 5 = 2^0 + 2^2$ , we can add an early exit at the $K = 2^0$ and $K = 2^2$ squares.

...#####
.#.#####
......##
.##.#.##
.##...##
.####.##
.####.##
........

This will allow us to create a construction for any valid $K$ .

Full Solution Code

#include <vector>
using namespace std;

vector<vector<char>> solve(long long K) {
    if (K == 1) {
        return {{'.'}};
    }
    vector<vector<char>> ans(200, vector<char>(200, '#'));
    ans[0][0] = '.';
    ans[199] = vector<char>(200, '.');
    int x = 0;
    long long done = 0;
    for (int p = 0; done != K; ++p) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                ans[x + i][x + j] = '.';
            }
        }
        ans[x + 1][x + 1] = '#';
        if ((1LL << p) & K) {
            for (int i = x; i < 200; ++i) {
                ans[i][x] = '.';
            }
            done ^= 1LL << p;
        }
        x += 2;
    }
    return ans;
}

Double Agents (trees)

Full Solution

to-do

Full Solution Code

#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= MOD) {
    x -= MOD;
  }
  return x;
}

int sub(int x, int y) {
  x -= y;
  if (x < 0) {
    x += MOD;
  }
  return x;
}

int mul(int a, int b) {
  return (1LL * a * b) % MOD;
}

void dfs(int cur, int par, vector<vector<int>>& e, vector<int>& ways, vector<int>& ways_constrained) {
  ways[cur] = 1;
  int cnt1 = 0, cnt2 = 1;
  for (int child : e[cur]) {
    if (child == par) {
      continue;
    }
    dfs(child, cur, e, ways, ways_constrained);
    // fill root and one child subtree
    ways[cur] = add(ways[cur], ways_constrained[child]);
    // do not fill root, fill at least two child subtrees
    cnt2 = mul(cnt2, add(ways_constrained[child], 1));
    ways[cur] = sub(ways[cur], ways_constrained[child]);
    // do not fill root, fill only one child subtree
    cnt1 = add(cnt1, ways[child]);
  }
  ways[cur] = add(sub(ways[cur], 1), add(cnt1, cnt2));
  ways_constrained[cur] = 1;
  int cnt = 1;
  for (int child : e[cur]) {
    if (child == par) {
      continue;
    }
    cnt = mul(cnt, add(ways_constrained[child], 1));
  }
  ways_constrained[cur] = add(ways_constrained[cur], sub(cnt, 1));
}

int count_sets(int N, vector<int> u, vector<int> v) {
  vector<vector<int>> e(N);
  vector<int> ways(N), ways_constrained(N);
  for (int i = 0; i + 1 < N; ++i) {
    e[u[i]].push_back(v[i]);
    e[v[i]].push_back(u[i]);
  }
  dfs(0, -1, e, ways, ways_constrained);
  return ways[0];
}

Parcel Post (multihop)

Full Solution

Root the tree arbitrarily. Note that we can calculate the cost of moving from a node $U$ to its immediate ancestor (i.e. parent) $V$ very easily, it’s just $\min(A_i, B_i + C)$ , where $i$ is the indice of the edge connecting $U$ and $V$ .

If we keep track of some additional information, such as whether a path from a node to its ancestor starts and/or ends using a high power firing, we can keep track of $4$ states for each node from itself to its parent. Now, since we have the cost to get from a node to its $2^0 = 1$ -st ancestor, we can use binary lifting to calculate the cost, for each station, to its $i$ -th ancestor for all $1 \le i \le 16$ , with a little bit of casework for matching the states (you can see it in my code below!).

We can do the same binary lifting-dp to keep track of costs for downwards paths in the tree. Now, the cost of a path from $U$ to $V$ can be broken down into two paths: one upwards path from $U$ to $L$ , the lowest common ancestor of $U$ and $V$ , and one downwards path from $L$ to $V$ . Combining these two paths will tell us the lowest common cost for sending a parcel on this path.

Time complexity: $O(n \log n)$

Full Solution Code

#include <vector>
#include <array>
using namespace std;

struct min_cost {
    array<array<long long, 2>, 2> mc;
    // prefix/suffix closed/open
    void init() {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                mc[i][j] = 1e18;
            }
        }
    }
};

const int N = 1e5, L = 17;
int p[N], h[N], a[N], b[N], c, lift[L][N];
vector<int> e[N];
min_cost dp_up[L][N], dp_down[L][N];

min_cost merge(min_cost first, min_cost second) {
    min_cost ans;
    ans.init();
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                ans.mc[i][k] = min(ans.mc[i][k], first.mc[i][j] + second.mc[j][k]);
            }
        }
    }
    return ans;
}

void dfs(int cur) {
    for (int i = 1; (1 << i) <= h[cur]; ++i) {
        lift[i][cur] = lift[i - 1][lift[i - 1][cur]];
        dp_up[i][cur] = merge(dp_up[i - 1][cur], dp_up[i - 1][lift[i - 1][cur]]);
        dp_down[i][cur] = merge(dp_down[i - 1][lift[i - 1][cur]], dp_down[i - 1][cur]);
    }
    for (int i : e[cur]) {
        if (i == p[cur]) {
            continue;
        }
        p[i] = cur;
        h[i] = h[cur] + 1;
        lift[0][i] = cur;
        dp_up[0][i].mc[0][0] = min(a[i], b[i] + c);
        dp_up[0][i].mc[0][1] = min(a[i] + b[cur], b[i] + c);
        dp_up[0][i].mc[1][0] = min(c, a[i]);
        dp_up[0][i].mc[1][1] = min(c, a[i] + b[cur]);
        dp_down[0][i].mc[0][0] = min(a[cur], b[cur] + c);
        dp_down[0][i].mc[0][1] = min(a[cur] + b[i], b[cur] + c);
        dp_down[0][i].mc[1][0] = min(c, a[cur]);
        dp_down[0][i].mc[1][1] = min(c, a[cur] + b[i]);
        dfs(i);
    }
}

void init(int n, int C, vector<int> A, vector<int> B, vector<int> u, vector<int> v) {
    for (int i = 0; i < n; ++i) {
        a[i] = A[i];
        b[i] = B[i];
    }
    c = C;
    for (int i = 0; i < n - 1; ++i) {
        e[u[i]].push_back(v[i]);
        e[v[i]].push_back(u[i]);
    }
    dfs(0);
}

int lca(int x, int y) {
    if (h[x] < h[y]) {
        swap(x, y);
    }
    for (int i = 0; i < L; ++i) {
        if ((h[x] - h[y]) & (1 << i)) {
            x = lift[i][x];
        }
    }
    if (x == y) { return x; }
    for (int i = L - 1; i >= 0; --i) {
        if (lift[i][x] != lift[i][y]) {
            x = lift[i][x];
            y = lift[i][y];
        }
    }
    return lift[0][x];
}

long long query(int x, int y) {
    int z = lca(x, y);
    min_cost cur_ans;
    cur_ans.init();
    cur_ans.mc[0][0] = 0;
    vector<array<int, 2>> v;
    for (int i = 0; i < L; ++i) {
        if ((h[x] - h[z]) & (1 << i)) {
            cur_ans = merge(cur_ans, dp_up[i][x]);
            x = lift[i][x];
        }
        if ((h[y] - h[z]) & (1 << i)) {
            v.push_back({y, i});
            y = lift[i][y];
        }
    }
    while (!v.empty()) {
        cur_ans = merge(cur_ans, dp_down[v.back()[1]][v.back()[0]]);
        v.pop_back();
    }
    return cur_ans.mc[0][0];
}

Make All Equal (equal)

Full Solution

From Subtask $3$ , we can come up with a method for making $N = 2$ piles of stones equal: starting from $i = 19$ and working down to $0$ , we can add $2^i$ stones to the smaller pile. After the $i$ -th operation, we can be sure that the difference between $H_0$ and $H_1$ is no more than $2^i$ , that is, $| H_0 - H_1 | \le 2^i$ . Our last operation ensures that the difference between the two is at most $2^0 = 1$ , after which we can use a singular one of our $\textit{compare}$ operations to check whether $H_0$ and $H_1$ are equal. If they are not, we add $1$ stone to $H_0$ , and after doing so, $H_0 = H_1$ , as desired.

An intuitive idea follows: we can use a divide-and-conquer-esque method with segment merging, and solve our problem layer by layer, i.e. before solving for $[1, 2^{i + 1}]$ , solve for $[1, 2^i]$ and $[2^i + 1, 2^{i + 1}]$ , and make each subsegment equal first before making the new segment equal. This however, takes about $20 \times 2047$ $\textit{add}$ operations, which is not sufficient.

We notice that on each layer - each segment of length $2^i$ - all merges of subsegments are independent, and thus can occur at the same time. Now, for each layer, we perform about $20$ (plus some extra, I’ll leave it as an implementation detail :P) $\textit{add}$ operations, which solves the problem.

Full Solution Code

#include "equal.h"
#include <vector>
using namespace std;
 
void make_all_equal(int N, int, int) {
    for (int p = 2; p <= N; p *= 2) {
        vector<int> query_indices;
        for (int i = 0; i + p - 1 < N; i += p) {
            for (int j = i; j < i + p / 2; ++j) {
                query_indices.push_back(j);
            }
        }
        for (int i = 18 + __lg(p); i >= 0; --i) {
            add(query_indices, 1 << i);
        }
        query_indices.clear();
        for (int i = 0; i + p - 1 < N; i += p) {
            if (!compare(i, i + p - 1)) {
                for (int j = i; j < i + p / 2; ++j) {
                    query_indices.push_back(j);
                }
            }
        }
        if (!query_indices.empty()) {
            add(query_indices, 1);
        }
    }
}

Mazes (mazes)#

Double Agents (trees)#

Parcel Post (multihop)#

Make All Equal (equal)#

Mazes (mazes)

Double Agents (trees)

Parcel Post (multihop)

Make All Equal (equal)