brain

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 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 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 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.

The problem can be restated as follows. Mr. Black has a house with two sets of doors, each leading to a separate exit: left and right. Each door is initially closed, and we know the exact sequence in which Mr. Black opens them.

We are given a sequence of integers arranged in a line. In one move, we pick two neighboring positions and use the difference between their values to either increase or decrease one of them by exactly that difference.

We are given a single sequence, and we are told that it was originally formed by taking two hidden sequences and interleaving them.

We are given a connected undirected graph with n vertices and m edges. Our task is to assign a direction to every edge so that the resulting directed graph does not contain any path of length two or more.

We are asked to find the median string between two given strings of the same length, s and t, using lexicographical ordering. Both strings consist only of lowercase Latin letters, and s is guaranteed to be strictly smaller than t.

We are given a multiset of integers that was created by taking two sequences, one strictly increasing and one strictly decreasing, merging all their elements together, and then shuffling the result. The original order inside the merged array is lost.

We are given a sequence of integers, and we are allowed to remove elements one by one under a parity constraint that depends on the previous deletion. The first removed element can be anything.

We are given several short strings, and for each one we need to decide whether it forms a single continuous block of the alphabet without any gaps or repetition. Think of the lowercase alphabet as a line from ‘a’ to ‘z’.

We are given a single string of uppercase letters with length between 1 and 10. The task is to determine whether this string is "neat." A neat word, in this context, is defined as one where no letter appears more than once at even positions or more than once at odd positions.

This is an interactive game against a fixed but unknown opponent program. The opponent chooses one deterministic strategy at the beginning of the test and sticks to it for all 20 rounds.

We are given a small array of integers, each between 1 and 32, and we are asked to find a certain integer that represents the maximum number of consecutive elements that satisfy a bitwise property.

We are given a small supervised learning task disguised as a programming problem. There are 50 grayscale images indexed from 1 to 50. For the first 20 images, we are given binary labels indicating whether each image is considered a “Fourier doodle” or not.

We are given a single integer a between 0 and 15. This integer represents a configuration of a simple 4-bit circuit, where each bit can be either 0 or 1. The task is to compute an output integer based on a mysterious internal rule of the circuit.

We are asked to determine whether a given number can be represented as the sum of any number of integers equal to 4 or 7. The input is a single integer $a$ between 1 and 99, and the output is either "YES" if such a representation exists, or "NO" otherwise.

We start with an array whose length is a power of two. The allowed operation is very unusual: whenever the current array is not sorted in non-decreasing order, we may delete either its left half or its right half. After that, we repeat the same process on the remaining half.

We are given a set of $n$ points on a 2D plane, with the guarantee that no three points are collinear. From these points, we want to count the number of 5-point subsets that can form a pentagram-a star-shaped configuration where the points are connected in a specific…

We are given a rooted tree with n nodes, where node 1 is the root. Each node other than the root has a parent specified. A leaf is any node without children.

We are asked to assign heights to houses along a street in order to maximize total profit. The street has n available positions, each of which can host a house with an integer height between 0 and h. The profit from a house of height a is a^2. There are m city restrictions.

A frog starts at position 0 on a number line. From any position, it can move forward by adding a or move backward by subtracting b. However, during the process of exploring what is reachable, we only allow it to stay within the segment [0, x] when computing f(x).

We are given an array of integers and a series of queries. Each query instructs us to flip the sign of numbers in the array that satisfy a comparison: either all numbers greater than a threshold or all numbers less than a threshold.

We are asked to determine the diameter of an unknown weighted tree. The tree has n nodes connected by n-1 edges, each with a positive integer weight at most 100. We do not have direct access to the edges.

The game is played on a complete bipartite graph with two equal groups of vertices. Every vertex on the left side connects to every vertex on the right side, and each such edge has a unique weight.

We are given a hidden assignment of colors to numbered coins, where each coin is exactly one of three colors. The goal is to partition the coins into three groups so that each group contains coins of a single color, but we do not know the colors directly.

We are given a binary string pattern s consisting of '1', '0', and '?', with the guarantee that the first character is '1'.

We are working on a line of $n$ cells where a token starts somewhere and may move over time. Bob asks a sequence of queries, each query naming a cell, and Alice must always answer “NO” to every query.

We are asked to analyze a two-player game played on an array of piles, each containing some number of stones. There are $n$ piles, and $n$ is guaranteed to be even.

The problem gives a rectangular grid of characters representing a pattern on a metal plate, where each cell contains either a . (empty) or a (filled). The task is to find the smallest rectangle that contains all the characters.

We are asked to maintain an array that grows dynamically. On each operation, we append a new element to the array and immediately count the number of contiguous subarrays (segments) within a given range [l, r] whose mex equals a given number k.

We are given an array of integers placed on vertices of a complete set of labels. Between any two vertices we implicitly define an undirected edge if the two associated values share a nontrivial common divisor, meaning their gcd is greater than one.

We are given a permutation of the numbers from 1 to $n$, where $n$ is guaranteed to be even. A permutation means each number appears exactly once in the array. The task is to sort this permutation in ascending order.

We are given a collection of objects, each contributing a signed value and a binary mask. We must choose a positive integer s. Once s is fixed, each object is either kept as-is or flipped in sign depending on a parity condition computed from s and its mask.

We are given two multisets of integer positions on a number line. One multiset describes where stones start, the other describes where we want them to end.

We are given three pools of building blocks. There are a pieces of the letter string "a", b pieces of "b", and c pieces of "ab". We are allowed to select any subset of these blocks and concatenate them in any order we want.

We are given a collection of $n$ disjoint pairs of integers. Every integer from $1$ to $2n$ appears exactly once across all pairs, so each number belongs to exactly one pair and there is no overlap.

We are given two sorted timelines of flights forming a mandatory two-leg journey. A passenger first chooses a flight from A to B, spending a fixed travel time, and then immediately connects to a flight from B to C, again with a fixed travel time.