brain

tamnd's digital brain — notes, problems, research

43815 notes

Kvant Math Problem 560

For a fixed position of the cover, let $C$ be the convex cover and let $H$ be the hole.

kvantmathematicsolympiad
CF 336E - Vasily the Bear and Painting Square

The problem presents a geometric pattern generated on a coordinate plane and asks for the number of ways to sequentially paint this pattern with a given number of colors. Instead of thinking about coordinates, we can abstract the problem into combinatorial structures.

codeforcescompetitive-programmingbitmaskscombinatoricsdpimplementation
Kvant Math Problem 543

The expression

kvantmathematicsolympiad
CF 336D - Vasily the Bear and Beautiful Strings

We are asked to count binary strings containing exactly n zeros and m ones that can be reduced to a single bit g after applying a sequence of specific "modifications." A modification takes the last two characters of a string and replaces them with a single new character.

codeforcescompetitive-programmingcombinatoricsmathnumber-theory
CF 336B - Vasily the Bear and Fly

Vasily has painted two rows of circles on the plane, each row containing m circles of the same radius R. The first row lies on the line y = 0 and the second on y = 2R.

codeforcescompetitive-programmingmath
CF 335C - More Reclamation

We are dealing with a two-column grid of arbitrary height r, where each cell initially represents water. Two cities take turns reclaiming cells to turn them into land, but there is a restriction: reclaiming a cell blocks the three neighboring cells in the opposite column from…

codeforcescompetitive-programminggames
Kvant Math Problem 533

A heptagon has $7$ vertices and $14$ diagonals.

kvantmathematicsolympiad
CF 335B - Palindrome

We are given a single string made of lowercase letters. From this string, we are allowed to delete characters while keeping the remaining characters in order, and we are interested only in the resulting subsequences that are palindromes. The task is twofold.

codeforcescompetitive-programmingconstructive-algorithmsdp
Kvant Math Problem 506

Let $x=a^2,\; y=b^2,\; z=c^2,\; w=d^2$.

kvantmathematicsolympiad
CF 335F - Buy One, Get One Free

We are given a list of pies with positive prices and a store promotion: for each pie you pay full price for, you can take another pie that is strictly cheaper for free. The goal is to determine the minimum total amount you must spend to acquire all pies.

codeforcescompetitive-programmingdpgreedy
CF 335E - Counting Skyscrapers

We are asked to relate two counting schemes over a sequence of randomly sized skyscrapers. Imagine a row of skyscrapers with random heights, where the height of each building follows a geometric distribution with probability $2^{-i}$ for height $i$.

codeforcescompetitive-programmingdpmathprobabilities
CF 335D - Rectangles and Square

We are given a collection of axis-aligned rectangles with integer coordinates, and we are allowed to pick any subset of them.

codeforcescompetitive-programmingbrute-forcedp
CF 335A - Banana

We are asked to help Piegirl buy sheets of stickers to construct a target string s. Each sheet contains exactly n stickers, and all stickers on a sheet are predetermined by the string we choose for that sheet.

codeforcescompetitive-programmingbinary-searchconstructive-algorithmsgreedy
Kvant Math Problem 494

Let the square be partitioned into a regular grid of $n \times n$ congruent squares, each of side length $1/n$.

kvantmathematicsolympiad
CF 333A - Secrets

We are asked to analyze a situation with coins of denominations that are powers of three: 1, 3, 9, 27, and so on. A buyer wants to pay an exact amount n but cannot do so because he lacks the right combination of coins.

codeforcescompetitive-programminggreedy
CF 333B - Chips

We are given an $n times n$ grid with some blocked cells. Gerald is allowed to place chips only on the boundary cells, but corners are forbidden starting positions.

codeforcescompetitive-programminggreedy
Kvant Math Problem 493

The expression

kvantmathematicsolympiad
CF 333E - Summer Earnings

We are given a set of candidate points in the plane, and we must choose exactly three of them to serve as centers of three identical circles. All three circles must have the same radius, and they are allowed to touch but not overlap in their interiors.

codeforcescompetitive-programmingbinary-searchbitmasksbrute-forcegeometrysortings
CF 333D - Characteristics of Rectangles

We are given a rectangular grid of numbers with $n$ rows and $m$ columns. Each cell contains a non-negative integer. The "property" of the table is defined as the minimum value among the four corner cells.

