An anagram is any arrangement of the letters of a word in which each letter of the alphabet occurs exactly as many times as in the original. For example, clarinets is an anagram of larcenist.

An amalgram is any arrangement of the letters of two words in which each letter of the alphabet occurs at least as many times as in either of the originals. For example, administration is an amalgram of mantis and raisin, although not the shortest possible because the letter d appears in neither.

Given two words, invent an amalgram for them that contains as few letters as possible.

You are an analyst, studying the relationship between advertisement budget spending (denoted by $$$x$$$) and sales (denoted by $$$y$$$) over the period of $$$n$$$ months. More specifically, for every month of time from 1 to n you have the value of spending $$$x_i$$$ and sales $$$y_i$$$.

To quantify the relationship you are using linear regression with regularisation, which means that you are modelling $$$y$$$ as $$$y=Kx+B$$$, where $$$K$$$ and $$$B$$$ are real numbers minimising the penalty function:

(Note: this is the standard penalty function for L2 regularised linear regression.)

For the report requested by your manager, you need to make several predictions. More specifically, you have a list of prediction queries, each described by four numbers — $$$L_j$$$, $$$R_j$$$, $$$\lambda_j$$$ and $$$X_j$$$. To process such a query you need to perform the following steps:

• take the spending and sales values for the months from $$$L_j$$$ to $$$R_j$$$ inclusive;
• find the coefficients $$$K$$$ and $$$B$$$, which minimise the penalty function for the given regularisation coefficient $$$\lambda_j$$$;
• plug the $$$X_j$$$ into the resulting model and compute the prediction.

You are given the ads spending and sales data, and the prediction queries descriptions. You are to process the queries and output the predictions.

Cross-country running is a sport in which contestants run a race on an open-air course over natural terrain. To record contestants' progress, the organisers set up RFID checkpoints that each span a line across part of the course.

A contestant has finished the race once they go through all of the checkpoints in order from $$$1$$$ to $$$n$$$. Crossing a checkpoint out of order conveys no advantage or penalty to a runner, as they simply have to cross it again later at the right time. Thus, for example, a runner may choose to cross a checkpoint once and then immediately cross it again in another direction if it leads to a quicker finish.

Optimal running route for the course given in sample input 3.

Your objective is to find the shortest distance one has to run to finish the race, so that we can use this as the official distance of the course.

You are designing a controller for an interesting aircraft called the Single Copter. It only has one propeller, but the outgoing air flow is further shaped by four flaps that control three Euler angles (pitch, roll and yaw) that help maintain the requested orientation of the craft. Each of these flaps can assume any angle requested by the flight controller, and the effects of the flaps being at certain angles should translate to exerting the requested forces on pitch, roll and yaw.

Pitch	Roll	Yaw

Pitch, roll and yaw on a Single Copter

Define the angles of the flaps to be $$$n$$$, $$$e$$$, $$$s$$$, and $$$w$$$ (for "north", "east", "south" and "west" respectively). The forces in the directions of pitch, roll and yaw are defined by the following equations:

As there are four variables and three constraints, you decided that, from the perspective of aerodynamics, it makes sense to make the maximum of the flap angles as small as possible, that is, you additionally want to minimise $$$\max\{ |n|, |e|, |s|, |w| \}$$$.

Find the best parameters to send to the Single Copter to achieve the desired pitch, yaw, and roll.

The members of the No-Weather-too-Extreme Recreational Climbing society completed their first successful summit seven years ago to this day!

At the time, we took a picture of all the members standing together in one row. However, the photograph looks messy, as the climbers were not standing in order of height, and we have no way to reorder them.

We will need to cut some of the climbers out of the picture.

This picture of 7 (formerly 11) climbers was edited to solve Sample Input 3.

An optimal solution minimises the size and number of visible gaps in the photo. We define the cost as the sum of the squares of the lengths of gaps left in the edited photo. For example, if two individual climbers are removed from the photo and one pair of adjacent climbers are removed, the total cost is $$$1^2 + 1^2 + 2^2 = 6$$$.

