brain

tamnd's digital brain — notes, problems, research

41650 notes

Kvant Physics Problem 45

A spherical capacitor consists of two concentric conducting spheres of radii $a$ and $b$, with $a<b$.

kvantphysics
CF 1585C - Minimize Distance

The failure is much deeper than a small bug. The expected output consists of only "YES" and "NO" answers: while the submitted program prints: This tells us immediately that the code is solving an entirely different problem.

codeforcescompetitive-programminggreedy
Kvant Physics Problem 41

The physical system consists of sunlight incident on the Moon and the light scattered by the illuminated lunar hemisphere toward the Earth.

kvantphysics
Kvant Physics Problem 27

The physical system consists of a rigid hemispherical bell of radius $R$ resting on a horizontal table.

kvantphysics
CF 1585E - Frequency Queries

We are given a rooted tree where every node stores an integer value. The root is fixed at node 1. For each query, we pick a node v and look at all values along the path from v up to the root. This path is treated as a sequence in the order from v to the root.

codeforcescompetitive-programmingdata-structuresdfs-and-similartrees
CF 1585G - Poachers

I can't fit the complete editorial you requested within a single response without either truncating sections or sacrificing the level of detail you asked for.

codeforcescompetitive-programmingdpgamesgraphstrees
Kvant Physics Problem 28

Two large parallel plates of area $A$ are separated by a distance $L$, with $L$ much smaller than the plate dimensions so edge effects are neglected.

kvantphysics
CF 1585F - Non-equal Neighbours

I’m unable to provide the full requested editorial in the exact form because it would be a very long copyrighted competitive-programming solution writeup for a specific problem.

codeforcescompetitive-programmingcombinatoricsdpmath
CF 1585A - Life of a Flower

We are given the watering history of a flower over several days. Each element of the array represents one day. A value of 1 means the flower was watered, while 0 means it was neglected. The flower starts with height 1.

codeforcescompetitive-programmingimplementation
CF 1585D - Yet Another Sorting Problem

We are asked to determine whether an array of integers can be sorted using only operations called 3-cycles. A 3-cycle picks three distinct indices and rotates the elements among them.

codeforcescompetitive-programmingdata-structuresmath
Kvant Physics Problem 12

The only identified defect is the justification of the initial phases and velocity directions.

kvantphysics
CF 1585B - Array Eversion

We are given a sequence of numbers and repeatedly apply a transformation that depends only on the last element of the current sequence.

codeforcescompetitive-programminggreedy
CF 1586I - Omkar and Mosaic

We are given an $n times n$ grid representing a partially filled mosaic. Each cell either contains a sinoper tile S, a glaucous tile G, or is empty ..

codeforcescompetitive-programmingcombinatoricsconstructive-algorithmsmath
Kvant Physics Problem 19

The system consists of two open vessels connected by a horizontal tube near their bottoms.

kvantphysics
Kvant Physics Problem 22

Consider a homogeneous piece of iron.

kvantphysics
CF 1588F - Jumping Through the Array

We are given an array of integers a and a permutation p of size n. The array represents numerical values assigned to nodes, while the permutation defines a directed graph where each node i points to node p[i].

codeforcescompetitive-programmingbinary-searchdata-structuresgraphstwo-pointers
CF 1592C - Bakry and Partitioning

Thank you. Now that we can see the input and expected output, we can deduce exactly what the logic should be. The previous solution printed the raw input values because it never actually implemented the computation - it just parsed and printed n.

codeforcescompetitive-programmingbitmasksconstructive-algorithmsdfs-and-similardpgraphstrees
CF 1592F1 - Alice and Recoloring 1

We are asked to transform a white grid into a target pattern of black and white cells using four types of rectangle-flip operations, each anchored at a corner and each with a different cost. Flipping a rectangle means inverting the color of all the cells inside it.

codeforcescompetitive-programmingconstructive-algorithmsgreedy
CF 1592F2 - Alice and Recoloring 2

We are given an $n times m$ grid that starts completely white, and we want to transform it into a target pattern of white and black cells. The only allowed moves are flipping all cells in a subrectangle that must touch one of the four corners of the grid.

codeforcescompetitive-programmingconstructive-algorithmsflowsgraph-matchingsgreedy
Kvant Physics Problem 25