codeforcescompetitive-programmingbinary-searchbitmasksbrute-forceimplementationsortings
Kvant Math Problem 484

A dissection of a convex polygon into regular polygons means that every piece is an equilateral triangle, a square, or a regular polygon of higher order, all glued edge-to-edge without overlap.

kvantmathematicsolympiad
CF 333C - Lucky Tickets

We are asked to construct a large collection of 8-digit strings, where each string is a “ticket”. Each ticket is considered valid if it is possible to insert arithmetic operations between its digits and fully parenthesize the resulting expression so that the final value…

codeforcescompetitive-programmingbrute-forceconstructive-algorithms
CF 332B - Maximum Absurdity

We are given a list of numbers placed on a line, where each position represents a law and its value represents how “useful” or “valuable” it is. We must select exactly two contiguous blocks of fixed length k.

codeforcescompetitive-programmingdata-structuresdpimplementation
Kvant Math Problem 477

The sequence is defined by iteration of an integer polynomial $P$ satisfying $P(x)>x$ for all natural $x$.

kvantmathematicsolympiad
CF 332C - Students' Revenge

We are given a collection of orders. From these, we must select exactly $p$ orders that will be enforced. Each chosen order has two effects: if the chairperson complies with it, it contributes some amount of “damage” measured by $ai$, and if she refuses, it causes…

codeforcescompetitive-programmingdata-structuresgreedysortings
CF 332E - Binary Key

We are given a string p, which acts as a container, and a target message s that we want to extract. To do this, we must construct a binary key q of length k.

codeforcescompetitive-programmingdpgreedyimplementation
CF 332D - Theft of Blueprints

We are asked to analyze a network of missile silos connected by underground passages, each guarded by a certain number of droids. The silos form a highly structured network: for any subset of silos of size k, there is exactly one silo connected directly to all of them.

codeforcescompetitive-programminggraphsmath
CF 332A - Down the Hatch!

The game can be thought of as a circle of n players taking turns performing one of two actions, denoted by 'a' for elbow and 'b' for nod. Vasya, at index 0, wants to maximize the number of times he can drink a glass of juice.

codeforcescompetitive-programmingimplementation
CF 331B1 - Shave Beaver!

We are given a permutation of the numbers from 1 to n, but the permutation is not just data, it defines a fixed ordering of “beavers in a line”. Each number appears exactly once, but the position of each value changes over time due to swaps.

codeforcescompetitive-programmingimplementation
Kvant Math Problem 471

Two intersecting circles partition the plane into exactly three bounded regions: the common lens $R_0$, the two asymmetric caps $R_1$ and $R_2$ lying respectively in the first and second circle but ou…

kvantmathematicsolympiad
CF 331A1 - Oh Sweet Beaverette

We are given a linear sequence of trees, each carrying an integer value that represents how aesthetically pleasing that tree is. We are allowed to remove any subset of these trees, keeping the remaining ones in their original order.

codeforcescompetitive-programmingbrute-forceimplementation
CF 331E2 - Deja Vu

The problem gives a directed graph where vertices represent locations and edges represent streets between them. Every street has two pieces of information: where it goes, and a fixed sequence of “visions”, which is just a list of vertices.

codeforcescompetitive-programmingconstructive-algorithmsdp
CF 331E1 - Deja Vu

We are asked to model Neo's “deja vu” experiences as paths in a directed graph. The graph nodes represent shops, and directed edges represent streets. Each edge carries a sequence of visions, which is a list of shop indices that Neo sees when traveling that edge.

codeforcescompetitive-programmingconstructive-algorithmsgraphsimplementation
CF 331D3 - Escaping on Beaveractor

We are asked to simulate the movement of a vehicle, the Beaveractor, inside a square campus. The campus is a grid from (0,0) to (b,b).

codeforcescompetitive-programmingdata-structuresimplementationtrees
Kvant Math Problem 465

A ticket is a length-$k$ word over the alphabet ${0,1,\dots,9}$.

kvantmathematicsolympiad
CF 331D2 - Escaping on Beaveractor

We are asked to simulate the movement of a “Beaveractor” on a square campus of size b×b. The campus contains several arrows that act like teleportation instructions: whenever the Beaveractor reaches an arrow, it immediately changes its direction to match the arrow and…

