← All solutions

Problem authors:
Federico Glaudo and Per Austrin
Solved by 0 teams.
Shortest judge solution: 2537 bytes.

This was, in the judges’ opinion, the hardest problem in this set.

Each pyramid position corresponds to a vector in Z³, with the ankh corresponding to 0, the eye to 1, and the ibis to 2. Similarly, each lever corresponds to a vector in Z^3k, with not moving a pyramid corresponding to 0, moving it clockwise corresponding to 1, and counterclockwise — to 2. Moving a lever corresponding to a vector u corresponds to adding the vector representing the lever to the vector representing the pyramids.

So, in the backstory, we had n ≤ 40 lever vectors in Z^3k. We took all possible 2ⁿ sums of some of those vectors, and in each case got some vector describing the positions of all the n pyramids; call those vectors (s_i)_i=1^2ⁿ. We are asked to find some possible sequence of vectors (u_j)_j=1ⁿ that would generate the observed s_i. This is a hard problem, and we will solve it in parts.

Part 1: k = 1 First, let us make an observation about the problem in dimension 1. In this case, (u_j) is just a multiset of numbers in Z³, and similarly (s_i) — so (s_i) is just a zeroes, b ones, and c twos. Let’s see what are the effects on the multiset (s_i) of appending a single number to (u_j). If we append a zero, then a, b, and c get multiplied by two. If we append a 1, then a, b, c := a + c, b + a, c + b (and the results of appending a 2 are similar). If we first append all the 1s and 2s, we can see that the multiplicities (a, b, c) are always either {x, x + 1, x + 1} or {x, x, x + 1}, in some order. The important part is that at least one of the numbers a, b, c is always odd if we only add levers corresponding to one and two. So, the number of levers corresponding to zero is the largest power of two dividing all of a, b, c.

Part 2: Summing over a linear subspace Now, let’s try to use the reasoning for k = 1 in the more general case. Consider any vector x ∈ Z^3k, and take the scalar product of everything with that vector. More precisely, consider the set of numbers (u_j · x)_j=1ⁿ; then the multiset of all possible sums of those numbers is (s_i · x)_i=1^2ⁿ, because scalar products commute with addition. So, from Part 1, we can find out how many u_js satisfy u_j · x = 0, for any x. Let us denote f(x) = |{j : u_j · x = 0}|. There are only 3^k possible x’s, and up to 3^k possible values of s_i, so we can calculate f(x) for all possible x in O(k 3^2k), which is easily fast enough.

This means that for any linear subspace of dimension k − 1, we can find out how many of the u_js are in that subspace. We can use this in a number of ways to narrow it down.

For example, consider an arbitrary-dimension subspace H, and G = H^⊥, and look at the ∑_x∈H f(x). This is

∑x∈H f(x) = ∑j=1n ∑x∈H [x ⊥ uj] = ∑x∈H ∑j=1n [x ⊥ uj] = ∑j=1n |H ∩ uj⊥|,

which is the size of the intersection of H and u_j^⊥, summed over j. How much does a single u_j contribute to that sum? If u_j ∈ G, then u_j is orthogonal to every vector in H, and so it contributes |H|. Otherwise, the intersection of H and u_j^⊥ will be a subspace of dimension one smaller, and so u_j will contribute |H|/3. So, just by counting, for any G we can calculate how many u_js are in G — it is

( (1/2) (3/|G⊥|) ∑x∈G⊥ f(x) − n )

Having previously calculated f(x) for any x, we can calculate the value above in O(|G⊥|) for any G.

Part 3: Flipping signs First, take G = {0} — the zero-dimensional subspace. We find out how many all-zero levers are in the set {u_j}. Then, take G = {0, x, −x} for any x. We find how many of the u_js are in G — and, since we already know how many u_js are zero, how many are in the set {x, −x} for any x ∈ Z^3k. Calculating this for all (3^k − 1)/2 values of x takes O(3^2k). So, we know all the u_j up to the selection of signs; we now need one last idea.

We potentially have up to 2ⁿ possibilities to assign the signs to check (possibly less, if we had any zero vectors, or if any group of {x, −x} is larger than one element). We need to find one that works. Notice that if we calculate the sums s_i for some u₁, . . ., u_n, then the sums s_i′ for u₁, . . ., u_n−1, −u_n are going to be the multiset {s_i − u_n} (the bijection is that we map any set of indices containing n to the same set without n, and vice versa). So, we do the following:

1. We pick any set of signs for u_i, and calculate the multiset s_i.
2. While doing this, for any element of the multiset s_i also remember any one way of reaching it as a sum of some u_is.
3. For any vector v in Z^3k, look at the multiset {s_i − v}, and check if it is equal to the multiset given on the input.
4. For any v that worked, see if it can be represented as a sum of some u_is, and how (this is what we stored the ways of reaching elements for in point 2).
5. If we do find one, then we flip the signs of the u_is that are used to reach v, leave the rest alone, and output that as a solution.
6. If none of the v’s that lead to the input multiset can be represented as a sum of some u_is, output impossible.

You can also see this paper or this paper for a detailed examination of a more generic problem.