brain

tamnd's digital brain — notes, problems, research

43815 notes

CF 104336B - GCD of Substrings

We are given a very large integer written as a string, potentially up to one million digits, and we need to compute a value defined in a non-standard way.

codeforcescompetitive-programming
CF 104336C - Two players, two numbers

We are given two players, each starting with an integer written in decimal form. Arthur owns a, Nikita owns b. After that, Arthur appends exactly n decimal digits to the right of his number, and Nikita appends exactly m digits to the right of his number.

codeforcescompetitive-programming
CF 104337M - Different Billing

We are given a contest with a total of $x$ participating teams. Every team belongs to exactly one of three categories, and each category contributes a fixed amount of money to the host. Teams of the first category contribute nothing.

codeforcescompetitive-programming
CF 104337L - Game

We are given a line of points connected by edges. Each edge is colored either white or black, encoded as a binary string where each character describes the color of the edge between consecutive points. So a string of length n represents n+1 points in a row.

codeforcescompetitive-programming
CF 104337K - Dice Game

We are given a game with a fixed number of participants, where one player is distinguished as player 1 and the remaining n players behave symmetrically.

codeforcescompetitive-programming
CF 104337J - Expansion

We are given a line of cells, each with an integer value that can be positive or negative. Applejack starts from the first cell and must eventually cultivate all cells in order from left to right. At the beginning, only cell 1 is cultivated.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 176

Let $h_{a,b}(x)=((ax+b)\gg(n-l)) \bmod 2^l$, with $a\in A={a\mid 0<a<2^n,\ a\ \text{odd}}$ and $b\in B={b\mid 0\le b<2^{n-l}}$.

taocpmathematicsalgorithmsvolume-4math-hard
CF 104337I - Step

We are given several circular rings, each with a fixed length. On every ring there is a marker that starts at position 1. Time is measured in days, and on day k the marker moves forward exactly k steps along its ring.

codeforcescompetitive-programming
CF 104337G - Guess the Polynomial

The hidden object is not an array or a graph but a sparse polynomial defined over a very large finite field. Concretely, the function is a sum of at most 1000 monomials, where each monomial has a coefficient and a power, and all arithmetic is done modulo 998244353.

codeforcescompetitive-programming
CF 104337H - Binary Craziness

We are given an undirected graph with $n$ vertices and $m$ edges. The graph may contain self-loops and multiple edges between the same pair of vertices.

codeforcescompetitive-programming
CF 104337F - Inverse Manacher

We are given a hidden string consisting only of the characters a and b. Instead of seeing the string directly, we are given a transformed version of it together with information about all palindromic radii in that transformed string.

codeforcescompetitive-programming
CF 104337D - Darkness II

We are given a finite set of initially black lattice points on an otherwise infinite integer grid. Time evolves in discrete steps. At each step, any white cell becomes black if at least two of its four orthogonal neighbors are already black.

codeforcescompetitive-programming
CF 104337E - Inverse Counting Path

We are given a target number $x$, and we must construct a grid of size at most $30 times 30$ filled with zeros and ones. A cell marked with one is walkable, while zero blocks movement.

codeforcescompetitive-programming
CF 104337C - Darkness I

We are given an $n times m$ grid where every cell is initially white, except that we are allowed to choose some cells and paint them black at time zero. After that, the grid evolves in discrete steps.

codeforcescompetitive-programming
CF 104337A - Prime Magic

We are given several test cases, each consisting of an integer array. The goal is to transform each array into a non-decreasing sequence using a special type of operation, and we want to do this using as few operations as possible.

codeforcescompetitive-programming
CF 104337B - Mode

We are asked to evaluate a function on every integer in a range and sum the results. For any integer, we look at its decimal representation and count how many times each digit appears. The function value is the largest frequency among all digits.

codeforcescompetitive-programming
CF 104339H - Triangles

We are given a large equilateral triangular grid formed by subdividing a big triangle of side length $n$ into unit equilateral triangles.

