brain

tamnd's digital brain — notes, problems, research

43815 notes

CF 104598C - Lots of Triangles

We are given a collection of geometric objects in three-dimensional space. Each object is a triangle, described by three points in $(x, y, z)$ coordinates.

codeforcescompetitive-programming
CF 104598H - Model Evaluation

The task gives two square grids of numbers, both of size $N times N$, representing pixel intensities of two images. For each query, we are given a rectangular subregion inside these grids, specified by two opposite corners.

codeforcescompetitive-programming
CF 104598F - Silly Nilly's Stuffies

We are given a sequence of piles, each pile containing some number of stuffed animals. In one move, we are allowed to increase or decrease the size of any single pile by exactly one, and we can do this as many times as needed.

codeforcescompetitive-programming
CF 104598B - Speedrun Splits

Each run of the game records a sequence of split times, and every run contains the same number of splits. You can think of the input as a matrix with $N$ rows and $K$ columns, where row $i$ stores the time taken for each split in run $i$, and the columns correspond to the same…

codeforcescompetitive-programming
CF 104598A - Dividing Data

We are given a collection of files, each with a positive size measured in bits, and a storage budget that limits how many total bits we can allocate.

codeforcescompetitive-programming
CF 104599H - Light Tree

The structure described is a rooted binary tree embedded in an array form. Each node is labeled from $1$ to $N$, and each node can point to at most two children, a left child and a right child. A value of $0$ means that the corresponding child does not exist.

codeforcescompetitive-programming
CF 104599J - Groups of Bots

We are given a set of robot groups placed on a number line. Each group has a position and a number of robots sitting on that position.

codeforcescompetitive-programming
CF 104599I - Intergalactic Terrorism

We are given a rooted tree with $n$ nodes. Each node $i$ carries a positive value $ai$. The structure is already a tree, so there are exactly $n-1$ edges, each implicitly having weight $1$.

codeforcescompetitive-programming
CF 104599G - Consecutive Segments

We are given a string consisting of lowercase characters and a large number of queries. Each query selects a contiguous substring of the string, and for that substring we must count how many substrings consist of only one repeated character.

codeforcescompetitive-programming
CF 104599E - Speedrun Splits

We are given several speedrun attempts of the same game, where each run records the time taken to complete each split.

codeforcescompetitive-programming
CF 104599F - Navigation Puzzle

We are given a circular track with $n$ labeled positions. Three tokens start at positions $a$, $b$, and $c$. In one move, we pick exactly one token and shift it one step clockwise or counterclockwise along the circle.

codeforcescompetitive-programming
CF 104599D - Dividing Data

We are given a collection of files, each with a fixed size in bits, and a storage budget $X$. From these files, we want to select as many as possible while ensuring the total size of selected files does not exceed $X$.

codeforcescompetitive-programming
CF 104599C - Model Accuracy

Each test case gives two lists of numbers: expected outputs and actual outputs produced by a model. For every pair $(ei, ai)$, we decide whether the prediction is acceptable by checking if the absolute difference $ The task is to compute the fraction of correct cases among all…

codeforcescompetitive-programming
CF 104599B - Birthday

We are given a range of years from $x$ to $y$, both inclusive. For every year in this interval, we must output the calendar date corresponding to March 7th in that year. Each output line represents one such date, formatted as a day number, then the month name, then the year.

codeforcescompetitive-programming
CF 104599A - Tall Bots Short Bots

We are given a collection of robot friends, each described only by a single integer value representing its height. Bob wants to build a single “mega robot” by stacking all of them vertically.

codeforcescompetitive-programming
CF 104603N - Lucky Number

We are given a multiset of integers representing cards. Each card has a value, and we want to partition some of these cards into as many disjoint groups as possible. A group is valid if the sum of all values inside it is divisible by 5.

codeforcescompetitive-programming
CF 104603K - Kitties

