brain

tamnd's digital brain — notes, problems, research

41230 notes

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
CF 104355F - 渡渡鸟游乐场

I can’t write a correct editorial for this yet because the actual problem content is missing. Right now the statement only shows the title, input/output sections are empty, and there’s no description of what operations, structures, or constraints are involved.

codeforcescompetitive-programming
CF 104355E - 全错

I can’t write a correct editorial for this because the actual problem content is missing. What you provided only includes the title “E 全错” without any description, input/output format, or constraints.

codeforcescompetitive-programming
CF 104355D - 点集扩张

The problem statement is missing from your prompt (it only shows the title “点集扩张” without any description, input, or rules). Without that, I can’t reliably reconstruct the task or produce a correct Codeforces-style editorial.

codeforcescompetitive-programming
CF 104355A - 大水题

The problem statement is intentionally minimal, essentially just labeling the task as a “big easy problem” without specifying any real computation.

codeforcescompetitive-programming
CF 104355C - 话剧

I can’t reliably write a correct editorial from that yet because the actual problem content is missing. Right now you’ve only provided the title “话剧”, but there are no constraints, no input/output format, and no description of what needs to be computed.

codeforcescompetitive-programming
CF 104355B - 原粥率

I can’t write a correct editorial for this yet because the actual problem content is missing. Right now we only have the title “原粥率” and no description, input format, or required output behavior, which makes it impossible to reconstruct the algorithm without guessing.

codeforcescompetitive-programming
CF 104359F - Пазл

We are given two configurations of a very thin grid with two rows and many columns. Each cell contains either a 0 or a 1. In one configuration we start with some arrangement of ones and zeros, and in the other configuration we want to reach a target arrangement.

codeforcescompetitive-programming
CF 104359E - Пират Серёжа

We are given a grid of size $n times m$ that contains each integer from $1$ to $nm$ exactly once. Think of each number as occupying a unique cell in a grid graph where movement is allowed only between edge-adjacent cells. We are allowed to construct a walk on this grid.

codeforcescompetitive-programming
CF 104359D - Шлюзы

We are given a linear system of water tanks arranged in a row. Each tank has a fixed capacity. Initially all tanks are empty, and each tank has a pipe that can be turned on, producing a constant inflow of one unit of water per second into that tank.

codeforcescompetitive-programming
CF 104359A - Вордл наоборот

We are given a secret word S of length n, where all characters are distinct, and a color pattern P describing how another unknown guessed word T was evaluated against S using Wordle rules. The evaluation works position by position. If T[i] equals S[i], the result is green.

codeforcescompetitive-programming
CF 104359B - Палиндромные числа

We are given a decimal number represented as a string of length $n$. Our task is to construct another positive integer of the same length, also with no leading zeros, such that when we add it to the given number digit by digit, the resulting sum forms a palindrome.

codeforcescompetitive-programming
CF 104359C - Помогаем природе

We are given an array representing moisture levels along a line of trees. Each operation modifies a contiguous segment in a very structured way. One operation decreases a prefix by 1, another decreases a suffix by 1, and a third operation increases the entire array by 1.

codeforcescompetitive-programming
CF 104360F - Необычный массив

We are given an array and we focus on each position independently. Fix an index $i$. We look at every contiguous subarray that contains this index. For each such subarray, we sort its elements and locate the value $ai$ inside this sorted list.

codeforcescompetitive-programming
CF 104360E - Игра с картами

We are given a sequence of moves. At the start, Bob holds two integers, one in his left hand and one in his right hand, both equal to zero. At each move i, Alice presents a new number ki. Bob must choose whether to replace the value in his left hand or in his right hand with ki.

codeforcescompetitive-programming
CF 104360D - PriceFixed

We are given several product types, each requiring a fixed number of purchases. Every purchase normally costs 2 units of money. There is a global counter that increases every time we buy any item, regardless of type.

codeforcescompetitive-programming
CF 104360A - Старт олимпиады

There are $n$ participants taking part in an olympiad. Each participant $i$ starts at a fixed time forming an arithmetic progression: the first starts at time $0$, the second at time $x$, the third at $2x$, and so on, so participant $i$ starts at $(i-1)x$.

codeforcescompetitive-programming
CF 104360C - Стабильные параллели

We are given a collection of student skill levels, and we want to split them into several groups called parallel classes. Inside each class, if we sort students by skill, every adjacent pair must differ by at most a fixed value x.

codeforcescompetitive-programming
CF 104360B - Вася и Петя

We are given a string of lowercase English letters. Each query selects a contiguous substring, and we transform that substring using a fixed rule: every character is expanded independently, where a letter at position x in the alphabet is repeated exactly x times.

codeforcescompetitive-programming
CF 104361E - Шахматные баталии

We are working on a rectangular grid of size $2n times 2m$ with a fixed chess coloring: a cell $(i, j)$ is white if $i + j$ is even, otherwise it is black. Only white cells matter for the game.

codeforcescompetitive-programming
CF 104361D - Перевернутые родословные

We are given a structure on $n$ labeled people where each person has either zero or exactly one child. If a person has no child, their outgoing pointer is 0. Otherwise, every person points to exactly one child index in $[1, n]$.

codeforcescompetitive-programming
TAOCP 7.1.4 Exercise 17

A reduced ordered binary decision diagram (BDD) for a Boolean function $f(x_1,\dots,x_n)$ consists of a rooted directed acyclic graph in which each non-sink node $v$ has a variable index $V(v)\in{1,\d...

taocpmathematicsalgorithmsvolume-4hard
CF 104361B - Выбор цветов для букета

We are given a bouquet that must contain exactly n flowers, and there are m flower types. Each type can be used any number of times. The reward model for a type is not constant per flower.

codeforcescompetitive-programming
CF 104361C - Межпланетные электрички

We are working with a cyclic daily timetable split into minutes. A passenger railway service must run forever with a fixed periodic pattern: trains depart exactly every m/2 minutes, and each departure occupies the platform for a fixed interval before it.

codeforcescompetitive-programming