Momo has a string $$$s$$$ which he plays with. After each day, he takes the initial string and appends it to the one that he currently has, that is, if the string is "$$$abc$$$", on the first day the string will remain "$$$abc$$$", on the second day the string will become "$$$abcabc$$$", on the third day the string becomes "$$$abcabcabc$$$", and so on.

Bobo has another string $$$t$$$. Bobo is curious whether his string $$$t$$$ can be found as a subsequence in Momo's string. He is curious what is the first day when this property will hold.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.

How exciting! Today is your little brother's birthday! That's why you ordered a huge ($$$1 \times 1$$$)-meter cake. It is a special vanilla cake with $$$n$$$ sweet chocolate chips and $$$m$$$ refreshing strawberries.

You show him your awesome surprise, and... bummer! It turns out that he hates fruit! "Of course, how could I have forgotten?" you say. Nonetheless, he has a sweet tooth for chocolate, so he would be happy if you could cut him a piece of the cake that contains no strawberries. To make him happy, you'd want to give him a piece having as many chocolate chips as possible.

The picture above depicts the example test case.

You can only make one cut along a straight line through the cake, and you are not allowed to cut though either chocolate chips or strawberries. What is the maximum number of chocolate chips that you may give your little brother?

Note: The picture above is for illustration purposes. You should consider both chocolate chips and strawberries to be infinitesimally small.

During the standard yearly testing, $$$n$$$ people are being tested for COVID.

Because of the limited amount of available tests, a procedure called batch testing is in place. More specifically, for each of the available $$$m$$$ tests, a subset of people is selected and they are tested as a group. If any of the people of the group is positive, the test will yield a positive result (and similarly, if none of the tested people are infected, the test will yield a negative result).

More specifically, test $$$i$$$ ($$$1 \leq i \leq m$$$) is done on the group of people with IDs $$$a_{i,1}, a_{i, 2}, \ldots, a_{i, k_i}$$$. All $$$m$$$ tests are perfect (they always yield positive if and only if at least one person of the group is positive), and they, unfortunately, all came back positive.

Before testing, each person was expected to have a $$$50\%$$$ probability of being positive. Additionally, all of the probabilities of having COVID were independent (i.e. one person having / not having the disease did not influence the probability of someone else having it). However, given the $$$m$$$ positive test results, some people are now more likely to have COVID than others, and it is crucial for the medical team to figure out what is the new status.

Sort the people from least probable to have the disease, to most probable, after the batch testing procedure.

Tip: It can be proven that the posterior probability of person $$$i$$$ ($$$1 \leq i \leq n$$$) having the disease is proportional to the number of scenarios (out of the $$$2^n$$$) in which all $$$m$$$ tests output the correct result, and person $$$i$$$ is positive.

A tree $$$T$$$ is special if the number of vertices with an odd degree (with respect to $$$T$$$) is a multiple of $$$4$$$.

You are given a connected graph with $$$n$$$ vertices and $$$m$$$ edges. Determine if there is a special spanning tree in this graph.

As a reminder, a spanning tree of a graph is a subset of the edges of the graph that forms a tree.

In a classroom, there are $$$2n$$$ students. The $$$i$$$-th student has skill $$$c_i$$$. A teacher is holding an exercise that requires working in pairs. Initially, students $$$2i-1$$$ and $$$2i$$$ are paired, for each $$$i$$$ from $$$1$$$ to $$$n$$$.

Now, the teacher wants to form new pairs $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$ with the following conditions:

• Each student is in exactly one pair. That is, each number from $$$1$$$ to $$$2n$$$ appears among numbers $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ exactly once.

• No two students that were in a pair before will be in a pair again. That is, there are no $$$1 \le i, j \le n$$$ such that $$$a_i = 2j-1, b_i = 2j$$$, or $$$a_i = 2j, b_i = 2j-1$$$.

The teacher wants to minimize the sum of differences in skills over the $$$n$$$ pairs, as this would be more productive. In other words, $$$|c_{a_1} - c_{b_1}| + |c_{a_2} - c_{b_2}| + \ldots + |c_{a_n} - c_{b_n}|$$$ should be as small as possible.

What is the smallest value of $$$|c_{a_1} - c_{b_1}| + |c_{a_2} - c_{b_2}| + \ldots + |c_{a_n} - c_{b_n}|$$$ the teacher can achieve?

There is a tennis tournament happening right around the corner, with $$$n$$$ vicious participants.

