Conditions for solving a Circulant-plus-diagonal system

Let $\matrix{C}$ be a $n \times n $ circulant matrix with generating vector $\vec{c} = \{0 , c_1, c_2, \cdots, c_k, 0,\cdots, 0\} $ where $k \le n-1$. Let $\matrix{A}$ be a diagonal matrix with entries $a_i \ge 1$, $i =0\cdots n-1$. Let $\vec{s}$ be a "binary" vector with entries $s_i = \pm 1$, $i =0\cdots n-1$.

Regard the equation $$ \matrix{C} \vec{s} = \matrix{A} \vec{s} $$

Fix $\vec{s}$. Can the equation be solved by assigning $\matrix{C}$ and $\matrix{A}$? The aim is to keep $k$ as small as possible: for which $k$ (as a fraction of $n$) can this be achieved?

One can get a first hold on that question by restricting the situation even further to $a_i \color{red}{=} 1$, $i =0\cdots n-1$. Then $$ \matrix{D} \vec{s} = (\matrix{C} - \matrix{A})\vec{s} = \vec{0} $$ and $ \matrix{D} = \matrix{C} - \matrix{A} $ is a circulant. Applying a discrete fourier transformation (DFT), let DFT($ \vec{s}$) = $\vec{x}$ and we obtain $$ \matrix{\Lambda_D} \vec{x} = \vec{0} $$ where $\matrix{\Lambda_D}$ is the diagonal matrix of the eigenvalues of the circulant $\matrix{D} $. Assuming that the components of $\vec{x}$ are nonzero, this results in the requirements $\lambda_i = 0$ , $i =0\cdots n-1$. This is equivalent to DFT($ \vec{d}$) = $\vec{0}$ which however is only possible for $ \vec{d}$ = $\vec{0}$. Hence a solution is impossible. (Note that $c_0 = 0$, hence $d_0 = - a_0 = -1$.)

The situation is slightly different if one or more of the components of $\vec{x}$ are zero. For example, when exactly one component is zero, namely $x_0 = 0$, this means that $ \vec{s}$ has zero mean. Then, this results in the requirements $\lambda_i = 0$ , $i =\color{red}{1}\cdots n-1$. This can be generated by assigning $d_i = -1$, $i =0\cdots n-1$. Hence $c_i = -1$ , $i =\color{red}{1}\cdots n-1$. Hence a solution is possible for $k = n-1$.

Now drop the strict requirement $a_i = 1$, $i =0\cdots n-1$. Then we have a situation where $\matrix{D} $ is a Circulant-plus-diagonal matrix which is established in the literature. However, the discussion there focusses on fixed $\matrix{D} $ and finding a solution $\vec{s} $. Here, the question is posed the other way around, and I didn't find approaches for that.

In the limit of large $n$, there is numerical evidence quoted in the literature that a solution exists, averaged over all binary choices of $\vec{s} $, in almost all cases, for $n \le 1.7 k$.

Any ideas / references? Either for fixed $\vec{s} $, or in the limit of large $n$, averaged over all binary choices of $\vec{s} $?