Internet Problem Solving Contest

IPSC 2018

Problem F – Farmer's code

Bob is a farmer. Among other endeavours, he grows apple trees. Not all of his trees are perfect, though. Some produce sour fruit, some are too small, and some are just crooked. His dream is a perfectly symmetrical tree with extremely sweet apples. However, he isn’t very fluent in genetics, so he needs your help!

Problem specification

In this problem, you will interact with an online farm dashboard page.

You have a population of n trees, sorted from oldest to youngest. In the beginning all trees have distinct genotypes (their genetic code) and phenotypes (their appearance) but this may change based on your actions. You are also given an image of your goal – the tree that Bob wants to grow.

You may select any two living trees to cross them. When you do this, the following happens:

You will see the same set of trees if you connect from two different browser windows.

You can use the Reset button if you think that your genetic diversity became insufficient to produce the requested phenotype, or you simply want to start over. The farm will go back to the initial population and you’ll receive a Wrong answer. You can reset as often as you want – you are not limited to 10 submissions per subproblem.

However, you can only cross trees a limited number of times. The limit is separate for each subproblem and is displayed on the farm page. The number will not reset when you click Reset. If you run out, you won’t be able to solve that subproblem.

Input specification

In the easy subproblem F1 we have n = 4.

In the hard subproblem F2 we have n = 18.

Output specification

You don’t have to submit anything. You will automatically get OK or Wrong answer submissions by interacting with the farm page.

Word of advice

Knowledge of real-life tree genetics probably won’t help you solve this problem.