We are maintaining a dynamic set of axis-aligned rectangles drawn inside a large vertical panel. The panel has fixed width and a fixed total height, and at any moment the user only sees a horizontal window of height equal to the screen height.

codeforcescompetitive-programming
CF 104603M - Multiple Downloads

The solution does not correctly establish the existence of a sequence satisfying Definition R5 while enforcing the prefix constraint.

codeforcescompetitive-programming
CF 104603L - Game series

The task describes a two-match football series between two teams, Archimedians F.C. and Pithgoreans F.C. Each match produces a score for both teams, and the winner of the series is decided by summing goals across both matches.

codeforcescompetitive-programming
CF 104603H - Robotic Skills

We are given an $N times N$ grid where every cell contains a distinct integer from $1$ to $N^2$. A robot moves in straight segments aligned with the grid axes.

codeforcescompetitive-programming
CF 104603J - Jester in danger

We are given an undirected graph with two special nodes: city 1 and city N. These act as fixed endpoints, and we care about how “efficient” a route between them can be.

codeforcescompetitive-programming
CF 104603I - Regional Integration

We are given a collection of geometric regions in the plane, each region being either a disk, a square, or a triangle. All regions are disjoint even on their boundaries, so no two shapes touch. We must choose exactly one square and one triangle.

codeforcescompetitive-programming
CF 104603G - Great Heights

We are given a set of horizontal platforms placed at different heights above the ground. Each platform occupies an interval on the x-axis, and is located at a fixed height. You can think of each platform as a segment floating in 2D space, all parallel to the ground.

codeforcescompetitive-programming
CF 104603F - Cold day at the beach

Two teams take turns throwing discs onto a rectangular beach court. Each throw is a point in a 2D plane, and there is a fixed target point, the “tejin”, somewhere inside the same rectangle. The score is determined entirely by Euclidean distance to this target.

codeforcescompetitive-programming
CF 104603C - Chromatic

We are given many independent pairs of integers $(a, b)$. For each pair, we must decide whether it is possible to construct four positive integers $u, v, x, y$ such that two constraints are satisfied simultaneously. First, $a = u + v$, and both $u$ and $v$ must divide $b$.

codeforcescompetitive-programming
CF 104603E - Finding progressions

We are asked to count how many arithmetic progressions of integers exist that satisfy three constraints simultaneously. Each valid progression is a sequence with a positive common difference, so it strictly increases. Every term must lie inside a fixed interval from L to R.

codeforcescompetitive-programming
CF 104603D - Assigning problems

We are given a fixed structure for a contest: each contest has $K$ difficulty levels, and level $i$ requires exactly $Ci$ problems. Problems are categorized by a minimum usable level: a problem of grade $d$ can only be assigned to levels $d, d+1, dots, K$.

codeforcescompetitive-programming
CF 104603A - Alfajores

We are given a fixed sequence of office groups, where each office has a certain number of employees, and a sequence of trips. On each trip, Seba starts with a box containing a given number of alfajores. He visits offices in order.

codeforcescompetitive-programming
CF 104603B - Black and white

We are given an $N times N$ grid where each cell is either usable (black) or forbidden (white). The task is to place as many horizontal dominoes as possible, where each domino covers exactly two adjacent cells in the same row.

codeforcescompetitive-programming
CF 104604D - Segedinense

We are given many independent pairs of integers $(a, b)$. For each pair, we must decide whether it is possible to construct four positive integers $u, v, x, y$ such that two constraints are satisfied simultaneously. First, $a = u + v$, and both $u$ and $v$ must divide $b$.

codeforcescompetitive-programming
CF 104604E - Sueno

I can’t write a correct editorial for this yet because the actual problem statement (input format, output requirements, constraints, and rules of the task) is missing.

codeforcescompetitive-programming
CF 104604C - Multiplodivisor

There is a hidden integer $n$ that we are not allowed to see directly. Instead, we can interact with a judge by asking two types of queries, each revealing partial arithmetic structure around $n$.

codeforcescompetitive-programming
CF 104604A - Flechas

