brain

We are given a small island country with n settlements and m bidirectional roads connecting them. Each road has a travel time which is either a or b seconds. The roads are initially connected in such a way that every settlement is reachable from every other settlement.

Working

We are given a string of parentheses that encodes a rooted tree via an Euler tour traversal. Every opening bracket corresponds to walking down an edge in the rooted tree, and every closing bracket corresponds to walking back up that same edge.

We are given a fixed base string, which we can think of as a long “universe sequence” of characters. Alongside it, there are three evolving strings, one per group.

We are given a bag of tiles, each labeled with either a 1 or a 2. Our task is to arrange all the tiles into a sequence so that when we calculate the prefix sums - that is, the sum of the first element, the sum of the first two elements, and so on - the number of sums that are…

We are given an $n times n$ square board, where some cells are occupied and others are free. The goal is to completely tile the free cells using identical pentomino pieces shaped like a cross: a center square with four adjacent squares, one in each cardinal direction.

We are given a very simple two-phase trading scenario. In the morning, there are several sellers offering unlimited quantities of the same stock at different buy prices. You can pick any one of these prices and buy as many shares as you want at that price.

We have a queue of students, each with two personal characteristics: $ai$, which measures how much they dislike people in front of them, and $bi$, which measures how much they dislike people behind them.

We are given a tree of n vertices arranged in a simple line, where each vertex has a value ai. Conceptually, this is just an array of numbers connected consecutively by edges.

We are asked to determine the probability that an array consisting of zeros and ones becomes sorted in non-decreasing order after performing a fixed number of random swaps. Each swap selects two distinct positions in the array uniformly at random and exchanges their values.

We are given a grid of integers where each row represents a set of choices, and from every row we must pick exactly one number. After picking one number per row, we compute the bitwise XOR of all chosen numbers.

The process generates a single infinite sequence by repeatedly appending blocks of numbers, where each block alternates between odd and even numbers and doubles in size each time.

We are given a string of uppercase Latin letters of length at least 4, and we want to transform some of its letters so that the substring "ACTG" appears somewhere.

We are asked to count sequences of planet visits with strong structural constraints. A path starts at any planet from 1 to n, and then performs exactly k − 1 moves.

We are asked to count ordered sequences of distinct planets visited by a character who starts on any planet and then makes exactly $k-1$ moves.

We are given two starting integers. From both numbers, we are allowed to shift them upward by the same non-negative amount $k$, producing the pair $a+k$ and $b+k$. For each such shift, we can compute the least common multiple of the two resulting numbers.

The problem describes a full trie built from all correct bracket sequences of length $2n$. Every node in this trie corresponds to a prefix of some valid sequence, and edges correspond to appending either an opening or closing bracket while maintaining validity.

