Alternative Editorial to 2019 USACO Gold February, Problem 1 (Cow Land)

Revision en12, by nsqrtlog, 2022-09-14 02:47:08

The official editorial to this problem is not asymptotically optimal and involves an advanced concept that's infrequent in USACO Gold. I managed to derive a relatively "low-tech" and faster solution, which I will describe below.


Problem link


Solution

for the sake of convenience, let $$$\sum\limits_u^v$$$ denote the XOR of all labels on the path from node $$$u$$$ to node $$$v$$$.

Subtask 1

We want a way to efficiently calculate the XOR of every label along an arbitrary path without modifications. Note that after rooting the tree at an arbitrary root $$$r$$$, if we split a path by the LCA of its endpoints, this can be computed alongside binary-jumping LCA, but that approach can't be easily transferred to subtask 2.

The key observation is that, since XOR is an involution, if we take the XOR of $$$\sum\limits_u^r$$$ and $$$\sum\limits_v^r$$$, nodes that are on both paths will not contribute. By definition, these are exactly the common ancestors of $$$u$$$ and $$$v$$$, and almost all of them are nodes that we wouldn't want to count in the query!

Since the LCA is the only common ancestor of $$$u,v$$$ on the path between them, we can simply return $$$(\sum\limits_u^r\oplus\sum\limits_v^r)\oplus e_{\text{LCA(u,v)}}$$$ for each query. The "prefix sums" of labels can be pre-computed in $$$O(n)$$$ with any graph traversal algorithm, so the overall complexity of this subtask is $$$O(n+b(n)+q\cdot (1+c(n))$$$, where $$$b(n),c(n)$$$ are the pre-computation and query times of our LCA method, respectively.

Subtask 2

Going further along the idea to keep track of paths sourcing from the root, for some arbitrary node $$$x$$$, which prefix sums will have to be updated if it is modified? The answer is exactly every node that has $$$x$$$ as an ancestor. This is the subtree of $$$x$$$ by definition, and subtree modifications are right up the alley of the Euler Tour technique!

If we establish an Euler Tour of the tree, we can effectively modify subtrees in $$$O(\log(n))$$$ with any data structure that supports range modification, such as a lazy propagation segment tree. However, note that when retrieving the answer, we only need to query two individual nodes, so it's sufficient to use a slightly modified version of an iterative segment tree due to Al.Cash, where a node keeps track of every update ever done over its corresponding segment, instead of the value of its corresponding segment; that way, to query a specific index, we can traverse along the path from it to the root of the segment tree, and their XOR is the current value of that index. A more detailed explanation of iterative segment trees and this specific trick can be found here.

(EDIT: it's also plausible to simply use a typical point-update range-query data structure on the difference array. Not sure why I didn't include that in my initial revision.)

Every technique used here can be found in multiple past USACO Gold problems (excluding range modification/point query, but that is a fairly natural extension of vanilla segment trees IMO), hence I consider my solution canonical to the gold division.

Time complexity: $$$O(n+b(n)+q\log(n))$$$.


My C++ code, which comfortably AC's, is shown below. Credits to Al.Cash once again for the segment tree implementation.

Click

Thank you for reading, and remember to praise the cows.

Tags usaco, segment tree, euler tour, lca

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English nsqrtlog 2022-09-14 02:47:08 177
en11 English nsqrtlog 2022-09-07 05:33:35 397
en10 English nsqrtlog 2022-09-07 02:00:34 0 (published)
en9 English nsqrtlog 2022-09-07 01:59:58 50 Tiny change: 'oiler>\n\n\nThank ' -> 'oiler>\n\nThank '
en8 English nsqrtlog 2022-09-07 01:57:22 64
en7 English nsqrtlog 2022-09-07 01:53:46 25
en6 English nsqrtlog 2022-09-07 01:52:48 16 Tiny change: 'b19.html) is not as' -> 'b19.html) to this problem is not as'
en5 English nsqrtlog 2022-09-07 01:52:24 4 Tiny change: '------\n\n[Problem l' -> '------\n\n### [Problem l'
en4 English nsqrtlog 2022-09-07 01:49:32 168
en3 English nsqrtlog 2022-09-07 01:46:30 4736 Tiny change: 'e std;\n\n\n#defin' -> 'e std;\n\n#defin'
en2 English nsqrtlog 2022-09-07 01:20:16 1353 Tiny change: 'ion:**\n\n' -> 'ion:**\n\nfor the sake of convenience, let $\sum\limits_u^v$ denote '
en1 English nsqrtlog 2022-09-06 16:22:47 407 Initial revision (saved to drafts)