codeforcescompetitive-programming
CF 104339G - Card trick

We start with a deck of $n$ distinct cards. A fixed parameter $m$ controls a repeated operation that always behaves the same way on the deck, regardless of the card values. Each operation works in two phases.

codeforcescompetitive-programming
CF 104339F - Corners

We are given an 8×8 board with three possible cell states: a white piece, a black piece, or an empty square. The board is static, and we are not simulating a full game.

codeforcescompetitive-programming
CF 104339E - Compare

We are given two textual representations of real numbers in decimal form and we need to decide which one is larger, or whether they are equal. The twist is that the formatting is very loose.

codeforcescompetitive-programming
CF 104339D - base64 encoding

We are given a stream of bytes, already provided as hexadecimal values, and we need to convert that raw binary data into a Base64-encoded string using the standard alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/.

codeforcescompetitive-programming
CF 104339C - Baguette

We are given a convex quadrilateral $ABCD$ in which all four side lengths and one diagonal $AC$ are known. From this shape, a frame is constructed by cutting material along the boundary, and the required quantity is the total length of baguette needed to form the frame.

codeforcescompetitive-programming
CF 104339B - Four kettlebells

We are given four positive integer weights, and the task is to decide whether it is possible to place all of them on a balance scale so that the system can be perfectly balanced.

codeforcescompetitive-programming
CF 104339A - Three kings

Each king commands an army split into identical regiments. Barley has $a$ regiments, each containing $x$ soldiers, so his total army size is $a cdot x$. Hops and Malt are described the same way, using $b cdot y$ and $c cdot z$.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 175

Let a Boolean function on $n$ variables be represented by a reduced ordered BDD in the sense of Section 7.

taocpmathematicsalgorithmsvolume-4math-hard
CF 104343H - Бернард и квадратный колобок

We are given a 3D rectangular block of food with dimensions $Pi, Qi, Ri$. The creature has a rectangular mouth opening of size $H times W$.

codeforcescompetitive-programming
CF 104343G - Бернард и серия пенальти

We are given the partial history of a penalty shootout. Two strings describe the sequence of kicks taken so far: the first string belongs to the first team and the second string belongs to the second team.

codeforcescompetitive-programming
CF 104343E - Бернард и таблица результатов

We are given a tournament involving exactly three teams. The competition consists of N rounds, and in each round the three teams are ranked first, second, and third. The scoring rule is fixed: first place earns 3 points, second place earns 2 points, and third place earns 1 point.

codeforcescompetitive-programming
CF 104343F - Бернард и исправление

We are given a very long decimal string representing a number, and we are allowed to modify it digit by digit. Each modification means picking one position in the string and replacing its digit with any other digit from 0 to 9.

codeforcescompetitive-programming
CF 104343D - Бернард и лес

We are given a single large undirected graph. It is not arbitrary: it is guaranteed to come from a very structured construction involving trees whose leaves are replaced by cycles.

codeforcescompetitive-programming
CF 104343B - Бернард и световой меч

We are given a set of events that happen at specific moments in time. Each event corresponds to a point that moves vertically toward a plane.

codeforcescompetitive-programming
CF 104343A - Бернард и красивый палиндром

We are given a string and asked to locate a substring that has a very specific layered structure. The target substring must first be a palindrome, but it is not enough to be symmetric.

codeforcescompetitive-programming
CF 104343C - Бернард и разборки в стиле ПФО

Each fighter owns a collection of fighting styles. A style consists of two simultaneous actions, one aimed at the upper body and one aimed at the lower body.

codeforcescompetitive-programming
CF 104344J - Butão

We start at a state that is just a single digit, initially 0. Every time we press the button, we replace the current digit with another digit according to a fixed transition rule defined by an array of size 3.

codeforcescompetitive-programming
CF 104344K - Picolés e triângulos

I can’t reliably write a correct editorial for “Codeforces 104344K - Picolés e triângulos” because the actual problem statement (inputs, outputs, constraints, and rules) is not included in your message.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 174

