C2411 - Letter Count

If you tried to use getline(cin, s) and failed to get the next line of input, it is because you need to read in the \n at the end of the first line first. You can use cin.get() or cin.ignore() after reading the character $C$.

C2412 - Mode

As a starting point, create a counting array to count the number of occurrences of each number.

C2413 - Circular Shift

Subtask 2

Let $n = |S|$ be the length of $S$. Then $n$ shifts, or a multiple of $n$ shifts, simply result in the original string $S$. So we can take $k \mod n$ shifts instead.

Now, with $k < n$, performing the $k$ shifts one by one is still inefficient. We can recognize that the resulting string is just $s_k \cdots s_n s_1 \cdots s_{k-1}$.

C2414 - Matrix Multiplication

The mathematical statement of this task is complicated - it is typically content covered in Form 5 if you study M2. However, it actually boils down to reading the statement carefully and implementing the operation as stated.

C2415 - Susequences

Subtask 1

We can implement a brute force solution: loop over the string with indices $i$, $j$ and $k$, where $i < j < k$. If $s_i$ is s, $s_j$ is u and $s_k$ is s, then we have found a sus subsequence.

Subtask 2

For each u in $S$, the number of desired subseqeunces containing this u is the product of the number of s on its left hand side and the number of s on its right hand side. We can count the s on each side for each u in $S$.

Subtask 3

Solving this subtask requires some form of precomputation. One way is to precompute the number of s on each prefix and suffix of $S$ and apply the idea in Subtask 2.

Let us first define the indicator function $I(\cdot)$. It gives the value 1 when the expression written inside is true, otherwise it gives the value 0.

Let $C[i]$ be the number of s in $s_1 \cdots s_i$ and $D[i]$ be the number of s in $s_i \cdots s_n$. Then we can compute $C$ and $D$ efficiently: $$\begin{align*} C[i] &= \begin{cases} I(s_0 = \texttt{s}) & \text{ for } i = 1 \\ C[i - 1] + I(s_i = \texttt{s}) & \text{ for } i = 2, 3, \cdots, n - 1 \end{cases} \\ D[i] &= \begin{cases} I(s_n = \texttt{s}) & \text{ for } i = n \\ D[i + 1] + I(s_i = \texttt{s}) & \text{ for } i = n - 1, n - 2, \cdots, 1 \end{cases} \end{align*}$$ so $I(s_i = \texttt{s})$ gives 1 when $s_i$ is s and 0 otherwise.

Then, for $i = 2, 3, \cdots, n - 1$, if $s_i$ is u, we can add $C[i - 1] \cdot D[i + 1]$ to the answer.