European Championship 2024 Problem Explanation

European Championship 2024 - Online Mirror

A. Grove#

You are given a $20 \times 20$ grid, and you need to place as many circles with a radius of $r$ (where $r$ is a three-digit decimal) on the integer points inside it as possible.

Having seen some conclusions from packing problems, it seems that the arrangement methods don't have much reasoning behind them.

It feels like a problem that involves memoization + heuristics + exhaustive search. Clearly, you should place them as close as possible, using memoization to eliminate some duplicate searches. Since there are no teammates writing, it seems completely unreasonable to just blabber without any basis?

B. Charming Meals#

A teammate wrote one problem and then left.

C. Annual Ants' Gathering#

You are given a tree, with an ant on each node. Each time, you can move all ants at node $u$ along an edge to node $v$ , provided that the number of ants at $u$ is less than or equal to the number at $v$ . The question is whether you can eventually gather all ants at one node.

Clearly, if you leave one node empty, the tree will be disconnected, so you can only shrink one leaf at a time. Moreover, since smaller nodes are more likely to shrink, only after shrinking smaller nodes can larger nodes be created to allow other things to move.

Thus, it seems you can maintain a min-heap and simulate something like a topological sort.

F. Dating#

You are given $n$ people, each with a set. A good match is defined as two people's sets having an intersection but not being subsets of each other. Find a good match or report that there isn't one.

I made up a method based on the fact that the number of types of set sizes is on the order of the square root (600 types).

First, for each set size, check if there are any completely identical sets and remove them (using an unordered set hash). Then, check if there are any two people's sets that intersect, which means checking if any numbers appear more than once; if so, there is an intersection, and since the lengths are the same and not completely identical, it is the answer.

Thus, we now have 600 lengths, each containing a bunch of disjoint sets.

Then, enumerate the lengths from largest to smallest, construct a forest containing the set relationships, and maintain which node last covered each tree.

For each set in the current length, traverse the set to find out which node last covered each number; for this covering node set, there are several cases:

If there are two points on two different trees in the forest, then we have found a set of answers, the current set and either of the two points: because finding a point indicates an intersection, being on different trees means the numbers in the current set must not be in the other, and due to the length restriction, the current set must not contain all sets in between.
If there are two points on the same tree in the forest, then due to the inclusion relationship, these two must have an ancestor relationship, choosing the current set and the deepest one as the answer: because finding a point indicates an intersection, being able to find two last covering points indicates that this number is in the ancestor set and not in the descendant set, and due to the length restriction, the current set must not contain all sets in between.
If there is one point on the same tree in the forest, then connect them with an edge, indicating a parent-child relationship.

G. Scooter#

No teammates are willing to write.

It seems that just constructing according to the problem statement will do, for example, -m mc cm mc c- -c cm m- -c cm m-.

I. Disks#

You are given a bunch of circles that may be tangent or disjoint, and you need to determine whether it is possible to adjust the radius of all circles such that the original tangential and disjoint relationships remain unchanged, and the sum of all circle radii decreases.

By observing, you can find that since you need to maintain the tangential relationship, if you shrink one circle, it will inevitably cause another circle to enlarge, balancing the two.

Then, looking at the example gives a chain of length 3, which can be arranged in a "small - large - small" manner, thus reducing the sum of the radii. Then consider how complex graphs would behave, for example, cycles; even cycles are possible, but odd cycles are not, naturally leading to the thought of bipartite graphs. Therefore, it seems that coloring the original graph as a bipartite graph corresponds to reducing and increasing two types of changes, checking whether there are connected components with differing numbers of points on both sides.

J. Amanda the Amoeba#

No teammates are willing to write.

It just feels like enumerating each point in the target grid, then deleting some boundary points that are not well placed, and moving step by step.

Code#

C. Annual Ants' Gathering#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, deg[maxn], cnt[maxn], visited[maxn];
vector<int> edge[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }

  priority_queue<pair<int,int>> pq;
  for (int i = 1; i <= n; i++) {
    cnt[i] = 1;
    if (deg[i] == 1) {
      visited[i] = true;
      pq.push({ -1, i });
    }
  }

  bool ok = true;
  while (!pq.empty() && ok) {
    auto cur = pq.top();
    pq.pop();

    int u = cur.second;
    assert(visited[u]);

//    printf("F %d\n", u);

    for (int v: edge[u]) {
      if (visited[v]) continue;

      if (cnt[u] <= cnt[v]) {
        deg[v]--;
        cnt[v] += cnt[u];
        cnt[u] = 0;
        if (deg[v] == 1) {
          visited[v] = true;
//          printf("PUSH %d -> %d\n", u,v);
          pq.push({ -cnt[v], v });
        }
      } else {
        ok = false;
        break;
      }
    }
  }

  puts(ok ? "YES" : "NO");

  return 0;
}

F. Dating#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <random>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 200000 + 5;
const int maxm = 1000000 + 5;

int n, m;

unsigned int hsh[maxn], key[maxm];
int dep[maxn], fa[maxn], bel[maxm];

vector<int> bag[maxn];
vector<int> lens[maxm];

