brain

We are given a base string $s$ and a pattern string $t$, both made of lowercase letters. The task is to answer many independent queries, where each query asks: inside a given substring of $s$, how many times does $t$ appear as a contiguous substring?

We are simulating how writing progresses through an infinite notebook where each page can store a fixed number of names.

We are given a shelf containing an ordered sequence of films, where each film has a “type” or ending label from 1 to m. This initial sequence is fixed and indexed from 1 to n.

We are working with a rooted tree where vertex 1 is the root, and every node is initially colored white. Over time, we apply three kinds of operations that either flip colors, reset parts of the tree, or ask for the current color of a node.

We are asked to evaluate a number-theoretic sum over all integers from 1 to $n$, where each integer contributes a value defined through its prime factorization. For a number $x$, we factor it as a product of primes $x = prod pi^{ai}$.

Each engine is a finite set of points in the plane, and we are allowed to rigidly move each set independently before they interact. Rigid motion here means we can translate and rotate a set arbitrarily, but not deform it.

We are given a collection of binary strings, all of the same fixed length $n le 12$. Each string in this collection appears with multiplicity, so duplicates matter. Alongside this, every position $i$ has a non-negative weight $wi$.

We are given two binary strings of equal length. You are allowed to pick any two positions in the first string and swap their bits. The second string stays fixed.

We are given a number $n$, and we must construct a permutation of the integers from $1$ to $n$. Among all such permutations, we are asked to minimize a quantity defined on the permutation. This quantity is the sum of two classical subsequence measures.

We are given a class of students, each identified by a unique integer id starting from 1. Every student has four exam scores corresponding to different subjects. The task is to rank all students by their total score across the four subjects.

We are given a tree where each edge represents a bidirectional road between two houses. Every road has two parameters: a base traversal time and a rate at which it worsens each day. On day $t$, the cost of an edge becomes a linear function $bi + ai cdot t$.

We are given a set of points on a plane, each point representing a city. The task is to select three distinct cities such that the triangle formed by them has a prescribed area $S$. If no such triple exists, we must report failure.

We are given a circle of $n$ students, where $n$ is even. Each student holds an unknown integer, and the only structural guarantee about these values is local: any two neighbors on the circle differ by exactly one in value.

We are given a directed graph with up to one million vertices and one million edges. The task is to choose a subset of vertices $Q$ with two properties that interact in a non-trivial way.

The election has a fixed set of voters, each initially committed to one of several parties. The United Party is party 1, and its goal is not just to get a lot of votes, but to strictly outperform every other party in final vote count.

The building can be thought of as a grid of points arranged in $n$ vertical columns (towers) and $h$ horizontal levels (floors).

We are given a directed structure over students where each student points to exactly one other student. This forms a functional graph: every node has outdegree one, so starting from any node and repeatedly following pointers eventually forces us into a cycle.

We are given a weighted tree where each edge represents a river with a travel time. Fish can move continuously along these edges: traversing an edge of length $l$ takes exactly $l$ days, and fish may also wait arbitrarily at vertices.

We are given a connected graph with two types of edges. One set is already fixed by a competitor, each with a known cost. The second set is ours: these edges form a forest, and we are allowed to assign any integer weights to them.

We are given a final array of length n that was produced by repeatedly painting segments with increasing labels from 1 to q. During the i-th operation, a chosen segment is overwritten entirely with value i, and later operations can overwrite earlier ones.

We are given an unknown $n times n$ grid where each cell is either open or blocked. Movement is only allowed from a cell to its right neighbor or its bottom neighbor, and only if the destination cell is open.

We are given a pattern string s and a target string t. The pattern looks almost like a normal string of lowercase letters, except that it may contain a single special character .

We are given a correctly balanced bracket sequence, meaning every prefix of the string never has more closing brackets than opening ones, and in total the counts match perfectly.

We are given a range of toy prices that is completely regular: there are toys priced from 1 up to n, each integer price appearing exactly once. We want to count how many distinct unordered pairs of different toys have a combined price exactly equal to k.

We are given a system of startups arranged into a structure where some startups are already “active” and others are “acquired” and attached to exactly one active startup.

