2017 South Pacific ANZAC Rounds

ANZAC Round 3

Back to List of ANZAC Rounds


Contest Stuff: Problem Statements


Problem A: Atrium (Geometry)

The input is the area of the square room. Take the square root and multiply by 4 to get the perimeter.

Take care with the size of the input: up to $10^{18}$, so 64-bit integer is required. Take care with output precision - C++ needs to set the precision explicitly.


Problem B: Candle Box (Math, Arithmetic progression)

Consider two finite arithmetic progressions:

Say that Theo placed $X$ of his candles in Rita's box. Given $R + X$, $T - X$, and $D$ (difference between the ages of Rita and Theo), find $X$.

If you somehow knew how old Rita is, then we can calculate how old Theo is ($D$ years younger). Iteratively search through all possible ages of Rita, and for each one, check if $R+T = (R+X) + (T-X)$. The maximum age of Rita is roughly $\frac{\sqrt{R}}{2}$, so it should not take long to find.


Problem C: Careful Ascent (Math, Trigonometry)

Given the target's coordinates $(x, y)$ and descriptions of shields and taking into account the interference of the shields, what is the right horizontal velocity for hitting the target?

  1. Easy, if there are no shields: $v_{\text{hor}} = \cot(\alpha) = x/y$.
  2. Replace every shield $(l_i, h_i, f_i )$ by a layer with effective thickness $t_{\text{eff}_i} = f_i \cdot (u_i - l_i )$ and calculate $y_{\text{eff}}$.
  3. $v_{\text{hor}} = \cot(\alpha) = x/{y_{\text{eff}}}$

Alternatively:

  1. For given $v_{hor}$, simulate the flight.
  2. Adjust $v_{hor}$ depending on whether Mal is too far to the right or too far to the left from the Firefly.
  3. Use binary search to reach the needed precision fast enough.


Problem D: Performance Review (Graph Theory, Trees, Data Structures)

Given a rooted tree with $N$ nodes, where each node has a (key, value) pair, find for each node $x$ the sum of values in its children whose key is smaller than $x$'s key.

Naive approach: Process each node's children and sum the values. Complexity is $O(N^2)$ -- too slow.

Several valid approaches:

  • Post-order traversal of the tree + Fenwick Tree
  • Pre-order traversal + Segment Tree
  • Process nodes from the deepest leaves to the root and merge (key,value) pairs


Problem E: Flowery Trails (Graph Theory, Shortest Paths)

Given an undirected multigraph, determine the edges that are part of a shortest path between vertices $0$ (source, $s$) and $P-1$ (target, $t$).

#Flowers = Twice the length of edges that occur in the shortest paths from $s$ to $t$.

  • Use Dijkstra's algorithm to find compute the distance from $s$ to every other vertex.
  • Do the same thing to find the distance from $t$ to every other vertex.
  • An edge $(u,v)$ is on a shortest path from $s$ to $t$ if $\text{dist}(s,t) = \text{dist}(s,u) + \text{length}(u,v) + \text{dist}(v,t)$ (or $\text{dist}(s,t) = \text{dist}(s,v) + \text{length}(u,v)$ + \text{dist}(u,t))

Complexity: $O(E \log E)$


Problem F: Free Weights

Given two rows of weights, find the largest weight that must be moved so that all weights can be put into pairs.

  1. Decision problem: can we solve it by moving all weights smaller than or equal to $M$?
    • Remove all weights that are smaller than $M$.
    • For every $i$, $W_{2i}$ should be equal to $W_{2i+1}$.
    • Otherwise, it isn't possible.
  2. So binary search on the maximum weight moved.

Possible pitfalls:

  • Not checking for weights split across rows.
  • Trying to put the weights into ascending order.


Problem G: Pascal's Hyper-Pyramids (Maths, Dynamic Programming)

Calculate the numbers at the base of Pascal's "triangle" generalized to higher-dimensions.

General recurrence for dimension $D$:

To compute $C(x_1, ... , x_D)$: If any $x_i = 0$, then $C(x_1, ... , x_D) = 1$. Otherwise, it is $C(x_1 - 1, x_2, \dots , x_D) + C(x_1, x_2 - 1, \dots , x_D) + \dots + C(x_1, x_2, \dots , x_D - 1)$.

Base of the hyper-pyramid of height $H$: $\{C(x_1, ... , x_D) | 0 \leq x_i < H \text{ and } \sum_i x_i = H - 1\}$.

Implementation:

  • Use 64-bit integer arithmetic
  • Recursively generate vectors of size $D$ that sum $H - 1$
  • Calculate recurrence using memoization
  • Collect results into a set
  • Choice of memo and set data structures is not critical

However, the above is not enough! we need to exploit symmetry:

  • $C(x_1, ... , x_D) = C(\rho \circ (x_1, ... ; x_D))$ for any permutation $\rho$
  • Normalize memo keys, e.g., ascending order (sort vectors before lookup/insert)
  • Generate only ascending vectors $x_1 \leq \dots \leq x_D$ that sum to $H - 1$

