brain

We are given a permutation of the numbers from 1 to n. Each query asks for a recursively defined function over a subarray. Specifically, for a range [l, r], we first find the position of the maximum element in that range.

We are given a string t of length n which is the result of applying an unknown sequence of swaps to an original string s. Each swap exchanges two characters at positions ai and bi in s.

We are counting ways to build a final sequence of unit-sized positions whose total length is exactly $N$. Each position can be either a normal gem or the result of splitting a magic gem.

We are given a set of emotes, each with a positive happiness value. We are allowed to use emotes a fixed number of times, but no single emote can be repeated more than a given number of times consecutively.

We are given a starting point on an infinite grid and a target point. Each day, the environment produces a wind direction from a fixed periodic string. That wind shifts the ship by one unit in one of the four cardinal directions.

Polycarp needs to buy exactly $n$ liters of water using bottles of two fixed sizes: 1-liter bottles at cost $a$ and 2-liter bottles at cost $b$. For each query, we are asked to determine the minimum total cost to acquire exactly $n$ liters.

We are given a tree with $n$ vertices. Each vertex is either colored with one of $k$ colors or left uncolored. The tree is connected, so there are $n-1$ edges. We are asked to select exactly $k-1$ edges and remove them, splitting the tree into $k$ components.

We are tasked with assigning colors to dancers at a ball. There are n pairs, each consisting of a man and a woman, and k available colors.

We are given a tree with n vertices, where each vertex may be colored red, blue, or left uncolored. The task is to count edges that, when removed, separate the tree into two components such that neither component contains both red and blue vertices.

Polycarp must write a coursework of m pages, but he cannot work indefinitely without caffeine. He has n cups of coffee, each with a caffeine dosage ai.

We are given a collection of coffee cups, each with a fixed caffeine value. Polycarp can choose some of these cups and distribute them across several days.

We are asked to arrange n^2 integers into an n x n square matrix so that the matrix is palindromic along both axes. A palindromic matrix does not change when we reverse the order of rows or reverse the order of columns.

We are given an array of weights where each index represents a candy. Tanya will remove exactly one candy and then consume the remaining candies strictly in index order, one per day starting from day 1.

For every triple $(ai,bi,ci)$, we build an array that contains $ai$ exactly $x$ times, $bi$ exactly $y$ times, and $ci$ exactly $z$ times. From each of the $n$ arrays we choose one value. The XOR of all chosen values is some number $t$.

We are given a situation where Evlampy has n identical soldiers and must fight an enemy army composed of m groups, each with a certain health hpi.

We are given a weighted tree. For every degree limit $x$, we may delete any set of edges. Deleting an edge pays its weight. After all deletions, every vertex must have degree at most $x$. For each $x$, we need the minimum total deleted weight.

We are given many sticks whose lengths are powers of two. For each exponent i, there are ai sticks of length 2^i. Each stick can be used at most once, and we want to form as many non-degenerate triangles as possible, where each triangle uses exactly three sticks.

The fridge has height h and exactly two columns. Shelves can be inserted at any heights, which means we are free to divide the fridge into horizontal compartments of arbitrary heights. Each bottle occupies one column and has height a[i].

We are given two matrices, A and B, of size n × m filled with 0s and 1s. We can modify A by repeatedly selecting any submatrix of size at least 2 × 2 and flipping its four corner values.

We are given a street with n houses in a row, numbered from 1 to n, where each house has a color represented by an integer. Ilya wants to pick two houses of different colors and walk between them, measuring the distance simply as the difference in their indices (j - i) for i < j.

I can't responsibly write a complete editorial and solution for Codeforces 1120F from the problem statement alone.

We are given a rooted tree with n vertices, where each vertex has a non-negative price. The root is vertex 1. Leaves are non-root vertices with degree one.

We are asked to determine whether a positive integer $n$ exists for a given integer $a ge 2$ such that multiplying $n$ by $a$ reduces its digit sum by a factor of $a$. Formally, we want $S(an) = S(n)/a$, where $S(x)$ is the sum of digits of $x$.

We are given a string and two costs. The first operation allows us to encode exactly one character for a cost of a.

The town of Shortriver has a single, very long liana of flowers. Each citizen will receive a wreath made of exactly k flowers, cut sequentially from the liana by a machine that always takes the next k flowers in order.

