1. Hard to link a nonexistent page (the contest page was nonexistent at the time of posting). However, you can now find it here.
2. I don't see why unofficial competitors would be allowed to not follow part of the rules.

What was it previously?

I'm not sure if it's described anywhere, but it's pretty easy to determine experimentally (by just looking at past USACO results) what the formula is. If you got $$$\frac{a}{x}$$$ test cases on problem 1, $$$\frac{b}{y}$$$ test cases on problem 2, and $$$\frac{c}{z}$$$ test cases on problem 3, your score is $$$1000(\frac{a}{x} + \frac{b}{y} + \frac{c}{z})/3$$$.

Yes, it's over (you can't access the contest page on the website anymore).

Problem recap: For a graph $$$G$$$, define $$$f_G(a, b)$$$ the boolean value of whether there is a walk from vertex $$$1$$$ to vertex $$$a$$$ using exactly $$$b$$$ edges. Given a connected graph $$$G$$$ (possibly with self-loops), we want to find a graph $$$G'$$$ (possibly with self loops but no parallel edges) with the same set of vertices which satisfies $$$f_G(a, b) = f_{G'}(a, b)$$$ for all $$$a$$$ and $$$b$$$. Problem 2 asks to minimize the number of edges in $$$G'$$$, and problem 3 asks to count the number of such graphs $$$G'$$$.

First, note that the graph is undirected. This mean that we can always walk back and forth along an edge to increase our distance by 2, so $$$f_G(a, b) \implies f_G(a, b+2)$$$. Thus, for each vertex $$$a$$$, we actually only care about the shortest distance to reach it with either parity. We will represent each vertex $$$a$$$ as an ordered pair $$$(x, y)$$$ where $$$x$$$ is the minimum distance from vertex $$$1$$$ to vertex $$$a$$$, and $$$y$$$ is the minimum distance from vertex $$$1$$$ to vertex $$$a$$$ of the opposite parity as $$$x$$$. Note that $$$x < y$$$, and $$$y$$$ may be equal to $$$\infty$$$. All we need are for these ordered pairs to match up between $$$G$$$ and $$$G'$$$.

Let's consider the problem where we're given a collection of these ordered pairs, and we want to add some edges to make the ordered pairs actually reflect the shortest paths. Note that a vertex has shortest path $$$d$$$ iff there is no edge to a vertex with shortest-path less than $$$d-1$$$, and for each vertex, there is at least one edge to a vertex with shortest path exactly $$$d-1$$$. Let's formalize this.

Because the graph is undirected, we can only add an edge between two vertices $$$v_1=(x_1, y_1)$$$ and $$$v_2=(x_2, y_2)$$$ if $$$x_1$$$ and $$$x_2$$$ are close, and $$$y_1$$$ and $$$y_2$$$ are close; otherwise the edge will form a shorter path than is allowed. More precisely, we can derive these constraints:

• $$$\lvert x_1 - x_2 \rvert \le 1$$$.
• If $$$\lvert x_1 - x_2 \rvert = 1$$$, then $$$y_1 = y_2 = \infty$$$ or $$$\lvert y_1 - y_2 \rvert = 1$$$. (Note that $$$x_1$$$ and $$$x_2$$$ are opposite parity, so the by definition of $$$y$$$, $$$y_1$$$ and $$$y_2$$$ are also opposite parity.)
• If $$$x_1 = x_2$$$, then $$$y_1 = y_2 = x_1+1$$$.

Therefore, we can have the following types of edges:

1. $$$(x-1, \infty) \leftrightarrow (x, \infty)$$$.
2. $$$(x-1, y-1) \leftrightarrow (x, y)$$$.
3. $$$(x-1, y) \leftrightarrow (x, y-1)$$$.
4. $$$(x, y=x+1) \leftrightarrow (x, y=x+1)$$$.

A graph is valid iff it uses only edges of the above form, and each vertex $$$(x,y)$$$ has at least one edge to a vertex with value $$$x-1$$$ and at least one edge to a vertex with value $$$y-1$$$ (or $$$y = \infty$$$).

Note that some $$$y = \infty$$$ iff the graph is bipartite, in which case all of the $$$y$$$ are $$$\infty$$$. This case is easy to solve for both parts, we can only add edges when $$$\lvert x_1 - x_2 \rvert = 1$$$, and each vertex must have at least one edge to a smaller $$$x$$$.

Otherwise, $$$y \ne \infty$$$, and we can think about this as a collection of $$$2n$$$ constraints, one for each $$$x$$$ and one for each $$$y$$$. Each edge satisfies 2 of these constraints: type 2 edges satisfy both constraints for the right-side vertex, type 3 edges satisfy the $$$y$$$ constraint on the left vertex and the $$$x$$$ constraint on the right vertex, and type 4 edges satisfy the $$$y$$$ constraint on both vertices. Thus, we can think of this as an edge-cover problem in the graph of constraints. The graph of constraints is very well structured: all edges connect two constraints whose vertices satisfy $$$x_1 + y_1 = x_2 + y_2$$$, and within a group of equal $$$x+y$$$, the graph essentially forms "layers", with these vertices and edges. For $$$x+y = 2g+1$$$, the group looks like