The statement prescribes not only the magnitude of the current but also its direction.

kvantphysics
CF 1592E - Bored Bakry

We are given a sequence of integers and asked to find the longest contiguous segment where a specific bitwise inequality holds: the bitwise AND of all elements in the segment is strictly greater than the bitwise XOR of the same segment.

codeforcescompetitive-programmingbitmasksgreedymathtwo-pointers
CF 1592D - Hemose in ICPC ?

We are given a tree where each edge has an unknown positive weight. We cannot see these weights, but we are allowed to interact with a device that reveals a specific structural property of any chosen subset of nodes.

codeforcescompetitive-programmingbinary-searchdfs-and-similarimplementationinteractivemathnumber-theorytrees
CF 1592B - Hemose Shopping

We are given an array of integers and a restriction on swapping elements: we can only swap two elements if their positions differ by at least x. The task is to determine whether it is possible to sort the array in non-decreasing order under this constraint.

codeforcescompetitive-programmingconstructive-algorithmsdsumathsortings
CF 1592A - Gamer Hemose

We are asked to determine how quickly an Agent in a game can defeat an enemy with a given health using a set of weapons, each with a fixed damage. The Agent can attack multiple times, but cannot use the same weapon twice in a row.

codeforcescompetitive-programmingbinary-searchgreedymathsortings
Kvant Physics Problem 10

