brain

tamnd's digital brain — notes, problems, research

43815 notes

Kvant Math Problem 562

Our systems have detected unusual activity coming from your system.

kvantmathematicsolympiad
CF 2087H - Nim with Special Numbers

We are dealing with a variant of Nim, a classical two-player impartial game. In standard Nim, the state of the game is defined by piles of stones. On their turn, a player selects any non-empty pile and removes one or more stones. The last player able to move wins.

codeforcescompetitive-programming*special
CF 2087F - Weapon Upgrade

I’m sorry, but I can’t reliably produce a complete editorial and accepted solution for this problem from the information available here.

codeforcescompetitive-programming*specialdp
CF 2087G - Esports in Berland

We are given a sequence of daily competitions. On each day Monocarp either participates in the competition or spends the day training.

codeforcescompetitive-programming*specialgreedy
CF 2087D - Uppercase or Lowercase?

We are given a sorted list of strings, called handles, with the total number $n$ and a target handle $h$. The goal is to determine the 1-based position of $h$ in this list.

codeforcescompetitive-programming*specialinteractive
CF 2087E - Color the Arrows

We are given a sequence of arrows arranged in a line, each pointing either left or right. Each arrow also has an associated integer reward for painting it red, which can be positive, negative, or zero. Initially, all arrows are blue.

codeforcescompetitive-programming*specialdp
CF 2087A - Password Generator

We are asked to generate a password that satisfies three constraints simultaneously: it must contain a specific number of digits, uppercase letters, and lowercase letters, and no two adjacent characters can be the same.

codeforcescompetitive-programming*special
CF 2087C - Coin Game

We are given a string made of three possible characters, each position representing a coin of a certain type. For any subsegment of this string, two players play a deterministic picking game where each move consists of choosing a type and then taking all remaining coins of…

codeforcescompetitive-programming*specialgreedy
CF 2087B - Showmatch

We are asked to organize a showmatch for a competitive game involving $2n$ distinct players, each with a unique rating. The key requirement is that every player should be paired with another player whose rating is closest to theirs.

codeforcescompetitive-programming*special
Kvant Math Problem 666

The problem considers a network of $n$ vertices connected by $m$ undirected edges with positive integer weights.

kvantmathematicsolympiad
CF 2089E - Black Cat Collapse

The problem describes a rooted tree with nodes labeled from $1$ to $n$, where node $1$ is the root. Liki and Sasami perform explorations over several days, and each exploration destroys the chosen node and its entire subtree.

codeforcescompetitive-programming
CF 2089D - Conditional Operators

We are given a binary string of length 2n+1. The goal is to insert exactly n conditional operators ?: between the characters to form a valid C++-style expression, optionally adding parentheses, and determine if the final expression can evaluate to 1.

codeforcescompetitive-programmingconstructive-algorithms
CF 2089C2 - Key of Like (Hard Version)

We are given a game where n members take turns trying to open l locks using a set of l + k keys. Among these keys, exactly l are genuine and each opens exactly one lock, while the remaining k keys are fake.

codeforcescompetitive-programmingdpmathprobabilities
CF 2089C1 - Key of Like (Easy Version)

In this problem, we are asked to simulate a sequential game where a group of n participants try to unlock l locks using exactly l valid keys. Each participant takes one turn at a time in a fixed cyclic order.

codeforcescompetitive-programmingdpgamesmathprobabilities
CF 2089B2 - Canteen (Hard Version)

Working

codeforcescompetitive-programmingbinary-searchdata-structuresdpflowsgreedytwo-pointers
CF 2089B1 - Canteen (Easy Version)

We are given two arrays of equal length. You can think of each index as a station that holds two piles of units: one pile from array a and one pile from array b. The process runs in synchronized rounds, and each round has a fixed structure.

codeforcescompetitive-programmingbinary-searchdata-structuresflowsgreedytwo-pointers
CF 2089A - Simple Permutation

We are asked to construct a permutation of integers from 1 to $n$ with a special property. For each prefix of the permutation, we compute the average of the first $i$ elements, take its ceiling, and call that $ci$.

codeforcescompetitive-programmingconstructive-algorithmsnumber-theory
CF 2090A - Treasure Hunt

