It is 2067 and the fine astronauts Adrian and Ashton just landed on Venus, marking a significant step forward in space exploration for mankind! However, they are currently having a dispute trying to figure out who should get the honor of being the first to touch down on the surface. To prevent further arguing, their advisor Maverick suggests that they play the following game to decide.

In this game, there is an array $$$a$$$ of $$$3n$$$ $$$(1 \leq n \leq 10^5)$$$ numbers. In each round:

• Adrian may (or may not) $$$\textbf{cyclically shift}^\dagger$$$ the array any number of times.
• Adrian then will select two indices $$$i, j$$$ in the array such that they are not next to each other ($$$i \lt j$$$ and $$$|i - j| \neq 1$$$). He will add $$$a[i] + a[j]$$$ to his score (the values at these indices).
• Ashton then will select an index $$$k$$$ between $$$i,j$$$ ($$$i \lt k \lt j$$$) and add $$$3 * a[k]$$$ to his score.
• After this, elements at indices $$$i, j, k$$$ are removed from the array.

This process repeats until there are no elements left in $$$a$$$, at which point the game ends.

Adrian and Ashton both want to maximize their score, as the player with the higher score at the end of the game wins. If Adrian and Ashton play optimally, what score will both of them have at the end of the game?

$$$^\dagger$$$Given an array $$$a$$$ of size $$$k$$$, a cyclic shift of $$$a$$$ turns $$$[a_1, a_2, ..., a_{k-1}, a_k]$$$ into $$$[a_k, a_1, a_2, ..., a_{k-1}]$$$

Warith has been coping for a while about not being able to see Le Sserafim in Dallas, so he decided to take a mental break. He decided to go down to the Colorado River and skip some stones. When he arrived, he found $$$n$$$ stones arranged in a line. Warith knows that each stone has some mass $$$a_i$$$ $$$(1 \le i \le n)$$$. With all the stuff on his mind, he wants to maximize his enjoyment from skipping stones by picking a contiguous subarray $$$a'$$$ of the original stone array. Note that Warith cannot rearrange the stones, he can only pick a contiguous subarray from the original order.

For an array $$$a'$$$, the enjoyment from skipping all these stones is calculated as follows:

• For each unique mass $$$m$$$ in the stones of $$$a'$$$, find the number of stones with this mass ($$$f$$$)
• The enjoyment is the sum of $$$m \cdot f$$$ across all unique $$$m$$$

The only issue is that Warith also does not want the mass of the stones to vary too much either. Specifically, he doesn't want his subarray to contain more than $$$k$$$ distinct masses. With this in mind, can you help Warith maximize his enjoyment?

In the solar system, it is often said that the most habitable planet besides Earth is Mars. Indeed, scientists have recently begun settling on Mars and have set up a base for permanent living. However, while Mars has an abundance of water and soil nutrients, it's missing the greatest natural resource: Milk! Unfortunately, this means that the scientists must import milk from Earth in order to sustain themselves.

Johnny, one of the scientists, has a particular affinity for milk. He has knowledge of spaceship trips which can transport jugs of milk from Earth to Mars and vice versa. Each of these trips has a departure and arrival time, and all of these times are distinct from each other.

Due to restrictions regarding waste, in order to import milk, Johnny must place an empty jug of milk on a spaceship bound for Earth where it will be filled immediately. He can then request for a particular spaceship bound for Mars to carry the milk back, where Johnny can empty the milk jug in a large storage container. Each spaceship can only carry one of Johnny's milk jugs at most (other scientists want to use the spaceships as well!).

Before any of the spaceships begin transporting items, Johnny has two empty milk jugs on hand. Given this knowledge, Johnny would like to know the maximum jugs' worth of milk he can import from Earth with the spaceships available.

Jupiter is home to the largest Coriolis forces in the Solar System. Specifically, the Coriolis force causes horizontal bands on the planet to experience strong winds either East or West. Jupiter has $$$8$$$ of these prominent bands.

Embarking on a mission to navigate Jupiter, you are well aware of winds and need to factor them into the amount of fuel you need to bring on your mission. Your spaceship will enter Jupiter at coordinate $$$S$$$, and need to end at coordinate $$$D$$$. A coordinate can be denoted by the band you are in (vertical position), and the columns (horizontal position) along that band at time $$$t=0$$$.

Each timestep, the Coriolis winds take effect, rotating all positions of even-indexed bands right, and all positions of odd-indexed bands left.

Jupiter also has numerous storms that move along with these bands. You want to avoid these storms at all costs.

Consider the following 4 banded system example, as we can find on Earth:

        col1   col2   col3   col4   col5
band1 |   .  |   X  |   .  |   D  |   .  | <–
band2 |   X  |   .  |   X  |   X  |   X  | –>
band3 |   .  |   S  |   .  |   .  |   .  | <–
band4 |   .  |   .  |   .  |   .  |   .  | –>

After one timestep, the world would look like:

        col1   col2   col3   col4   col5
band1 |   X  |   .  |   D  |   .  |   .  | <–
band2 |   X  |   X  |   .  |   X  |   X  | –>
band3 |   S  |   .  |   .  |   .  |   .  | <–
band4 |   .  |   .  |   .  |   .  |   .  | –>

