Optimising your Solutions

(Yu Peng here)

Sometimes, you feel like you should be on the right track in solving a problem, but your solution falls short a little, due to issues like having a suboptimal bound, or having a condition you need but isn't true. At other times, you could just be struggling to find the optimal construction. At such times, it would often do you good to take a step back, and think about how you can optimise your solution. Sometimes you might just need to throw ideas around until you get it right, but often you just need to identify exactly why your solution doesn't work, and focus on optimising specific areas.

I'll talk about my thought process while solving ISL 2019 C8 (which is quite straightforward for its placement) to illustrate how to optimise a solution. I just picked this problem because we are clearly trying to optimise the number of questions we ask, so it is more straightforward in some sense, and since the focus of the question is literally optimisation it might be more illustrative.

Problem

(2019 C8) Alice has a map of Wonderland, a country consisting of $n \geq 2$ towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be “one way” only. Alice has no information on the direction of the roads, but the King of Hearts has offered to help her. She is allowed to ask him a number of questions. For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the direction of the road connecting those two towns.

Alice wants to know whether there is at least one town in Wonderland with at most one outgoing road. Prove that she can always find out by asking at most $4n$ questions.

Spoilers Start Here

First thoughts:

• Firstly, I realised that Alice only needs to know if such a town exists, and not which town exactly it is. For example if $n = 3$ the answer is always yes, and Alice doesn't need to ask any questions. However, since it is probably simpler to determine exactly which town it is directly, we will try to do that instead, and we'll think about this again if we fail.
• Thus to determine whether a particular town satisfies the condition, we need to ask at least $n - 2$ questions concerning that town. This feels expensive so we don't want to do this too often.
• Now notice that if a town has 2 outgoing roads, it is no longer a candidate. We could use this to reduce our search space.

Attempt at an algorithm:

Consider the set of vertices $S$ with at most one known outgoing edge. Pick two of them where the direction of the road between them is still unknown, then ask a question regarding these two towns. If one of these two towns now has 2 known outgoing edges, kick it from the set $S$.

In other words, keep track of the candidates of the town satisfying the desired property, and reduce our search space accordingly.

Note that this algorithm terminates when either $|S| \leq 1$, or if the direction of the roads between every pair of vertices in $S$ is already known. Then, we will ask questions about the roads between every town in $S$ and every town outside $S$, to determine if any of the towns in $S$ satisfy the conditions.

Now, since we will probably be using $\approx n$ queries for each town in $S$, we don't want $S$ to be too big. So how big can $S$ be? Note that every town in $S$ must have at most 1 outgoing road, and there are $\binom{|S|}{2} = \frac{|S|(|S| - 1)}{2}$ roads between towns in $S$, whose direction we already know. So one town in $S$ has at least $\frac{|S| - 1}{2}$ outgoing roads. Thus if $|S| \geq 4$ we have a contradiction.

Hence $|S| \leq 3$. Then in the worst case scenario we need to ask $3(n - 3) = 3n - 9$ more questions to determine if any of the towns in $S$ has at most one outgoing road.

Then how many questions did we use to reach this state? Since we need 2 outgoing edges to kick a town out of $S$, all the towns not in $S$ have at least 2 outgoing edges, which costs 2 queries at least. Plus the 3 edges between the towns in $S$. Hence we use $3 + 3n - 9 + 2(n - 3) = 5n - 12$ queries in the worst case.

Some analysis:

• While we haven't solved the problem, we're quite close - we got to $5n$ queries at least. Let's try to reduce this number. Largely speaking, we have two ways we can do this:
  • Optimise our current algorithm, or find a better one.
  • Find a way to figure out if the answer is yes or no, without finding the exact town if it is yes.
• If we think a little more, by intuition the second option will probably not save us that many queries, so let's stick to the first for now.
• Since we probably still need 2 queries to get rid of candidate towns, we can't really decrease the $2(n - 3)$ component. So let's try to reduce the $3(n - 3)$ part instead.
• If $|S| \leq 2$, we are done.
• Alternatively, if we still have $|S| = 3$, we want as many of the roads between the towns in $S$ and the towns not in $S$ to be queried already, so we do not need the full $3(n - 3)$ queries.
  • However, since we do not really have control over the remaining 3 towns in $S$, this might not be very viable. But maybe it is, so we keep this possibility in mind.
• Also notice that our algorithm was quite arbitrary, in that we just picked random pairs to query, ignoring any structure of the edges we have already found.
• Maybe we can try to query in a more structured way? Let's first try to make it our goal to query in a way that prevents the case $|S| = 3$ in the end.

Let's rethink about the algorithm from the start. Suppose our first query tells us there is a road $1 \rightarrow 2$. Now if we query $1, 3$ and find there is a road $1 \rightarrow 3$, we will discard 1 as a candidate. However, now we are left with the towns $2, 3, \dots, n$, with no information about any roads between them.

Recall that our goal is to make $|S| \leq 2$ in the end. If we keep removing a town and have no information about the remaining towns, we could end up with 3 towns left and none of the roads between the towns are known, so we can still be forced into the $|S| = 3$ case if the roads between the towns form a cycle.

As such, we probably do not want to kill off a vertex immediately. So instead of querying $1,$ something after receiving the info $1 \rightarrow 2$, maybe we can query $2, 3$? Then we will get the info $2 \rightarrow 3$ or $3 \rightarrow 2$, which makes either 3 or 2 have 0 outgoing roads respectively.

Let's just try to continue this idea. Suppose we have made $k - 1$ queries about roads between $1, 2, \dots, k$, and the roads we query form a tree in the vertices (towns) $1, 2, \dots, k$, where all but one town $v$ has exactly one outgoing road, and $v$ has 0 outgoing roads currently. Then we make a query $v, k + 1$, so that now either $v$ or $k + 1$ will be the town with 0 outgoing roads. We keep doing this until we get a tree with vertices $1, 2, \dots, n$. This tree will be rooted at some vertex $v$ which is the town with 0 outgoing roads, and all edges will point from child to parent.

Now let's see if this lets us avoid the $|S| = 3$ case. Instead of trying random algorithms here, we think about how we can avoid the $|S| = 3$ case. So we will suppose we do reach the $|S| = 3$ case, and try to see what it implies.

The roads between the 3 vertices in $S$ must form a cycle. However, if the "highest" vertex in the set in the tree is not $v$, then it has another outgoing road pointing to its parent in the tree, which gives it 2 outgoing roads, so it should not be in the set $S$!

Hence to reach the $S = 3$ case, we must necessarily have $v \in S$! Since we want to avoid this, lets try to get rid of $v$ first.

Hence, let's query $v$ with all the towns which are not already connected to $v$ by a known road, until $v$ has 2 outgoing roads or we know the directions of all the roads connected to $v$. In the second case, since $v$ has only one outgoing road, it is the town we want.

Otherwise, $v$ will be kicked from $S$. Then we can go back to our algorithm of querying random pairs still in $S$, since we can now ensure that at the end $|S| \leq 2$. So we are done!

In summary, when we try to optimise a solution, it helps to identify which part exactly we want to optimise, think about what is stopping us from optimising it, and try to find a way to get around this problem. In this case, we first realised that our initial idea was discarding too much structure of the graph, so we change the algorithm to preserve some structure, then later we identify what happens if we run into the $|S| = 3$ case and take appropriate measures to avoid it.