We are asked to determine who will dig up a buried treasure first between two people, Little B and Little K. The treasure is buried at a fractional depth a.5 meters, which is key: it means the threshold is always .5 meters beyond the integer a.

codeforcescompetitive-programmingimplementationmath
Kvant Math Problem 1520

Let $P(x)$ and $Q(x)$ be polynomials of degrees $m$ and $n$ respectively, with leading coefficients equal to $1$.

kvantmathematicsolympiad
CF 2091G - Gleb and Boating

Gleb needs to travel along a one-dimensional river segment from position 0 to position $s$ using a kayak. He starts with a given power $k$, and each paddle stroke moves him exactly his current power in the direction he is facing.

codeforcescompetitive-programmingbrute-forceconstructive-algorithmsdata-structuresdpgraphsgreedymathnumber-theoryshortest-paths
CF 2091F - Igor and Mountain

We are given a rectangular grid representing a vertical slice of a mountain. Each cell is either empty or contains a hold that Igor can use. The rows are horizontal layers of the mountain, with row 1 at the top and row n at the bottom. The columns are vertical segments.

codeforcescompetitive-programmingbinary-searchbrute-forcedp
CF 2091E - Interesting Ratio

We are asked to count pairs of integers $(a, b)$ where $1 le a < b le n$ such that the ratio $F(a, b) = frac{text{lcm}(a, b)}{gcd(a, b)}$ is a prime number.

codeforcescompetitive-programmingbrute-forcemathnumber-theorytwo-pointers
CF 2091D - Place of the Olympiad

We are given a rectangular hall with n rows and m spots per row where participants can sit. A total of k participants need seats. Desks that are consecutive in the same row form a bench, and the bench's length is the number of consecutive desks.

codeforcescompetitive-programmingbinary-searchgreedymath
CF 2091A - Olympiad Date

We are asked to figure out the earliest step at which a specific date, March 1, 2025, can be formed from a sequence of digits drawn one by one.

codeforcescompetitive-programminggreedystrings
CF 2091C - Combination Lock

We are asked to construct a permutation of numbers from 1 to $n$ with a very specific property: for every cyclic shift of the permutation, there should be exactly one fixed point. A fixed point in a permutation is an index $i$ such that the element at that index equals $i$.

codeforcescompetitive-programmingconstructive-algorithmsgreedy
CF 2091B - Team Training

We are given a group of students, each with a fixed skill value, and we must split them into teams so that every student belongs to exactly one team. For any team, its strength is defined as the number of students in the team multiplied by the smallest skill inside that team.

codeforcescompetitive-programmingdpgreedysortings
CF 2092F - Andryusha and CCB

We are given a binary string that represents a pie, and we need to split it into contiguous segments such that each segment has the same "beauty." The beauty of a string is defined as the number of places where consecutive characters differ.

codeforcescompetitive-programmingbrute-forceconstructive-algorithmsgreedymathnumber-theorystrings
CF 2092E - She knows...

The board is an enormous $n times m$ grid where almost every cell is initially uncolored (“green”), except for $k$ cells that are already fixed as either black or white. We are allowed to assign a color to every remaining green cell.

codeforcescompetitive-programmingcombinatoricsconstructive-algorithmsgraphsmath
CF 2092D - Mishkin Energizer

We are given a string representing a drink, made of the letters L, I, and T, each corresponding to a component. The drink is "balanced" when the number of each character is equal. Edmond can insert new letters between two consecutive, different characters.

codeforcescompetitive-programmingbrute-forceconstructive-algorithmsgreedyimplementationstrings
Kvant Math Problem 478

Represent the tournament by a directed complete graph.

kvantmathematicsolympiad
Kvant Math Problem 563

Assume, seeking a contradiction, that

kvantmathematicsolympiad
CF 2092C - Asuna and the Mosquitoes

We are given a collection of towers, each with a positive integer height, representing gifts from Asuna's admirers. Asuna evaluates the beauty of her gifts as the height of the tallest tower.

codeforcescompetitive-programmingconstructive-algorithmsgreedymath
CF 2092B - Lady Bug

We are given two bit strings of equal length, a and b, representing a password. Lady Bug wants to transform the first string a so that it contains only zeros.

codeforcescompetitive-programmingbrute-forceconstructive-algorithmsimplementationmath
CF 2092A - Kamilka and the Sheep

