Oct 18, 2023

Hints 8

A: Apple Market

This problem might seem difficult at the first glance, since connect an edge from every customer to every stand results in \( knm\ge 10^8 \) edges.

Instead, consider adding some helper nodes \( s_{i, j, a, b} \) indicating the whole stand range from \( (i, j) \) to \( (i+2^a, j+2^b) \).

• We only need to connect one customer to four helper nodes.
• We only need to connect one large helper node to two smaller helper nodes (or to the destination).

B: Dots and Boxes

Try to show that the graph is bipartite.

C: Amazing Adventures

Let us start from the middle point. We then need to find two non-intersecting paths to the start and the end.