\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{CodeForces 1667C}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 113}
\maketitle

\section*{Problem}
Let $n$ be a positive integer.
We wish to place $m$ \emph{half-queens} on an $n \times n$ chessboard;
these can attack horizontally, vertically, or along the down-right/up-left
diagonal (i.e.\ in six directions), and they attack the cells they occupy.
Determine the smallest $m$ needed so that there exists some placement in which
every cell in the board is attacked by at least one half-queen.

\section*{Video}
\href{https://www.youtube.com/watch?v=UEspJ8Xkmpo&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/UEspJ8Xkmpo}}

\section*{External Link}
\url{https://codeforces.com/problemset/problem/1667/C/}

\newpage

\section*{Solution}
Answer: $\left\lceil \frac{2n-1}{3} \right\rceil$.

For the bound, color green any cell that is not in the same
row or column as one of our $m$ half-queens.
That means we have (at least) an $(n-m) \times (n-m)$ array of green cells,
and each green cell must be in a diagonal of a half-queen.
In this array, observe that the leftmost column and topmost row
of green cells cannot ever lie in the same diagonal (marked X below).
\begin{center}
\begin{asy}
  usepackage("skak");
  size(6cm);
  fill(shift(4,0)*unitsquare, lightgreen);
  fill(shift(6,0)*unitsquare, lightgreen);
  fill(shift(4,2)*unitsquare, lightgreen);
  fill(shift(6,2)*unitsquare, lightgreen);
  fill(shift(4,5)*unitsquare, lightgreen);
  fill(shift(6,5)*unitsquare, lightgreen);

  for (int i=0; i<=7; ++i) {
    draw( (0,i)--(7,i), grey );
    draw( (i,0)--(i,7), grey );
  }
  label("\BlackQueenOnWhite", (0.5,6.5));
  label("\BlackQueenOnWhite", (1.5,3.5));
  label("\BlackQueenOnWhite", (2.5,1.5));
  label("\BlackQueenOnWhite", (3.5,6.5));
  label("\BlackQueenOnWhite", (5.5,6.5));
  label("\BlackQueenOnWhite", (5.5,3.5));
  label("\textsf{\textbf{X}}", (4.5,0.5));
  label("\textsf{\textbf{X}}", (4.5,2.5));
  label("\textsf{\textbf{X}}", (4.5,5.5));
  label("\textsf{\textbf{X}}", (6.5,5.5));
\end{asy}
\end{center}
If the queens did cover all green cells, $2(n-m)-1$ half-queens.
In other words,
\[ m \ge 2(n-m)-1 \implies m \ge \frac{2n-1}{3} \]
which implies the bound.

For the construction, consider first $n \equiv 2 \pmod 3$.
We give a construction for $n=17$ that generalizes ready.
\begin{center}
\begin{asy}
  unitsize(0.7cm);
  usepackage("skak");
  for (int i=0; i<=17; ++i) {
    draw( (0,i)--(17,i), grey );
    draw( (i,0)--(i,17), grey );
  }
  dot((11.5,0.5), blue);
  dot((16.5,5.5), blue);
  draw( (11.5,0.5)--(5.5,6.5), lightblue );
  draw( (16.5,5.5)--(10.5,11.5), lightblue );
  label("\BlackQueenOnWhite", (0.5,12.5));
  label("\BlackQueenOnWhite", (1.5,13.5));
  label("\BlackQueenOnWhite", (2.5,14.5));
  label("\BlackQueenOnWhite", (3.5,15.5));
  label("\BlackQueenOnWhite", (4.5,16.5));
  label("\BlackQueenOnWhite", (5.5, 6.5));
  label("\BlackQueenOnWhite", (6.5, 7.5));
  label("\BlackQueenOnWhite", (7.5, 8.5));
  label("\BlackQueenOnWhite", (8.5, 9.5));
  label("\BlackQueenOnWhite", (9.5, 10.5));
  label("\BlackQueenOnWhite", (10.5,11.5));
  draw(box( (11,0), (17, 6) ), red+1.5);
\end{asy}
\end{center}
When $n \equiv 1 \pmod 3$, use the construction for $(n+1)\times(n+1)$
and delete the rightmost row and bottom column.
When $n \equiv 0 \pmod 3$, add a row and column at the top and left,
and place a new queen in the upper-left hand corner.

\end{document}