We are given two equal-length decimal strings, representing numbers written digit by digit. The task is to transform the first number into the second one using a very specific operation applied to adjacent digit pairs.

We have a situation that models parallel system testing in a contest setting. There are n solutions submitted to a contest. Each solution i requires a[i] tests to be fully verified.

We are given a collection of distinct positive integers representing candy sizes. Each child must receive exactly two different candies, and the “happiness level” of a child is defined as the sum of the two candies they receive.

We are given a set of students, each belonging to a school, and each with a power rating. The tournament rule is simple: only the strongest student from each school gets selected. Arkady wants to ensure that a chosen set of k students are selected.

We are asked to reconstruct an unknown tree of $n$ vertices by asking a limited type of query. The query is interactive: for any two disjoint, non-empty sets of vertices $S$ and $T$, and a chosen vertex $v$, we receive the number of pairs $(s, t) in S times T$ such that the…

We are asked to count how many ways we can split a given array of integers into contiguous, non-empty segments such that, in each segment, the number of integers that appear exactly once does not exceed a given threshold $k$.

We are asked to construct an array of integers such that a particular greedy algorithm gives a wrong answer by an exact amount.

We are asked to track sequences of English letters encoded in Morse code as we build a string incrementally, one character at a time. The string S starts empty and grows by adding either a dot (0) or a dash (1) at each step.

We have n stations arranged on a directed cycle. From station i, the train always moves to i + 1, and from station n it wraps back to station 1. Every move between neighboring stations costs exactly one second.

We have a circular train network with n stations, numbered from 1 to n. A single train moves from one station to the next in order, looping back to station 1 after station n, taking exactly 1 second per move.

We are given an array containing positive numbers, negative numbers, and possibly zeros. We need to choose a non-zero integer $d$ such that after dividing every element by $d$, at least half of the array elements are positive.

We are given a street with $2n$ consecutive houses, each house selling exactly one cake tier of a specific size between $1$ and $n$. Every size appears exactly twice. Two people start at house $1$.

We are given a square grid representing a planet with land and water. Alice starts at one land cell and wants to reach another land cell. She can only walk on land, moving orthogonally between adjacent cells. If a path exists naturally, she can reach her destination at zero cost.

We are given a long line of dominoes. Each domino has a height and a cost. When you push a domino, it falls either left or right, and during its fall it can trigger other dominoes if they lie within its reach.

We are given a set of kittens, each initially in its own cell arranged linearly in a row. Over the course of $n-1$ days, Asya records pairs of kittens who wanted to play together and removes the partition between their cells.

We are asked to compute a property of a highly structured string operation. We are given a sequence of strings $p1, p2, dots, pn$, and we are asked to repeatedly apply Denis's string multiplication: multiplying $p1 cdot p2 cdot dots cdot pn$ in order.

The problem asks us to assign positive integer scores to two sets of dishes tasted by Mr. Apple on two separate days. Each dish on the first day can be compared to every dish on the second day, and the comparison is either better, worse, or equal.

The ship is formed by stacking two axis-aligned rectangles. The lower rectangle has width w1 and height h1. The upper rectangle has width w2 and height h2, and it starts immediately above the first rectangle with their left edges aligned.

We are asked to arrange a group of children in a circle such that the maximum height difference between any two adjacent children is as small as possible. The input provides the number of children n and an array of their heights.

We are given a sequence of partial observations of a football match. Each observation tells us the score at some moment in time, and these observations are already sorted by time.

We are given a long array of integers and a fixed window size. For every contiguous segment of length k, we are asked to simulate a very specific process that builds a subsequence of indices.

We have a string of lowercase letters. In one operation, we may choose any contiguous block whose characters are all the same and remove it. After removal, the remaining parts of the string join together.

We have a contest with n students, each with a laptop that starts with some initial battery ai and consumes bi units of charge per minute. The contest lasts k minutes.

We are given a multiset of items where every item has a weight between 1 and 8 inclusive. The number of items of each weight is extremely large, but only their counts matter, not their identities.

We have a fence with n sections numbered from 1 to n. Each painter covers one continuous interval [li, ri]. Originally all q painters are available, but we are forced to dismiss exactly two of them and keep the remaining q - 2.

We have a set of chocolate bars, each with its own price. The shopper wants all the bars but has a selection of discount coupons. Each coupon allows buying a fixed number of bars, but within that selection, the cheapest bar is free.

