brain

tamnd's digital brain — notes, problems, research

41641 notes

IMO 1979 Problem 3

Let the two circles intersect at $A$ and another point $B$.

imomathematicsolympiad
CF 105267J - 简单的指数运算

We are given two numbers: a positive integer $N$ and a prime $P$. The task is to compute a double sum over all ordered pairs $(i, j)$ where both indices run from $1$ to $N$.

codeforcescompetitive-programming
CF 105267I - 黄金树

We are given a rooted tree where every node starts with an initial positive integer value. Time evolves in discrete steps, and each node carries a value that changes every day according to a local rule involving its parent. At day zero, each node i has a value a[i].

codeforcescompetitive-programming
CF 105267H - Duel on the Chessboard

We are given a small grid with obstacles and two special cells containing pieces A and B. Initially these two pieces occupy adjacent cells.

codeforcescompetitive-programming
CF 105267G - Candidate Master of Both (VI)

We are given an array of length $n$, and for every pair of indices $(l, r)$ with $l le r$, we define a value that depends on whether the greatest common divisor of the two endpoints equals a chosen parameter $k$.

codeforcescompetitive-programming
CF 105267F - 静流的路径

We are given a number $N$ that is fully described by its prime factorization. Every prime $pi$ appears with the same exponent $m$, so $N = p1^m p2^m cdots pk^m$.

codeforcescompetitive-programming
CF 105267E - Rolling for the Destination

We start at position zero on an infinite number line and repeatedly roll a fair four-sided die, which produces one of the values 1, 2, 3, or 4 with equal probability. After each roll we move forward by the rolled amount.

codeforcescompetitive-programming
CF 105267A - 2026美加墨世界杯

We are simulating the final round of a four-team football group. Three matches are already known: China has already played two matches against Thailand, and now only the last round remains, consisting of China versus Korea and Thailand versus Singapore.

codeforcescompetitive-programming
CF 105267B - Stop! High School Maths Please No More

We are given an array of positive integers and we are allowed to overwrite elements arbitrarily. Each overwrite picks an index and assigns it any positive integer value. The goal is to transform the array into a geometric progression whose common ratio is a positive integer.

codeforcescompetitive-programming
IMO 1979 Problem 2

A direct attempt to force a contradiction from mixed colors on a single pentagon typically fails because cross edges can absorb local inconsistencies without producing a monochromatic triangle.

imomathematicsolympiad
CF 105351A - Ancient Berland Roads

We are given a graph of towns connected by roads, and each town carries a population value. A “region” is simply any connected component formed using the roads that are currently usable.

codeforcescompetitive-programming
CF 105482A - Acoustic String

We are given a binary string and a deterministic transformation that repeatedly shrinks it. Each transformation step replaces the string with a new one formed by taking XOR of adjacent characters.

codeforcescompetitive-programming
IMO 1979 Problem 1

The alternating sum is examined for small truncations to detect structure.

imomathematicsolympiad
IMO 1978 Problem 6

The previous argument attempted to manufacture a recurrence for Schur numbers by deleting minimal elements of color classes.

imomathematicsolympiad
CF 105536A - Подготовка к олимпиаде

We are asked to distribute a fixed number of problems across a fixed number of days. Each day we choose how many problems to solve, and the sequence of daily counts must be non-decreasing.

codeforcescompetitive-programming
CF 105535K - Know Your Duration of Stay

We are given a calendar that is no longer the standard one year structure, but instead consists of a sequence of months, each with its own number of days. A date is represented as a pair of integers: a day inside a month and the month index.

codeforcescompetitive-programming
CF 105535I - Imperial Decree

We are given an $n times m$ grid where each cell has a non-negative weight. A random process picks two points in the grid, and those two points define a rectangle whose sides are parallel to the grid. The task is to compute the expected area of that rectangle.

codeforcescompetitive-programming
CF 105535A - Arithmetics and That's It

We are given a sequence of integers and allowed to delete at most k of them. After deletions, the remaining numbers must form an arithmetic progression when read in their original order.

codeforcescompetitive-programming
CF 105535D - Desired Distance

We are given a set of points in the plane, except one point is missing. There are already $n-1$ fixed points, and we are allowed to choose the coordinates of the final $n$-th point.

codeforcescompetitive-programming
CF 105530I - Delete the String