We are given a list of sheep, each with a distinct beauty level. Kamilka can feed every sheep the same number of extra grass bunches, effectively increasing all beauty levels by the same integer $d ge 0$.

codeforcescompetitive-programminggreedymathnumber-theorysortings
CF 2093F - Hackers and Neural Networks

Working

codeforcescompetitive-programmingbitmasksbrute-forcegreedy
CF 2093G - Shorten the Array

We are asked to find the shortest subarray of a given array a whose "beauty" reaches or exceeds a threshold k. The beauty of an array is the maximum XOR value between any pair of its elements.

codeforcescompetitive-programmingbinary-searchbitmasksdata-structuresdfs-and-similargreedystringstreestwo-pointers
CF 2093E - Min Max MEX

We are given an array and asked to cut it into exactly k contiguous pieces that together cover the whole array. Once the array is split, each piece has a MEX value, and we care about the worst piece, meaning the smallest MEX among all k segments.

codeforcescompetitive-programmingbinary-searchbrute-forcegreedy
CF 2093D - Skibidi Table

We are filling a $2^n times 2^n$ grid with integers from $1$ to $2^{2n}$, but the order is not row-major or column-major. Instead, the grid is constructed recursively.

codeforcescompetitive-programmingbitmasksimplementation
CF 2093B - Expensive Number

We are given a decimal number as a string. We may delete any subset of its digits while preserving the relative order of the remaining digits. The resulting sequence of digits must represent a positive number, although leading zeros are allowed.

codeforcescompetitive-programminggreedymath
CF 2093C - Simple Repetition

We are given a base integer x and a repetition count k. From x, we construct a new number y by writing the decimal representation of x consecutively k times without inserting separators. For example, if x = 52 and k = 3, then y = 525252. If x = 6 and k = 7, then y = 6666666.

codeforcescompetitive-programmingmathnumber-theory
CF 2093A - Ideal Generator

We are given a number $k$. The task is to decide whether it is possible to represent every integer $n ge k$ as the sum of a palindromic array of length exactly $k$, where all elements are positive integers.

codeforcescompetitive-programmingmath
CF 2094G - Chimpanzini Bananini

We are asked to maintain an array under three types of operations: appending an element to the end, reversing the array, and performing a cyclic shift that moves the last element to the front.

codeforcescompetitive-programmingdata-structuresimplementationmath
CF 2094F - Trulimero Trulicina

We are asked to fill an $n times m$ grid with integers from $1$ to $k$ in such a way that each number occurs exactly the same number of times and no two adjacent cells contain the same number.

codeforcescompetitive-programmingconstructive-algorithms
CF 2094H - La Vaca Saturno Saturnita

We are given an array a of integers and a hidden function f(k, a, l, r) defined as follows: for each index i from l to r, repeatedly divide k by a[i] as long as it is divisible, then add the resulting k to a running total.

codeforcescompetitive-programmingbinary-searchbrute-forcemathnumber-theory
Kvant Math Problem 1489

Work over the vector space $\mathbb F_2^{mn}$ of all $0$-$1$ configurations on the $m\times n$ rectangle.

kvantmathematicsolympiad
CF 2094E - Boneca Ambalabu

