<center> <h1> week of 12/12 </h1> have a great holiday break! </center> --- ### `📝 notes` happy new year \>.< --- ## contest reflection (USACO Dec 2022) one of the most disappointing performances in the past year... i came about as close as i did on last year's open contest. in fact, this time i was even closer, because i came up with the solution, after the contest. my score on this contest was ~$700$, which was in the top $350$ or so competitors for silver. manifesting for the january contest. :pray: ### problems note that the problems aren't officially released as i write this, im really just working from memory. they should be on: http://www.usaco.org/index.php?page=contests, by the time you read this. #### barn tree this problem was actually pretty tricky, and what killed my promotion. we have a tree, where each node has some amount of hay bales, and we want to make it all equal. we can transfer any amount of available hay bales between any two adjacent nodes. find the minimum operations, and output them. --- the main observation is that we always must have enough to handle deltas of subtrees with negative value. essentially for each subtree, we'll distribute the correct number of bales between the current subtree, and push up any extra to their parent. then, we'll take as much as we can, and give all extra to any "negative" subtrees. #### circular barn one of the most fun problems of this set! i actually know 2/3 people who wrote this ! we're given a circle with $n$ steps and numbers written at each step. Farmer John and Nhoj step together throughout the circle together. At each step, they both perform one move. They either take $1$ away or any prime $p < w$ array, where $w$ is the current number at the step. Farmer John always goes first. Find who wins if they both play optimally. --- this is a play on the classic nim game, the only key observation being that we only care about the number $\pmod 4$, and whether it's prime or not. here's a somewhat formal proof, if you'd like, you can prove it by strong induction also. note that at any $n$, if it's mod $4 \equiv 0$, then our only choice is to remove $1$ or $2$. removing any other prime, would allow the opponent to make it zero on the first step, which is undesired, and not a move that any of them will make, ever. Thus, if it's mod $4$ doesn't equal zero, then we should make it zero, before we give it to our opponent, otherwise, there isn't any winning state for us. We'll go around the circle, checking mods and whether it's prime. We are allotted enough time to do this with eratosthenes' sieve, or a basic $n\sqrt{n}$ prime check. the amount of moves it takes is $\lfloor \frac{n}{4} \rfloor + (n \mod 4 \neq 0)$ time complexity: $\mathcal{O}(n \sqrt n)$. #### range reconstruction given $r_{ij} = \max(a[i \dots j]) - \min(a[i \dots j])$, for all $i, j$. reconstruct a possible array $a$. $n \leq 400$ --- note that we only have two choices per number, either the previous plus $r_{i-1,i}$, or minus $r_{i-1,i}$. we can make it easier by keeping an overall max, min to quickly check the current index, or, like i did, bash it with a segment tree :) time complexity: $\mathcal{O}(n^3 \log n)$ (with some extra constant for construction of segment tree) --- overall this contest was pretty decent, im just really salty for missing problem $1$. /(â•Ĩīšâ•Ĩ)\ --- ## GCD Queries In this problem, we are given a permutation of length $n$, and we can query two indices to get $\gcd(i,j)$. find two $i, j$ such that either $p_i = 0$, or $p_j=0$ in $\leq 2n$ queries.