brain

We are asked to simulate a limited-edition shop where Alice and Bob take turns picking items, but with a twist: we do not control who goes first or in which order they enter. Each item has a value according to us, and Alice and Bob each have a personal ranking of the items.

Let $m = 2^e$ and consider the modified middle-square sequence defined by Coveyou: $X0 text{ given}, qquad X{n+1} = operatorname{middle}(Xn^2 + 2^{e-1} Xn), eqno(4)$ where the function $operatorname{middle}(cdot)$ extracts the middle $2e$ bits of the argument in double precision.

We are given a virtual strip with cells numbered from 1 to $10^9$, where some cells are initially black and the rest are white. Multiple people start from cell 1, and each executes a prefix of a command string composed of two instructions.

We are given a sequence of 2n timestamps representing moments when visitors passed through a single museum door. Each timestamp corresponds either to an entrance or an exit, but the sensor cannot distinguish which.

We are given a set of sliders on a one-dimensional track, each occupying a single position. The sliders are initially ordered left to right, with no overlaps. Each operation attempts to move a particular slider to a target position.

We are working with a rooted tree where every vertex will eventually be assigned either a zero or a one, but the assignment is not fixed. We only know how many zeros must appear overall, while the remaining vertices become ones.

We are given a rooted tree with n vertices, where each vertex must be labeled either 0 or 1. Exactly k vertices are labeled 0, and the remaining n-k are labeled 1. The tree's root is vertex 1, and each other vertex has a specified parent.

We are given a permutation and asked about many contiguous segments of it. For each segment, imagine trying to sort it into increasing order.

Maple has multiple ovens, each producing cakes at a fixed rate per second. She can collect all the cakes from one oven at the end of each second, and she can teleport to any oven, including the one she is already at.

The solution correctly interprets the problem. A "gap of length $r$" is the number of consecutive $U$’s falling outside $[alpha, beta)$ before the next $U$ falls inside that interval.

We are interacting with a text editor whose behavior depends on a hidden parameter $W$, the width of a line. An article is a sequence of word lengths, and the editor lays words into lines greedily: it fills the current line until the next word would overflow $W$, then starts a…

We are given an undirected connected graph where each vertex carries an integer label. Some labels are fixed, while others are unknown and must be chosen from the range $0$ to $V-1$. For any simple path, we define its value as the XOR of all vertex labels along that path.

We are given an interactive editor that wraps words into lines based on a hidden width parameter $W$. Each article is represented as a sequence of word lengths.

Let $p = beta - alpha$ be the probability that a single $Uj$ lies in the interval $[alpha, beta)$, as in equation (4). A gap of length $r$ occurs when $r$ consecutive $U$'s fall outside $[alpha, beta)$, followed by a $U$ inside the interval.

We are asked to construct a permutation of length $n$ that satisfies a positional maximum constraint determined by a binary string $s$ and an integer $k$.

We are given an array of integers, and our goal is to extract the longest possible subsequence that is "neat." A neat subsequence is made by concatenating one or more blocks, where a block is a sequence of identical numbers, and the value of the number equals the length of the…

We are asked to count permutations that produce a given scoring pattern in a dynamic coloring process. Think of it as a row of white cells indexed from 1 to $n$.

We are asked to reconstruct a hidden sequence of parentheses of length $n$ using an interactive oracle. The sequence contains only '(' and ')' characters and is guaranteed to have at least one opening and one closing bracket.

We are given a hidden sequence of parentheses of length n, containing at least one '(' and one ')'. The sequence is regular in the sense that some of its contiguous substrings are valid bracket sequences.

In the original interactive problem there is a hidden bracket sequence consisting of '(' and ')'. We may ask queries about selected positions, and the judge returns the number of regular bracket substrings in the constructed string.

We are given a permutation of length $n$, which means an array containing every integer from $1$ to $n$ exactly once. For each element in this permutation, we are allowed to either leave it as is or replace it with a "mirrored" value defined by $2n - pi$.

We are given an array of integers where each element is either 0, 1, or 2, and a target sum s. Alice wants to start at the first element and move either left or right, step by step, until she reaches the last element.