Find the minimum possible cost you can reach by removing climbers.

Little Claire studies proteins, which are sequences of amino acids. There are 20 amino acids from which proteins are built. While amino acids all have proper names, such as alanine or glycine, they are often denoted by single letters, so that proteins can be seen as sequences of different lengths, such as DTASDAAAAAALTAABAAAAAKLTABBAAAAAAATAA, TIFLQQQQQQQQQQQ or even maybe RICKRQLL.

Comparing two proteins can be difficult, because they may contain active sites, which determine their function in a cell, and less important parts of the sequence. Recent advances in artificial neural networks made it possible to train a network that, given a protein, outputs a sequence of $$$l$$$ numbers, where each number roughly corresponds to a feature of a protein that correlates with its possible functions in a cell. Such a sequence is called an embedding.

Claire is particularly interested in suspicious proteins, those which are really different from others. For this purpose, she considers the so-called Manhattan distance between embeddings of proteins. For two protein embeddings $$$p$$$ and $$$q$$$ of length $$$l$$$, the distance $$$\mathcal{D}(p, q)$$$ is computed as follows: $$$$$$ \mathcal{D}(p, q) = \sum_{i=1}^l |p_i - q_i|, $$$$$$

where $$$p_i$$$ is the $$$i$$$-th element of the embedding $$$p$$$.

Claire wants to find $$$k$$$ suspicious proteins in the given list of $$$n$$$ proteins. As a baseline for her studies, Claire wants to use the following greedy algorithm:

• Find a protein $$$p^{(1)}$$$ which is the most distant from the first protein in the list.
• The second protein, $$$p^{(2)}$$$, is chosen as the most distant protein from $$$p^{(1)}$$$.
• The third one, $$$p^{(3)}$$$, is chosen so that $$$\min\{\mathcal{D}(p^{(1)}, p^{(3)}), \mathcal{D}(p^{(2)}, p^{(3)})\}$$$ is maximum possible. That is, it must be far away from both previously chosen proteins.
• All subsequent proteins $$$p^{(i)}$$$, $$$4 \le i \le k$$$, are chosen in a similar way: the minimum of the distances to all the previously chosen proteins should be maximum possible.

Claire's implementation works nicely for small numbers $$$n$$$ and $$$k$$$, but becomes too slow as they increase. You must find a way to optimise this.

Find parts of a 2d grid matching a 2d word.

Our polygon-shaped bush needs a trim. We would like to cut it down to size so that the remaining leaves of the bush form a new shape of our choosing, with its centre sitting on the top of the stem – represented as the origin $$$(0, 0)$$$ in both shapes.

Bushes cut into beautiful shapes, as given in sample inputs 1, 2, & 3.

The original shape of the bush is a little unusual so it is not obvious how large we can make the new shape without leaving some gaps in the design.

Find out the largest scaling factor that you can apply to the new shape to make it fit into the old shape–meaning that there is no point contained by the re-scaled new shape that was not contained by the old shape as well.

The Simpson's Paradox is a phenomenon in statistics where a trend or pattern that appears in different groups of data is inconsistent (disappears or even reverses) with what we see when the groups are combined. It is named after the British statistician Edward H. Simpson, who described it in 1951, although similar observations had been made earlier.

For example, let assume that two teams have been training for the UKIEPC 2024 and have the following statistics for the graph and geometry problems:

• Team X has solved 81 out of 87 graph problems (success rate of approx 93%), and 192 out of 263 geometry (73%). Total is 273 out of 350 problems (78%).
• Team Y has solved 234 out of 270 graph problems (87%), and 55 out of 80 geometry (69%). Total is 289 out of 350 (83%).

If we look per category — team X has higher success rate in both categories, but when looking in combination, the pattern reverses, and team Y appears to have higher success rate.

