2024 KSA Automata Winter Contest

## Solution

Multiplying $111$ makes any digit a non-prime number. Be careful not to print $000$ or $11$, etc.


2024 KSA Automata Winter Contest - A - Editorial

## Solution

Let’s call strings of the form `KSAKSAK...` as **K string**, strings of the form `SAKSAKS...` as **S string**, and strings of the form `AKSAKSA...` as **A string**. Also, let's group these three together and call it **KSA string**.

Since characters can only be added at the front and the end, it is important to delete some characters from $X$ and create a **KSA string**.

A string created by deleting $0$ or more characters from $X$ is called a subsequence of $X$.

## Subtask 2

You only need to find the length of the longest subsequence of $X$, which is a **K string**.

## Subtask 3

### Method 1

By extending the solution of Subtask 2, you can compute the answer for the longest subsequence of $X$ that corresponds to **K string**, **S string**, and **A string**, respectively.

If the longest length of **K string** is $N$, the answer is $2(|X|-N)$. **S string** or **A string** requires exception handling because several characters must be added in front of them.

### Method 2

You can also find the longest length of **K string** after adding `K` and `KS` in front of $X$.


2024 KSA Automata Winter Contest - B - Editorial

## Subtask 1

Since $K \le 2$, it is best not to buy any speed effect at all. So the answer is $K$.

## Subtask 2

It can be solved with the Brute Force algorithm by trying all $K + 1$ possible choices every second.

## Subtask 4

Let $dp[i][j]$ be the maximum number of carrots that you can have at $i$ seconds when the value of $s$ is $j$.
* If you click once without buying the speed effect, $dp[i + 1][j] = dp[i][j] + j$.
* On the other hand, if you buy the $k$th speed effect, $dp[i + 1][j + B_k] = dp[i][j] - A_k$.

If you calculate the $dp$ array as above, it can be solved in $\mathcal O(NK^2 \cdot \max(B))$.


2024 KSA Automata Winter Contest - C - Editorial

## Subtask 1

If the coefficient matrix is designed to have nonzero determinants for all $N$, it can be solved in $\mathcal O(N^3)$ by Gaussian elimination.

## Subtask 2

If the coefficient matrix is ​​simply an **identity matrix**, it can be solved in $\mathcal O(N^2)$ because only the coefficients are needed, but this case does not satisfy the condition of the coefficients the problem wants. Therefore, you need to think about how to constructively find one character such as using the difference between two expressions.

From now on, you can directly implement calculations through methods such as modulo multiplicative inverse, etc., and since there are various possible methods, the solution by a tester is provided below for example.


* For the $i$-th line(starting from $1$), set the coefficient of $x_{j}$ to $2(i-1)+2n(j-1)$.

* Then for the matrix designed this way, add $1$ to the coefficient $x_i$ in the $i(i \ge 3)$th line. This process makes the elements of the coefficient matrix different from each other.

* You can see that the difference between the results of the first and second lines is $\left(\sum_{i=2}^{n}2x_{i}\right)\bmod 998\,244\,353$. Based on this, you can compute the values ​​of $x_{3}$ to $x_{n}$.

* For the first and second unknowns, you can compute them by eliminating $x_3, x_4, \cdots, x_n$ and solving a simple system of equations.

* When passing the coefficients to the right-hand side(transposition), modulo multiplicative inverse can be used. Since $998\,244\,353$ is a prime number, you can use Fermat's Little Theorem to organize it.
