Humans can only achieve $K \le 1.5N$? What a poor showing! This version improves the worst-case guarantee to

$$ \boxed{K\le\left\lfloor\frac{5N-2}{4}\right\rfloor.} $$

In other words, the leading term really drops from $4N/3$ to $5N/4$, rather than merely exploiting $N\le40$ to shave a constant off the old bound. Since the problem has $N\le40$, the largest ratio given by this rounded bound is $47/38$.

The key improvement is: the DFS does not return to the root at the end, and we rotate the cut-off prefix by $90^\circ$ instead of flipping it horizontally as in the previous version.

Construction and proof

As before, build a DFS tree of the input graph, rooted at $r$, with height $H$ measured in edges. Consider two constructions for this same tree and choose the smaller result.

The first construction retains the matching-based strips from the previous version. Match vertices from top to bottom, pairing every unmatched non-leaf vertex with one of its children. All remaining unmatched vertices are DFS leaves and therefore form an independent set. This is also the basic structure used by the existing $1.5N$ construction.

Let $p$ be the number of matched pairs, $\ell$ the number of unmatched leaves, and $D$ the diameter of the tree after deleting those leaves. The exact side length already proved and implemented in the previous version is $K_A=N+p-1-\lfloor D/2\rfloor$: traverse the diameter once and every other tree edge in both directions; handle the first matched pair and the unmatched leaves specially, and add two anti-diagonals for each remaining matched pair.

What we need here is a bound in terms of $H$. If $\ell=0$, then $D\ge H$. If $\ell>0$, deleting the leaves decreases the tree height by at most $1$, so we still have $\ell+D\ge H$. Together with $N=2p+\ell$, this gives $K_A\le\lfloor(3N-H-1)/2\rfloor$. This part of the code is unchanged.

Next, we improve the second construction.

First, construct a rectangle of width $2H$.

We retain the idea of “writing the ancestors into a row, then concatenating rows along a DFS walk.” The particular row definition below additionally ensures that its first entry is the current vertex and its last entry is the root. Both properties will be needed for the rotation and assembly step.

Let the path from the root to $v$ be $p_0=r,p_1,\ldots,p_d=v$. Construct the row $F(v)$ by iterating from $k=H-1$ down to $0$, appending two entries $X,Y$ at each level.

When $k\ge d$, append $(v,v)$. Otherwise, let $a=p_k,b=p_{k+1}$. If $(v,b)$ is an edge but $(v,a)$ is not, set $X=b$; otherwise, set $X=a$. If $(v,a)$ is an edge, set $Y=v$; otherwise, set $Y=a$. Finally, delete the first entry of the entire row and append the root $r$. The row still has length $w=2H$.

This definition has the following properties.

There are no illegal contacts within a row. Within a pair $X,Y$, if $Y=v$, then $X=a$ and the edge $(v,a)$ has been confirmed to exist. Otherwise, $X,Y$ have the same color or form a parent-child pair. For contacts between consecutive pairs, if the preceding pair ends in $v$, the next pair chooses the ancestor one level higher or its child according to whether $v$ is adjacent to that ancestor. Thus, these contacts also produce only legal edges.

The rows of a parent and its child can be placed directly above and below each other. At a shared ancestor level, the two values in the $X$ column belong to the same parent-child pair, while each value in the $Y$ column is either that ancestor or the vertex of its own row. If both rows choose their own vertices, the contact represents a parent-child edge. If only one row chooses its own vertex, the corresponding edge to the ancestor has already been confirmed to exist by the definition. All other positions likewise produce contacts only between a parent and child or between identical colors.

Moreover, the first entry of $F(v)$ is always $v$, its last entry is always $r$, and every entry of $F(r)$ is $r$. Every non-tree edge appears horizontally in the row of its deeper endpoint. There is one more detail that will be crucial later: if the depth of $v$ is less than $H$, then the parent-child edge $(\operatorname{par}(v),v)$ also appears horizontally in $F(v)$, because the corresponding pair $(\operatorname{par}(v),v)$ is not deleted.