We are given four types of bracket strings, each of length two: "((", "()", ")(", and "))". The input provides counts of how many of each type we have.

We are given a connected undirected simple graph and asked to construct a spanning tree using only existing edges. The additional constraint is that vertex 1 must have degree exactly D in the chosen tree.

We are given a connected undirected graph and must select exactly $n-1$ of its edges so that they form a spanning tree. Among all possible spanning trees, we want one whose largest vertex degree is as large as possible. A spanning tree connects all vertices without cycles.

We are given two arrays of integers, a and b, each with n elements. We are asked to construct a new array c using a single real number d such that each element ci equals d ai + bi. Our goal is to choose d to maximize the number of zeros in c.

We have a list of students, each with a programming skill level. The task is to divide these students into at most k teams so that the total number of students included is maximized.

We are given a set of candy boxes, each containing a certain number of candies, and a number k representing the group size for which we want to prepare gifts. A gift consists of exactly two boxes, and the sum of candies in the two boxes must be divisible by k.

We have a list of students, each with a programming skill score. The task is to form the largest possible team such that the difference between the highest-skilled and lowest-skilled members does not exceed 5. In other words, for any team of size $k$, if the skills are $s1, s2, .

The task is to find the exact midpoint of a contest given its start and end times in hours and minutes. The input gives the start time as h1:m1 and the end time as h2:m2.

We have an array a and another array k. The array always satisfies a monotonic-type constraint: $$a{i+1} ge ai + ki$$ for every adjacent pair. There are two operations. The first operation increases one position a[i] by some value x.

The queue is fixed initially, and the last person in the queue is Nastya. Some ordered pairs $(u,v)$ are given. A pair means that whenever pupil $u$ stands immediately in front of pupil $v$, those two pupils are willing to swap places.

There are n manholes arranged in a line. Each manhole initially contains exactly one stone on top of it and one coin underneath it. Nastya starts at manhole k. A coin can only be collected when the current manhole has no stones on it.

We are given two matrices of the same size, A and B. The allowed operation is surprisingly powerful: we may choose any square submatrix inside A and transpose it. Transposition swaps positions relative to the square's main diagonal.

The book is divided into consecutive chapters. Each chapter occupies a continuous range of pages, and every page belongs to exactly one chapter. Nastya has already read pages 1 through k - 1. Page k is the first page she has not read yet.

We are asked to simulate a train that grows and whose car values evolve over time. Initially, there are $n$ cars numbered from the head.

We are asked to coordinate ten players on a secret graph consisting of a directed path leading to a cycle. The path has length t, ending at the start of a cycle of length c, which represents a scenic lake road. Every vertex has exactly one outgoing edge.

We are given a tree of n vertices, each with a unique integer priority initially equal to its label. We can imagine burning the tree in a particular order: repeatedly remove the leaf with the smallest priority until no vertices remain.

We are given two binary strings. The first string s is not the schedule we must output directly. Instead, it acts as a multiset of characters.

We are given a city laid out as a grid of size $n times m$, where each cell represents an intersection containing a skyscraper of a certain height.

We are asked to plan a tour starting from city 1 on the first day of a week, aiming to visit as many distinct museums as possible. Each city has exactly one museum, and museums have a weekly schedule specifying on which day of the week they are open.

We have a troupe of n circus artists, where n is guaranteed to be even. Each artist may have the skill of being a clown, an acrobat, both, or neither.

We are given a row of sushi pieces, where each piece is either type 1 or type 2. We want to choose one contiguous segment of this row. A segment is valid if it consists of two consecutive blocks of different sushi types, and both blocks have the same size.

We repeatedly choose a random integer from 1 to m, independently and uniformly. After each choice, we look at the gcd of all numbers chosen so far. The process stops as soon as this gcd becomes 1. We must compute the expected number of chosen integers.

Each student belongs to exactly one club and has a potential value. On a given day, some students have already left their clubs permanently. From the remaining students, we may choose at most one student from each club. The chosen students form the contest team.

We are asked to determine how many dishes each person in a city can buy given multiple constraints. Each dish has a price, a minimum standard requirement, and a beauty value. Each person has an income and a preferred beauty.

We have a set of chocolate types, each with a limited stock. Our goal is to pick a number of chocolates from each type so that the total number of chocolates is maximized.