We are given a string, and we repeatedly perform an operation where we delete a contiguous segment. Each deletion removes a substring, and after deletions, the remaining characters collapse together as if the string is reindexed.

codeforcescompetitive-programming
CF 105530H - Break the Walls

We are given a grid where movement is restricted to only two directions: right and down. Some cells contain obstacles, and normally stepping into an obstacle would block movement.

codeforcescompetitive-programming
CF 105530G - I am Tired of Xor Problems

The task revolves around a multiset of values that are interpreted as exponents in a polynomial-like structure where addition is replaced by XOR.

codeforcescompetitive-programming
CF 105530E - Nice (Medium Version)

We are looking at numbers formed using only two digits, 6 and 9. Any valid number is “nice” if every position is one of these two digits.

codeforcescompetitive-programming
CF 105530B - Modular MEX

We are looking at all remainders produced by fixing a number $n$ and dividing it by every integer $i$ from $1$ to $n$. This gives a set of values of the form $n bmod i$.

codeforcescompetitive-programming
CF 105530C - Too Much Walking

We are given a collection of points on a 2D grid, where each point can be thought of as a cell with integer coordinates. For every point, we want to determine how far it is from the farthest other point, where distance is measured using Manhattan distance.

codeforcescompetitive-programming
IMO 1978 Problem 5

The expression involves a weighted sum of distinct positive integers $f(1),\dots,f(n)$ with weights $1/k^2$, which decrease strictly with $k$.

imomathematicsolympiad
CF 105505J - Jigsaw of Shadows

We are given a line, which we can think of as the x-axis. On this line there are several vertical people standing at distinct x-coordinates. Each person has a height, so you can think of each one as a vertical segment anchored on the line.

codeforcescompetitive-programming
CF 105505D - Diverse T-Shirts

We are given a set of N items, where each item represents a T-shirt model. Two models are considered incompatible if they share either the same text color or the same background color.

codeforcescompetitive-programming
CF 105505G - Grand Glory Race

We are given a weighted tree representing villages connected by roads. Every leaf village contains exactly one runner.

codeforcescompetitive-programming
IMO 1978 Problem 4

The configuration involves a triangle with $AB = AC$, a circle tangent to both equal sides at $P$ and $Q$, and also tangent internally to the circumcircle.

imomathematicsolympiad
IMO 1978 Problem 3

The sequence $f(1)<f(2)<f(3)<\cdots$ is strictly increasing and consists of positive integers, hence it defines an increasing subset $S\subset \mathbb{N}$.

imomathematicsolympiad
IMO 1978 Problem 2

The configuration consists of three mutually perpendicular segments $PA$, $PB$, $PC$ with common endpoint $P$, where $A,B,C$ lie on a fixed sphere centered at some point $O$.

imomathematicsolympiad
IMO 1978 Problem 1

The original failure comes entirely from an unverified claim about the multiplicative order of $978 \bmod 125$.

imomathematicsolympiad
IMO 1977 Problem 6

Testing small indices does not reveal any oscillatory behavior compatible with the condition $f(n+1) > f(f(n))$.

imomathematicsolympiad
CF 105507K - Раскраска матрицы

We are working with an $n times m$ grid that starts completely white. One operation chooses a single cell $(x,y)$ and a color among white, red, or blue, but the effect is not local: the whole row $x$ and the whole column $y$ are repainted in that color, overwriting anything…

codeforcescompetitive-programming
CF 105507L - Идеальная фотография

We are given a set of players, each with a distinct height. We want to place all existing players in a single line and possibly add new players so that the final lineup forms a perfectly consecutive sequence of heights.

codeforcescompetitive-programming
CF 105507J - Поиск и замена

We are given an array of integers. Each operation modifies this array in a very specific way: we locate two special positions, one containing a maximum value and one containing a minimum value.

codeforcescompetitive-programming
CF 105507I - Этажи, этажи...

A high-rise building is described where apartments are numbered continuously starting from 1, beginning on the first floor, and every floor contains the same number of apartments.

codeforcescompetitive-programming
CF 105507H - Вычитание

We are given a very large positive integer written in decimal form. From this number we want to subtract another positive integer $b$, chosen by us, under two constraints. First, $b$ must be strictly smaller than the given number.

codeforcescompetitive-programming
CF 105507G - Задача про сортировку