Alternative approach (for the more math-savvy):

  • Numbers in Pascal's hyper-pyramids are the multinomial coeffcients
  • Compute directly using the closed factorials formula: $C(x_1, x2; ... , x_D) = \binom{H-1}{x_1 ; x_2 ; \cdots ; x_D} = \frac{(H - 1)! }{ x_1! x_2! ... x_D!}$
  • No recurrence, no memoization
  • Caveat: requires larger precision (BigIntegers) or careful implementation to avoid overflow with 64-bits.


Problem H: Hamiltonian Hypercube

Given two code-words a and b of an n-bit Gray Code, compute the number of code-words between them.

Note that the output does not depend on n. Reduce the problem to determining the index of $a$ in the Gray-Code. $\text{dist}(a, b) = \text{ind}(b) - \text{ind}(a) - 1$.

The index can be computed in the following way. If $x$ starts with a 0 (say it is 0y), then $\text{ind}(x) = \text{ind}(y)$. If $x$ starts with a 1 (say it is 1z), then $\text{ind}(x) = 2^{\text{len}(x)} - \text{ind}(y) - 1$.


Problem I: GREAT + SWERC = PORTO (Backtracking + pruning or Brute Force Enumeration)

Given a word addition problem, e.g. GREAT + SWERC = PORTO, compute the number of solutions. i.e., how many distinct digit assignments yield a correct sum.

Backtracking + pruning:

  • The more letters and words, the easier it is to prune an exhaustive search
  • Process columns from right to left and prune bad solutions earlier
  • But this is unnecessary ...

Brute force enumeration:

  • There are at most 10 distinct letters.
  • 10! = 3 628 800 candidate solutions - Try them all!


Problem J: Book Club (Graph Theory, Maximum Bipartite Matching)

Given a directed graph where each edge $(A, B)$ means that person $A$ likes the book person $B$ has, is it possible for the group of people to exchange books, so that each one receives a book (s)he likes?

  • Bipartite graph: if X likes Y 's book.
  • The answer is YES iff there is a perfect matching.
  • Either the Hopcroft-Karp algorithm or any maximum flow algorithm was accepted.

I saw that one team asked for a proof of this solution. What is written here is a brief write-up. Not even close to rigorous, but unfortunately, the proof is so straightforward, it is hard to make it more rigorous without getting really boring. There is a bijection between the set of perfect matchings and the set of permutations: Let $G$ be a bipartite graph; $L = \ell_1, \ell_2 , \dots, \ell_n$ and $R = r_1, r_2, \dots, r_n$ are the two halves of the bipartite graph. Imagine you have a perfect matching P, we will create the permutation $\rho$. If $\ell_i$ is matched with $r_j$ in $P$, then send $i$ to $j$ in the permutation (i.e., $\rho(i) = j$). Creating a perfect matching from a permutation is the same, but opposite. Now that we know that, cycles in the permutation correspond to 'cycles' as they described in the problem statement. This tells us all we need to know--that is, we know that any perfect matching always has 'cycles' since the corresponding permutation has cycles.


Problem K: Balls and Needles (Graph Theory, cycle detection)

Given a set of needles / line segments $((x_1, y_1, z1), (x_2, y_2, z_2))$ in 3D: Is there a true closed chain, i.e., a cycle in the (simple) graph whose edges are the line segments? Is there a floor closed chain, i.e., a cycle in the (simple) graph whose edges are the line segment projections $((x_1, y_1), (x_2, y_2))$?

  • Sculpture with $K$ needles / line segments
  • Graph for 3D:
    • $|E| = K, |V| \leq 2K$
    • Map each point $(x, y, z)$ to an integer $0, 1, 2, \dots$
  • Graph for 2D:
    • $|E| \leq K, |V| \leq 2K$
    • Map each point $(x, y)$ to an integer $0, 1, 2, \dots$.
    • Leave self-loops out and do not add repeated edges.
  • Cycle detection: DFS or Union Find.
  • Time and space complexity: $O(K)$


Problem L: Promotions (Graph Theory)

Given a directed acyclic graph where each edge $(x,y)$ means that employee y may be promoted only if employee $x$ is promoted and a number $N$ of promotions (which is an endpoint of $[A,B]$): (a) How many employees will certainly be promoted? (b) How many employees have no possibility of being promoted?

DAG with $V$ nodes and $E$ edges; $N$ promotions. Employee $x$ has no possibility of being promoted if the number of predecessors of $x$ (excluding $x$) is at least $N$: $\text{Pred}(x) \geq N$.

Employee $x$ will certainly be promoted if the number of successors of $x$ (excluding $x$) is at least $V - N$: $\text{Succ}(x) \geq V - N$.

For every employee $x$, compute $\text{Pred}(x)$ and $\text{Succ}(x)$. Any $O(V^2 + VE)$ time algorithm (BFS/DFS/TS) was accepted.