Your spaceship lets you move one tile in any cardinal direction (not diagonally) before the Coriolis effect takes effect each timestep. Note you can also choose to not move, in which you move along with the band. Also, note that columns 1 and $$$N$$$ are adjacent, but band1 and band8 are not.

Find the minimum amount of timesteps to travel from coordinate A to coordinate B (if possible) so we can know how much fuel to bring!

Note: The following problem, Uranus, may be easier if you prefer solving in order of increasing difficulty.

Christiaan Huygens was the first to propose there was a ring surrounding Saturn, in 1655. He did this by publishing his claim as an anagram: aaaaaaacccccdeeeeehiiiiiiillllmmnnnnnnnnnooooppqrrstttttuuuuu. Only three years later did he have enough evidence to publish the true claim: Annulo cingitur, tenui, plano, nusquam cohaerente, ad eclipticam inclinato ("It is encircled by a thin, flat ring, nowhere touching, inclined to the ecliptic").

Shani recently became inspired by Huygens and published some similar anagrammed claim. Unfortunately, it was mostly a joke, but now the research committee is calling upon her to back it up.

Luckily, she does have some data that she has yet to publish. Specifically, she has $$$1 \le n \le 1000$$$ data points, each a string $$$s_i$$$ with $$$1 \le |s_i| \le 100$$$. She may publish any subset of these data points, and once published, she knows the committee will concatenate them in their original order (the data points are dated). Her original claim is a string $$$t$$$ with $$$1 \le |t| \le 20$$$. The committee will then count how many times $$$t$$$ occurs as a substring in the published data (overlaps are counted), and for each occurrence she will earn one reputation score.

Report the maximum reputation score Shani can get.

Although it is not the farthest planet from the Sun, Uranus is considered to be the coldest planet in the Solar System, experiencing a minimum temperature of 49 K and extreme winds of up to 900 km/h. Undaunted, Sir Vedward V's twin brother, Sir Udward, wishes to send probes to explore Uranus.

Currently, VASA has developed $$$n$$$ probes, where the $$$i^{\text{th}}$$$ probe can survive temperatures of up to $$$x_i$$$ degrees Kelvin and wind speeds of up to $$$y_i$$$ km/h; however, it costs $$$c_i$$$ dollars to construct. In addition, VASA has conducted $$$q$$$ measurements of locations on Uranus, where the $$$i^{\text{th}}$$$ location has a temperature of $$$t_i$$$ degrees Kelvin and a wind speed of $$$w_i$$$ km/h.

Sir Udward will reward you handsomely if you help him determine, for each landing location, the cheapest probe that can survive its temperature and wind speed.

Recently, Poseidon has gotten addicted to a game called Craftmine. In Craftmine, there is a crafter that consists of $$$k$$$ slots, each of which can store an unlimited amount of a single type of ingredient. If the slot has 0 ingredients, it is considered empty. A recipe represents a configuration of the crafter that will produce a desired product. Each recipe is an array of length $$$k$$$ whose elements are either an empty slot or a type of ingredient.

Each time the crafter is used, it checks if the current configuration matches a recipe by comparing the ingredients in each of the slots (but not the amount of each ingredient). If the configuration matches a recipe, every slot uses up exactly 1 of the ingredients in that slot (except for empty slots, where nothing happens).

Currently, Poseidon has $$$n$$$ unique recipes and (being a god) has an unlimited amount of all ingredients. However, Poseidon is quite lazy, so he plans to fill the crafter only once, then use it as many times as he can to create unique recipes.

What is the maximum number of unique recipes that can be created after filling the crafter once?

Warning: Java and Python solutions are probably too slow for this problem.

Shortly after solving their previous dilemma, the Plutonian government has asked for your help once again. There is a special vault in the heart of the Plutonian capitol, and the government needs to unlock it (don't ask why), but the process of doing so is quite complex so they've requested your help.

The vault has a lock consisting of $$$n$$$ switches, numbered $$$1...n$$$, where $$$n$$$ is odd. The initial state of the lock is given as a bitstring of length $$$n$$$, where the $$$i$$$-th character represents the state of the switch $$$i$$$, and a '1' denotes that the switch is up while a '0' denotes that it is down. To unlock the safe, all of the switches need to be down. You want to unlock the lock, but you can only perform the following two operations on the lock:

• Flip two adjacent switches. In other words, choose some $$$i$$$ such that $$$1 \leq i \leq n - 1$$$ and flip the value of switch $$$i$$$ and $$$i + 1$$$ simulatneously.
• Flip all switches simultaneously.

The Plutonian government is short on time, so they want you to determine the minimum number of operations necessary to set all switches to the down ('0') state.

Of course it isn't that simple though. After all, the government is short on time because every minute for $$$q$$$ minutes the state of the lock changes. During the $$$i$$$th update, all switches $$$j$$$ such that $$$l_i \leq j \leq r_i$$$ are flipped. Note that the updates persist. Please help the Plutonians and output the minimum number of operations to set all switches to the down state after each update.