I can’t reliably write a correct editorial for Codeforces 104604A - Flechas without the actual problem statement. Right now the prompt only includes the template, but the core missing piece is what “Flechas” is asking us to compute (grid? strings? directions? graph?

codeforcescompetitive-programming
CF 104604B - Lightcycles

I can’t write a correct editorial yet because the actual problem statement for CF 104604B - Lightcycles isn’t included in your prompt (the statement section is empty).

codeforcescompetitive-programming
CF 104605B - Goulash

We are given a target number of knedlíky $N$. There are three types of restaurants: some give 4 knedlíky, some give 5, and some give 6. We may choose several restaurants of each type, but we cannot exceed the available counts $A, B, C$. Each restaurant can be used at most once.

codeforcescompetitive-programming
CF 104605E - Prision

We are given a geometric prison layout that is not a grid or graph in the usual sense, but a collection of convex polygonal regions drawn on a plane.

codeforcescompetitive-programming
CF 104605D - Numeros

I need to correct course here: I don’t actually have the statement for Codeforces 104605D - Numeros available from reliable context, and I cannot reconstruct a correct editorial without knowing the exact problem definition.

codeforcescompetitive-programming
CF 104605C - Lista

I don’t have the actual statement for Codeforces 104605C - “Lista” available in context, and without the input/output definition it’s not possible to produce a correct editorial, especially under the requirement that the solution be fully precise and re-derivable.

codeforcescompetitive-programming
CF 104605A - Cuchicheo

We are missing the actual statement of Codeforces 104605A “Cuchicheo”. Without the problem text, any attempt to write a correct editorial would be guesswork, and for Codeforces problems even small misread assumptions completely change the intended solution.

codeforcescompetitive-programming
CF 104609J - Cranes

We have a straight line of positions numbered from 0 to m. All boxes initially sit at position 0, and the goal is to get all k boxes to position m. There are n cranes, all starting at position 0. Time advances in discrete seconds.

codeforcescompetitive-programming
CF 104609I - Easter Eggs

We are given a row of $n$ positions, initially all distinguishable. Each position will eventually hold one painted egg, and each egg is colored using one of $k$ available colors. A full arrangement is therefore a length-$n$ sequence over an alphabet of size $k$.

codeforcescompetitive-programming
CF 104609H - Emergency

We are given a small grid of rooms, each room having up to four possible exits corresponding to the four cardinal directions.

codeforcescompetitive-programming
CF 104609G - Puzznic

The board is a very small grid, at most 7 by 7, filled with three kinds of cells: walls, empty spaces, and numbered tiles from 1 to 9. Each number represents a tile type, and tiles of the same number interact with each other according to adjacency.

codeforcescompetitive-programming
CF 104609D - Circular Sequence

We are given a sequence arranged in a circle, meaning index 1 is adjacent to index N. Each position carries a value, and we want to pick a subset of indices that maximizes the sum of chosen values.

codeforcescompetitive-programming
CF 104609F - Urns and Balls

We start with an array of size $n$ where each position initially contains exactly one ball, and that ball is uniquely identified by its starting position.

codeforcescompetitive-programming
CF 104609E - Largest Triangle

We are given the vertices of a strictly convex polygon in counterclockwise order. From these vertices, we are allowed to pick any three distinct vertices and form a triangle.

codeforcescompetitive-programming
CF 104609B - Convex Polygon

We are given a convex polygon with vertices in counterclockwise order. Each vertex has fixed coordinates, but during the process we are allowed to temporarily remove and later restore vertices.

codeforcescompetitive-programming
CF 104609A - Busy Bees

We are given a set of positions in an infinite hexagonal grid, where each position contains a group of worker bees. Movement happens along shared edges of hex cells, and the cost between two cells is the minimum number of such moves required to travel between them.

codeforcescompetitive-programming
CF 104609C - Hexagonal Billiards

We are simulating a billiard ball inside a regular hexagon where motion is perfectly elastic: the ball travels in straight lines and reflects off edges with equal incidence and reflection angles.

codeforcescompetitive-programming
CF 104611A - 开开心心233

We are simulating a very small “playlist system” that evolves over a sequence of operations. At any moment there is a queue of songs waiting to be performed. Two kinds of operations happen in order.

codeforcescompetitive-programming
CF 104611G - 套娃收纳

We are given a collection of items, each described by two values $li$ and $ri$. You can think of each item as a container: it has an inner capacity $l$ and an outer size $r$.

codeforcescompetitive-programming
CF 104611E - ytree

We are given a rooted tree with nodes numbered from 1 to N, where node 1 is fixed as the root. Each node starts with an implicit weight, initially zero. The system supports three kinds of operations that affect or query values on the tree.

codeforcescompetitive-programming
CF 104611C - 室温超导

We are given two strings, one called $S$ and another called $T$. We construct new strings by taking a non-empty substring from $S$, say $S[i..j]$, and then attaching a suffix of $T$, say $T[k..m]$, to its right.

codeforcescompetitive-programming
CF 104610B - Pascal Walk

We are walking on Pascal’s triangle starting from the top cell. Each position in the triangle has a value equal to a binomial coefficient, and from any cell we can move to one of its six neighboring cells: up-left, up-right, left, right, down-left, or down-right, as long as…

codeforcescompetitive-programming
CF 104610C - Square Dance

We are given a rectangular grid where each cell contains a competitor with a fixed skill value. All competitors start on the board simultaneously.

codeforcescompetitive-programming
CF 104610A - Pattern Matching

We are given several patterns, each consisting of uppercase letters and wildcard characters . Each can be replaced independently by any string of uppercase letters, including the empty string. After all replacements, a pattern becomes a concrete string.

codeforcescompetitive-programming
CF 104611J - radius

We are given a set of points in three-dimensional space. Each point has integer coordinates, and there are up to ten thousand of them. We want to place a sphere whose center is constrained to lie somewhere on one of the coordinate axes, meaning on the x-axis, y-axis, or z-axis.

codeforcescompetitive-programming
CF 104611K - 毕业季

We are given a small undirected graph with up to 20 vertices. A traveler starts at any vertex and moves for exactly d days. Each day consists of taking one edge to a neighboring vertex, so the sequence of visited vertices has length d.

codeforcescompetitive-programming
CF 104611I - hard math

We are given two very large integers, $L$ and $R$, both written with exactly $n$ decimal digits. The task is to count how many integers $X$ lie in the inclusive range $[L, R]$ such that when we look at the decimal representation of $X$, the number of distinct digits appearing…

codeforcescompetitive-programming
CF 104611F - 宝石交易

We are given two circular sequences of gemstones, both of length n. Each position holds a gemstone type, and the sequences are considered cyclic, meaning we can choose any starting point and traverse them in a fixed direction around the circle.

codeforcescompetitive-programming
CF 104611D - Container Orders

We are given a collection of containers, each container having a fixed weight of 2 and an associated cost. Each container is not unique in structure, but each input line describes a group of identical containers: a count $ki$ and a cost $Wi$, meaning there are $ki$ containers…

codeforcescompetitive-programming
CF 104611B - square game

We are given several independent piles of stones. Each pile starts with some positive number of stones, and two players alternate moves.

codeforcescompetitive-programming
CF 104614D - Determining Nucleotide Assortments

We are given a DNA strand consisting only of the four nucleotide types A, T, G, and C. After the strand, several range queries follow. Each query specifies a contiguous section of the strand, and for that section we must determine how frequently each nucleotide appears.

codeforcescompetitive-programming
CF 104614L - Which Warehouse?

We are given a set of warehouses connected by directed roads with travel costs. Each warehouse initially stores quantities of several product types.

codeforcescompetitive-programming
CF 104614K - Two Charts Become One

We are given two textual descriptions of rooted hierarchical structures. Each structure defines departments labeled by integers, where every department may have several direct subdepartments.

codeforcescompetitive-programming
CF 104614J - Simple Solitaire

We are given a fixed sequence of 52 playing cards, read in the exact order they are revealed. We simulate a process where cards are turned face up one by one and placed into a growing sequence.

codeforcescompetitive-programming
TAOCP 5.1 Exercise 4

We start from the standard interpretation of inversions in a permutation $a_1 a_2 \dots a_n$, where an inversion is a pair $(i,j)$ with $i<j$ and $a_i>a_j$.

taocpmathematicsalgorithmsvolume-3
TAOCP 5.1.3 Exercise 13

Let $X_1 X_2 \cdots X_{52}$ be the sequence of suits obtained from a uniformly random permutation of a multiset containing $13$ clubs, $13$ diamonds, $13$ hearts, and $13$ spades, ordered $C<D<H<S$.

taocpmathematicsalgorithmsvolume-3simple
TAOCP 5.1.3 Exercise 12

Let the multiset be M=\{n_1\cdot 1,\; n_2\cdot 2,\; \ldots,\; n_m\cdot m\}, \qquad n=n_1+\cdots+n_m.

taocpmathematicsalgorithmsvolume-3math-hard
TAOCP 5.1.3 Exercise 5

Let $p$ be a prime.

taocpmathematicsalgorithmsvolume-3math-medium
TAOCP 4.3.3 Exercise 13

Let $M$ be an $m$-bit integer and $N$ an $n$-bit integer with $n \gg m$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 3.2.1.2 Exercise 13

Let $p$ be prime and suppose $a$ is not a primitive element modulo $p$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 3.2.1.1 Exercise 9

Let $q = \lfloor m/a \rfloor$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 3.3.1 Exercise 5

Let $x_1,\dots,x_{20}$ denote the observations, and let $x_{(1)} \le \cdots \le x_{(20)}$ be the ordered sample.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 4.7 Exercise 17

Let $V(z)=\sum_{m\ge1} V_m z^m,$ and define $v_{nk}=\frac{1}{n}[z^k]V(z)^n,\qquad V_n(x)=\sum_{k=0}^n v_{nk}x^k.$ From the multinomial expansion of a power series,

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 3.1 Exercise 22

Let $f$ be a random function on a (typically infinite) set, meaning that for each input $x$, the value $f(x)$ is chosen according to a fixed distribution on outputs, and the random variables $\{f(x)\}...

taocpmathematicsalgorithmsvolume-1medium
TAOCP 3.4.2 Exercise 17

Let $S_j$ denote the set after the $j$th iteration of the algorithm, where $j$ runs from $N-n+1$ to $N$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 4.5.2 Exercise 35

The solution does not correctly answer the problem.

taocpmathematicsalgorithmsvolume-1math-medium
CF 104614I - Road To Savings

The city is modeled as an undirected weighted graph. Each intersection is a vertex and each road is an edge whose weight is its length.

codeforcescompetitive-programming
TAOCP 3.3.3 Exercise 2

The function $((x))$ is $1$-periodic and defined on $0 \le x < 1$ by $((x)) = x - \frac12,$ since $\lfloor x \rfloor = 0$ and $\lceil x \rceil = 1$ for $0 < x < 1$ in (7).

taocpmathematicsalgorithmsvolume-1hm-medium
TAOCP 4.6.1 Exercise 22

Let $f_0=f,\ f_1=f',\ f_{i+1}=-\operatorname{rem}(f_{i-1},f_i)$ be the Sturm sequence, and let the process terminate with a nonzero constant $f_s$.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 4.6.1 Exercise 18

A correct solution must repair three fundamental issues in the previous attempt: 1.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 3.4.1 Exercise 27

Let a subroutine be available that returns independent random bits $B \in {0,1}$ with $\Pr{B=1}=\Pr{B=0}=\tfrac12$.

taocpmathematicsalgorithmsvolume-1medium
TAOCP 3.4.1 Exercise 14

Let $X$ have continuous distribution function $F(x)=\Pr{X\le x}$ and define $Y=cX$, where $c$ is a constant.

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 4.3.1 Exercise 33

Let $u = (u_{n-1}\ldots u_1u_0)_b$.

taocpmathematicsalgorithmsvolume-1
TAOCP 4.3.1 Exercise 4

Let $U = (u_{n-1}\ldots u_0)_b,\quad V = (v_{n-1}\ldots v_0)_b,\quad W = (w_{n-1}\ldots w_0)_b.$ Define for each $j$ with $0 \le j \le n$ the partial values $U_j = \sum_{i=0}^{j-1} u_i b^i,\quad V_j =...

taocpmathematicsalgorithmsvolume-1math-medium
TAOCP 3.2.2 Exercise 34

Let $p$ be prime and let f(x)=x^{2}-cx-a\in\mathbb{F}_{p}[x],\qquad R=\mathbb{F}_{p}[x]/(f).

taocpmathematicsalgorithmsvolume-1math-medium
CF 104614H - Picking Up Steam

We are given a terrain described by a polyline that is monotone in x, so it is a chain of straight segments from left to right. A camera sits at a fixed point on this terrain, at a specified x-coordinate, meaning its y-coordinate is determined by the terrain at that x.

codeforcescompetitive-programming
CF 104614G - Pea Pattern

We are given two very large integers written as digit strings. The first number is used as the starting point of a deterministic sequence, and the second number is the target we are trying to locate inside that sequence. The sequence evolves in a very specific way.

codeforcescompetitive-programming
CF 104614F - It's About Time

We are asked to design a simplified “leap-year system” for a fictional planet whose year length is not exactly an integer number of local days. From physics, the input gives enough information to compute how long the planet takes to complete one orbit around its star.

codeforcescompetitive-programming
CF 104614E - Hilbert's Hedge Maze

The maze is not given explicitly. Instead, it is generated by repeatedly expanding a symbolic string that behaves like a growing fractal instruction system.

codeforcescompetitive-programming
CF 104614A - A-Mazing Puzzle

We are given a rectangular maze and two robots placed on different cells with initial directions. The maze is a grid where movement is blocked by internal walls and the outer boundary, except for a single exit located on the southern border of one specific cell.

codeforcescompetitive-programming
CF 104614C - Cribbage On Steroids

We are given a multiset of cards, each card described only by its rank. Suits do not matter. The task is to compute a single score based on three independent scoring rules applied over the entire collection, not just five cards.

codeforcescompetitive-programming
TAOCP 3.2.2 Exercise 31

Let $m = 2^e$ with $e \ge 4$.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 3.2.2 Exercise 4

In MIX arithmetic each word consists of several bytes, and operations such as multiplication and addition propagate carries from less significant positions toward more significant positions.

taocpmathematicsalgorithmsvolume-1simple
TAOCP 3.5 Exercise 31

Let ${U_n}_{n \ge 0}$ be a binary sequence, so each $U_n \in {0,1}$.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 3.5 Exercise 30

Let $(Y_n)_{n\ge 1}$ be an i.

taocpmathematicsalgorithmsvolume-1math-project
TAOCP 3.5 Exercise 21

Let $U_0, U_1, \ldots$ be a $[0,..,1)$ sequence with $U_0 = 0$.

taocpmathematicsalgorithmsvolume-1hm-project
TAOCP 4.5.3 Exercise 40

We fix the construction precisely before proving any properties.

taocpmathematicsalgorithmsvolume-1math-hard
TAOCP 4.5.3 Exercise 33

Define f_0(z)=\tanh z=\frac{e^z-e^{-z}}{e^z+e^{-z}},\qquad f_{n+1}(z)=\frac{1}{f_n(z)}-\frac{2n+1}{z}.

taocpmathematicsalgorithmsvolume-1math-hard