brain

tamnd's digital brain — notes, problems, research

43815 notes

CF 1170D - Decoding of Integer Sequences

We are given a single flattened sequence that was produced from several hidden integer sequences. The encoding process mixed all sequences together in “column order”: first all first elements of each sequence, then all second elements, then all third elements, and so on.

codeforcescompetitive-programming*specialdata-structuresimplementation
CF 1170C - Minus and Minus Give Plus

We are given two strings consisting only of two symbols, a “minus” and a “plus”. The only allowed move takes two neighboring minus signs and replaces them with a single plus sign, which shortens the string by one character.

codeforcescompetitive-programming*specialimplementationstrings
CF 1170A - Three Integers Again

We are given two numbers per query, and each query hides a simple structure built from three unknown positive integers $a$, $b$, and $c$. From these three values we can form three pairwise sums: $a+b$, $a+c$, and $b+c$.

codeforcescompetitive-programming*specialmath
CF 1167G - Low Budget Inception

The city is a sequence of unit square buildings placed along an infinite horizontal line. Each building occupies an interval of length one, starting at some integer coordinate $ai$. So building $i$ spans $[ai, ai + 1]$, and these positions are strictly increasing.

codeforcescompetitive-programmingbrute-forcegeometry
CF 1167E - Range Deleting

We are given an array where every element lies between 1 and x, and we consider a transformation defined by a value interval [l, r]. This transformation deletes every array element whose value falls inside that interval, while leaving all other elements in their original order.

codeforcescompetitive-programmingbinary-searchcombinatoricsdata-structurestwo-pointers
CF 1167B - Lost Numbers

We are given an unknown ordering of six fixed numbers: 4, 8, 15, 16, 23, and 42. Each number appears exactly once in an array of length six, but their positions are hidden.

codeforcescompetitive-programmingbrute-forcedivide-and-conquerinteractivemath
CF 1167F - Scalar Queries

We are given an array of distinct numbers, and we look at every possible contiguous subarray. For each subarray, we temporarily reorder its elements in increasing order, then assign weights based on position in that sorted subarray: the smallest element gets weight 1, the next…

codeforcescompetitive-programmingcombinatoricsdata-structuresmathsortings
CF 1106F - Lunar New Year and a Recursive Sequence

We are given a sequence that starts from a very simple base and then evolves through a multiplicative recurrence.

codeforcescompetitive-programmingmathmatricesnumber-theory
CF 1105E - Helping Hiasat

We are given a timeline of events. At any moment, Hiasat’s profile has a single visible handle, and he is allowed to change this handle only at specific moments marked in the input. Between changes, the handle stays fixed.

codeforcescompetitive-programmingbitmasksbrute-forcedpmeet-in-the-middle
CF 1103D - Professional layer

We are given a collection of judges. Each judge contributes two values: a number $ai$, which controls how “resistant” their opinion is, and a cost parameter $ei$, which is the time cost if we decide to interact with that judge. We may choose to play with a judge at most once.

codeforcescompetitive-programmingbitmasksdp
CF 1103B - Game with modulo

We are interacting with a hidden number $a$, which is fixed for each game and lies between 1 and $10^9$. We cannot query it directly. Instead, we can ask questions consisting of two non-negative integers $x$ and $y$, and the judge compares $x bmod a$ and $y bmod a$.

codeforcescompetitive-programmingbinary-searchconstructive-algorithmsinteractive
CF 1075B - Taxi drivers and Lyft

We are given a set of people positioned on a number line. Each person is either a rider or a taxi driver, and all positions are distinct and already sorted in increasing order.

codeforcescompetitive-programmingimplementationsortings
Kvant Physics Problem 43

A spherical planet of radius $R$ is filled with an incompressible жидкость of constant density $\rho$ in hydrostatic equilibrium under its own gravitational field.

kvantphysics
Kvant Physics Problem 42

A uniform rope of linear mass density $\lambda$ (kg/m) passes over a frictionless pulley.

kvantphysics
Kvant Physics Problem 41

The system consists of the Sun, the Moon, and an observer on Earth.

kvantphysics
Kvant Physics Problem 40

A neon lamp consists of two large parallel plate electrodes separated by a distance $d = 3 \times 10^{-3},\text{m}$.

kvantphysics
Kvant Physics Problem 39

A planet of mass $M$ and radius $R$ is surrounded by an atmosphere of height $H$.

kvantphysics
data structuresgreedyimplementation
brute forceimplementationtrees
mathprobabilitiestrees
hashingnumber theory
combinatoricsdata structuresmath
flowsgraph matchingsgraphs
bitmasksdpgreedy
constructive algorithmsdp
constructive algorithms
greedysortings
data structuresdfs and similardsugraphsgreedysortingstrees
*specialdp
math
implementationprobabilitiesstrings
fftmath
binary searchimplementation
binary searchconstructive algorithmsdfs and similargraphsinteractive
data structures
math
math
dpgreedymath
hashingstring suffix structuresstrings
data structuresgreedyimplementation
dfs and similargraphstrees
binary searchimplementationmath
combinatorics
dp
binary searchdata structures
*specialstringstrees
brute forcegreedy
brute forcedata structuresmathnumber theorytrees
brute force
binary searchbrute forceconstructive algorithms
dfs and similardsugraphsgreedystrings
fftmathmatrices
*specialimplementation
math
brute forcecombinatoricsdpgreedymath
implementation
binary searchflows
data structuresdp
binary searchtwo pointers
data structurestrees
implementation
binary searchdpgreedysortings
implementation
dfs and similargraphs
data structuresdpgraphs
constructive algorithmsgraphsimplementation
geometrygraphs
dpgeometrymatricesprobabilities
greedysortings
constructive algorithmsgraphsimplementation
bitmasksdfs and similardsugraphs
binary searchmath
data structures
bitmasksbrute forcedpimplementation
combinatoricsdp
data structuresdivide and conquertwo pointers
hashingstrings
binary searchmathnumber theory
data structures
brute forcecombinatoricsmath
brute forcedata structures
dfs and similardpgreedytrees
expression parsingmath
binary searchdata structuresdfs and similar
data structures
combinatoricsdp
constructive algorithmsmath
gamesgreedy
implementation
binary searchdata structures
implementationmath
bitmasksdpmathmatrices
constructive algorithmsstrings
data structuresdivide and conquerdpmath
*specialgraphsimplementation
brute forcedata structuresdsutrees
brute forceimplementation
data structuresdp
brute forcemath