We are given a sequence of integers, and for each element in the sequence, we can compute the sum of XORs between it and every other element. Our task is to find which element maximizes this sum. More concretely, for a sequence a = [a1, a2, ...

codeforcescompetitive-programmingbitmasks
CF 2094D - Tung Tung Sahur

We are given a recorded sequence of intended drum hits, where each character is either a left hit or a right hit. Each intended hit does not produce a fixed sound length.

codeforcescompetitive-programminggreedystringstwo-pointers
CF 2094C - Brr Brrr Patapim

We are given an $n times n$ grid that was generated from an unknown permutation $p$ of length $2n$. The construction rule is simple: the value in cell $(i,j)$ is $p{i+j}$.

codeforcescompetitive-programmingmath
Kvant Math Problem 450

Normalize the width of the bottom rectangle to $1$, and let the common height of all rectangles be fixed.

kvantmathematicsolympiad
CF 2094B - Bobritto Bandito

We are asked to track the spread of an infection along an infinite line of houses. The infection starts at house 0 on day 0, and each day it spreads to exactly one additional house that is adjacent to any currently infected house.

codeforcescompetitive-programmingbrute-forceconstructive-algorithms
CF 2094A - Trippi Troppi

Each test case describes a “country name” that is stored in an older format consisting of three separate words.

codeforcescompetitive-programmingstrings
Kvant Math Problem 431

The trees are vertical cylinders.

kvantmathematicsolympiad
CF 2095H - Blurry Vision

The task looks almost intentionally trivial: we are given a single integer $x$, which represents a line number in a fixed text image. The problem is essentially asking us to “look” at line $x$ in a predefined visual and output the word printed there.

codeforcescompetitive-programming*specialfftmath
CF 2095J - Premiere at a Wrong Time

Before I start drafting the full editorial, I need to clarify one point. Could you briefly describe the mechanics of "Premiere at a Wrong Time"? Specifically, what are we given and what are we supposed to compute or output?

codeforcescompetitive-programming*special
CF 2095E - Pair Count

This problem comes from the April Fools Day Contest. The key trick is that the symbol shown as ⊕ is not actually bitwise XOR. The link attached to the symbol leads to a puzzle whose solution reveals that ⊕ should be interpreted as multiplication.

codeforcescompetitive-programming*specialnumber-theory
CF 2095I - Mysterious Script

The problem presents an alien numeral system used by the Balikons, where each word corresponds to a number. We are asked to take two numbers expressed in Balikon script, interpret them as standard integers, compute their sum, and then output the result in Balikon script.

codeforcescompetitive-programming*specialexpression-parsingnumber-theory
CF 2095G - Definitely a Geometry Problem

We are given a set of points on a plane, each point representing a slime. Megumin can choose a single circle anywhere on the plane and eliminate every slime lying inside it or on its boundary.

codeforcescompetitive-programming*specialgeometry
CF 2095F - ⅓ оf а Рrоblеm

Before I start, I need a clarification: the “Problem” section you provided appears garbled and incomplete - there’s a string of symbols and no clear description of what the problem actually is.

codeforcescompetitive-programming*specialmath
CF 2095B - Plinko

The problem is an interactive simulation of a simple Plinko game, where a ball drops through a triangular pegboard and eventually lands in one of ten numbered slots at the bottom. Each round of the game is labeled from Game 1 to Game 10.

codeforcescompetitive-programming*specialgamesinteractive
CF 2095D - Where Am I?

I can do that. Before I start, can you confirm: do you want me to reconstruct the full editorial for Codeforces 2095D - Where Am I?, even though the problem statement image and input/output examples are missing?

codeforcescompetitive-programming*specialgeometry
CF 2095C - Would It Be Unrated?

The problem is unusual because it is more about recognizing a fixed property than performing traditional computation. We are asked to determine how many tests the problem itself has. The input is essentially a prompt asking "how many tests does this problem have?

codeforcescompetitive-programming*specialbinary-searchbrute-force
CF 2095A - Piecing It Together

I can’t reliably reconstruct the full problem from the screenshot link alone, and I don’t want to risk inventing details and giving you a wrong editorial. Please paste the full problem statement (or at least the input/output format and constraints).

codeforcescompetitive-programming*specialstring-suffix-structures
Kvant Math Problem 377

The required condition is

kvantmathematicsolympiad
CF 2096H - Wonderful XOR Problem

We are given n intervals, each defined by a lower and upper bound [li, ri]. From each interval, we can pick a number ai within its bounds. Our goal is to consider all sequences (a1, a2, ...

codeforcescompetitive-programmingbitmaskscombinatoricsdpfftmath
CF 2096G - Wonderful Guessing Game

We are asked to play an interactive guessing game with a student, Alice. She secretly selects a number between 1 and $n$. We do not know her number in advance. Our task is to determine her number by submitting a fixed sequence of queries and then analyzing the responses.

codeforcescompetitive-programmingbitmasksconstructive-algorithmsinteractive
CF 2096D - Wonderful Lightbulbs

We are given a final configuration of lit cells on an infinite integer grid. Initially, all cells are off except one hidden “origin” cell that was on at the beginning.

codeforcescompetitive-programmingcombinatoricsconstructive-algorithmsmath
CF 2096F - Wonderful Impostors

We are given a game with n viewers, each of whom may either be a crewmate or an impostor. The viewers make statements about themselves and others in contiguous ranges.

codeforcescompetitive-programmingdata-structuresimplementationtwo-pointers
CF 2096E - Wonderful Teddy Bears

We are given a row of teddy bears, each colored either black or pink. A sequence of teddy bears is considered beautiful if all black bears appear to the left of all pink bears. Our goal is to transform any given arrangement into a beautiful one using the fewest possible moves.

codeforcescompetitive-programminggreedyimplementationsortings
CF 2096C - Wonderful City

We are given an $n times n$ grid where each cell contains an initial building height. We are allowed to modify the grid using two kinds of operations.

codeforcescompetitive-programmingdpimplementation
CF 2096B - Wonderful Gloves

We are given a collection of gloves in a drawer, where each glove has a color and a type: left or right. For each of the $n$ colors, we know exactly how many left gloves $li$ and right gloves $ri$ exist.

codeforcescompetitive-programminggreedymathsortings
CF 2096A - Wonderful Sticks

We are given a permutation task over the numbers from 1 to n. Each number represents a stick length, and every length must be used exactly once. The goal is to arrange these sticks in a sequence so that the relative constraints between consecutive positions are satisfied.

codeforcescompetitive-programmingconstructive-algorithmsgreedy
Kvant Math Problem 325

Let $x_{n,m}$ be the entry in row $n$ and position $m$, where $0\le m\le n$.

kvantmathematicsolympiad
Kvant Math Problem 240

The examples suggest that divisions should be used together with repeated squaring.

kvantmathematicsolympiad
Kvant Math Problem 1481

Let $a=BC$, $b=CA$, $c=AB$.

kvantmathematicsolympiad
CF 2097F - Lost Luggage

We are dealing with a network of airports where lost luggage moves around according to daily flights and is partially recovered through inspections. Each airport has an initial number of lost luggage pieces.

codeforcescompetitive-programmingdpflows
Kvant Math Problem 360

Let

kvantmathematicsolympiad
Kvant Math Problem 371

Consider the problem on a $2\times 2$ chessboard first.

kvantmathematicsolympiad
Kvant Math Problem 1451

Let $d=\gcd(a,b)$ and write $a=dx$, $b=dy$ with $\gcd(x,y)=1$.

kvantmathematicsolympiad
CF 2098B - Sasha and the Apartment Purchase

We are given a line of houses indexed by large integers, and a multiset of bar positions along this line. Multiple bars can occupy the same house, but each bar is treated as a separate point.

codeforcescompetitive-programmingmathsortings
CF 2101D - Mani and Segments

We are given a permutation and asked to examine every contiguous segment of it. For each segment we compute two classical sequence measures: the length of its longest strictly increasing subsequence and the length of its longest strictly decreasing subsequence.

codeforcescompetitive-programmingdata-structuresimplementationsortingstwo-pointers
Kvant Math Problem 234

Alice moves on the integer lattice starting at $(0,0)$, and her motion is periodic, determined by a string of $n$ moves repeated indefinitely.

kvantmathematicsolympiad
CF 2101F - Shoo Shatters the Sunshine

We are given a tree with n vertices. Each vertex can be colored red, blue, or white. The "coolness" of a coloring is the largest distance between a red and a blue vertex. If there are no red or no blue vertices, the coolness is zero.

codeforcescompetitive-programmingcombinatoricsdptrees
CF 2101E - Kia Bakes a Cake

We are given a tree on $n$ vertices and a binary marker on each vertex that tells us whether that vertex is “active”. Only active vertices participate in the construction of a second structure: a complete weighted graph formed from these active nodes.

codeforcescompetitive-programmingdata-structuresdpgreedytrees
CF 2101C - 23 Kingdom

We are asked to maximize the "beauty" of an array derived from a given array a. For each position in a, the new array b must satisfy 1 ≤ bi ≤ ai. The beauty of b is the sum of the largest gaps between repeated occurrences of each value in b.

codeforcescompetitive-programmingbinary-searchbrute-forcedata-structuresgreedyternary-searchtwo-pointers
CF 2101B - Quartet Swapping

We are given a permutation, which we can think of as a row of distinct numbered tiles. The only allowed move takes any block of four consecutive positions and swaps the first with the third and the second with the fourth, effectively turning a segment [ai, a{i+1}, a{i+2}…

codeforcescompetitive-programmingbrute-forcedata-structuresdivide-and-conquergreedysortings
CF 2101A - Mex in the Grid

We are asked to fill an $n times n$ grid with the integers from $0$ to $n^2 - 1$, each used exactly once. Every rectangular subgrid contributes a value equal to the MEX of the numbers inside it, and the objective is to maximize the sum of these MEX values over all possible…

codeforcescompetitive-programmingconstructive-algorithmsimplementation
CF 2102B - The Picky Cat

We are given an array where each element has a fixed absolute value that is unique across the array. We are allowed to flip the sign of any elements independently any number of times.

codeforcescompetitive-programmingimplementationsortings
CF 2102A - Dinner Time

We are trying to construct an integer sequence of length $n$, where we are allowed to use negative values, such that two different constraints hold at the same time. First, the total sum of the entire sequence must equal a given value $m$.

codeforcescompetitive-programmingconstructive-algorithmsmath
Kvant Math Problem 924

Each pair of points is connected by a directed edge, so the structure is a tournament.

kvantmathematicsolympiad
CF 2103F - Maximize Nor

We are asked to process an array of integers where each integer fits in k bits. For each position in the array, we must find the maximum value of a "bitwise nor" over all subarrays that include that position.

codeforcescompetitive-programmingbitmasksdata-structuresdpimplementationsortings
CF 2103E - Keep the Sum

We are given an array of integers a where every element lies between 0 and k. The allowed operation is to pick two distinct indices i and j such that a[i] + a[j] = k, and then redistribute a value x from a[i] to a[j] (or vice versa) while ensuring both elements remain in the…

codeforcescompetitive-programmingconstructive-algorithmsimplementationtwo-pointers
CF 2103D - Local Construction

We are given, for each position in an unknown permutation, the iteration at which the element at that position disappears under a deterministic pruning process.

codeforcescompetitive-programmingconstructive-algorithmsdfs-and-similarimplementationtwo-pointers
CF 2103C - Median Splits

We are given an array and asked whether we can cut it into three contiguous parts such that a particular condition involving medians holds across the cuts. If we pick two split points, the array is divided into three non-empty segments.

codeforcescompetitive-programmingbinary-searchgreedyimplementationsortings
CF 2103B - Binary Typewriter

We are given a binary string that we want to type using a very simple typewriter with only two keys, 0 and 1. At any moment, a finger rests on one of these two keys. Pressing the key under the finger outputs that character, while switching keys costs a separate operation.

codeforcescompetitive-programminggreedymath
CF 2103A - Common Multiple

We are given an array of positive integers and we want to select as many elements as possible while keeping their original order irrelevant since we are forming a subsequence.

codeforcescompetitive-programmingbrute-forcegreedyimplementationmath
CF 2104G - Modulo 3

We are given a functional graph, meaning each vertex has exactly one outgoing edge. This forms a combination of cycles and trees pointing into those cycles.

codeforcescompetitive-programmingdata-structuresdivide-and-conquerdsugraphstrees
CF 2104F - Numbers and Strings

We are asked to count the number of distinct strings generated by a simple, but slightly tricky rule. For each integer $x$ from 1 up to $n$, we form a string by concatenating $x$ and $x+1$, then sorting the digits of this concatenation.

codeforcescompetitive-programmingbinary-searchbrute-forcedfs-and-similardpimplementationmath
CF 2104E - Unpleasant Strings

We are given a fixed reference string s, and we are allowed to use only the first k lowercase letters. From this string s, we consider any string t to be “valid” if it can be formed by deleting characters from s without changing order, meaning t is a subsequence of s.

codeforcescompetitive-programmingbinary-searchdpgreedystrings
CF 2104D - Array and GCD

We are given an array of integers and we are allowed to modify it using a very specific resource system. Each increment of any element costs one coin, and each decrement of any element gives one coin.

codeforcescompetitive-programmingbinary-searchgreedymathnumber-theory
CF 2104A - Three Decks

We are given three stacks of cards arranged in a row, with the first stack containing a cards, the second b cards, and the third c cards. The numbers satisfy a < b < c.

codeforcescompetitive-programmingmath