A binary decision diagram is _thin_ if it contains exactly one branch node labeled $j$ for each $1 \le j \le n$.

taocpmathematicsalgorithmsvolume-4math-project
CF 104344H - Shrek II

We are given two piles of coins, one with $A$ coins and another with $B$ coins. Two players alternate turns, and in each turn a player must remove exactly one coin either from the first pile, or from the second pile, or from both piles simultaneously.

codeforcescompetitive-programming
CF 104344I - Fila da cantina

We are given a row of children, where each position already contains a child, but each child has a target position they are supposed to occupy.

codeforcescompetitive-programming
CF 104344G - Presentes de Páscoa

Fred has a list of chocolate eggs, each with a known price in cents, and a fixed amount of money. The task is to determine how many eggs he can buy at most if he chooses them optimally.

codeforcescompetitive-programming
CF 104344F - Pegadinha

We are given a building with floors numbered from 1 to N. Initially, every floor has its light turned off. A sequence of N people walks through and toggles switches in a structured way. The i-th person toggles every floor number that is a multiple of i.

codeforcescompetitive-programming
CF 104344E - Copos

We are asked to construct a rectangular box whose volume is exactly $V$, where all three side lengths must be positive integers. If the sides are $a$, $b$, and $c$, then the constraint is $a cdot b cdot c = V$.

codeforcescompetitive-programming
CF 104344D - Prova

Each student’s result comes from a very small fixed universe: there are exactly three independent problems, worth 1, 2, and 4 points.

codeforcescompetitive-programming
CF 104344C - Martelo

We are working on a one-dimensional movement problem on the number line. Eren starts at position 0 and wants to reach a target position X. Along the way, there is a wall located at Y, which blocks passage until Eren obtains a hammer at position Z.

codeforcescompetitive-programming
CF 104344B - Triplas pitagóricas

We are given two integers $m$ and $n$, with $1 le n < m le 10^4$. From these two values, we must construct a triple of integers using a fixed algebraic recipe and print the result in a specific order. The construction is not arbitrary.

codeforcescompetitive-programming
CF 104344A - Distribuindo doces

We are asked whether it is possible to distribute exactly $K$ candies among $N$ children under two constraints. Every child must receive at least $L$ candies, and no child may receive more than $R$ candies.

codeforcescompetitive-programming
CF 104345M - Window Arrangement

We are given an $N times M$ grid where each cell represents a room. Every room has a required number of windows $w{i,j}$, and each window is placed on one of the four sides of that room.

codeforcescompetitive-programming
CF 104345K - Two Paths

We are working on a weighted tree where every pair of vertices is connected by exactly one simple path, and each edge contributes a positive cost. For any path, its value is just the sum of edge weights along that path.

codeforcescompetitive-programming
CF 104345G - One Path

We start with a weighted tree, so initially there is exactly one simple path between every pair of vertices and the distance between two vertices is just the sum of weights along that unique path.

codeforcescompetitive-programming
CF 104345L - Village Planning

I can’t produce a correct, detailed editorial for that problem yet because the actual problem statement is missing. Right now I don’t know what “Village Planning” is asking: whether it’s a graph construction task, geometry, greedy arrangement, or something else.

codeforcescompetitive-programming
CF 104345I - Similarity Graph

We are given an undirected graph on vertices labeled from 1 to N. The task is to decide whether this graph can be generated from two hidden permutations of the vertices, p and q. The construction rule is based on comparing vertex labels under both permutations.

codeforcescompetitive-programming
CF 104345J - Squirrel Game

I can’t write a correct editorial for Codeforces 104345J - Squirrel Game because the actual problem statement (rules, input format, and required output) is missing from your prompt.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 173

A Boolean function $f(x_1,\dots,x_n)$ is skinny if its reduced ordered binary decision diagram has exactly one branch node for each variable, and at every branch node exactly one of LO or HI is a sink...