Now choose a deepest vertex $t$. Starting at the root, traverse the entire DFS tree, leaving the path from the root to $t$ until last and never backtracking along that path. Thus, every edge outside the path is traversed twice, while every edge on the path is traversed once, giving a sequence $W$ of length $L=2N-1-H$.

Use $F(W_i)$ as the successive rows of the rectangle. This produces a valid $L\times w$ rectangle. Every vertex appears, non-tree edges appear within rows, and tree edges appear in the first column when the walk traverses them.

Rotate the prefix by $90^\circ$ and place it in the bottom-right corner.

Set $K_B=\max(w,\lceil(L+w-1)/2\rceil)$, and let $a=\max(0,L-K_B)$ and $b=L-a$. Split the rectangle into $A$, consisting of the first $a$ rows, and $B$, consisting of the remaining $b$ rows.

Place $B$ unchanged on the left side of the square. Its rightmost column consists entirely of the root $r$. If it has fewer than $K_B$ rows, repeat its last row to fill the remaining rows.

Rotate $A$ counterclockwise by $90^\circ$ and place it in the bottom-right corner. Before rotation, both the first row and the last column of $A$ consist entirely of the root, so after rotation, both its leftmost column and its top row consist entirely of the root. Its leftmost column can therefore overlap the rightmost column of $B$. Fill the unused area above it on the right entirely with the root. If any columns on the right remain unfilled, repeat the last column of the rotated $A$.

The required height is now at most $\max(b,w)$, and the required width is at most $w+a-1$. By the definition of $K_B$, neither exceeds $K_B$. Every new seam passes through a row or column consisting entirely of the root, so no illegal edges are introduced.

Substituting $L=2N-1-H$ and $w=2H$ gives the new size bound:

$K_B=\max(2H,N-1+\lceil H/2\rceil)$.

For example, when $N=40,H=20$, this construction needs only a $49\times49$ square, whereas the previous horizontal-flip construction is bottlenecked by its width of $4H-1$.

We must still check: can cutting the rectangle lose an edge?

The cut removes only one boundary between rows. All contacts within rows are preserved, so no non-tree edges are lost.

For tree edges outside the path from the root to $t$, each appears vertically in the first column at least twice, so it survives the removal of one boundary. On the path from the root to $t$, every edge except the final edge into $t$ has a deeper endpoint of depth less than $H$. We have already proved that these edges also have horizontal representations.

The only remaining concern is the final edge into $t$. It appears between the last two rows of the original rectangle. Since $b=\min(K_B,L)\ge2$, both of those rows are in $B$, so this edge is not cut away.

Thus, the rotation and assembly preserve the complete edge set of the input graph.

Finally, combine the two constructions.

For any DFS tree, we now have

$$ K\le\min\left( \left\lfloor\frac{3N-H-1}{2}\right\rfloor,\, \max\left(2H,N-1+\left\lceil\frac H2\right\rceil\right) \right). $$

When $H< N/2$, choose the second construction. In this case, $2H\le N-1$, and $N-1+\lceil H/2\rceil\le N-1+\lfloor(N+1)/4\rfloor=\lfloor(5N-3)/4\rfloor$.

When $H\ge N/2$, choose the first construction, giving $K\le\lfloor(3N-\lceil N/2\rceil-1)/2\rfloor=\lfloor(5N-2)/4\rfloor$.

Therefore, for every $N\ge2$, we guarantee $K\le\lfloor(5N-2)/4\rfloor$. Handle $N=1$ separately by returning a single cell. Within the problem's range of $N\le40$, the largest ratio given by this rounded bound is $47/38$, attained by the side-length bound of $47$ when $N=38$.

This does not rely on enumerating DFS roots or on any subsequent compression succeeding. The bound already holds for any fixed DFS tree.

Submission: https://qoj.ac/submission/2955547 IOI problems really are easy.