nickbelov's blog

Spring 2025 Rutgers Programming Contest Editorial
By nickbelov, history, 17 months ago, In English

Thank you to everyone for participating! Here are the solutions.

105813A - Thomas

Solution

105813B - Stone Jump

Solution

105813C - Maxwell's Tiles

Solution

105813D - Distributive Property

Solution

105813E - 1D Super Checkers Solitaire

Solution

105813F - Walkable Strings

Solution

105813G - K-Regular Array

Solution

105813H - Cubist Painting

Solution

105813I - Unfair Game

Solution

105813J - Another Expected Value Problem

Solution

105813K - Pointers

Solution

105813L - Permutation Recovery

Solution

105813M - Subsequence MEX

Solution

105813N - Ramen Packs

Solution
  • Vote: I like it
  • +24
  • Vote: I do not like it

»
17 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

The proof for K is kind of involved, here is the code + intuitive version of it:

The high level idea is that there are 2m infinite states (we can show this), and we will find one of the "baseline" ones that start with the starting node $$$s$$$.

    vector<vector<int>> adj(n + 1), ptr(n + 1);
    vector<int> q{s}, nq;
    for (int level = 0; q.size(); swap(q, nq), nq.clear(), level++)
      for (auto s : q) {
        while (ptr[s].size() < adj[s].size()) {
          int nxt = adj[s][ptr[s].size()];
          ptr[s].push_back(level);
          s = nxt;
          nq.push_back(s);
        }
      }
    cout << s;
    for (int i = 1; i <= n; ++i) {
      while (ptr[i].back() != ptr[i][0])
        ptr[i].pop_back();
      cout << " " << adj[i][ptr[i].size() % adj[i].size()];
    }
    cout << '\n';

The intuition behind the while loop is that we can iteratively expand an eulerian tour.

The reason why we care about only the first "level" of edges that touch a node is because roughly the process for a node goes:

A. Unvisited on iteration $$$ \lt i$$$

B. Visited on iteration $$$i$$$, all edges may or may not be consumed

C. Consume rest of edges on iteration $$$i + 1$$$, furthermore re-consume the edges visited in $$$B$$$

D. For the rest of time, the order is fixed and you visit all edges, so you will always stay in $$$|B|$$$

→ Reply
  • »
    »
    17 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Also fun trivia:

    One of the earlier iterations of the problem was, "Does the graph return to the starting state an infinite number of times?", where "state" does NOT care about what the current node is, only the pointers.

    This is actually cancer to write tests for and most common cheeses pass, so I reworked the problem so that most random graphs are good tests. I didn't understand the structure of the problem enough T-T

    I have a very cool but unproven solution that relies on BCC decompositions — find the bridges, process each BCC individually, then run an algorithm that works on a tree on it.

    I believe some teams during the on-site were trying something like this — the following algorithm can verify whether the initial state repeats infinitely, but it seems hard to recover the initial state of nodes. I still have the old problem package if people want to submit to this version of the problem and try their hand at it. I didn't have a proof for this version of the problem so it didn't make its way into the contest.

    //boilerplate above
bool tree_verify(int i, int p, int free_pass) {
  if (!free_pass and adj[i][0] != p)
    return false;
  int cur = i;
  while (1) {
    if (adj[cur].empty()) {
      assert(cur == i);
      return true;
    }
    int nxt = adj[cur].back();
    adj[cur].pop_back();
    if (bridges.count({cur, nxt})) {
      if (nxt == p)
        continue;
      if (free_pass and cur == i and adj[i].empty())
        return tree_verify(nxt, cur, true);
      if (!tree_verify(nxt, cur, false))
        return false;
    } else {
      cur = nxt;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= n; ++i) {
      int k;
      cin >> k;
      adj[i].resize(k);
      for (int j = k - 1; j >= 0; --j)
        cin >> adj[i][j];
    }
    {
      bridges.clear();
      fill(bridge::visited, bridge::visited + n + 1, 0);
      bridge::dfs(s);
    }
    bool answer = tree_verify(s, -1, true);
    for (int i = 1; i <= n; ++i)
      answer &= adj[i].empty();
    cout << (answer ? "YES" : "NO") << '\n';
  }

  return 0;
}
    → Reply