We are given an $n times n$ grid and $m$ identical-sized cubes, each having a unique color. Each cube starts on a distinct cell, and each also has a target cell where it must eventually be placed.

We are given a set of points in the plane with two strong structural guarantees: no two points coincide and no three are collinear. From these points we can form triangles by choosing any three vertices, and every such triangle is non-degenerate.

We are given a sorted list of distinct integers, and we want to build a binary search tree using exactly these values as node keys.

We are given a binary string made of two symbols, black and white, and we want to extract a long contiguous segment that alternates perfectly between the two colors.

We are given a collection of pairs of integers. From each pair, we are allowed to pick exactly one number. After making one choice per pair, we obtain a multiset of selected values. The task is to find an integer greater than 1 that divides every chosen value.

We are given a string representing the colors of a line of puppies, where each character is a color from 'a' to 'z'. The goal is to determine whether we can transform this string so that all characters become the same, using a very specific operation.

We are given a collection of tasks, each task representing an exam that must be scheduled on exactly one of two possible days. For exam $i$, there are two candidate days $ai$ and $bi$, and we must choose one of them.

We are given a system of rooms labeled from 0 to $m-1$. A token, called the x-mouse, starts in an unknown room and evolves deterministically: if it is in room $i$, after one second it moves to $i cdot x bmod m$.

We are counting binary matrices of size $n times n$, where each cell is either black or white, but with two structural restrictions. The first restriction is a strong symmetry condition called “beauty”.

We can think of the dorm as a directed graph where each room has exactly one outgoing edge. From every room i, the mouse deterministically moves to a[i] after one second.

We are given several independent sets of stick lengths. For each set, we need to pick exactly four sticks such that they form a rectangle, meaning we need two equal pairs of lengths: one pair for the height and one pair for the width.

We are given several independent strings. Each string has even length, and every character is a lowercase English letter. For each character, we are forced to modify it exactly once, and the modification rule is fixed: we can only move one step in the alphabet either down or up.

We are working with an $n times n$ grid whose cells are filled with the numbers from $1$ to $n^2$, but not in a simple linear order. Instead, the grid is split into two disjoint groups of cells based on the parity of the sum of coordinates.

We are given a long array, and we repeatedly answer queries on subsegments of it. For each query range, we are allowed to slightly modify numbers in that segment by multiplying or dividing by primes, where each such operation changes a number by a single prime factor.

We are trying to identify an unknown integer $x$ in a very large range from $1$ to $M = 10004205361450474$. Instead of asking direct yes or no questions, we are allowed to submit up to five queries, where each query is an increasing list of integers.

We are given a cyclic structure of length $n$, where each position in the hidden array $a$ produces an observed value $bi$ through a modulo operation with its next neighbor.

We maintain a dynamic set of points on the integer grid. The set changes over time through insertions and deletions.

We are given a chronological log of events in a trading system where orders are inserted and then later executed. Each order has a unique price and, when it is created, it could be either a buy order or a sell order, but this direction is not recorded in the log.

We are asked to construct two positive integers, call them $a$ and $b$, such that their digit sums are both large enough, while the digit sum of their sum is kept small.

We are given a collection of axis-aligned rectangles on a 2D integer grid. Each rectangle is described by its bottom-left corner and top-right corner, and it includes its boundary as well as its interior.

We are given a grid of size $n times m$ consisting of two types of cells, white and black. Initially the entire grid is white, but at some point a single square region with an odd side length was painted black. That square is axis-aligned and fully filled with black cells.

We are given a tree where vertex 1 plays a special role: it is the root of our concern. The structure is initially fixed, but we are allowed to add new edges between any two previously unconnected vertices.

We are given a list of positive integers and a modulus $k$. For every ordered pair of distinct indices $(i, j)$, we form a new number by writing $ai$ directly followed by $aj$ in decimal representation. We need to count how many such ordered concatenations are divisible by $k$.

We are given two counts, $a$ red tiles and $b$ blue tiles, and we must place them on an infinite grid so that all colored tiles together form a single axis-aligned rectangle of area $a+b$.