We are given a permutation of length $n$, and the task is to transform it into the identity permutation $[1,2,dots,n]$. The only allowed operation is reversing any subarray of length at least two. However, the transformation is constrained in two additional ways.

codeforcescompetitive-programming
CF 105507F - Бильярд

We are given a triangular arrangement of balls, where row 1 has 1 ball, row 2 has 2 balls, and so on up to row n. The balls are numbered consecutively row by row from top to bottom, and within each row from left to right.

codeforcescompetitive-programming
CF 105507E - Рассадка на экзамене

We are given a single row of seats in an exam hall, represented as a string of length $n$. Each position is either occupied by a student or empty. Our task is to reorganize students by moving some of them from their current seats into empty ones.

codeforcescompetitive-programming
CF 105507C - Дерево обхода в глубину

We are given a connected undirected graph $G$ with up to $n$ vertices and $m$ edges, and inside this graph we are also given a spanning tree $T$ on the same set of vertices. Every edge of $T$ is guaranteed to exist in $G$, but $G$ may contain additional edges.

codeforcescompetitive-programming
CF 105507B - Голы

We are given several independent seasons of a football team. For each season, we know how many matches were won and lost, and we also know the total number of goals scored and conceded across all matches. No draws exist, so every match is strictly either a win or a loss.

codeforcescompetitive-programming
IMO 1977 Problem 5

The division condition is written as $a^2+b^2 = q(a+b) + r$ with $0 \le r < a+b$, and the constraint $q^2 + r = 1977$ forces $r = 1977 - q^2$.

imomathematicsolympiad
CF 105505L - Latin Squares

We are given a sequence of operations applied to an unknown Latin square. A Latin square is an $N times N$ grid filled with numbers from $1$ to $N$, where each number appears exactly once in every row and in every column.

codeforcescompetitive-programming
IMO 1977 Problem 4

The expression is a trigonometric polynomial containing first and second harmonics.

imomathematicsolympiad
CF 105505H - Heraclosures

The program is a directed acyclic graph of function calls. Each function has a base cost, and whenever it calls another function, that callee’s full execution cost is added immediately, and this effect propagates recursively through all further calls.

codeforcescompetitive-programming
CF 105505I - Inversion Insight

We are asked to reconstruct a permutation of the numbers from 1 to N given its position in a very specific ordering of all permutations. The ordering is not the usual lexicographic order.

codeforcescompetitive-programming
CF 105505B - Biketopia's Cyclic Track

We are given an undirected connected graph where every city has degree at least three and there is at most one road between any pair of cities.

codeforcescompetitive-programming
IMO 1977 Problem 3

The set $V_n$ consists of integers congruent to $1 \pmod n$, namely numbers of the form $1+kn$ with $k \ge 1$.

imomathematicsolympiad
CF 105498H - Optimizing Weekend Days

We are given a long continuous period defined by a start date and an end date, and inside this period we also receive a list of public holidays. Each holiday either repeats every year on a fixed month and day, or occurs only once in a specific year.

codeforcescompetitive-programming
CF 105498G - User Registration System

We are maintaining a live database of usernames under two operations: insertion and deletion. Each username is a short string, and every operation either tries to add it or remove it. When inserting a username, the system behaves like a reservation mechanism.

codeforcescompetitive-programming
CF 105498E - Cyclic Inversion

We are given an array and asked to reason about its inversion count under a restricted but flexible operation. The operation is a cyclic shift applied to the prefix of length k: we can take the first k elements, rotate them left any number of times, and append them back to the…

codeforcescompetitive-programming
CF 105498D - Maximum AND

We are given an array of integers. For each value of a parameter $k$, we are allowed to repeatedly perform an operation that takes two positions $i$ and $j$ that are at least $k$ apart and copies the bitwise OR of $aj$ into $ai$.

codeforcescompetitive-programming
CF 105498A - Optimal Point

We are given a set of points in four-dimensional Euclidean space. Each point has coordinates $(xi, yi, zi, wi)$. We are allowed to choose a single point $o = (ox, oy, oz, ow)$, and we measure its distance to every input point using standard Euclidean distance in 4D.

codeforcescompetitive-programming
CF 105494B - Ant Hill

