The wise turtles: Rafael, Leonardo, Donatello, and Michelangelo.

At the Latin American finals of the ICPC 2025 in Salvador, the organization visited the Tamar Project, where various sea turtles are rescued and cared for. Among them, four are especially respected for their wisdom and intellect: Rafael, Leonardo, Donatello, and Michelangelo.

The organization asked each of these turtles to create a plan on how they think the event's programming should be. Then, a vote was held to choose the winning plan. Each person could vote for only one turtle.

A turtle wins if it has more than half of the total votes.

So far, several people have already voted, but $$$N$$$ people have not voted yet, as they are late. The turtles then wonder: which of them still have a chance to win? After all, being wise, if a turtle has no chance of winning, it prefers to return to the sea and eat algae.

Your task is, given the current number of votes for each turtle and the number of remaining votes, to print which turtles can still win the vote.

Ber after winning the push-up competition. To achieve this, he did more than $$$250$$$ push-ups, with breaks of 30 seconds after every $$$50$$$.

In Astana, Kazakhstan, in 2024, the 48th edition of the ICPC (International Collegiate Programming Contest) took place. Along with it, the first push-up marathon in the history of the competition was held. The great champion was Bernardo Archegas from UNICAMP.

As everyone knows, winning a push-up marathon is not easy at all. To achieve this feat, Bernardo had to train with great discipline. For this, he used the GymRats app, which works as follows: every day he goes to the gym and does push-ups, he logs a visit in the app. Additionally, the app shows the longest streak of consecutive days he went to the gym without missing.

Your task is to implement this functionality of the app. Given the list of days (in increasing order) that Bernardo went to the gym, determine the length of the longest streak of consecutive days he attended.

Teams from UNICAMP at the beach of João Pessoa, in the Brazilian final of 2024

João Pessoa, the capital of Paraíba, is known for being the first city in Brazil to see the sun rise. On a special morning at Jacaré Beach, the locals were preparing for the famous sunrise spectacle accompanied by Ravel's Bolero. But there was a curious problem...

A local artist was preparing a decorative banner made only with parentheses '(' and ')', representing the movement of the sun on the horizon. The banner needed to be visually harmonious, meaning the sequence of parentheses had to be balanced. Formally, at every position in the banner, the number of opening parentheses up to that point must never be less than the number of closing parentheses. Some examples are "()", "(())()", or "()()(()()())".

However, when it came time to place the parentheses on the banner, he realized he had glued them in the wrong order! Since the total number of '(' and ')' is still correct and equal, the artist decided to cut the banner, removing some parentheses from the beginning and then sewing them to the end, without changing the order or direction. More formally, he performs a cyclic rotation — that is, moving some characters from the beginning of the banner to the end.

Your task is to help the artist figure out how many characters from the beginning need to be moved to the end for the sequence to become valid. It can be proven that under these conditions, there is always a valid rotation. If there is more than one way to do this, you may choose any of them.

Leal with his Arab scarf that he negotiated from 10 dollars to 1 dollar

In April 2024, two world finals took place in Luxor, Egypt, due to a delay from Covid. Egypt is known for many things, such as its rich history, stunning pyramids, and an intense bargaining culture. It is common to enter a store without any prices, and when asking how much something costs, the response is often "don't worry Habibi, choose everything you want and then we'll see the price." Because of this, the prices of items in stores vary greatly, ranging from dozens of dollars to just a few cents for others.

After his adventures in Egypt, Matheus Leal decides to open his own store. To do this, he makes a large purchase of various items, such as keychains, stones, sculptures, papyrus, and other souvenirs. Then comes the fun part: bargaining with customers, a battle of intellect and willpower to see who can get the best price.

However, at the end of each month comes the tedious part: doing the accounts. Throughout the month, Leal records all the purchase and sale amounts and has an array $$$A$$$ of size $$$N$$$, with values in cents. As a good computer scientist, Leal programmed his computer to sum the values in the given order. However, to his surprise, his program does not always work!

The reason is that Leal's machine has only $$$(x+1)$$$-bits, meaning that during his summation algorithm, the value can never exceed $$$2^x-1$$$ or be less than $$$-2^x$$$, otherwise he will experience overflow (or underflow), and the result will be incorrect!

Your task is to help Leal by reordering the list so that the sum never exceeds the limit values. If it is impossible, let Leal know!