We are given a collection of segments on a number line, and we want to understand how much they overlap if we remove exactly one of them.

We are given a sorted list of distinct problem difficulties. From this list, we must choose a subsequence, not necessarily contiguous, that will form a contest.

We are given a pattern string t of length n and a target number k. We need to build a new string s as short as possible such that when we slide a window of length n across s, the pattern t appears exactly k times as a substring.

We are given a fixed line of cells where each box sits at a distinct integer coordinate. Each box also has a weight, and that weight determines how expensive it is to move that box one step left or right.

We are given a system that evolves an $n$-dimensional vector over discrete steps. Each coordinate evolves independently using the same type of rule: a linear transformation modulo a prime.

We are given an array of integers, and we need to count how many contiguous subarrays have a special property. A subarray is considered valid if we can “rearrange bits inside each number independently” by swapping any two bits in its binary representation any number of…

We are working inside an integer grid that forms a rectangle from the origin to the point $(n,m)$. We need to pick three lattice points inside or on the border of this rectangle and form a triangle whose area is exactly $frac{nm}{k}$.

The task is to classify points in a plane relative to a fixed geometric region defined by four boundary points: $(0, d)$, $(d, 0)$, $(n, n-d)$, and $(n-d, n)$.

We are given a sequence of digits written as a single string. The task is to decide whether we can split this sequence into several consecutive parts, at least two parts, such that every part has exactly the same sum of digits.

We are given a small group of people, each giving a binary opinion about a single problem. Each response is either 0, meaning the person considers the problem easy, or 1, meaning the person considers it hard.

Stopped thinking

We are given a binary array and a single operation that flips exactly three positions, but those three positions must form an arithmetic progression.

We are given two arrays of length $n-1$. Each position $i$ describes a relationship between two unknown consecutive values $ti$ and $t{i+1}$, where each $ti$ is an integer in the range $[0, 3]$, meaning we can treat every value as a 2-bit number.

Lesha has two separate time budgets, one for today and one for tomorrow. Each lecture note has a fixed reading cost equal to its index: note 1 takes 1 hour, note 2 takes 2 hours, and so on.

We are given an $n times n$ grid of lowercase letters. We are allowed to modify at most $k$ cells, changing their letters to any lowercase character we want.

We are working with a rectangular grid of size $w times h$, where each cell can be thought of as a unit square on a plate. We repeatedly draw “rings” of gilding on this grid. The first ring covers the outer border of the whole rectangle.

We are given a circular arrangement of parrots, where each parrot has a numeric “influence radius” derived from its respect level. If a parrot at position i starts speaking at time 0, then at time 1 all parrots within distance ri to its left and right also start speaking.

We are given a multiset of weights, each weight having an integer mass between 1 and 100, but the weights are indistinguishable to us. We do not know which physical item corresponds to which mass, only the full list of masses exists somewhere in our friend’s knowledge.

We are given a tree and we are allowed to remove any subset of its edges. After removals, the tree becomes a forest. On this resulting forest, we consider all possible matchings and focus on those that achieve maximum size.

We are given the multiset of utensils that remained after a banquet and the number of guests who attended. Each guest received several identical “dishes”, and each dish came with a fixed set of utensils.

We are given a single string representing the winner’s handle, and we must print it as a rectangular grid. Each cell of the grid contains either a character from the string or an asterisk.

We are working in a city where movement is allowed only along two types of roads. The first type is the standard integer grid: you can travel freely along any vertical line x = k or horizontal line y = k, and the cost is simply Euclidean distance along those lines, which…

We are given a collection of up to 30,000 integers, each representable in at most 12 bits. Alongside this, we are given many “bitwise machines”, where each machine defines a transformation from two input numbers into one output number.

We are given several independent piles of chips. Each pile has a large initial size, and two players, Alice and Bob, first choose how many chips they will remove per move, denoted by a and b. After these choices, they play a turn-based game on all piles combined.

We are given a collection of integers, each of which is known to be “almost prime structured” in the sense that its number of divisors is very small, between 3 and 5.