We are given a set of integer pairs, each representing both a segment on a number line and an edge in a graph. Our goal is to select a subset of these pairs to maximize the difference between the total length of covered integers, called $f(S')$, and the number of nodes that…

The problem can be reframed as follows. Gellyfish faces a group of n monsters, each with a given HP hi. She wants to reduce every monster's HP to exactly 1. She has m rounds of attacks, and in each round a special sword may “shine” with probability p.

In this problem, we have a sequential two-player game with a numeric twist. Each round has a pair of numbers, one from array a and one from array b. There is also a binary string c that decides whose turn it is.

We are given a length-n array that evolves under q operations. Each operation takes two indices x and y, computes the smaller of their current values, and writes that value into a third position z.

We are given two permutations p and q of the numbers 0...n-1. For every position i, we must evaluate all pairs of indices (j, i-j) such that 0 ≤ j ≤ i, and compute $$2^{pj}+2^{q{i-j}}$$ Among all these candidates, we take the maximum and store it in r[i].

We are given an array of positive integers. In one operation, we choose two different positions and replace one value with the gcd of the two values. The process may be repeated as many times as needed.

We are asked to predict the winner of a turn-based duel between two players, Gellyfish and Flower. Each player has a main character and a knight, each with its own health points (HP). Gellyfish has a HP, Flower has b HP, Gellyfish's knight has c HP, and Flower's knight has d HP.

We are given a permutation and asked to count how many of its contiguous segments have a very specific structural property involving order.

We have a permutation and a single allowed operation on four consecutive positions: $$[ai,a{i+1},a{i+2},a{i+3}] rightarrow [a{i+2},a{i+3},ai,a{i+1}]$$ Viewed differently, the element at position $i$ swaps with $i+2$, and the element at position $i+1$ swaps with $i+3$.

We are asked to maximize the "beauty" of a derived array based on an input array. The input array a gives an upper bound on each element of a new array b, which must have the same length. Each element of b satisfies 1 ≤ bi ≤ ai.

We are asked to place all integers from $0$ to $n^2 - 1$ into an $n times n$ grid, each number used exactly once.

We are given two binary strings of equal length. We are allowed to repeatedly apply a structured operation that splits a string into two halves and then either mixes the halves coordinate-wise using XOR, or recurses into both halves and applies the same process independently.

Working

We are asked to model a simplified version of the Bermuda Triangle as a right triangle on a 2D coordinate plane, with vertices at $(0,0)$, $(0,n)$, and $(n,0)$. A plane starts inside this triangle at $(x,y)$ and moves with a velocity vector $(vx,vy)$.

Each student fixes a specific day, and Vadim is essentially trying to “predict” what will happen on the next two days after that chosen day.

We are asked to simulate a sequential key-and-lock game among n players. There are l locks, each with a unique corresponding key, and k counterfeit keys that do not open any lock.

We are given two sequences of integers, a and b, both of length n. Each element of a represents some resource or quantity that we want to reduce to zero, and each element of b represents a capacity or counter-resource.

We are asked to calculate the expected number of successful key-lock matches for each participant in a turn-based game. There are $n$ members taking turns sequentially, $l$ locks, and exactly $l$ keys (since $k = 0$ in this easy version). Each key opens exactly one lock.

We are given two sequences of integers, a and b, both of length n. The goal is to reduce all elements of a to zero by performing a repeated operation called a round.

We are given the final occupancy pattern of a grid after some sequence of ball insertions. A ball can be pushed either from the left side of a row or from the top side of a column. The ball travels forward until it reaches a cell. If that cell is empty, it stays there.

The dining hall is an infinite grid of cells. Some of these cells are grouped into tables, each table occupying a 2×2 square located at coordinates of the form $(3x+1,3y+1)$ through $(3x+2,3y+2)$, and all other cells are corridors.

We are asked to construct a permutation of the first $n$ positive integers such that a sequence derived from it has many prime numbers. Specifically, for a permutation $p1, p2, dots, pn$, we define $ci = lceil frac{p1 + p2 + dots + pi}{i} rceil$.

We are asked to compute the minimum spanning tree (MST) of a complete graph, but the edge weights are unusual. Each vertex has an associated weight $pi$, and the weight of an edge between two vertices $x$ and $y$ is defined as $max(px, py) bmod min(px, py)$.

We are given a matrix where each cell contains a number between 0 and 3. The task is to transform this matrix into what the problem calls a "good" matrix. A matrix is good if the XOR of all elements in every row is zero and the XOR of all elements in every column is zero.

The only thing that matters about the original array is the sign of every adjacent comparison. For each position $i$, define an edge between $ai$ and $a{i+1}$. If $ai < a{i+1}$, call the edge positive. If $ai a{i+1}$, call the edge negative.

We start with an integer value and must perform two kinds of halving operations a fixed number of times. One operation replaces the current value with the floor of half the value. The other replaces it with the ceiling of half the value.

We are given a positive integer in binary representation, and the task is to compute the expected number of operations needed to reduce this number to 1.

We are given an array of integers representing darkness levels for a strip of paper, and we have a peculiar operation: we can fold the strip any number of times, drop black dye at one position, and then unfold.

We are working with a binary string that changes over time through flip operations. After every flip, we consider all non-empty subsequences of the current string. Each subsequence is assigned a score based on how it can be split into two parts.

We are given two hidden non-negative integers, x and y, each less than $2^{30}$. Our goal is to determine the sum of bitwise ORs $(m mid x) + (m mid y)$ for a given integer m.

We have two lanes. Each lane starts with exactly one person. The level consists of n rounds. In each round there is a left gate and a right gate. A gate either adds a fixed number of people or multiplies the number of people currently in its lane.

We are given a sequence of integers of length 2n+1 that satisfies a special alternating sum property: the first element equals the sum of the remaining elements taken with alternating signs, specifically a1 = a2 - a3 + a4 - a5 + ... + a2n - a2n+1.

We are given a labyrinth with $n$ cells arranged linearly, where cell $i$ is $n-i$ kilometers away from the exit at cell $n$. Each cell initially contains one person.

We are given an array of integers, and three variables P, Q, R initially set to zero. For each element of the array, we must choose to XOR it into exactly one of the three variables. The main restriction is that at every step, the three variables cannot all be distinct.

We are given a collection of barrels, each containing some amount of water, and one of them has a tiny amount of poison. The poison adds an imperceptible 0.179 kilograms to the barrel's weight.

Working

We start with an array of n numbers in the first bag and an empty second bag. Since the final bags must be identical, each bag must end up containing exactly n/2 numbers. There are only two allowed operations.

We are given an array x of length n with integers from 1 to n, and a hidden array y of the same length. Each pair (xi, yi) is unique and xi ≠ yi.

We have a directed graph of cities. City i initially contains ai messengers. A messenger can move along directed roads. If a messenger already knows the plan, he can carry it while travelling.

We are given a set of cities represented by their coordinates on a 2D plane. Four merchants want to split the cities among themselves using a single dividing point $(x0, y0)$.

Alyona builds a square puzzle layer by layer around a central piece. The first layer consists of only the center piece, so it contains 1 tile. Every later layer forms a complete square ring around the previous puzzle. Each day she adds some number of pieces, given by the array a.

We are given an array of integers and allowed to perform a single type of operation any number of times. The operation lets us select an element, increase it by one, and then move it to the end of the array.

We are given a string of lowercase English letters, and we can perform exactly one operation: choose two positions, possibly the same, and set the first character equal to the second.

We are given a 2-row matrix with n columns, where each cell contains an integer. We are allowed to swap entire columns any number of times, meaning both elements in a column move together.

For $n=0$, the condition is

We are working with two sequences that interact through a kind of “resource budgeting” process. The first sequence, a, represents a list of tasks we must completely remove by repeatedly cutting off prefixes.

We are asked to determine how many elements must be removed from an array to make it vulnerable. A vulnerable array is one that can be made non-increasing by repeatedly applying Stalin Sort on any of its subarrays.

We have an array a that must be removed completely. At any moment we are at some index k in array b, starting from k = 1. For the current value b[k], we may repeatedly remove a non-empty prefix of the remaining array whose sum is at most b[k]. Every such removal costs m - k.

We are given an array of integers, and we can perform a specific operation repeatedly to extend its length. The operation allows us to choose a position i in the array (not the first element) such that the value at that position equals the array’s current size minus i plus one.

The game revolves around a deck of cards, each labeled with an integer. Monocarp can start by taking any card. On subsequent turns, he can only take a card that either has the same number as the last card taken or is exactly one greater.

For a polynomial $f$ of degree $n$, define $Fk(x)=sum{j=0}^{k}f(x+j).$ The dependence on $k$ is described by Faulhaber's formulas.

Each game has a success probability $pi/100$ and a reward $wi$. We may choose any subset of games. The catch is that we receive the reward only if every chosen game is won. If even one chosen game is lost, the final reward becomes zero.

We are given two directed graphs, each with the same number of vertices, and we are asked to add exactly one edge from each outgoing vertex to an incoming vertex in the other graph.

We are given a process that starts from problem 1 and moves through problems in a very unusual way. At each problem, we either submit it or skip it. Submitting gives us points and forces the next problem to be chosen only from strictly smaller indices than the current one.

Consider a triangle $ABC$ with outward squares $ABMN$, $BCKL$, and $ACPQ$ constructed on its sides.

We have a vending machine with n hidden slots, each containing a known number of lemonade cans. There are also n buttons, each mapped to exactly one slot, but the mappings are lost.

We are given several test cases, and each test case consists of a collection of pairs. Each pair behaves like a tiny block of length two, and we are allowed to reorder these blocks arbitrarily. After choosing an order, we concatenate all blocks into one long array of length $2n$.

We are given a collection of cards, where each card has an integer written on it. For each number from 1 to $n$, we know exactly how many cards of that type we initially possess. In addition, we have $k$ coins, and each coin allows us to buy a card of any type we choose.

We are given a sorted list of integer coordinates on a line. From every pair of these points, we draw a closed segment, meaning every integer point between the endpoints is included in that segment.

We are given an array of positive integers, and we are allowed to mark some of them as "red" under the constraint that no two adjacent elements can both be red.

I cannot produce a mathematical solution to Kvant M1553 because the problem statement itself is missing.

The polynomial $P_n(x)=1+x+\cdots+x^{n-1}$ satisfies

We have a row of $n$ cities, each with a deadline $ai$. You pick one city to start conquering at time 1, and each subsequent time step you expand to an adjacent unconquered city. The goal is to conquer every city $i$ at or before time $ai$.

We are given a tree rooted at vertex 1 where each node contains either a 0, 1, or an undecided value represented as ?.

We are given an array of integers and two fixed step sizes, $a$ and $b$. We can repeatedly pick any position and add either $a$ or $b$ to that element any number of times.

For every subarray, we throw all of its values into a set, removing duplicates. Starting from that set, we may repeatedly pick two distinct elements whose average is an integer and add that average if it is not already present.

We are given a rooted tree with vertex 1 as the root. Each non-root vertex $i$ has a parent $pi$ and an unknown non-negative weight $ti$ on its connecting edge. The sum of all weights is $w$.

We are given a one-dimensional line of 100 rooms, connected consecutively by 99 doors. Each door can either be open or locked, and movement is only possible through open doors between adjacent rooms.

We are given a list of items with integer costs, and two players, Alice and Bob, take turns picking items starting with Alice. After all items are taken, the score is the total cost Alice collected minus the total cost Bob collected.

We are given a digit string. For every substring of length exactly k, we must compute the minimum possible length after performing one compression operation.

Working

We are given a set of integer points on a one-dimensional line. The distance between two points is their absolute difference.

We are maintaining a dynamic set of integers drawn from a bounded universe up to about two million. Elements can be inserted and removed, and after each modification we may be asked a query about the structure of the “holes” in the set.

We have a line of cells. Each cell contains a positive value a[i] and a character, either L or R. An operation chooses a pair of positions (l, r) with l < r, where position l currently contains L and position r currently contains R.

We are working on a weighted undirected graph where each edge has two travel modes. Walking is always available and slower, while a bus ride is faster but only usable outside a fixed time interval during the day.

We have a bus with n seats in a single row, numbered from 1 to n. Passengers board one by one, and each chooses a seat according to a simple rule: the first passenger can sit anywhere, but any subsequent passenger must sit adjacent to an already occupied seat.

We are given a fixed array of integers and a target value, and we are allowed to choose a single non-negative integer x. The operation applied to the array is simple: we XOR every element of the array with x, then sum the results.

The first problem asks whether an infinite sequence of perfect squares $(an^2)$ can exist such that each term starting from the third satisfies the Fibonacci-type recurrence $an^2 = a{n-1}^2 + a{n-2}^2.