We are given a sequence of changes applied over time, where each element describes how the number of ants in an anthill changes after an observation. Positive values mean ants are added, negative values mean ants leave. We do not know the initial number of ants in the anthill.

codeforcescompetitive-programming
IMO 1977 Problem 2

The inequality system is local with two window lengths, $7$ and $11$, so every term participates in multiple overlapping constraints.

imomathematicsolympiad
IMO 1977 Problem 1

A square suggests a $90^\circ$ rotational symmetry about its center, and the repeated construction of equilateral triangles on each side introduces a $60^\circ$ rotational component locally.

imomathematicsolympiad
IMO 1976 Problem 6

The recurrence couples each term with the previous two terms in a nonlinear way, and the conclusion concerns the integer part of a logarithm, suggesting that the central structure is a hidden power of…

imomathematicsolympiad
CF 105494I - Study Day

We are given a sequence of lectures, each lecture providing some amount of knowledge represented by an integer value. For every lecture, you make a decision in two layers: whether you attend it, and whether you apply a special “meditation” effect right before attending it.

codeforcescompetitive-programming
CF 105494H - Hierarchy

We are given a collection of employees where each employee belongs to exactly one company, and each company is structured as a hierarchy rooted at a CEO.

codeforcescompetitive-programming
CF 105494G - Need More Gold

We are given a collection of monsters, each described by two numbers. One value represents how much gold you need to have before you can defeat that monster, and the other represents how much gold you gain after defeating it.

codeforcescompetitive-programming
CF 105494E - Mountain Ranges

We are given a sequence of mountain heights arranged in a line. A parameter $k$ defines when two neighboring mountains are considered “compatible”: if the height difference between adjacent positions exceeds $k$, then that adjacency is broken.

codeforcescompetitive-programming
CF 105494D - Grouping

We are given an array of integers and we are asked to split it into several groups. The cost of a solution is the number of groups, and every element must belong to exactly one group.

codeforcescompetitive-programming
CF 105494A - Problem Statement

We are given a very simple process that starts from a single object, called a part. Every time we press Enter, the number of parts increases by exactly one. After performing some number of presses, the system ends with exactly $n$ parts.

codeforcescompetitive-programming
IMO 1976 Problem 5

Each equation is a homogeneous linear relation in $q=2p$ integer variables with coefficients in ${-1,0,1}$.

imomathematicsolympiad
CF 105493C - Tomorrow Will Be Better Than Yesterday

We are given a sequence of points in the plane, and we look at the displacement vectors between consecutive points. Each such vector captures how we move from one point to the next.

codeforcescompetitive-programming
IMO 1976 Problem 4

A product of positive integers with fixed sum increases when the summands are replaced by a partition that favors factors close to the maximizer of the function $x \mapsto x^{1/x}$.

imomathematicsolympiad
IMO 1976 Problem 3

Let the box be a parallelepiped with side lengths $a,b,c>0$.

imomathematicsolympiad
IMO 1976 Problem 2

The polynomials are defined by iteration of $P_1(x)=x^2-2$, so that $P_n$ is the $n$-fold composition of $x^2-2$ with itself.

imomathematicsolympiad
IMO 1976 Problem 1

Let a convex quadrilateral $ABCD$ be given.

imomathematicsolympiad
IMO 1975 Problem 6

Condition (i) says that $P$ is a homogeneous polynomial of degree $n$.

imomathematicsolympiad
IMO 1975 Problem 5

The flawed argument tried to force a cyclotomic structure via Mann’s theorem.

imomathematicsolympiad
CF 105493H - Tiring Wait

We are simulating a traveler who moves back and forth between two stops, A and B, using two fixed timetables. One timetable lists departure times from A to B, and the other lists departure times from B to A.

codeforcescompetitive-programming
CF 105493I - Fair Diversity

Each establishment receives some number of visits over a fixed number of days. From this history we compute a frequency array $ci$, where each value represents how many times establishment $i$ was visited.

codeforcescompetitive-programming
CF 105493E - Training Camps

We are given a directed acyclic graph where two special vertices act as starting points. From each of these starting vertices, we must construct a path that follows directed edges forward.

codeforcescompetitive-programming
CF 105493G - Exhausting Training

We are modeling a training schedule that improves two independent skills over a number of days. Each skill has an initial level, a target level, and two ways to train it: a normal training mode that increases the skill slowly, and an intensive mode that boosts progress more…

