Hey Codeforces!↵
↵
The [BioCode 2024](https://tjbioinfo.netlify.app/biocode/) contest concluded yesterday. Thanks to the 26 teams who participated!↵
↵
We (the organizers) thought it would be great to share this with the Codeforces community. You can now access the problemset in the Gym [here](https://mirror.codeforces.com/gym/105123). This competition was tailored specifically for participants around the Div2/3/4 level, and the authors are [user:avnithv,2024-04-21], [user:AryGad11,2024-04-21], and [user:DanielQiu,2024-04-21]. ↵
↵
We hope you enjoy the problems, and please let us know in the comments if you have any questions. Best of luck!↵
↵
**UPD**: Added Solution Sketches for A-F↵
↵
<spoiler summary="A. Mitosis">↵
Just print YES if $a+b=c$ and NO otherwise.↵
</spoiler>↵
↵
↵
<spoiler summary="B. Neural Network">↵
The answer is the sum of $a_i \cdot a_{i+1}$ over all $1 \leq i < n$, which can be computed in a single for loop.↵
</spoiler>↵
↵
↵
<spoiler summary="C. Flipped DNA">↵
In this scenario, 'A' and 'T' are equivalent and 'C' and 'G' are equivalent. So we can replace all 'T' with 'A' and all 'G' with 'C' and check if the resulting strings are equal.↵
</spoiler>↵
↵
↵
<spoiler summary="D1. Predator or Prey (Easy Version)">↵
Let's loop over all pairs of animals and determine whether or not they have a predator-prey relationship and update the respective counts. This can be checked by seeing if $a \leq \lvert p_i - p_j \rvert < b$.↵
</spoiler>↵
↵
↵
<spoiler summary="D2. Predator or Prey (Hard Version)">↵
The previous version is too hard for these constraints. We need a faster way to find the number of predators and prey an animal has. Notice that for animal $i$, its predators will be in the range $[p_i + a, p_i + b)$, and its prey will be in the range $(p_i - b, p_i - a]$. If we sort the array of predator factors, we can binary search for the indexes of the endpoints of these ranges and determine the number of animals in that range. Thus, we can solve the problem in $O(n \log n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="E. Powerhouse of the Cell?">↵
We can notice that it is always better to do less costly tasks before more costly tasks if we consider both. Let's say we know the optimal solution for $k=i$. When we consider the $i+1$-th element, there are three cases:↵
↵
- We can add it to our solution without running out of ATP, which would clearly be optimal if possible.↵
- We can use it to replace a task in our solution. In this case, we would obviously want to replace the most costly task.↵
- We do not add it to our solution. In this case, it would have to be worse than the most costly element in our solution, since otherwise option $2$ would be better.↵
↵
So we need to be able to add an element to our solution and find/remove the element with the maximum cost. This sounds like a job for a priority queue.↵
</spoiler>↵
↵
↵
<spoiler summary="F. Wildfires">↵
First, we can show that if a wildfire of strength $k$ is sufficient, so is a wildfire of strength $k+1$ (try proving this yourself!). So for each forest, we can separately compute the minimum strength needed to burn all of the forests to the left and to the right and take the maximum of those values. ↵
↵
For now, let's only consider the left case; the other case is symmetric. If the minimum strength needed for forest $i$ is $k$, then the minimum strength for forest $i+1$ is $k-1$ if $t_i \geq k$ and $k+1$ otherwise. So we can compute the answer in two linear sweeps, one for the forests to the left and one for the forests to the right.↵
</spoiler>↵
↵
<spoiler summary="G. Cut and Splice">↵
You might notice that the statement implicitly assumes that the number of linear strands is well-defined regardless of how *LOPITAL* cuts and splices. Understanding why this is true is the key to the solution.↵
↵
**Claim 1**: The number of new linear strands formed from a cut is equal to the number of cuts made (i.e. consecutive occurrences of $x$ and $y$). ↵
Clearly, this is true when we cut an already linear strand. The first cut we make to a circular strand converts it to linear and increases the answer by $1$.↵
↵
**Claim 2**: During a splice, the number of linear strands reduces by $min(a_{1x}, a_{2y})$ where the $a_{1i}$ is the number of linear strands that begin with $i$ and $a_{2j}$ is the number of linear strands that end with $j$.↵
If the $x$-$y$ pair that we splice are the beginning and end of the same strand, then the number of linear strands decreases by $1$. In the other case, we splice two different linear strands, reducing the number of linear strands by $1$.↵
↵
Since there are only $4$ possibilities, we can update the values $a_{ij}$ and the number of consecutive occurrences of two characters in $O(1)$ per query.↵
</spoiler>↵
↵
<spoiler summary="H. Bacteria Colony">↵
There are several solutions to this problem. A straightforward approach is to binary search on the smallest possible value of $t$. For a fixed value of $t$ to be possible, there needs to be a point $(x, y)$ that is within a Manhattan distance of $t$ from each of the $n$ given points. We can reformulate this by noticing that the set of points that a bacteria can expand to can be represented as a square centered at the point of origin rotated $45^\circ$ from the coordinate axes. ↵
↵
So to determine if a value of $t$ is possible, we just need to check if the intersection of these squares is non-empty and contains a point with integer coordinates. Implementation can get tricky. The author's solution rotates the plane by $45^\circ$ to make all squares axis-aligned. Then finding the intersection of two rectangles is much simpler. Off-by-one errors will most likely happen, so we also recommend checking all possibilities within a certain range around the solution you found.↵
</spoiler>↵
↵
<spoiler summary="I. Evolutionary Pathways">↵
Let $a_i$ be the number of evolutionary pathways over $i$ generations **without** any OP gene. We can see that this satisfies $a_{i+1} = \binom{2^{i+1}-1}{2^i} \cdot a_i^2$. The intuitive way to understand this is that the species which splits off in the first generation will have $2^i$ descendants and each way to choose these descendants is unique.↵
↵
The second key observation is that the generations in which the OP gene is "activated" depend only on $n$. (Hint: think about the binary representation of $n$.) Now, we can go from the first to the most recent generations and follow the OP gene. If the species with the OP gene splits in the $i$-th generation, then the new species without the OP gene will have $a_{i-1}$ possibilities, multiplied by the appropriate binomial factor. Otherwise, the species does not evolve and there is no change. So we can compute the answer for each query in $O(\log n)$.↵
</spoiler>↵
↵
↵
The [BioCode 2024](https://tjbioinfo.netlify.app/biocode/) contest concluded yesterday. Thanks to the 26 teams who participated!↵
↵
We (the organizers) thought it would be great to share this with the Codeforces community. You can now access the problemset in the Gym [here](https://mirror.codeforces.com/gym/105123). This competition was tailored specifically for participants around the Div2/3/4 level, and the authors are [user:avnithv,2024-04-21], [user:AryGad11,2024-04-21], and [user:DanielQiu,2024-04-21]. ↵
↵
We hope you enjoy the problems, and please let us know in the comments if you have any questions. Best of luck!↵
↵
**UPD**: Added Solution Sketches for A-F↵
↵
<spoiler summary="A. Mitosis">↵
Just print YES if $a+b=c$ and NO otherwise.↵
</spoiler>↵
↵
↵
<spoiler summary="B. Neural Network">↵
The answer is the sum of $a_i \cdot a_{i+1}$ over all $1 \leq i < n$, which can be computed in a single for loop.↵
</spoiler>↵
↵
↵
<spoiler summary="C. Flipped DNA">↵
In this scenario, 'A' and 'T' are equivalent and 'C' and 'G' are equivalent. So we can replace all 'T' with 'A' and all 'G' with 'C' and check if the resulting strings are equal.↵
</spoiler>↵
↵
↵
<spoiler summary="D1. Predator or Prey (Easy Version)">↵
Let's loop over all pairs of animals and determine whether or not they have a predator-prey relationship and update the respective counts. This can be checked by seeing if $a \leq \lvert p_i - p_j \rvert < b$.↵
</spoiler>↵
↵
↵
<spoiler summary="D2. Predator or Prey (Hard Version)">↵
The previous version is too hard for these constraints. We need a faster way to find the number of predators and prey an animal has. Notice that for animal $i$, its predators will be in the range $[p_i + a, p_i + b)$, and its prey will be in the range $(p_i - b, p_i - a]$. If we sort the array of predator factors, we can binary search for the indexes of the endpoints of these ranges and determine the number of animals in that range. Thus, we can solve the problem in $O(n \log n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="E. Powerhouse of the Cell?">↵
We can notice that it is always better to do less costly tasks before more costly tasks if we consider both. Let's say we know the optimal solution for $k=i$. When we consider the $i+1$-th element, there are three cases:↵
↵
- We can add it to our solution without running out of ATP, which would clearly be optimal if possible.↵
- We can use it to replace a task in our solution. In this case, we would obviously want to replace the most costly task.↵
- We do not add it to our solution. In this case, it would have to be worse than the most costly element in our solution, since otherwise option $2$ would be better.↵
↵
So we need to be able to add an element to our solution and find/remove the element with the maximum cost. This sounds like a job for a priority queue.↵
</spoiler>↵
↵
First, we can show that if a wildfire of strength $k$ is sufficient, so is a wildfire of strength $k+1$ (try proving this yourself!). So for each forest, we can separately compute the minimum strength needed to burn all of the forests to the left and to the right and take the maximum of those values. ↵
↵
For now, let's only consider the left case; the other case is symmetric. If the minimum strength needed for forest $i$ is $k$, then the minimum strength for forest $i+1$ is $k-1$ if $t_i \geq k$ and $k+1$ otherwise. So we can compute the answer in two linear sweeps, one for the forests to the left and one for the forests to the right.↵
</spoiler>↵
↵
<spoiler summary="G. Cut and Splice">↵
You might notice that the statement implicitly assumes that the number of linear strands is well-defined regardless of how *LOPITAL* cuts and splices. Understanding why this is true is the key to the solution.↵
↵
**Claim 1**: The number of new linear strands formed from a cut is equal to the number of cuts made (i.e. consecutive occurrences of $x$ and $y$). ↵
Clearly, this is true when we cut an already linear strand. The first cut we make to a circular strand converts it to linear and increases the answer by $1$.↵
↵
**Claim 2**: During a splice, the number of linear strands reduces by $min(a_{1x}, a_{2y})$ where the $a_{1i}$ is the number of linear strands that begin with $i$ and $a_{2j}$ is the number of linear strands that end with $j$.↵
If the $x$-$y$ pair that we splice are the beginning and end of the same strand, then the number of linear strands decreases by $1$. In the other case, we splice two different linear strands, reducing the number of linear strands by $1$.↵
↵
Since there are only $4$ possibilities, we can update the values $a_{ij}$ and the number of consecutive occurrences of two characters in $O(1)$ per query.↵
</spoiler>↵
↵
<spoiler summary="H. Bacteria Colony">↵
There are several solutions to this problem. A straightforward approach is to binary search on the smallest possible value of $t$. For a fixed value of $t$ to be possible, there needs to be a point $(x, y)$ that is within a Manhattan distance of $t$ from each of the $n$ given points. We can reformulate this by noticing that the set of points that a bacteria can expand to can be represented as a square centered at the point of origin rotated $45^\circ$ from the coordinate axes. ↵
↵
So to determine if a value of $t$ is possible, we just need to check if the intersection of these squares is non-empty and contains a point with integer coordinates. Implementation can get tricky. The author's solution rotates the plane by $45^\circ$ to make all squares axis-aligned. Then finding the intersection of two rectangles is much simpler. Off-by-one errors will most likely happen, so we also recommend checking all possibilities within a certain range around the solution you found.↵
</spoiler>↵
↵
<spoiler summary="I. Evolutionary Pathways">↵
Let $a_i$ be the number of evolutionary pathways over $i$ generations **without** any OP gene. We can see that this satisfies $a_{i+1} = \binom{2^{i+1}-1}{2^i} \cdot a_i^2$. The intuitive way to understand this is that the species which splits off in the first generation will have $2^i$ descendants and each way to choose these descendants is unique.↵
↵
The second key observation is that the generations in which the OP gene is "activated" depend only on $n$. (Hint: think about the binary representation of $n$.) Now, we can go from the first to the most recent generations and follow the OP gene. If the species with the OP gene splits in the $i$-th generation, then the new species without the OP gene will have $a_{i-1}$ possibilities, multiplied by the appropriate binomial factor. Otherwise, the species does not evolve and there is no change. So we can compute the answer for each query in $O(\log n)$.↵
</spoiler>↵
↵