The marketing experts have devised an $$$n \times n$$$ matrix $$$P$$$, where $$$P_{i, j}$$$ is the popularity score gained if player $$$i$$$ competes in a match with player $$$j$$$. They also observed the following social phenomenon: whenever player $$$i$$$ competes against player $$$j$$$ and wins, player $$$i$$$ will inherit all the popularity scores of player $$$j$$$, that is, $$$P_{i, x}$$$ becomes the maximum of $$$P_{i, x}$$$ and $$$P_{j, x}$$$, for all $$$1 \leq x \leq n$$$ (and similarly for $$$P_{x, i}$$$).

Since fairness isn't a concern, the tournament doesn't have to be perfect. In that sense, any set of $$$n-1$$$ matches played in order can be a valid tournament. To top if off, the contestants are numbered from $$$1$$$ to $$$n$$$ in descending order of their performance. In that sense, if players $$$i$$$ and $$$j$$$ were to compete in a match, where $$$i \lt j$$$, then player $$$i$$$ will always win.

Given the popularity matrix $$$P$$$, you have to decide the $$$n-1$$$ matches that are going to be played in order during the tournament, such that the total popularity score over the $$$n-1$$$ matches is as large as possible. Note that once a match takes place, the loser gets disqualified, therefore she/he cannot not participate in future matches.

You have an intricate system of $$$n$$$ circular gears connected in a line, with their centers fixed in $$$n$$$ corresponding axles. The $$$i$$$-th axle is fixed on the wall at coordinate $$$x_i$$$ on the (imaginary) number line.

The picture above depicts the example test case.

However, a massive earthquake just hit, and all gears have fallen to the ground, leaving the axles hanging on the wall. Given the radii of the $$$n$$$ gears $$$r_i$$$ and the coordinates of the axles, you are asked to reinstall the system by putting the gears back onto their original places.

The original problem "Towers of Hanoi" is about moving $$$n$$$ circular disks of distinct sizes between $$$3$$$ rods. In one move, the player can move only the top disk from one rod to the top of another. The disks should always be placed one over the other in decreasing order of sizes. Initially, the $$$n$$$ disks reside on rod $$$1$$$ and the goal is to have them all $$$n$$$ reside on rod $$$3$$$.

There is a myth of an Indian temple where priests are solving the instance of "Towers of Hanoi" with $$$64$$$ disks since the beginning of time. It is believed that once this instance is solved, the world will end.

However, this "Relaxed Hanoi" problem is not that apocalyptic. In fact, it is pretty optimistic as once you correctly solve it, you will get a positive verdict. In this variation, rod $$$1$$$ is not subject to the order rule. In other words, the disks on rod $$$1$$$ can reside in any order at any point of time.

For an instance of the "Relaxed Hanoi" problem, provide at most $$$2 \cdot n^2$$$ moves that solve the problem.

You are given an array $$$a$$$ of $$$n$$$ nonnegative integers. In one operation, you can choose any $$$i$$$ such that $$$1\le i \le n-1$$$ and $$$\max(a_i, a_{i+1}) \gt 0$$$, and replace both $$$a_i$$$ and $$$a_{i+1}$$$ by $$$\max(a_i, a_{i+1}) - 1$$$.

Find the smallest number of operations required to make all elements equal to $$$0$$$. It can be proven that it's always possible to make all numbers equal to $$$0$$$.

You are Psycho Cookmaster, a devil-possessed spirit with a surprisingly humble love for food. Tonight is the opening night of your brand new restaurant – "Food to Die For" – and it's already full with reservations from $$$n$$$ elves! The $$$i$$$-th elf has a current sickness of $$$s_i$$$.

The $$$n$$$ elves will come in order tonight for their unforgettable dinner. To avoid having surprises, you have prepared $$$m$$$ dishes in advance, each of them having a health index $$$h_i$$$ and a tastiness index of $$$t_i$$$. If an elf $$$x$$$ eats a dish $$$y$$$ such that $$$h_y \lt s_x$$$, then elf $$$x$$$ will die.

Tonight is a great opportunity to show your evil side; after all, you are a psychopath god! Consequently, you want to distribute the $$$m$$$ dishes such that the elves that eat them will die, but you also want to show them some remorse and your love for tasty feasts. Therefore, you decided to give the elves that are going to die delicious food so that they will die with no regret. The elves that wouldn't die will have their reservations cancelled, and receive a nifty coupon to spend some other day at your restaurant.