bool check(int x, int y) {
  set<int> mp1, mp2;
  for (int t: bag[x]) mp1.insert(t);
  for (int t: bag[y]) mp2.insert(t);
  int cond1 = false, cond2 = false, cond3 = false;
  for (int t: mp1) {
    if (mp2.count(t)) cond1 = true;
    else cond2 = true;
  }
  for (int t: mp2) {
    if (mp1.count(t)) cond1 = true;
    else cond3 = true;
  }
  return cond1 && cond2 && cond3;
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &m);

  mt19937 rnd((unsigned) time(nullptr));
  for (int i = 1; i <= m; i++) {
    key[i] = rnd();
  }

  for (int i = 1; i <= n; i++) {
    int c;
    scanf("%d", &c);
    for (int j = 1, x; j <= c; j++) {
      scanf("%d", &x);
      bag[i].push_back(x);
      hsh[i] ^= key[x];
    }
    sort(bag[i].begin(), bag[i].end());
    lens[c].push_back(i);
  }

  for (int l = 1; l <= m; l++) {
    if (lens[l].empty()) continue;

    // Remove same
    {
      map<unsigned, int> mp;
      vector<int> uniqued;
      for (int id: lens[l]) {
        if (mp.count(hsh[id])) {
          continue;
        }
        mp[hsh[id]] = id;
        uniqued.push_back(id);
      }
      lens[l] = uniqued;
    }
    // Check intersect
    {
      memset(bel, 0, sizeof bel);
      for (int id: lens[l]) {
        for (int x: bag[id]) {
          if (bel[x]) {
            puts("YES");
            printf("%d %d\n", bel[x], id);
            assert(check(bel[x], id));
            return 0;
          }
          bel[x] = id;
        }
      }
    }
  }

  vector<int> groups;
  for (int l = m; l >= 1; l--) {
    if (lens[l].empty()) continue;

    if (groups.empty()) {
      // Largest length
      for (int id: lens[l]) {
        groups.push_back(id);
        for (int x: bag[id]) {
          bel[x] = id;
        }
      }
    } else {
      vector<int> ngroups;
      for (int id: lens[l]) {
        // bel[x]: the last bag id which covers x
        // visited: set of bel[x]
        // roots: set of the roots of bel[x]
        set<int> visited, roots;
        for (int x: bag[id]) {
          if (!visited.count(bel[x])) {
            visited.insert(bel[x]);

            int last = bel[x];
            if (bel[x]) {
              int f = bel[x];
              while (f) {
                last = f;
                f = fa[f];
              }
            }
            roots.insert(last);
          }
        }
        
        if (roots.size() == 0 || (roots.size() == 1 && *roots.begin() == 0)) {
          // Create a new tree in the forest
          fa[id] = 0;
          dep[id] = 1;
        } else if (roots.size() >= 2) {
          // Intersect with two tree chains
          int root = 0;
          for (int x: roots) {
            if (x) {
              root = x;
              break;
            }
          }
          puts("YES");
          printf("%d %d\n", root, id);
          assert(check(root, id));
          return 0;
        } else {
          // Intersect with one tree chain
          if (visited.size() == 1) {
            // Connect tree father
            int cur = *visited.begin();
            assert(cur != 0);
            fa[id] = cur;
            dep[id] = dep[cur] + 1;
          } else {
            // Intersect with multiple bags in one chain
            // That is to say that id is subset of the root, but intersect with the deepest node
            int tag = -1;
            for (int x: visited) {
              if (tag == -1 || dep[x] > dep[tag]) {
                tag = x;
              }
            }
            assert(tag != -1);
            puts("YES");
            printf("%d %d\n", tag, id);
            assert(check(tag, id));
            return 0;
          }
        }
      }
      
      for (int id: lens[l]) {
        ngroups.push_back(id);
        for (int x: bag[id]) {
          bel[x] = id;
        }
      }
      groups = ngroups;
    }
  }

  puts("NO");

  return 0;
}

I. Disks#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, deg[maxn];

vector<int> edge[maxn];
int flag, cnt, visited[maxn], col[maxn];

struct Circle {
    int x, y, r;
} a[maxn];

void dfs(int u) {
  cnt += col[u] == 0 ? 1 : -1;
  for (int v: edge[u]) {
    if (visited[v]) {
      if (col[v] != !col[u]) {
        flag = false;
      }
      continue;
    }
    visited[v] = true;
    col[v] = !col[u];
    dfs(v);
  }
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      long long dis = 1ll * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1ll * (a[i].y - a[j].y) * (a[i].y - a[j].y);
      if (dis == 1ll * (a[i].r + a[j].r) * (a[i].r + a[j].r)) {
        deg[i]++;
        deg[j]++;
        edge[i].push_back(j);
        edge[j].push_back(i);
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    flag = true;
    cnt = 0;
    dfs(i);
    if (flag && cnt > 0) {
      puts("YES");
      return 0;
    }
  }

  memset(visited, 0, sizeof visited);
  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    col[i] = 1;
    
    visited[i] = true;
    flag = true;
    cnt = 0;
    dfs(i);
    if (flag && cnt > 0) {
      puts("YES");
      return 0;
    }
  }

  puts("NO");

  return 0;
}