In this problem you are to construct an example of the dataset illustrating the Simpson's paradox. More specifically, let us assume (similarly to the example above) that there are two teams who have been solving problems of $$$N$$$ categories and the total number of problems solved by each of the teams is $$$M$$$. Let us denote the number of the problems in $$$i$$$-th category solved by Team X as $$$a_i$$$, attempted — by $$$b_i$$$. Similarly, let us define $$$c_i$$$ as the number of problems solved by Team Y in the $$$i$$$-th category and $$$d_i$$$ as the number of problems attempted.

You are to find such $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ and $$$d_i$$$ that:

• $$$\sum b_i = \sum d_i = M$$$
• $$$a_i \le b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$
• $$$c_i \le d_i$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$
• $$$a_i, b_i, c_i, d_i \gt 0$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$
• $$$\frac{a_i}{b_i} \gt \frac{c_i}{d_i}$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$
• $$$\frac{\sum a_i}{\sum b_i} \lt \frac{\sum c_i}{\sum d_i}$$$

Dave, an old Computer Science professor, still maintains a local community computer network even after retirement. Each community member has a computer with three networking cards, and some of these cards may be connected by a cable. They form a connected network, and, following a long resource-saving tradition, the number of cables is kept to the minimum possible.

The habits of all the community members are quite stable: for every two computers the number of packets per second between them is known exactlyc. However, the network was first assembled a long time ago, so the connections are not necessarily be optimal any more. For two computers numbered $$$i$$$ and $$$j$$$ we define $$$d_{ij}$$$ the shortest path between them, measured in the number of cables, and $$$c_{ij}$$$ the number of packets per second that should be transferred from $$$i$$$ to $$$j$$$. The commutation stress is defined to be the sum of $$$c_{ij} \cdot d_{ij}$$$ for all $$$i \lt j$$$, and one would like to minimise it.

Dave realised that it is finally the time to upgrade the cables — after all, they do degrade with time. He wants to take this opportunity to also optimise the network, such that the commutation stress becomes smaller. However, he is no longer as quick as in his youth, and his friends may get dissatisfied if too much disruption happens at once. So he decided that he will perform the upgrade using the following scenario. For each of the old cables, he will do the following:

1. Remove the old cable.
2. Connect the network back using a new cable, choosing the computers to connect in such a way that the resulting commutation stress is minimum possible.
3. If there are many ways to do this, break ties by choosing the computers with the smallest numbers: if $$$(u_1, u_2)$$$ and $$$(v_1, v_2)$$$ result in the same commutation stress, but $$$u_1 \lt v_1$$$ (or $$$u_1 = v_1$$$ and $$$u_2 \lt v_2$$$), then $$$(u_1, u_2)$$$ should be chosen.

A single reconnection operation (the first one in the sample input)

Note that, since each computer only has three network cards, Dave cannot connect two arbitrary computers on the second step: if one of them is already connected to three other computers, it is impossible to connect it to yet another computer. Fortunately, it is not hard to show that it is always possible to find two computers to connect: for instance, Dave can choose the two just-disconnected computers.

Unfortunately, the task appeared to be more difficult than it seemed initially. Could you help Dave?

You are knitting a scarf in a striped pattern, having made strong progress on the first few stripes. You have multiple colours available to continue creating the pattern and would very much like that no colour appears too often – more specifically, that the colour appearing most often still appears as few times as possible.

A knitted solution to sample input 1. No colour is used more than twice, nor is any colour repeated within 3 consecutive stripes.

Please extend the given design to fashion a nice scarf.

You have been given a new training plan for the month, consisting of days focusing on legs or arms interspersed with rest days. This training plan will be repeated for as any times as necessary to get to the end of the month.

Each day of the training plan either contains the word "rest", in which case it is a rest day, or if not may still contain "leg", in which case it is a leg day, or contains neither, meaning that of course it is an arm day.

Produce a motivational 31-day calendar, starting on a Monday, showing what types of exercises you will do on each day.