codeforcescompetitive-programminggraphs
CF 331D1 - Escaping on Beaveractor

We are asked to simulate the motion of a "Beaveractor" on a square campus of size $b times b$. The campus contains a set of directional arrows, each either horizontal or vertical, which force the Beaveractor to change its motion direction when it crosses them.

codeforcescompetitive-programmingdfs-and-similarimplementation
CF 331C3 - The Great Julya Calendar

We are asked to reduce a positive integer to zero by repeatedly subtracting one of its digits. On each step, you must choose any digit that is present in the current number and subtract it. The goal is to minimize the number of subtraction operations needed to reach zero.

codeforcescompetitive-programmingdp
Kvant Math Problem 460

We begin with small values of $n$ to understand the structure.

kvantmathematicsolympiad
CF 331C2 - The Great Julya Calendar

We are given a positive integer n representing a "magic number" from the Julya calendar. The Smart Beaver can reduce n to zero by repeatedly subtracting one of its digits. For instance, if n = 24, the Beaver could subtract 2 or 4, producing 22 or 20 respectively.

codeforcescompetitive-programmingdp
CF 331C1 - The Great Julya Calendar

We start with a non-negative integer n. In one operation, we look at the decimal representation of the current number, choose any digit that appears in it, and subtract that digit from the number.

codeforcescompetitive-programmingdp
CF 331B2 - Shave Beaver!

We are given a permutation of n beavers, each with a unique ID from 1 to n. A high-tech machine can shave beavers in consecutive ID intervals, but only if the permutation contains all IDs in that interval in increasing order, not necessarily consecutively in positions.

codeforcescompetitive-programmingdata-structures
CF 331A2 - Oh Sweet Beaverette

We are given a linear sequence of trees, each with an integer esthetic appeal. The task is to remove some trees so that three conditions hold. First, the sum of the remaining trees' appeals is maximized.

codeforcescompetitive-programmingdata-structuressortings
CF 330A - Cakeminator

We are given a small rectangular grid representing a cake. Each cell is either an ordinary cake cell (.) or contains a strawberry (S).

codeforcescompetitive-programmingbrute-forceimplementation
Kvant Math Problem 453

Let $S$ be a subset of ${a_1,\dots,a_n}$ and write $s(S)$ for its sum.

kvantmathematicsolympiad
CF 330B - Road Construction

We have a graph with n cities and no roads initially. Some pairs of cities are forbidden, meaning we are not allowed to build a road directly between them. We must add the smallest possible number of roads so that two conditions hold.

codeforcescompetitive-programmingconstructive-algorithmsgraphs
CF 329B - Biridian Forest

We are given a rectangular grid representing the forest. Some cells are blocked by trees, one cell contains our starting position S, one cell contains the exit E, and some cells contain digits. A digit cell represents that many other breeders standing there initially.

codeforcescompetitive-programmingdfs-and-similarshortest-paths
Kvant Math Problem 442

For small primes the structure is very rigid.

kvantmathematicsolympiad
CF 329C - Graph Reconstruction

The original graph is very restricted. Every vertex has degree at most two, which means every connected component is either a simple path or a simple cycle. We must build another graph on the same set of vertices.

codeforcescompetitive-programmingconstructive-algorithms
Kvant Math Problem 433

The configuration imposes five independent parallelism relations between each side of a convex pentagon and a diagonal.

kvantmathematicsolympiad
CF 329D - The Evil Temple and the Moving Rocks

We are asked to design a placement of rocks on an n × n grid such that activating a single rock produces at least x sounds. Each rock has a fixed movement direction - up, down, left, or right - and rocks move until they hit either a wall or another rock.

codeforcescompetitive-programmingconstructive-algorithms
Kvant Math Problem 429

Write $x=n+t$ with $n=[x]\in\mathbb{Z}$ and $t={x}\in[0,1)$.

kvantmathematicsolympiad
CF 329A - Purification

We have an n × n grid. Some cells are usable (.), while some cells are forbidden (E). A spell may only be cast on a usable cell. When we cast a spell on cell (r, c), every cell in row r and every cell in column c becomes purified.

codeforcescompetitive-programmingconstructive-algorithmsgreedy
CF 327B - Hungry Sequence

We need to construct an increasing sequence of n positive integers such that no later element is divisible by any earlier element. The input contains a single number n. We must output any sequence of length n satisfying two conditions.