codeforcescompetitive-programming
IMO 1975 Problem 4

We are given the number

imomathematicsolympiad
CF 105493D - Conspiracy Theory

We are given a sequence of positive integers. After removing duplicates, we are interested in building a directed structure over their positions in increasing index order.

codeforcescompetitive-programming
CF 105493A - New Functionality

The process described in the problem behaves like a two-dimensional counter that advances in a very regular pattern. We start from a current position identified by a pair of values, and each “press” moves this position forward.

codeforcescompetitive-programming
CF 105492C - Concurrent Contests

There are several programming contests happening at the same time, and a set of participants must be distributed among them. Each contest has a single prize that only its winner receives.

codeforcescompetitive-programming
IMO 1975 Problem 3

Directed-angle accumulation across a multi-centered chain fails unless every angle is expressed as a single consistent invariant, because each construction triangle induces relations at two vertices r…

imomathematicsolympiad
IMO 1975 Problem 2

The statement concerns an arbitrary strictly increasing sequence of positive integers.

imomathematicsolympiad
IMO 1975 Problem 1

The expression to be minimized is

imomathematicsolympiad
CF 105492M - Museum Visit

We are given a timeline of days, each day having a known “discomfort cost” if we choose to visit the museum on that day. Alongside this, there are multiple exhibitions, and each exhibition is active over a contiguous range of days.

codeforcescompetitive-programming
IMO 1974 Problem 6

The earlier approach fails because it invents a hierarchy of sets based on “sign changes” without defining a meaningful invariant that survives passage to finite differences.

imomathematicsolympiad
CF 105492K - Karaoke Compression

We are given a single string representing a sequence of lyrics. We are allowed to perform exactly one compression operation.

codeforcescompetitive-programming
CF 105492J - Jumbled Scoreboards

We receive a sequence of snapshots from a game scoreboard, where each snapshot contains two integers representing the scores of two competing teams at that moment.

codeforcescompetitive-programming
CF 105492I - Interrail Pass

We are given a fixed itinerary consisting of n travel days, each occurring on a specific calendar day. For each of these days, there is a cost if we decide to buy a single ticket independently. These days are already sorted by time, and no two days share the same timestamp.

codeforcescompetitive-programming
CF 105492G - Grocery Greed

Each item has a price given with exactly two decimal places. You are allowed to split the set of items into groups, and each group can be paid for either in cash or by card. Card payment charges the exact sum of the items in the group.

codeforcescompetitive-programming
CF 105492F - Failing Factory

We are given a factory modeled as a directed graph where each node represents a processing step. Every step independently fails with a given probability.

codeforcescompetitive-programming
CF 105492E - Extraterrestrial Exploration

We are given an array of $n$ hidden integers, revealed only through queries. Each position corresponds to a canister of fuel, and querying index $i$ returns its value $ai$. The array is sorted in non-decreasing order.

codeforcescompetitive-programming
CF 105492D - Disgruntled Diner

We are given a log of orders where each order is a pair consisting of a menu item and a table number. Think of each order as an edge connecting a letter node (the dish) to a digit node (the table). The central computer knows all such edges.

codeforcescompetitive-programming
CF 105492A - ``Aaawww...'' or ``Aaayyy!!!''

We are given a frozen contest scoreboard with several teams already ordered from best to worst. Each team has a row describing its submission status per problem: accepted, rejected, pending, or no submission at all.

codeforcescompetitive-programming
CF 105487A - Box

A rectangular box is placed in 3D space with its bottom face lying flat on a known horizontal plane. The height of the box is given, so the top face is just a vertical translation of the bottom face.

codeforcescompetitive-programming
IMO 1974 Problem 5

Direct computation of extremal configurations shows that the expression approaches $2$ when two opposite variables are small and the other two are large, and approaches $1$ when two adjacent variables…

imomathematicsolympiad
IMO 1974 Problem 4

Small cases were checked to understand what truly restricts the number of rectangles.

imomathematicsolympiad
IMO 1974 Problem 3

Let

imomathematicsolympiad
CF 105487M - Covering a Tree

A tree is given in parent representation, so every node except the root has a single parent and the edges are implicitly directed upward toward that root. We are asked to cover every tree edge exactly once using several directed segments.

codeforcescompetitive-programming