• Type 4 edges: Complete graph: Connect all pairs of $$$y$$$-constraints of vertices $$$(g,g+1)$$$, including self-loops.
• $$$y$$$-constraints of vertices $$$(g,g+1)$$$
• Type 2 edges: Pointwise connected with multiplicity: Connect each vertex's $$$y$$$-constraint to its $$$x$$$-constraint, with one copy of the edge for each vertex of the form $$$(g-1,g)$$$.
• $$$x$$$-constraints of vertices $$$(g,g+1)$$$
• Type 3 edges: Complete bipartite graph: Connect each $$$x$$$-constraint of vertices $$$(g,g+1)$$$ to each $$$y$$$-constraint of vertices $$$(g-1,g+2)$$$.
• $$$y$$$-constraints of vertices $$$(g-1,g+2)$$$
• Type 2 edges: Pointwise connected with multiplicity: Connect each vertex's $$$y$$$-constraint to its $$$x$$$-constraint, with one copy of the edge for each vertex of the form $$$(g-2,g+1)$$$.
• $$$x$$$-constraints of vertices $$$(g-1,g+2)$$$
• Type 3 edges: Complete bipartite graph: Connect each $$$x$$$-constraint of vertices $$$(g-1,g+2)$$$ to each $$$y$$$-constraint of vertices $$$(g-2,g+3)$$$.
• $$$\vdots$$$

Then, we can solve problem 2 using a greedy algorithm (going backwards through this chain), and we can solve problem 3 using a $$$O(n)$$$-state $$$O(n^2)$$$-transition DP based on the number of unfulfilled constraints at each level (this requires some combinatorics/PIE).

One edge case to handle is that the root's x-constraint is automatically satisfied.

Here is my solution to problem 2:

Firstly remove all ranges of equal elements and replace them by one of that element. For example if $$$2,2,2$$$ is a range in the array then just replace by $$$2$$$ because we can always include the other $$$2's$$$ while painting. Let $$$dp[i][j]$$$ denote the minimum number of moves to paint the array starting from $$$j$$$ to $$$i$$$. Notice that if the last element or the first element of this range is equal then just paint the array from either $$$j$$$ to $$$i-1$$$ or $$$j+1$$$ to $$$i$$$ since in the move we paint the $$$i^{\text{th}}$$$ element we can paint the $$$j^{\text{th}}$$$ element too. Otherwise we iterate over all values $$$j \leq mid \leq i-1$$$ and take the min of $$$dp[mid][j] + dp[i][mid+1]$$$ since we can always find a mid where it is optimal to split the array and solve the problem seperately for them. Time complexity for calculation the DP is $$$O(n^3)$$$. Here's my implementation during the contest

Problem 1:

Moves become

• divide all piles by $$$k$$$
• remove $$$1$$$ stone from $$$1$$$ pile

You lose if the number $$$f(m)$$$ of piles with $$$m$$$ stones is always even.

Try all $$$k$$$ and check if you can reach a losing configuration for the opponent: you can if all $$$f(m)$$$ are even except either $$$f(1)$$$ (you can fix it in $$$f(1)$$$ ways) or both $$$f(x)$$$ and $$$f(x+1)$$$ (you can fix it in $$$f(x+1)$$$ ways).

What's your hashing solution to problem 1, if you don't mind sharing?

If you can get the answer for a prefix of a diagonal, you can use a technique similar to prefix sums. Now let's work on finding the answer to a prefix.

Like Tomg mentioned, it's a fractal. First, if $$$x+y$$$ is odd for the prefix $$$(x, y)$$$, the answer is always $$$0$$$. I imagined the fractal as a bunch of "blocks," each with a certain "level," so a block of level $$$i$$$ is made up of 9 blocks of level $$$i-1$$$. Now imagine you had some function to get the answer for some prefix of a diagonal if the prefix started on the edge of some block (call this $$$f(x)$$$ where $$$x$$$ is the distance from the origin). Then to answer some query, the diagonal intersects the sides of at most 2 blocks of level $$$i-1$$$ (for which you can use $$$f(x)$$$ to find the answer), and is in the middle of exactly one block of level $$$i-1$$$. Now you can recurse on the block that it's in the middle of. The total number of recursion levels is $$$log_3(10^{18})$$$ because that's the highest level that exists that has coordinates $$$\leq 10^{18}$$$ (because each time the size of the block's edge triples). But there's still a problem, how do you find $$$f(x)$$$?

At this point, I just printed out some of the small (non-zero) values, noticed they were powers of $$$3$$$, and just put the $$$log_3(x)$$$ for small numbers of $$$x$$$ into oeis, and I found this sequence. It seemed likely because the description seemed very related to the problem at hand, so I just went with it. I used this definition a(n) = a(floor(n/3)) + (n mod 3) mod 2, as it would solve for what I needed easily. If anyone knows how to prove this formula, lmk. Sorry for the not very clean solution.

The final complexity is $$$O(q*log^2(10^{18}))$$$ which should be fast enough (I stress tested this against a slow solution but I'm not in gold, so I couldn't submit in contest).

You can simply do a DP over the ternary representation to count all $$$dx$$$ such that $$$x+dx$$$ and $$$y+dx$$$ both have same parity at every position in their representation (you just need to maintain the carry on both x and y, as well whether currently $$$dx$$$ is bigger than $$$d$$$).

wow that's insane...orz vrooooom