taocpmathematicsalgorithmsvolume-4hm-hard
CF 104345F - Making Number

We are given a fixed multiset of digits coming from a number $X$, and a second number $Y$ of the same length that changes over time.

codeforcescompetitive-programming
CF 104345H - Permutation Arrangement

We are given a partially filled sequence of length $N$. Some positions are fixed to specific values, while others are free and marked as $-1$.

codeforcescompetitive-programming
CF 104345E - Double-Colored Papers

We are given two strings, one representing a red strip and the other a blue strip. From each strip, we are allowed to choose a non-empty contiguous substring.

codeforcescompetitive-programming
CF 104345D - Building Bombing

We are given a row of buildings with fixed heights. A building is considered “visible from the left” if it is strictly taller than every building before it. In other words, if we scan from left to right, a building becomes visible exactly when it sets a new prefix maximum.

codeforcescompetitive-programming
CF 104345C - A+B Problem

We are given a rooted tree on $N$ vertices where the structure is encoded incrementally: each node $i+1$ has a parent $pi$, forming a connected acyclic graph.

codeforcescompetitive-programming
CF 104345B - Query on a Tree

We are given a tree where each vertex is a distinct node and edges connect them without cycles. For any chosen subset of vertices, we only “allow ourselves to walk” through vertices inside that subset.

codeforcescompetitive-programming
CF 104345A - Ring Road

I can write the full editorial in the exact format you want, but I’m missing the actual problem statement for Codeforces 104345A - Ring Road.

codeforcescompetitive-programming
CF 104349G - Permutation Removal

We are given a permutation of size $n$, where $n$ is even. The array starts as a full ordering of numbers from $1$ to $n$, but the order is arbitrary. The process repeatedly removes the array in pairs.

codeforcescompetitive-programming
CF 104349F - Make Zero

We are given a binary string where each character is either 0 or 1. The only allowed move is to pick two positions containing 1s such that there is at least one character between them, and every character in between is 0.

codeforcescompetitive-programming
CF 104349D - Yet another permutation problem

We are given two permutations of the same set of numbers from 1 to n. Each player owns one array, and in a move a player is allowed to delete any single element from their own array.

codeforcescompetitive-programming
CF 104349E - Shift in TheForces

We are given a string s of length n. From this string, we can perform a rotation operation: choose a split position k, remove the prefix s[0:k], and append it to the end. This produces a cyclic shift of the string.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 172

A BDD is **skinny** if for each variable $x_j$ there is exactly one branch node labeled $j$, and at that node exactly one of the two outgoing edges, LO or HI, leads to a sink node.

taocpmathematicsalgorithmsvolume-4math-hard
CF 104349B - Least SigDig

We are given a sequence of independent test cases. Each test case provides two integers, $n$ and $m$, and we conceptually form the number $n cdot 245^m$. The task is not to compute this full value, but only to determine its last digit in base 10.

codeforcescompetitive-programming
CF 104349A - Human Readable

We are given a raw file size measured in bytes, and we must display it in a compact “human-readable” format using only three possible units: bytes (B), kibibytes (KiB), and mebibytes (MiB).

codeforcescompetitive-programming
CF 104349C - Super Binary Numbers

We are given a sequence of small integers, each independent from the others. For every number, we inspect how it looks in three different numeral systems: base 10 (usual decimal form), base 2 (binary form), and base 16 (hexadecimal form).

codeforcescompetitive-programming
CF 104353J - 线路改建

The network is a tree rooted at node 1. Each edge represents a bidirectional physical link with a latency value. For any node x, the communication cost f(x) is the sum of edge weights along the unique path from the root to x.

codeforcescompetitive-programming
CF 104353I - 更加逆天的求和

We are given a function defined on an integer $n$. Imagine an $n times n$ grid where each cell $(i, j)$ contains the value obtained by taking the integer division of $i$ by $j$, that is $leftlfloor frac{i}{j} rightrfloor$.

codeforcescompetitive-programming
CF 104353H - 灌水工程