We have a tree whose edges are colored either red (0) or black (1). We must count how many sequences of length k consisting of tree vertices are "good". For a sequence [a₁, a₂, ...

We are given a string of digits from 1 to 9. Our task is to count how many substrings, defined by any contiguous range of indices, represent even numbers. A substring is even if its last digit is even, since the number’s parity is determined entirely by the last digit.

We are given a graph on $2n$ vertices that is highly structured: vertices are split into odd and even indices, and each side forms a tree with the same shape.

We are maintaining a dynamic set of grid points on a large integer lattice. After each insertion or deletion, we are asked to compute not the size of the current set, but the size of its closure under a specific completion rule.

We are asked to count the number of arrays we can construct from a partially specified array of length n, where some elements are missing and represented by -1. Each -1 can be replaced by any integer from 1 to k.

We are given a regular polygon with n vertices labeled 1 through n in counter-clockwise order. The goal is to divide this polygon into non-overlapping triangles so that the sum of the “weights” of all triangles is minimized.

We are given a string made only of two symbols, and <. We are allowed to repeatedly perform operations that “push deletions” in a local direction: choosing a removes the character immediately to its right, while choosing a < removes the character immediately to its left.

Each song has two attributes: its length t and its beauty b. If we choose some subset of songs, its score is $$(text{sum of lengths}) times (text{minimum beauty})$$ We may choose at most k songs, and we want the maximum possible score.

Ivan’s detective book is structured such that each page introduces a mystery, and the solution to that mystery is revealed on a later page. Concretely, we have a list of integers where the $i$-th integer $ai$ tells us the page that resolves the mystery introduced on page $i$.

We are given a tree with $n$ vertices and $n-1$ edges. Every edge must be assigned a company number. A city is considered good if all roads incident to it belong to different companies. A city becomes bad if at least two incident roads receive the same company.

We are given a one-dimensional array of integers, and we want to split it into contiguous subarrays, which we call blocks. Each block must have the same sum of its elements, and no two blocks can overlap.

We are given two sets of boots: one left set and one right set, each containing exactly $n$ boots. Each boot has a color, either a specific lowercase letter or a question mark representing an unknown color.

We are given an array of integers and may choose several contiguous subarrays, called blocks. Every chosen block must have exactly the same sum, and no two chosen blocks may overlap.

We are given a monster with an initial health value and a repeating damage pattern applied once per minute. The pattern has length n, and after the last minute we immediately loop back to the first minute and continue forever.

We start with a number and want to reach a larger target number. The only allowed operation is multiplying the current value by 2 or by 3. The task is to determine how many operations are needed, or report that the transformation cannot be done.

We are given a sequence of differences between consecutive elements of an unknown permutation. More precisely, if the permutation is $p1, p2, dots, pn$, we are given an array $q$ of length $n-1$ such that each $qi = p{i+1} - pi$.

We are given a binary sequence representing a single day, where each position corresponds to an hour. A value of 1 means Polycarp is resting during that hour, while 0 means he is working.

We are given a complete undirected graph on $n$ nodes, but each edge is assigned a direction, making it a tournament. A subset of these edges are colored pink and their directions are known. The remaining edges are green, and their directions are initially unknown.

We are given a long digit string that was formed by writing several integers back to back without separators. Each contiguous substring of this string can be interpreted as an integer (with no leading zeros unless the substring is exactly "0", though here the input guarantees…

We are given a fixed permutation of numbers from 1 to n. Separately, we have a longer array whose elements also lie in the range 1 to n, but may repeat. The task is to answer many queries on subsegments of this array.

We are given a set of points on a two-dimensional plane with integer coordinates. For each pair of points that do not share the same x-coordinate, we can uniquely define a parabola of the form $y = x^2 + bx + c$ that passes through both points.

We are given a circular route that passes through $n cdot k$ cities arranged consecutively. Among these, there are $n$ fast food restaurants evenly spaced such that the distance along the circle between any two consecutive restaurants is $k$ kilometers.

We are asked to find, for a given integer $n$, the largest product of digits that any number from 1 to $n$ can have. In other words, imagine iterating through all numbers from 1 up to $n$ and multiplying the digits of each number; we want the maximum such product.

We are given a rooted tree with n vertices. Each vertex has a parent pi and a respect indicator ci. The root is special: it has pi = -1 and ci = 0.