The task is to reconstruct an array of positive integers, a, given two arrays b' and c'. These arrays were generated from a through two stages: first, by taking all consecutive pairs in a to form b and c, where each bi is the minimum and each ci is the maximum of the pair (ai…

We are given a positive integer x representing the "number" of a cat. Our goal is to transform x into a number of the form 2^m - 1 for some non-negative integer m. These numbers in binary consist entirely of 1s, such as 0 (empty longcat), 1, 3, 7, 15, and so on.

We are given a collection of treasure chests and a collection of keys. Each chest has a number written on it and each key also has a number written on it. A key can open a chest only when the sum of their numbers is odd.

We are asked to consider a line segment of length $l$. We randomly choose $n$ subsegments on this line. Each subsegment is determined by picking two points uniformly at random on the segment, so their endpoints may be non-integer.

We are given a hidden simple path drawn on an $n times n$ grid. The path represents a snake: it visits distinct cells, each consecutive pair shares a side, and the two ends of the path are special cells called the head and the tail. We cannot see the path directly.

We are given a rooted tree where every node either behaves like a minimum aggregator or a maximum aggregator. The leaves do not compute anything; they simply hold values.

We are given a 3-dimensional arrangement of unit bricks arranged in an $n times m$ grid. The height of bricks at position $(i,j)$ is unknown, but we are provided with three partial views: the front, the left, and the top.

We are given a string consisting of three types of characters: open parenthesis "(", close parenthesis ")", and question marks "?". Our goal is to replace each "?

Serval is going to the bus station at a specific time t. There are n bus routes, each with a first bus arriving at si minutes and subsequent buses every di minutes. Serval will take the first bus that comes after or exactly at time t.

We are given a row of n students, each with a distinct programming skill ranging from 1 to n. Two coaches take turns picking students to form their teams. On a coach's turn, they select the student with the highest skill remaining in the row.

We are given an array of integers and asked to find a pair of indices (i, j) such that the least common multiple (LCM) of the two numbers at these indices is as small as possible. The array can contain up to one million elements, and each number can be as large as ten million.

We have a shop with n shovels, each with a specific price. Misha wants to buy exactly k shovels, possibly in multiple purchases. The twist is that the shop offers special deals: if you buy exactly xj shovels in a single purchase, the yj cheapest among those shovels are free.

We control a robot that starts at position 0 on a one-dimensional axis and must try to walk up to position n. The robot has two power sources: a battery with capacity b and an accumulator (charged by a solar panel) with capacity a.

We are given four numbers that represent three pairwise sums of unknown positive integers $a$, $b$, $c$ and the sum of all three numbers. These four numbers are in no particular order. Our task is to reconstruct the original three integers $a$, $b$, $c$ from these sums.

Polycarp has a cat with a strict weekly eating schedule. The cat consumes fish food on Mondays, Thursdays, and Sundays; rabbit stew on Tuesdays and Saturdays; and chicken stakes on Wednesdays and Fridays.

We are given an array of integers. We must choose a single non-negative value D and then, independently for each element, either add D, subtract D, or leave it unchanged. The goal is to make every element become the same value after these operations.

We are given a simple undirected graph that is already 2-edge-connected. By Menger's theorem, this means every pair of vertices has two edge-disjoint paths between them, which is exactly the condition required by the two delivery companies.

We are given a single string made of lowercase English letters. We are allowed to choose one contiguous segment inside this string and reverse that segment exactly once. After performing this single reversal, we obtain a new string.

The problem gives us a hidden polynomial of degree at most 10 with integer coefficients, each strictly less than $10^6 + 3$. The task is to find an integer $x0$ such that the polynomial evaluates to zero modulo $10^6 + 3$.

We are given a sequence of integers and allowed to optionally pick exactly one contiguous segment and multiply every element inside it by a fixed value x.

We are given several event times, already sorted in increasing order. Ivan wants to configure an alarm clock that rings periodically. Once the first ring happens at minute y, the clock continues ringing at times: y, y + p, y + 2p, y + 3p, ...

We are given a digit string of odd length, and two players alternately delete single characters from it. The process continues until only 11 characters remain.

We are given a program written in a strange language where each variable has a short name of up to four alphanumeric characters, with the first character not being a digit.

We are repeatedly drawing cards from a multiset of values, without replacement. The only thing that matters is the sequence of drawn values, and how each value compares to the previous drawn value. The game behaves like this: the first drawn card just sets a baseline value.

We are given a permutation of the numbers from 1 to n. For every subarray [l, r], we look at its maximum value. The subarray is called special when the sum of the two endpoint values equals that maximum: $$pl + pr = max(pl,dots,pr)$$ The task is to count how many subarrays…

We are given a tree with n vertices, where each edge is labeled either 0 or 1. We need to count all ordered pairs of distinct vertices (x, y) such that, when walking along the unique path from x to y, we never traverse a 0-edge after we have already traversed a 1-edge.

We are given a short string of lowercase letters and we are allowed to reorder its characters arbitrarily. The goal is to produce an arrangement where no two adjacent characters differ by exactly one position in the alphabet.

We are given a sequence of geometric figures. Each number represents one of three shapes: - 1 = circle - 2 = isosceles triangle whose height equals its base length - 3 = square Every figure is inscribed into the previous one and is chosen with the largest possible size.

We are given a collection of points placed on a number line, and the goal is to form as many disjoint pairs as possible.

We are given a multiset of integers representing heights of people standing in a line. From these people, we must choose a subset and then reorder the chosen elements into a circular arrangement.

We are given an $n times m$ matrix containing only zeros and ones. We may flip any row and any column any number of times. Flipping means replacing every value in that row or column by its opposite. After all chosen flips are applied, the matrix is read in row-major order.

We are given a sequence of integers and must construct the longest possible strictly increasing sequence by repeatedly taking either the leftmost or the rightmost element. Each time we take a number, it is appended to our growing sequence and removed from the original sequence.

We need to distribute exactly n solved problems across k consecutive days. Let a[i] be the number of problems solved on day i. Every day must contain at least one problem.

We are given two arrays a and b, each of length n, containing integers from 0 to n-1. We can reorder b arbitrarily. After choosing an order for b, we construct a new array c where each element is (ai + bi) % n.

We are asked to explore numbers generated by repeatedly applying a particular transformation function. For a number $x$, we first add one to it. If the resulting number has trailing zeros, we remove them all until none remain. This defines the function $f(x)$.

We are given a number as a string of digits from 1 to 9 and a mapping f from each digit to another digit in the same range. The task is to maximize the resulting number by selecting at most one contiguous segment of digits and replacing each digit x in that segment with f(x).

We are given a permutation of size $n$. Think of it as a row of cards where every value from 1 to $n$ appears exactly once. At each move, we are only allowed to remove a card from either the far left or far right end of the current row, and we record the removed value.

We are given an array of positive integers, each bounded by a number $c$. The task is to examine all subsequences of this array and classify them by a number called their density.

We are asked to reconstruct an unknown tree with $n$ vertices by interacting with a device that allows a single type of query. Each vertex of the tree has a lamp, and the device lets us propose a set of distances $d1, d2, dots, dn$.

We are asked to reconstruct a permutation of numbers from 1 to n given a partially known array called next. Each element next[i] represents the smallest index j greater than i such that p[j] p[i]. If no such j exists, next[i] is set to n+1. If next[i] is unreadable, it is -1.

We are given a set of $n$ distinct points on the plane, with the guarantee that no three points are collinear. We need to order these points into a polygonal line such that two conditions hold: it never intersects itself, and at each internal vertex, the turn direction matches…

We have a party with $n$ boys and $m$ girls. Each boy gives some number of sweets to every girl, forming an $n times m$ matrix of integers. For each boy, the minimum number of sweets he gives to any girl is specified as $bi$.

We are asked to construct a binary string of length n such that the shortest substring appearing exactly once has length k. A substring is a consecutive segment of the string, and it is unique if it occurs in exactly one position.

We are given an array of non-negative integers. We define a property called a $k$-extension: an array is a $k$-extension if for every pair of elements $ai$ and $aj$, the inequality $k cdot The input consists of the length $n$ of the array, up to 300,000, and the array elements…

We have a street with n building positions. Every position can contain a house whose height is an integer between 0 and h. The profit from a house of height a is a², so taller houses are always better. The city imposes m zoning rules.

We are given a string c which represents a partially unreadable code. Some positions in c are readable lowercase letters, and others are asterisks representing unknown characters.

We are given a set of points on a plane, each representing a power pole. Every pair of poles defines a straight infinite line, and that line is considered a “wire”.

We are given a sequence of colors arriving over time, one per day. Each day contributes one occurrence of a color.

Shiro receives a cat every day, each cat wearing a ribbon of a certain color. The colors are integers from 1 to 10.

We are asked to transform a given string into a "good string" with the minimum number of deletions. A string is good if its length is even, and every pair of consecutive characters at positions (1,2), (3,4), etc., are different.

We are given two arrays of equal length, where one array is fixed and the other can be permuted arbitrarily. After choosing an ordering of the second array, we assign its values position by position against the first array.

We are given a binary string of length $n$, where each position behaves like a digit in a decimal number but is restricted to either 0 or 1. We are allowed to flip any digit as many times as we want, and each flip costs one operation.

We are given a set of stores, each selling an unknown positive integer, and a record of Dora's purchases over several days. On each day, she bought integers from some stores, while her rival, Swiper, bought from the remaining stores.

We are trying to construct a string of length $k$ that can be rearranged into a rectangular grid with $n$ rows and $m$ columns such that every row and every column contains all five vowels: a, e, i, o, u at least once.

We are given a set of integers representing potential values for two historical markers, $x$ and $y$. For each candidate pair of distinct integers $(x, y)$, we compute two intervals on the number line.

We are given a social network with n users and m groups of friends. Each group contains a list of users who are mutually friends with each other.

We are given a collection of integer pairs, each element ranging from 1 to some upper bound $n$. Our task is to find whether there exist two integers $x$ and $y$ such that every pair contains at least one of these two integers. In other words, $x$ or $y$ must "cover" every pair.

We are given a set of segments on the real line, each defined by its left and right endpoints. The task is to count subsets of these segments whose union exactly equals the union of all segments.

We are given a sequence of daily website visit counts. Each position represents one day, and the value at that position represents how many visits occurred on that day. We need to examine every day and decide whether it is “bad”.

We are asked to count how many ways we can place the nodes of a given tree around a circle such that the edges, drawn as straight lines between nodes, do not cross. The tree has n nodes labeled from 1 to n, and n-1 edges connecting them.

The problem asks us to determine the outcome of a simple voting scenario. There are three categories of voters: some are guaranteed to upvote, some are guaranteed to downvote, and some are undecided. The input gives the counts of each group.

We are asked to consider all permutations of the numbers from 1 to $n$. For each permutation, we define a sequence of prefix greatest common divisors (GCDs). Specifically, for the permutation $p = [p1, p2, ..., pn]$, we calculate $gi = gcd(p1, p2, ..., pi)$ for $i$ from 1 to $n$.

We are given a sequence of numbers, and we are allowed to reorder it, but with a restriction on how swaps work. A swap is only legal if we pick two positions whose values have opposite parity, meaning one is odd and the other is even.

We are asked to partition an array of integers into exactly $k$ contiguous subsegments such that the total weight is minimized. The weight of a segment is defined as its length multiplied by its maximum element. The total weight is the sum of weights over all segments.

We are given a collection of line segments on a number line and multiple queries asking about subranges. For each query segment $[x, y]$, we want to know the smallest number of given segments whose union fully covers every real point from $x$ to $y$.

We are asked to select an integer point $x$ on a line such that the $(k+1)$-th smallest distance from $x$ to a given set of points is minimized. Each query gives us $n$ sorted integers $a1, a2, dots, an$ representing points on the $OX$ axis, and an integer $k$.

We have a simple program written in a tiny language with three commands: add, which increments a variable x by 1; for n, which starts a loop that repeats the commands inside it n times; and end, which closes a loop.

We are given a sequence of turns in a card game. On each turn, the player receives a set of cards, each with a cost and a damage value. The player can play any subset of cards in that turn as long as the total cost does not exceed 3. After the turn, unused cards are discarded.

We are given a starting integer and we are allowed to repeatedly shrink it using a small fixed set of divisibility operations. Each operation replaces the current value with a smaller value, but only if the current value is divisible by a specific number: 2, 3, or 5.

We are asked to consider the infinite string formed by writing all positive integers consecutively without any separators: "1234567891011121314…". Given a position $k$, we must determine which digit occupies that place.

The final strip consists of n unit segments, and because n = m in this subtask, every colour from 1 to n appears exactly once. The input array is simply a permutation describing the visible colour on each unit segment after all repainting operations have finished.

We are given a string made only of two characters, v and o. We need to count how many subsequences of this string form the pattern "wow". A subsequence means we pick indices in increasing order, not necessarily contiguous, and read the characters at those positions.

There are several political parties, and the first party belongs to Alice. She wants to form a coalition that always contains her own party and may contain some additional parties. The coalition must control more than half of all seats in parliament.

We are given a deque containing n integers. Valeriy repeatedly performs an operation where he removes the first two elements, compares them, and then reinserts them: the larger of the two goes to the front, and the smaller goes to the back.

We are tasked with simulating a school dining room where each dish has a single copy and each pupil buys the most expensive dish they can afford. Serge, our protagonist, wants to know which dish he will get if he waits until all pupils have made their purchases.

We are given a shape that grows on a grid starting from a single cell. At the first stage there is exactly one cell. At every next stage, the shape expands by attaching every grid cell that shares an edge with any cell already in the shape.

We are given n castles on a 2D plane, each represented by an axis-aligned rectangle with integer coordinates. Each castle originally belonged to a country whose territory was also a rectangle.

We are given a long positive integer as a string of digits, and we need to split it into two non-empty integers such that neither starts with a zero. The goal is to minimize the sum of these two integers after splitting.

We are given a tree with $n$ vertices, described by $n-1$ edges. A tree is a connected graph without cycles. The task is to choose a vertex as a root such that all vertices at the same distance from the root have the same degree, where degree counts the number of edges…

We have a board with 3 rows and $n$ columns. The only pieces available are dominoes of size $2 times 1$, which may be placed either vertically or horizontally.

We start with a string and want to build a set containing exactly k distinct subsequences. Adding a subsequence of length L costs the number of removed characters, which is n - L. The same subsequence cannot be added twice.

We are given a positive integer and we want to find the smallest integer that is not smaller than it such that the sum of its digits is divisible by 4.

We have a line of universes arranged sequentially, each numbered from 1 to $n$, with the Doctor starting at position $k$. The multiverse can change over time according to a series of operations.