Editorial for APIO '08 P3 - DNA - Olympiads Online Judge

Editorial for APIO '08 P3 - DNA

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First, we ignore the templates and only count the number of sequences of form- $k$ $k$ .

Let $A[i][k][\alpha]$ $A [i] [k] [α]$ denote the number of sequences of form- $k$ $k$ of length $i$ $i$ beginning with $\alpha$ $α$ . Note that if the second character $\beta$ $β$ comes before $\alpha$ $α$ , possible sequences of form- $k$ $k$ are those constructed by concatenating $\alpha$ $α$ with form- $(k-1)$ $(k - 1)$ sequences beginning with $\beta$ $β$ . On the other hand, if $\beta$ $β$ is $\alpha$ $α$ or comes after $\alpha$ $α$ , we can concatenate $\alpha$ $α$ with any form- $k$ $k$ sequence.

Thus, we have the following recurrence:

$\displaystyle A[i][k][\alpha] = \sum_{\beta \ge \alpha} A[i-1][k][\beta] + \sum_{\beta < \alpha} A[i-1][k-1][\beta]$ $A [i] [k] [α] = \sum_{β \geq α} A [i - 1] [k] [β] + \sum_{β < α} A [i - 1] [k - 1] [β]$

This idea can be extended to count the number of sequences that also match the templates. Table $A$ $A$ can be computed in time $\mathcal O(MK)$ $O (M K)$ .

Given $A$ $A$ , we can trace back the computation of $A$ $A$ to find the required $R$ $R$ -th gene sequence.

Comments

There are no comments at the moment.