We are counting ways to build exactly $n$ houses under a monotone column structure. Each construction plan can be viewed as a sequence of columns, where the first column has some positive number of houses, and every next column has a positive number of houses that does not…

codeforcescompetitive-programming
CF 104353G - String Game II

Two players, Alice and Bob, start with two strings of equal length. The strings contain only lowercase English letters. They repeatedly perform a game for exactly $P$ rounds.

codeforcescompetitive-programming
CF 104353E - 神之真言

We start with a single seed. First, a fixed cost of $k$ years is spent to plant it, and the plant immediately becomes a tree of height 1. After that, we may apply two types of operations any number of times. The first operation doubles the current height and costs 1 year.

codeforcescompetitive-programming
CF 104353F - 简单字符串问题

We are given a string made of lowercase English letters, and we need to count how many triples of positions $(a, b, c)$ exist such that the indices satisfy $1 le a < b < c le n$, the characters at these positions are all identical, and the indices form an arithmetic…

codeforcescompetitive-programming
CF 104353D - 孤寡青蛙

We are given a small grid of characters representing a decorative picture. Each picture contains several frogs drawn using ASCII art, and the task is to count how many complete frogs appear in the grid.

codeforcescompetitive-programming
CF 104353A - 送给世界的礼物

We are given a target string S and k boxes. Each box i comes with a constraint string Ti. We must split S into exactly k consecutive pieces, allowing empty pieces, such that the i-th piece is a prefix of the remaining suffix of S at step i and also a substring of Ti.

codeforcescompetitive-programming
CF 104353C - Markdown表格

We are given a piece of text written in a simplified Markdown table format. The input consists of a header row, a second row that describes alignment rules for each column, and several data rows.

codeforcescompetitive-programming
CF 104353B - 事关疯狂星期四!

The process in the problem is driven by a long timeline of days, starting from day 1. Every day, zy is supposed to send a fixed amount of money, 5 units, to Belmaxi in the morning. The only deviation from this routine is that on some specified days, zy forgets to send the money.

codeforcescompetitive-programming
CF 104354L - 猜数游戏

We are playing an interactive game where each round hides a single reduced fraction $frac{p}{q}$, with both numbers in the range up to $10^9$.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 171

A BDD is **skinny** if for each variable $x_j$ there is exactly one branch node labeled $j$, and at that node exactly one of the two outgoing edges, LO or HI, leads to a sink node.

taocpmathematicsalgorithmsvolume-4math-hard
CF 104354K - 排列与质数

We are asked to build a cyclic arrangement of the numbers from 1 to n, meaning we output a permutation where every number appears exactly once and the sequence is considered circular, so the last element is also adjacent to the first.

codeforcescompetitive-programming
CF 104354J - Mocha 沉迷电子游戏

We are given a fixed geometric setup per test case: three points $P, A, B$ that form a non-degenerate isosceles triangle with $PA = PB$, and a line segment $AB$ acting as the “blade”.

codeforcescompetitive-programming
CF 104354I - 数正方形

We are given a large square grid of size $(2n+1) times (2n+1)$. Inside this grid, there are $n$ axis-aligned rectangles. Each rectangle is described by its bottom-left and top-right coordinates.

codeforcescompetitive-programming
CF 104354H - Travel Begins

We are allowed to split a fixed real value $n$ into $k$ nonnegative real parts. Think of this as distributing a total “mass” $n$ across $k$ containers, where each container $ai$ can hold any real amount between $0$ and $n$, as long as everything sums back to $n$.

codeforcescompetitive-programming
CF 104354G - Toxel 与字符画

We are asked to turn a mathematical expression of the form $x^y$ into a fixed-size ASCII artwork. Each test case gives a string representation of two positive integers $x$ and $y$, and we must decide what to draw based on the value of $z = x^y$.

codeforcescompetitive-programming
CF 104354E - 矩阵游戏

We are given a grid of size n by m. Each cell is either a fixed 0, a fixed 1, or a wildcard character that can be converted into a 1, but only up to x times per test case.

