Hey Codeforces!

The BioCode 2024 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. This competition was tailored specifically for participants around the Div2/3/4 level, and the authors are avnithv, AryGad11, and DanielQiu.

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

**UPD2**: Added Solution Sketches for G-I

**A. Mitosis**

Just print YES if $$$a+b=c$$$ and NO otherwise.

**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.

**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.

**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$$$.

**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)$$$.

**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.

**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.

**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.

**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.

**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)$$$.

Is there an editorial please?

editorial?

I haven't written an editorial yet. Tell me what problems you need and I'll write one for those.

If you don't have any problem doing it then Making all the submissions public might help all of us.

Piper so cute :)

Predator or Prey

I put solution sketches for A-F. Let me know if you have questions

Thank you for the effort and the quick reply, but I actually got stuck after problem F. Are there solution sketches for the rest of the problems too?

Ok, I put in the rest.

Auto comment: topic has been updated by avnithv (previous revision, new revision, compare).