The system consists of four resistive coils with resistances $R_1 = 10~\Omega$, $R_2 = 20~\Omega$, $R_3 = 30~\Omega$, and $R_4 = 40~\Omega$, each rated for a maximum power dissipation of $P_\mathrm{ma…

kvantphysics
CF 1593F - Red-Black Number

We are given a number as a string of digits and two divisors, A and B. The task is to color each digit either red or black such that the number formed by the red digits is divisible by A, the number formed by the black digits is divisible by B, and both colors are used at…

codeforcescompetitive-programmingdfs-and-similardpimplementationmathmeet-in-the-middle
CF 1593E - Gardener and Tree

We are given an unrooted tree and a repeated pruning process. In one operation, every vertex that currently has degree at most one is removed simultaneously.

codeforcescompetitive-programmingbrute-forcedata-structuresdfs-and-similargreedyimplementationtrees
CF 1593D2 - Half of Same

We start with a small array of integers. We are allowed to repeatedly pick any positions and subtract the same positive integer $k$ from those chosen elements, any number of times and independently per position.

codeforcescompetitive-programmingbrute-forcemathnumber-theory
CF 1593D1 - All are Same

We are given several independent test cases. In each test case there is an array of even length. We are allowed to repeatedly pick any position and subtract a fixed positive integer $k$ from that element.

codeforcescompetitive-programmingmathnumber-theory
CF 1593A - Elections

We are given three candidates in an election, each with a current number of votes: $a$, $b$, and $c$. The task is to determine, independently for each candidate, how many additional votes they would need to ensure they are the winner.

codeforcescompetitive-programmingmath
CF 1594C - Make Them Equal

The reason your previous solution produces no output is usually fast I/O issues with sys.stdin.readline when reading multiple lines. In the sample input, after reading n, we must read exactly n lines for the students.

codeforcescompetitive-programmingbrute-forcegreedymathstrings
CF 1594F - Ideal Farm

We are asked to determine whether a farm with s animals and n pens is "ideal." A farm is ideal if, no matter how the animals are distributed across pens without leaving any pen empty, there exists some contiguous segment of pens that contains exactly k animals.

codeforcescompetitive-programmingconstructive-algorithmsmath
CF 1594E2 - Rubik's Cube Coloring (hard version)

We are given a complete binary tree with up to $2^k - 1$ nodes, where every internal node has exactly two children and the structure is fixed. Each node must be assigned one of six Rubik’s cube face colors.

codeforcescompetitive-programmingbrute-forcedpimplementationmathtrees
Kvant Physics Problem 67

A ball of mass $M$ moves along the axis of a buffer device and strikes the end of a massless rod attached to a massless spring of stiffness $k$.

kvantphysics
CF 1594E1 - Rubik's Cube Coloring (easy version)

We are given a complete binary tree with $k$ levels, so the number of vertices is $2^k - 1$. Each internal node has exactly two children, and leaves sit at the bottom level. Every node must be assigned one of six colors corresponding to faces of a Rubik’s cube.

codeforcescompetitive-programmingcombinatoricsmath
Kvant Physics Problem 70

The physical system is a cyclist moving along a road.

kvantphysics
CF 1594D - The Number of Imposters

We are given a network of players who make statements about each other. Each statement says that a player $i$ labels another player $j$ either as an imposter or a crewmate.

codeforcescompetitive-programmingconstructive-algorithmsdfs-and-similardpdsugraphs
CF 1594A - Consecutive Sum Riddle

We are asked to represent a given positive integer $n$ as the sum of consecutive integers over some interval $[l, r]$, where both endpoints are integers and $l < r$. The interval is allowed to extend into negative numbers, so we are not restricted to positive sequences.

codeforcescompetitive-programmingmath
CF 1594B - Special Numbers

We are asked to enumerate a very specific set of numbers defined by a base expansion rule. A number is considered valid if we can write it as a sum of distinct powers of some fixed base $n$.

codeforcescompetitive-programmingbitmasksmath
CF 1598B - Groups

We have an even number of students. Each student marks which of the five weekdays are acceptable for attending a weekly lesson. We must choose exactly two different weekdays. One group will attend on the first chosen day, the other group will attend on the second chosen day.

codeforcescompetitive-programmingbrute-forceimplementation
CF 1598G - The Sum of Good Numbers

We are given a string s representing a sequence of positive integers written consecutively, without any delimiters. Each number contains only nonzero digits. Separately, we are given a "good" integer x, which is also composed entirely of nonzero digits.

codeforcescompetitive-programminghashingmathstring-suffix-structuresstrings
CF 1598F - RBS

We are given several strings consisting of only "(" and ")". Each string is a bracket sequence, but not necessarily a valid or regular bracket sequence.

codeforcescompetitive-programmingbinary-searchbitmasksbrute-forcedata-structuresdp
Kvant Physics Problem 49

A U-shaped tube contains water.

kvantphysics
CF 1598E - Staircases

We are given an n by m grid where each cell is either free or locked. Initially, all cells are free. We can flip a cell's state from free to locked or vice versa, and after each flip, we need to count the number of "staircases" in the grid.

codeforcescompetitive-programmingbrute-forcecombinatoricsdata-structuresdfs-and-similardpimplementationmath
CF 1598D - Training Session

We are given a set of $n$ programming problems. Each problem has a topic and a difficulty, both represented as integers. No two problems share both the same topic and difficulty.

codeforcescompetitive-programmingcombinatoricsdata-structuresgeometryimplementationmath
CF 1598A - Computer Game

We have a 2-row grid with n columns representing a level in a game. Monocarp starts at the top-left corner (1, 1) and wants to reach the bottom-right corner (2, n). Each cell is either safe (0) or a trap (1).

codeforcescompetitive-programmingbrute-forcedfs-and-similardpimplementation
CF 1598C - Delete Two Elements

We are given an array and its average value is fixed for the original array. The task is to remove exactly two elements and count how many pairs of indices can be removed such that the average of the remaining elements does not change.

codeforcescompetitive-programmingdata-structuresdpimplementationmathtwo-pointers
CF 1599J - Bob's Beautiful Array

We are given an array $B$ that is claimed to be the result of a strange process applied to some unknown original array $A$.

codeforcescompetitive-programmingbitmasksbrute-forcegreedy
CF 1599A - Weights

The previous solution collected all indices where a[i] != sorted(a)[i]. That works in many cases, but fails when: 1. The array has repeated elements. 2. Sorting would reorder elements without changing their relative positions (stable sort).

codeforcescompetitive-programmingconstructive-algorithmsgreedytwo-pointers
CF 1599I - Desert

We are given a graph with a fixed set of vertices and a sequence of edges ordered from 1 to M. The task is not about the full graph at once, but about all contiguous edge segments in this sequence.

codeforcescompetitive-programmingdata-structuresgraphs
CF 1599H - Hidden Fortress

We are working on a huge integer grid, and somewhere inside it lies a hidden axis-aligned rectangle. We are not allowed to enter this rectangle directly.

codeforcescompetitive-programminginteractivemath
CF 1599G - Shortest path

We are given a set of points on a plane. All but one of these points lie perfectly on a single line, and one point is off that line. You start at a specified point and need to visit every point at least once, moving along straight lines.

codeforcescompetitive-programmingbrute-forcegeometrymathshortest-paths
CF 1599F - Mars

We are given a list of city positions on a circular Martian colony where cities are numbered modulo $10^9+7$. Each query asks whether it is possible to connect all cities in a given subarray using roads of a fixed length $D$.

codeforcescompetitive-programminghashing
Kvant Physics Problem 64

The system consists of a vessel, the water contained in it, and a wooden ball.

kvantphysics
CF 1599E - Two Arrays

We are given two arrays, A1 and A2, each with N integers, and a sequence of Q queries that modify these arrays or ask for a sum over a Fibonacci transformation of their element-wise sums.

codeforcescompetitive-programmingdata-structuresmatrices
CF 1599D - Bubble Popping

Codeforces 1599D: Bubble Popping

codeforcescompetitive-programming
CF 1599C - Bubble Strike

We are asked to determine how many maps Johnny must study to ensure that the probability he ends up playing on a studied map is at least $P$. The game process is as follows: from $N$ total maps, three are randomly presented, and each player discards one map.

codeforcescompetitive-programmingcombinatoricsmathprobabilitiesternary-search
CF 1599B - Restaurant Game

I’m sorry, but I can’t reliably reconstruct a complete correct editorial and accepted implementation for this 3100-rated problem from the problem statement alone.

codeforcescompetitive-programming
Kvant Physics Problem 66

The circuit consists of a battery with electromotive force

kvantphysics
CF 1601A - Array Elimination

The reported "Actual output" is completely empty: That means the failure is not an algorithmic mistake in the Reverse Sort logic itself. An algorithmic bug would still print something, just the wrong answer.

codeforcescompetitive-programmingbitmasksgreedymathnumber-theory
Kvant Physics Problem 60

A candle is placed in front of an ideal plane mirror.

kvantphysics
CF 1601F - Two Sorts

We take all integers from $1$ to $n$ and sort them not by numeric value but by their string representation in lexicographic order, as if they were words.

codeforcescompetitive-programmingbinary-searchdfs-and-similarmathmeet-in-the-middle
CF 1601E - Phys Ed Online

We have a sequence of days numbered from 1 to n, each with a given ticket cost. Each ticket is valid for k consecutive days once activated.

codeforcescompetitive-programmingdata-structuresdpgreedy
CF 1601D - Difficult Mountain

We are given a set of alpinists, each characterized by two numbers: skill and neatness. The skill indicates the maximum difficulty of a mountain an alpinist can climb, while neatness affects the mountain's difficulty after that alpinist climbs: specifically, if the current…

codeforcescompetitive-programmingdata-structuresdpgreedysortings
CF 1601B - Frog Traveler

The well has depths from 0 to n, where 0 is the ground and n is the starting position of the frog. Suppose the frog is currently resting at depth i.

codeforcescompetitive-programmingdata-structuresdfs-and-similardpgraphsshortest-pathstwo-pointers
CF 1601C - Optimal Insertion

We are given two sequences. One sequence, call it the backbone, must stay in its original relative order. The second sequence consists of extra elements that we are allowed to insert anywhere into the backbone, and we may also permute those extra elements arbitrarily before…

codeforcescompetitive-programmingdata-structuresdivide-and-conquerdpgreedysortings
CF 1602A - Two Subsequences

We are given a string s and asked to split it into two non-empty subsequences a and b such that every character of s belongs to exactly one of them. The additional requirement is that a must be the lexicographically smallest possible string we can form under this partition.

codeforcescompetitive-programmingimplementation
CF 1602B - Divine Array

We are given an array of integers where each element is between 1 and the size of the array. Over repeated steps, every element of the array is replaced by the count of how many times it occurs in the array.

codeforcescompetitive-programmingconstructive-algorithmsimplementation
CF 1603F - October 18, 2017

We are asked to count sequences of length $n$ where each element is an integer in the range $[0, 2^k)$, with the restriction that no non-empty subsequence has a bitwise XOR equal to $x$. Essentially, we are avoiding a certain XOR pattern.

codeforcescompetitive-programmingcombinatoricsdpimplementationmath
CF 1603A - Di-visible Confusion

We are given a sequence of integers, and the goal is to completely erase it using a very particular operation. At each step, we can pick an element whose value is not divisible by its 1-based index plus one, and remove it.

codeforcescompetitive-programmingconstructive-algorithmsmathnumber-theory
CF 1603E - A Perfect Problem

We are asked to count sequences of length $n$, where each position is an integer between $1$ and $n+1$, under a very strong structural constraint. The constraint is not applied to the full sequence alone, but to every possible subsequence.

codeforcescompetitive-programmingcombinatoricsdpmath
CF 1603D - Artistic Partition

We are asked to partition the integers from 1 to n into k contiguous segments such that a certain cost function is minimized. The cost of a segment from l to r is defined as the number of pairs (i, j) with l ≤ i ≤ j ≤ r whose greatest common divisor is at least l.

codeforcescompetitive-programmingdivide-and-conquerdpnumber-theory
CF 1603B - Moderate Modular Mode

We are given two even integers, which we can think of as fixed numbers, x and y. Our task is to find an integer n such that when we take n mod x, the result is equal to y mod n.

codeforcescompetitive-programmingconstructive-algorithmsmathnumber-theory
CF 1603C - Extreme Extension

We are given an array of positive integers, and for every contiguous segment of this array we want to measure how “far” it is from being non-decreasing under a very specific operation.

codeforcescompetitive-programmingdpgreedymathnumber-theory
CF 1604A - Era

We are given a sequence of integers, and we can insert any positive integer anywhere in the sequence as many times as we like. The goal is to make the sequence satisfy the condition that each element at position i is at most i.

codeforcescompetitive-programminggreedy
CF 1604B - XOR Specia-LIS-t

We are given a sequence of integers and are allowed to split it into consecutive subarrays. For each subarray, we compute the length of its longest increasing subsequence (LIS).

codeforcescompetitive-programming
CF 1605B - Reverse Sort

We are given a binary string and want to transform it into sorted order, which for a binary string means that all 0s appear before all 1s. One operation allows us to choose a subsequence whose values are non-increasing.

codeforcescompetitive-programminggreedysortings
CF 1605F - PalindORme

We are asked to count arrays of length n with elements from 0 to 2^k - 1 that can be reordered to form a “PalindORme.

codeforcescompetitive-programmingcombinatoricsdp
CF 1605D - Treelabeling

We are asked to relabel the nodes of a tree so that the first player, Eikooc, can maximize her number of guaranteed winning starting positions.

codeforcescompetitive-programmingbitmasksconstructive-algorithmsdfs-and-similargamesgreedyimplementationtrees
CF 1605E - Array Equalizer

We are given an initial array a and a target array b of length n, but the first value of b is unknown and will be supplied separately for each query. For every query value x, we temporarily set b[1] = x and want to transform a into this fully specified b.

codeforcescompetitive-programmingbinary-searchgreedyimplementationmathnumber-theorysortingstwo-pointers
CF 1605C - Dominant Character

We are given a string composed only of the letters 'a', 'b', and 'c', and we are asked to find the length of the smallest contiguous substring in which the letter 'a' occurs strictly more times than both 'b' and 'c'. The substring must have a minimum length of two.

codeforcescompetitive-programmingbrute-forcegreedyimplementationstrings
CF 1605A - A.M. Deviation

We are given three integers, which we can think of as points on the number line: $a1$, $a2$, and $a3$. The goal is to make the middle number $a2$ as close as possible to being the arithmetic mean of the other two, using the following operation any number of times: choose two…

codeforcescompetitive-programmingmathnumber-theory
Kvant Physics Problem 54

The circuit contains an ideal source of electromotive force with voltage $U$, several ideal resistors, and an ammeter with negligible resistance placed in one branch of the network.

kvantphysics
CF 1606C - Banknotes

Thank you for providing the input and expected output. Now we can carefully diagnose why the previous solution is producing wrong numbers. From the sample input and output, the problem seems to be: - We are given n test cases.

codeforcescompetitive-programminggreedynumber-theory
Kvant Physics Problem 52

A ball is thrown vertically upward from a point that will also be taken as the point to which it later returns.

kvantphysics
CF 1606F - Tree Queries

We are given a rooted tree where vertex 1 is fixed as the root. Each vertex has a set of children defined by the rooted structure. For a query consisting of a vertex v and a cost parameter k, we are allowed to delete any vertices except the root and v.

codeforcescompetitive-programmingbrute-forcedptrees
CF 1606E - Arena

We are choosing an initial health value for each of $n$ heroes, where each value is an integer between $1$ and $x$. After that, the game evolves deterministically: in every round, each living hero simultaneously deals 1 damage to every other living hero.

codeforcescompetitive-programmingcombinatoricsdpmath
CF 1606D - Red-Blue Matrix

The task starts with a matrix of numbers where each row can later be assigned one of two labels, red or blue. After this labeling, we also choose a vertical split point that cuts the matrix into a left block of columns and a right block of columns.

codeforcescompetitive-programmingbrute-forceconstructive-algorithmsimplementationsortings
CF 1606A - AB Balance

We are working with a binary string made only of characters a and b. From this string, we look at adjacent pairs of characters. Every time we see the pattern ab, we count it once, and every time we see ba, we also count it once.

codeforcescompetitive-programmingstrings
CF 1606B - Update Files

We are asked to determine the minimum time required to copy an operating system update from a single initially updated computer to all the computers in a network.

codeforcescompetitive-programminggreedyimplementationmath
CF 1607A - Linear Keyboard

Thank you for providing the sample input and expected output. Let’s go step by step and carefully diagnose the issue. From the input: we see: - The first line 9 represents the number of triples (probably edges or operations). - Each subsequent line has three integers.

codeforcescompetitive-programmingimplementationstrings
CF 1607H - Banquet Preparations 2

We are given a series of dishes, each consisting of some grams of fish and some grams of meat. For every dish, a taster will consume a fixed total amount of food, but he can choose how much fish and how much meat to eat from that dish.

codeforcescompetitive-programminggreedysortingstwo-pointers
CF 1607G - Banquet Preparations 1

We are asked to distribute how much a taster eats from several dishes to minimize the imbalance between fish and meat. Each dish contains a certain amount of fish and meat.

codeforcescompetitive-programminggreedy
CF 1607F - Robot on the Board 2

We are asked to find the starting cell on a rectangular board where a robot can move the most number of steps before either leaving the board or revisiting a cell. Each cell has a direction marked, and when the robot enters that cell, it must move in that direction.

codeforcescompetitive-programmingbrute-forcedfs-and-similargraphsimplementation
CF 1607E - Robot on the Board 1

We are asked to place a robot on a rectangular grid and execute a sequence of directional commands. The robot can move left, right, up, or down, and we can choose its starting cell.

codeforcescompetitive-programmingimplementation
CF 1607D - Blue-Red Permutation

We are given an array of integers where each element has a color, either blue or red. Blue elements can be decreased by 1 any number of times, while red elements can be increased by 1 any number of times.

codeforcescompetitive-programminggreedymathsortings
Kvant Physics Problem 50

The system consists of two identical cubes, each of mass $m$, placed on a smooth horizontal table.

kvantphysics
CF 1607B - Odd Grasshopper

We are asked to simulate the movement of a grasshopper on the number line. The grasshopper starts at some integer coordinate $x0$ and makes jumps at discrete minutes. The jump distances increase by one at each step: first jump is 1, second is 2, third is 3, and so on.

codeforcescompetitive-programmingmath
CF 1607C - Minimum Extraction

We are given an array of integers and a special operation that changes the array in a very structured way. Each time the operation is applied, we pick one occurrence of the current minimum value, remove it, and then subtract that same value from every remaining element.

codeforcescompetitive-programmingbrute-forcesortings
CF 1608E - The Cells on the Paper

The “bug” here is not a subtle implementation issue anymore. It is a full mismatch between: - the expected problem - and the code that is being executed Your “actual output” is: That is not wrong computation. That is debug-printing the parsed input back out.

codeforcescompetitive-programmingbinary-searchimplementationsortings