codeforcescompetitive-programmingmath
Kvant Math Problem 424

Let $ABCD$ be a tetrahedron.

kvantmathematicsolympiad
CF 327C - Magic Five

We are given a digit string a and an integer k. The actual plate is not a itself, but the string obtained by concatenating a with itself k times. From this long string, we may delete any subset of positions, except that we are not allowed to delete every digit.

codeforcescompetitive-programmingcombinatoricsmath
CF 327E - Axis Walking

We have n positive segment lengths. Their total sum is d, which is also the destination point on the number line. A route is simply an ordering of these lengths. While following a route, we keep a running prefix sum.

codeforcescompetitive-programmingbitmaskscombinatoricsconstructive-algorithmsdpmeet-in-the-middle
CF 327D - Block Tower

We are given a 2D grid with n rows and m columns. Each cell is either empty, where we can place a tower, or a hole, where no tower can be built.

codeforcescompetitive-programmingconstructive-algorithmsdfs-and-similargraphs
CF 327A - Flipping Game

We are given a binary array, every element is either 0 or 1. We must choose exactly one contiguous segment and flip every value inside it. A flip changes 0 to 1 and 1 to 0. After performing this single operation, we want the resulting array to contain as many ones as possible.

codeforcescompetitive-programmingbrute-forcedpimplementation
Kvant Math Problem 417

The object is a closed polygonal line drawn on the surface of a unit cube, with the condition that every face of the cube contains at least one entire segment of the polygonal line.

kvantmathematicsolympiad
CF 325D - Reclamation

We are asked to simulate a process of turning cells in a cylindrical grid from sea into land, one by one, while ensuring that a sea path connecting the top row to the bottom row always exists.

codeforcescompetitive-programmingdsu
Kvant Math Problem 409

The transformation replaces each entry in a row by the frequency of that value in the same row.

kvantmathematicsolympiad
CF 325B - Stadium and Games

We are given the exact number of football games that must be played, and we need to find every possible initial number of teams that produces exactly that many games under a specific tournament format.

codeforcescompetitive-programmingbinary-searchmath
Kvant Math Problem 406

Let the circle have center $O$ and radius $R$.

kvantmathematicsolympiad
Kvant Math Problem 401

Let $A,B,C$ be the angles of $\triangle ABC$.

kvantmathematicsolympiad
Kvant Math Problem 392

Let the positions of the three pedestrians at time $t$ be represented by vectors $A(t), B(t), C(t)$ in the plane.

kvantmathematicsolympiad
Kvant Math Problem 373

An infinite decimal expansion determines an infinite sequence of digits, hence an infinite word over the alphabet ${0,1,\dots,9}$.

kvantmathematicsolympiad
Kvant Math Problem 366

Assume such a configuration exists and consider the finite set of triangles.

kvantmathematicsolympiad
Kvant Math Problem 346

Place the square in a coordinate system with algebraic convenience so that perpendicularity can be tested by a dot product condition.

kvantmathematicsolympiad
Kvant Math Problem 330

Let $M_0$ and $M_1$ be convex polygons.

kvantmathematicsolympiad
Kvant Math Problem 322

Each circle contributes boundary pieces only where it is the lowest among the $N$ radii in some direction, since the intersection of disks can be described as the set of points satisfying $d(x,O_i)\le…

kvantmathematicsolympiad
Kvant Math Problem 315

Each edge of the convex polyhedron is oriented, so the 1-skeleton becomes an orientation of a connected planar graph embedded on the sphere.

kvantmathematicsolympiad
Kvant Math Problem 312

The outer parallelogram $P_1$ admits an affine normalization to a unit square without changing incidence relations such as “lying on a side” and “being parallel to fixed directions.

kvantmathematicsolympiad
Kvant Math Problem 310

An $n$-digit number is a sequence of digits $d_1d_2\ldots d_n$ where $d_1 \in {1,\dots,9}$ and $d_i \in {0,\dots,9}$ for $i \ge 2$.

kvantmathematicsolympiad
Kvant Math Problem 302

Let $O = AC \cap BD$ in the trapezoid $ABCD$ with $AB \parallel CD$.

kvantmathematicsolympiad
Kvant Math Problem 300

We are given a finite or otherwise fixed collection of forbidden words over the alphabet ${a,b,c}$, each forbidden word having length at least $2$, and all forbidden words having pairwise distinct len…