This is a 100% true story that took place in 2024, during the first Latin American final.

Emanuel, from the team "teambrbr002", went to the airport in Belo Horizonte 10 hours in advance, where he would catch a flight to the city of Guadalajara, Mexico, for the first competition "Programmers of the Americas." After much conversation, problem-solving at the terminal, and a trip to Guarulhos, Emanuel heads to the immigration area when he encounters a terrible scene. Some evil being had swapped his passport for a work ID, both items being very similar, and now it is too late!

Emanuel manages to convince the airport staff to get a new ticket to Mexico, but it would be a long and lonely journey taking the route: SP -> MG -> home to get the passport -> SP -> Chile -> Panama -> Mexico.

Without internet and without his friends to talk to, Emanuel now only has some coins with him. He then decides to play an ancient game, passed down from generation to generation, which involves only a few coins — but can entertain (or trap) a player for countless hours.

Initially, the coins are placed in a row, some with heads (represented by the letter H) facing up, others with tails (represented by a T). In each turn, the player must:

• Choose any coin that is heads (H) up and flip it (turning it to T);
• For each coin to the left of the chosen one, he can individually decide whether to flip it or not.

After each turn, the player repeats the process with the new configuration of coins. The game ends when all the coins are tails (T) up, as there are no more possible moves.

But there is a legend that says that, depending on the initial configuration, the game can last forever, never reaching a final state.

Your task is to write a program that:

• Detects if the game can be played infinitely. In this case, print only -1.
• Otherwise, print the longest possible sequence of configurations of the coins after each valid move, including the initial state and the final state. If there are multiple maximum-length sequences, print any one of them.

Each configuration must be represented by a string of characters, containing only 'H' for heads and 'T' for tails, in uppercase letters.

The UNICAMP team won 1st place in the marathon in Chapecó, a feat achieved only $$$3$$$ other times so far. Indeed, it was a very happy moment for everyone at UNICAMP.

The Brazilian final of 2023 took place in Chapecó, being the first edition to qualify teams for the Latin American final.

During the competition, something tragic happened to the team "We Are Living a Dream": they finished in 16th place, but only the top $$$15$$$ qualified for Latam.

Moved by the situation, the SBC decided to conduct a survey to measure the happiness of each team after the competition, assigning each a happiness score between $$$0$$$ and $$$10^9$$$. After analyzing the data, a curious conclusion emerged: the happiness of the teams, as a function of the final placement, behaves like a non-increasing function from position 1 to the first position that does not qualify for Latam, and like a non-decreasing function from the first position that does not qualify to the last place.

To avoid further frustrations, the teams from Unicamp asked Carlinhos to reveal the number of spots available for Latam. However, Carlinhos explained that this information is confidential. Still, using his mysterious statistical methods, he agreed to answer questions by providing the happiness level of a team at a certain placement.

With these answers, the teams realized that it is possible to determine an interval containing all possible values for the number of spots — but they need your help to calculate this interval.

Example of happiness as a function of position. In the test cases, the coordinates are integers. Note that the shape of the curve can vary greatly, but it is guaranteed that it goes down and then up, possibly maintaining the same value at times.

Tuk-tuks performing radical maneuvers.

In the busy streets of Dhaka, the capital of Bangladesh, it is common to see small vehicles called tuk-tuks. These three-wheeled vehicles are a popular and agile form of urban transport, widely used by both locals and tourists. It was in this city that the world marathon final took place in November 2022.

Every year, Dhaka hosts a traditional tuk-tuk race that attracts the attention of the entire city. Unlike conventional races with laps and turns, this competition is quite chaotic and fun: at any moment, any tuk-tuk can perform a daring maneuver, earning points that may improve its ranking position.

You have been called to work with the judging team of the competition and are responsible for tracking the positions of the tuk-tuks throughout the race, noting every time a tuk-tuk advances in position. Unfortunately, one of the assistants forgot to record the score values of the tuk-tuks — both the initial scores and the points earned for each maneuver.

Now that the race is over, newspapers are demanding the complete data, and you urgently need to reconstruct a possible sequence of scores compatible with the position records.

In this task, you will receive two integers $$$N$$$ and $$$Q$$$:

• $$$N$$$ is the number of participating tuk-tuks. Initially, tuk-tuk $$$i$$$ is in position $$$i$$$ (with position $$$1$$$ being the best placement).
• Next, you will receive $$$Q$$$ updates. Each update informs that tuk-tuk $$$P$$$ has moved to position $$$X$$$, which is better than or equal to its previous position.

Your task is:

• To find a possible assignment of initial scores to the $$$N$$$ tuk-tuks;
• For each update, report how many points tuk-tuk $$$P$$$ earned in the maneuver that led to its new position;

You must ensure that the ranking remains consistent after each maneuver — that is, the tuk-tuks must remain ordered by score after each update.

All score values (initial and earned) must be in the range $$$[0, 10^9]$$$. Additionally, the final scores must also be within this range. Finally, you must also ensure that at all times the scores are distinct (there are no ties).

During the programming marathon in Campo Grande in 2022, Jake Peralta and his friend Charles Boyle took the opportunity to visit the Bioparque Pantanal, one of the largest freshwater aquariums in the world. There, they were enchanted by the variety of fish of various species.

While observing the tanks, Jake had an idea for a game: Boyle would randomly choose a fish (with equal probability among all), and Jake would have to guess which one it was by asking only yes-or-no questions.

Jake could ask anything he wanted: "Does the name of the fish have an even number of letters?", "Does the fish have blue scales?", "Is the fish native to Brazil?", and so on...

Being extremely strategic, Jake decided to follow an optimal plan, minimizing the expected number of questions needed to discover the chosen fish. However, since he is not that good with calculations, he asked for your help. Your task is: given the list of names of the fish in the aquarium, all with distinct names, calculate the expected number of questions that Jake will need to ask if he uses the optimal strategy.

Matryoshka dolls. Illustrative. In the problem, the dolls may be out of order and are in a single line.

During his visit to Moscow, Russia, in 2021, during the ICPC World Finals, Arthur entered a charming antique shop and came across a display case filled with Matryoshka dolls, famous Russian dolls that can be nested inside one another. The dolls were arranged in a line but did not follow any size order. Some were larger, others smaller, and some were exactly the same size.

Arthur decided to buy some dolls, choosing a continuous set of dolls to take home. However, since Arthur will have to check in his luggage, he began to worry about the strength of the group of dolls during transport. Arthur defined that the strength of a group of dolls is calculated as follows. Let $$$T_i$$$ be the size of the $$$i$$$-th doll, the strength of the set of dolls starting from doll $$$l$$$ to doll $$$r$$$ is given by:

$$$$$$ F = (r-l+1)^2 \cdot \min\limits_{k=l}^{r}\left\{T_{k}\right\} $$$$$$

That is, the number of dolls squared times the size of the smallest doll.

It is no wonder that Arthur is in the world finals, so calculating which group would be the strongest or weakest is too easy for him. Instead, Arthur wants to choose the group with the $$$K$$$-th smallest strength.

Formally, the sizes of each doll are given as an array of $$$N$$$ integers $$$T_i$$$. Among all $$$\frac{N(N+1)}{2}$$$ ways to choose a continuous sequence of dolls (i.e., subarrays), which one has the $$$K$$$-th smallest strength?

The Brazilian finals of the programming marathon in $$$2021$$$ were held in the charming city of Gramado, in Rio Grande do Sul. At the end of the competition, it became clear from the scoreboard that the contest had been particularly difficult: the champion team solved $$$8$$$ problems, and the second place — still with a gold medal — solved $$$6$$$, the same number of problems solved up to the 16th place.

With so many challenges, frustrations, and cloudy weather, many participants decided to console themselves in the best way that Gramado can offer: with hot chocolate.

Among them was Naim, one of the judges responsible for creating the problems for the contest. Already full of chocolates, he began to ponder about life, about the contest... and then he had a completely random thought:

"What if I had to choose $$$K$$$ memories from that contest — represented by pairs of values $$$A_i$$$ (how much I learned) and $$$B_i$$$ (how much it hurt) — in such a way that the total sum of learnings minus the greatest suffering was as high as possible?"

As crazy as it sounds, Naim now needs your help to solve this problem urgently, before he has another hot chocolate!