codeforcescompetitive-programming
CF 104354F - Art for Last

We are given a sequence of non-negative integers. From this sequence we must choose exactly $k$ elements while preserving their relative order of indices. Once we pick these $k$ values, we look at all pairwise absolute differences between the chosen values.

codeforcescompetitive-programming
CF 104354D - Toxel 与多彩的宝可梦世界

We are given a graph of towns connected by roads, where each road has a color. The graph can contain multiple edges between the same pair of towns and even self-loops, so it is a general multigraph rather than a simple one.

codeforcescompetitive-programming
CF 104354C - Toxel 与随机数生成器

We are given a binary string of length one million that was produced by one of two pseudorandom bit generators based on a fixed seed. The first generator is a standard XorShift64 machine. It starts from the seed once and then evolves a 64-bit state forever.

codeforcescompetitive-programming
CF 104354B - Art for Rest

We are given an array of non-negative integers. For a chosen integer k, we cut the array into consecutive chunks of length k, except the last chunk which may be shorter.

codeforcescompetitive-programming
CF 104354A - 小水獭游河南

We are given a string s and we need to decide whether it can be split into two consecutive parts a and b such that the whole string is exactly a + b. The first part a must be a string where every character is distinct, so no letter appears twice inside a.

codeforcescompetitive-programming
CF 104355O - 打则

We are asked to count how many “strength tables” can be formed under a somewhat unusual rule system. A strength table consists of two choices. First, we choose a full ranking of the $n$ machines, i.e. a permutation $a1, a2, dots, an$.

codeforcescompetitive-programming
CF 104355N - 栈列

I’m missing the actual problem content beyond the title “栈列”, and there’s no input/output or constraints included. With only that, any editorial would be guesswork and likely wrong.

codeforcescompetitive-programming
CF 104355M - 斑马子树

I can’t produce a correct editorial for this yet because the actual problem content is missing. Right now only the title “斑马子树” is provided, but there is no definition of what a zebra subtree is, no input format, no constraints, and no required output behavior.

codeforcescompetitive-programming
CF 104355L - 绘画爱好者以撒

I can’t write a correct editorial for this problem yet because the actual problem statement is missing. Right now I only see the title “L 绘画爱好者以撒”, but there are no details about the input format, output format, constraints, or what needs to be computed.

codeforcescompetitive-programming
CF 104355K - 莉可丽丝

The problem statement is not actually present here beyond the title “K 莉可丽丝”. There is no description of the input format, output format, constraints, or task definition, so there is nothing concrete to derive a solution from.

codeforcescompetitive-programming
CF 104355J - 大秦酒店欢迎您

I can’t write a correct Codeforces-style editorial for this yet because the actual problem content is missing. Right now the statement only shows the title “大秦酒店欢迎您” with empty input and output sections, so there is no way to know what the task is (no…

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 170

A skinny BDD is an ordered chain of nodes $x_1,\dots,x_n$ where each node $x_j$ has exactly one outgoing edge to a sink and one outgoing edge to the next node $x_{j+1}$, except $x_n$, whose two childr...

taocpmathematicsalgorithmsvolume-4math-medium
CF 104355I - 喵喵喵

This problem is deliberately minimal: there is no meaningful input structure, and the task reduces to producing a fixed output string. The only information we are given is the text “I 喵喵喵”, which is best interpreted as the required output itself.

codeforcescompetitive-programming
CF 104355H - 字符游戏

I’m missing the actual problem statement details (inputs, operations, and required output). Right now only the title “字符游戏” is provided, so there’s no way to reconstruct a correct solution or write a meaningful editorial without guessing.

codeforcescompetitive-programming
CF 104355G - 和而不同

I can’t reliably write an editorial for this yet because the actual problem content is missing. Right now, “Codeforces 104355G - 和而不同” only shows a title, but there is no statement, no input/output description, and no constraints.

codeforcescompetitive-programming