kvantmathematicsolympiad
Kvant Math Problem 293

Let $\gamma_n = \angle C_{n+1} C_n O$.

kvantmathematicsolympiad
Kvant Math Problem 291

Let the triangle have vertices $A_1,A_2,A_3$.

kvantmathematicsolympiad
Kvant Math Problem 289

Let the total weight be $S$, and suppose the $N$ weights are partitioned into $K$ piles each of sum $T$, so $S = KT$.

kvantmathematicsolympiad
Kvant Math Problem 281

Consider small convex polygons whose diagonals are defined as segments joining non-adjacent vertices.

kvantmathematicsolympiad
Kvant Math Problem 278

The configuration involves a convex hexagon with side lengths bounded below or above and three “long” diagonals connecting every second vertex.

kvantmathematicsolympiad
Kvant Math Problem 271

For small values, direct checking clarifies the constraint.

kvantmathematicsolympiad
Kvant Math Problem 268

The game is played on the graph of an $n\times n$ chessboard, where vertices are squares and edges correspond to standard knight moves $(\pm2,\pm1)$ and $(\pm1,\pm2)$.

kvantmathematicsolympiad
Kvant Math Problem 266

Consider the circle through three consecutive vertices $A_{i-1},A_i,A_{i+1}$.

kvantmathematicsolympiad
Kvant Math Problem 255

Let the centers of the spheres be $O_1$ and $O_2$, with radii $R_1$ and $R_2$.

kvantmathematicsolympiad
Kvant Math Problem 253

Let the given points be $O$, $I$, and $I_a$, where $O$ is the circumcenter, $I$ the incenter, and $I_a$ one of the excenters of triangle $ABC$.

kvantmathematicsolympiad
Kvant Math Problem 251

The condition says no color appears more than $\frac{n}{2}$ times.

kvantmathematicsolympiad
Kvant Math Problem 246

Let the triangle be $ABC$ with circumcenter $O$.

kvantmathematicsolympiad
Kvant Math Problem 232

For a triple of points $A,B,C$, the condition that the triangle is obtuse means that one of the three angles exceeds $90^\circ$, equivalently one of the three opposite-side inequalities of the form

kvantmathematicsolympiad
Kvant Math Problem 227

Let the parallelogram be mapped by an affine transformation to the unit square, since affine maps preserve parallelism, ratios of areas, and the condition of a point lying on a segment.

kvantmathematicsolympiad
Kvant Math Problem 219

Let the four points be $A,B,C,D$ in space, not lying in one plane.

kvantmathematicsolympiad
Kvant Math Problem 216

We interpret the situation as a simple undirected graph on $N$ vertices, where each vertex represents a person and each edge represents a mutual acquaintance.

kvantmathematicsolympiad
Kvant Math Problem 214

Let $f(x)=ax^{2}+bx+c$ and assume the equation $f(x)=x$ has no real roots.

kvantmathematicsolympiad
Kvant Math Problem 206

Let the digits of the infinite sequence be $a_1,a_2,a_3,\dots$, where each $a_i \in {0,1,\dots,9}$.

kvantmathematicsolympiad
Kvant Math Problem 203

Let $ABCD$ be a cyclic quadrilateral with diagonals $AC$ and $BD$ intersecting at $P$.

kvantmathematicsolympiad
Kvant Math Problem 191

Let $A$ and $B$ be fixed, and let $l$ be a fixed line through $A$ not containing $B$.

kvantmathematicsolympiad
Kvant Math Problem 184

The expression is a finite alternating sum of simple fractions with shifts in the denominator.

kvantmathematicsolympiad
Kvant Math Problem 181

The wire must be bent into the full frame of a cube of side $10$, which is the 1-skeleton of a cube graph with $8$ vertices and $12$ edges, each of length $10$.

kvantmathematicsolympiad
Kvant Math Problem 178

Let $A$ be the vertex of the angle whose bisector contains $P$.

kvantmathematicsolympiad
Kvant Math Problem 171

A regular hexagon of side length $1$ provides three natural directions of equal unit segments forming angles of $60^\circ$.

kvantmathematicsolympiad
Kvant Math Problem 169

Each row contains $n$ numbers arranged increasingly, so the $k$-th column consists of the $k$-th smallest element in each row.

kvantmathematicsolympiad