In other words, your goal is to distribute some of the dishes amongst some of the elves (possibly none), such that the sum of tastiness of the dishes eaten by the elves that are going to die is as large as possible.

The only issue is that you do not know when the so-called 'good gods' might interfere with your plan. Therefore, knowing that the $$$n$$$ elves will come to the restaurant in order, you have to solve this problem independently for the first $$$i$$$ elves, for all $$$1 \leq i \leq n$$$.

Every respectable contest must have a textbook graph problem. No convoluted processes, no weird observations; just pure, raw algorithmics. Lucky for you, you've just found it!

The picture above depicts the example test case.

You are given an undirected, weighted graph with $$$n$$$ vertices and $$$m$$$ edges, as well as $$$q$$$ queries of form $$$(a_i, b_i)$$$. For each of the queries, find the length of the shortest path between vertices $$$a_i$$$ and $$$b_i$$$.

Steve discovered a new RPG video game he really wants to play. This game is unique: players who can finish it optimally get their money back for the game! What a world for Steve to live in!

The game has $$$n$$$ realms. The player starts in realm $$$1$$$, with level $$$1$$$ and a chosen quantity of hit points.

Each realm has a number of mobs, each with a specific strength. In each realm, the player should choose to engage and fight one non-empty subset of the mobs present in that realm. The fight happens in a turn-based combat system. First, all alive monsters attack, each of them yielding a damage to the player equal to its strength. Then, the player chooses one of the engaged mobs and kills it (that mob won't attack the player ever again). Every kill levels up the player (up to level $$$m$$$).

Once all the engaged mobs in realm $$$i$$$ are dead, the player heals $$$h_l$$$ hit points (where $$$l$$$ is its level after killing all the mobs) and advances to realm $$$i+1$$$. Advancing from realm $$$n$$$ will finish the game. There is no limit on the number of hit points the player can have in the play-through.

Steve's goal is to finish the game at the maximum level $$$m$$$ without ever having $$$0$$$ or less hit points on its play-through. Steve must play optimally, meaning that he needs to choose the minimum starting quantity of hit points possible such that he can finish the game with max-level.

Jerry has a network of $$$n$$$ chambers connected by $$$n-1$$$ bi-directional tubes, such that any two chambers are (directly or indirectly) connected. In each of the chambers is a certain quantity of cheese. In chamber $$$i$$$ ($$$1 \leq i \leq n$$$) the cheese quantity is $$$c_i$$$. The network has an exit at chamber $$$n$$$.

A mouse is initially located in chamber $$$1$$$. At each step, the mouse will use its smell to detect the quantity of cheese in the neighbouring chambers, and will randomly choose to go through a tube with a likelihood proportional to the quantity of cheese in the corresponding chamber. The mouse will never consider going back to a previous chamber. If there's no next tube to choose, the mouse will get trapped.

Jerry wants to maximize the probability of the mouse to reach the exit. In order to do that, he may add cheese to any of the chambers. However, he can only add integral amounts of cheese to each chamber, and the total quantity must not exceed $$$x$$$.

How much cheese should Jerry add to each chamber, so that he maximizes the chances of the mouse escaping?

Nusret Gökçe is, by all means, one of the most valuable chefs to this date (at least, judging by the bills his customers have to pay). He is preparing his signature dish: the 24-karat gold steak (literally). He cooked the perfect medium rare steak with a shiny crust, cut it tenderly into $$$n$$$ pieces, and was about to sprinkle just a pinch of salt, when the unthinkable happened: his novice apprentice tripped next to the steak, spreading salt wildly throughout the steak pieces! Now, the otherwise perfect gold steak has $$$s_1, s_2, \ldots, s_n$$$ grains of salt, respectively on each of the slices.

Nusret nourishing his signature dish. Source: eater.com

Nusret isn't the one to throw away dishes (especially when they are worth their weight in gold); therefore, he decided to fix the steak instead. He cannot remove the existing salt without compromising the texture of the steak; instead, he will use his salt sprinkling skills and grain-level precision to add more salt to some of the $$$n$$$ slices in order to make the salt distribution more uniform.

He knows that the customer will eat the $$$n$$$ slices in order, and so they will not sense anything suspicious if the amount of salt between every two adjacent slices does not differ by more than $$$m$$$ grains. At the same time, he doesn't want to make the steak unnecessarily salty; therefore, he will sprinkle the salt in such a way that the total number of grains of salt is as small as possible.

How many grains of salt will be on each slice after Nusret "fixes" his signature dish?