We are given a permutation of values placed on a line of positions from 1 to n. A token starts on any chosen position, and two players alternate moving it.

We start with a large square piece of cloth with side length $a$. From one corner, a smaller square of side $b$ is cut out. The remaining cloth is an L-shaped region whose area is simply the area of the big square minus the area of the removed square, so $a^2 - b^2$.

We are given a square chessboard with coordinates from 1 to n in both directions. A queen is fixed at one cell, and it attacks along rows, columns, and diagonals in the usual chess sense.

We are given a sequence of geometric intervals on the number line. Think of each interval as a segment of paint on an infinite ruler. Now instead of working with single intervals, we look at contiguous blocks of these intervals.

We are given two arrays indexed by bitmasks of length n, so each index represents a subset of an n-element universe encoded as a binary number from 0 to 2^n - 1.

Codeforces 1034C: Region Separation

We are given a list of positive integers and are allowed to delete some of them. After deletion, we look at the greatest common divisor of the remaining numbers.

We are given a very large rectangular grid where each cell can be identified by coordinates $(x, y)$. We repeatedly place two chess pieces at a time, but only if the Manhattan distance between the two chosen empty cells is exactly 3.

We are given a collection of straight line segments drawn on the integer grid. Each segment connects two lattice points, but the segment itself may pass through many other lattice points depending on its slope.

We start with a directed acyclic graph. Some vertices have no incoming edges, these are called sources, and some have no outgoing edges, these are sinks. The graph is guaranteed to have the same number of sources and sinks, and this number is at most 20.

We are looking at integers through the lens of their prime factorizations. Every number (x ge 2) can be uniquely written as a product of primes, and we focus on the exponents in that decomposition.

We are working with a notion of “sparse” numbers in base 10. A number is considered valid if, when you write it in decimal, at most three of its digits are non-zero.

The figure is a broken line made from points at integer x-coordinates from 0 to 2n. Initially every point lies on the x-axis, so every y-coordinate is zero. The only way to modify the shape is to pick an odd-indexed point and increase its height by one unit per move.

We are given a base string and then asked to answer many independent games played on substrings of it. Each game starts from a chosen segment of the string, and two players alternate turns.

We are given a fixed base string s. Each query selects a contiguous segment s[l..r] and a comparison string x. From that segment, we consider every distinct substring, meaning every string formed by choosing a start i and end j with l ≤ i ≤ j ≤ r.

Codeforces 1037A: Packets

We are given two binary strings of equal length. Think of them as two rows of switches, where each position is either on or off.

We are given a tree with vertices labeled from 1 to n, and a proposed ordering of all vertices. The task is to decide whether this ordering could arise from running a breadth-first search starting at vertex 1, under some valid choice of adjacency ordering.

We are given a list of integers and a target value s. The goal is not to make all elements equal to s, but only to ensure that after we sort the array, the middle element becomes exactly s. Since the length is odd, there is a single well-defined median position.

We are given a string made of uppercase letters, but only from the first $k$ letters of the alphabet. The task is not to rearrange or modify the string, but to select a subsequence of characters while preserving order.

We are given a binary string s and a length n. We want to construct all binary strings t of length n. Each such t is treated as circular, meaning its end wraps back to its beginning.

Each block can be viewed as a weighted undirected edge between two colors, where each endpoint is one of two possible colors depending on orientation.

We are given a line of slimes, each carrying an integer value, and we repeatedly perform an operation where one slime absorbs an adjacent slime. If a slime with value $x$ eats a neighbor with value $y$, that neighbor disappears and the eater’s value becomes $x - y$.

We are given the integers from 1 to n, and we must split them into two non-empty groups so that every number is used exactly once. After splitting, we compute the sum of numbers in each group and look at the greatest common divisor of these two sums.

We are given a sequence of photo intervals on a very large number line. Each photo covers a fixed window of length w, starting at position xi, so photo i covers [xi, xi + w - 1].

We are dealing with a single moving target on a very large numbered line of stations from 1 to n. At any moment there is exactly one station where the train is located, but after every query the train is allowed to move up to k stations left or right, and this movement is…