Formally, you are given $$$N$$$ pairs of integers $$$(A_i,B_i)$$$. A set $$$S$$$ has a learning value given by $$$v = \sum_{i \in S} A_i - max_{i \in S} B_i$$$. For every $$$K$$$ from $$$1$$$ to $$$N$$$, you must find the maximum learning value that a set $$$S$$$ of size $$$K$$$ can have.

During the pandemic of $$$2020$$$, the Brazilian Final of the Programming Marathon had to be held online. Before the competition started, participants could access the website, but the password would only be released when the competition began. Curious about security and programming, you decide to test a classic timing attack known as a timing attack.

The idea behind this type of attack is that, often, when comparing two strings, the verification function returns false as soon as it finds an incorrect character in the prefix. This means that the more correct characters you provide at the beginning of the string, the longer the response time tends to be. This problem is inspired by this principle.

// Function that compares if two strings are equal,
// stopping when any value in the prefix is different.
int isEqual(const std::string& a, const std::string& b) {
    if(a.size() != b.size()) return 0;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

You need to discover a hidden binary password, represented by a string $$$S$$$ of size $$$1 \leq N \leq 1000$$$, using only interactive queries.

• For each query, you send a binary string of size $$$N$$$.
• The judge will compare your string with the password $$$S$$$ and return an integer $$$T'$$$ based on the actual number of correct characters $$$T$$$ of the largest common prefix.
• The returned value $$$T'$$$ will be:
  • $$$T - 1$$$, $$$T$$$, or $$$T + 1$$$ with some fixed probability (not necessarily uniform).
  • If $$$T = 0$$$, the return will always be $$$1$$$ (never $$$0$$$ or negative).
  • If $$$T = 1$$$, the return will always be $$$1$$$ or $$$2$$$ (never $$$0$$$).
  • If the password is correct, the judge will return $$$1000000$$$ and you can terminate your program.
  • If you exceed the allowed number of queries or make an incorrect query, the judge will return $$$-1$$$.

You can use at most $$$3500$$$ queries.

The algorithm to obtain the largest common prefix is given below:

// a.size() == N and b.size() == N
int commonPrefix(const std::string& a, const std::string& b){
    int correct = 0;
    while(correct < N && a[correct] == b[correct])
        correct++;
    return correct;
}

Fmota (in the middle) and his friends after winning the Café Com Leite 2024. Source: https://maratona.sbc.org.br/hist/2024/JoaoPessoa/fotos/cafecomleite.jpg

The Brazilian final of 2019 was held in Campina Grande, Paraíba, where a living legend of Brazilian marathon studied. At UFCG, the legendary FMota studied, known by many as the Fastest Coder Alive Mota after managing to code Dijkstra from start to finish in less than 30 seconds. Since a very young age, he has participated in programming competitions and has accumulated several awards such as: two gold medals in the Senior OBI, champion of the first Latin American final in Mexico, and even Champion of the Café com Leite (CCL) 2024 competition in João Pessoa.

But with so much fame comes problems, and one of them is an overcrowded wardrobe. This is because, for every competition he participates in, FMota receives an exclusive t-shirt. Since he competes every year, he already has a huge collection that grows more and more each year.

Being obsessed with numbers, FMota likes to calculate how many distinct ways he can wear all his t-shirts over the next days until he exhausts his wardrobe. He does this by following a personal rule:

FMota wears one t-shirt per day and never repeats t-shirts until he has worn all of them from his wardrobe. Additionally, he wears the t-shirts from each competition in blocks, meaning he first wears all the OBI t-shirts (without repeating, in any order), then all the Marathon t-shirts (without repeating), and so on.

Given that he has an initial number of t-shirts from each competition, represented by the vector $$$C$$$, FMota wants to know how many different ways he can wear his t-shirts over the next $$$K + 1$$$ years (the current year plus $$$K$$$ future years). Each new year, he receives exactly one new t-shirt from each competition. Thus, in year 0 he has $$$C_i$$$ t-shirts from competition $$$i$$$, in year 1 he will have $$$C_i + 1$$$, in year 2 he will have $$$C_i + 2$$$, and so on.

Your task is to calculate how many ways FMota can wear the shirts from year 0 to year $$$K$$$. Since this number can be very large, print the answer modulo $$$998244353$$$. That is, if there are $$$x$$$ ways, you should print an integer $$$0 \leq x' \lt 998244353$$$ representing the remainder of the integer division of $$$x$$$ by $$$998244353$$$.