brain

tamnd's digital brain — notes, problems, research

41791 notes

CF 207C1 - Game with Two Trees

We are asked to maintain two dynamically growing rooted trees with labeled edges, and after each operation, compute the number of "good combinations.

codeforcescompetitive-programming
CF 207B3 - Military Trainings

We are given a column of n tanks numbered 1 to n. Each tank i has a message receiving radius a[i]. During the exercise, exactly n messages must be sent from the front of the column to the back. After each message, the last tank in the message path moves to the front.

codeforcescompetitive-programming
Kvant Math Problem 996

The octagon is the intersection of two congruent squares.

kvantmathematicsolympiad
Kvant Math Problem 995

Let

kvantmathematicsolympiad
CF 207B2 - Military Trainings

We are given a line of tanks, each occupying a fixed position in a row from left to right. Each tank has a parameter that determines how far it can receive a message when it is the recipient.

codeforcescompetitive-programming
Kvant Math Problem 994

Let

kvantmathematicsolympiad
CF 207B1 - Military Trainings

We are asked to simulate a training exercise where a line of tanks must pass messages from the front to the end, following specific rules. Initially, the tanks are numbered from 1 to n, and each tank i has a message receiving radius ai.

codeforcescompetitive-programming
CF 207A3 - Beaver's Calculator 1.0

We are asked to schedule problems brought by multiple scientists for a special calculator. Each scientist provides a sequence of problems that must be solved in the given order.

codeforcescompetitive-programminggreedy
Kvant Math Problem 993

Let $x$ be the smallest of $n$ consecutive natural numbers.

kvantmathematicsolympiad
Kvant Math Problem 992

Consider small examples of social networks where each person has at least 10 friends.

kvantmathematicsolympiad
Kvant Math Problem 991

Consider triangle $ABC$ with an altitude $CH$ and median $CK$.

kvantmathematicsolympiad
Kvant Math Problem 990

Consider three lines in space, each pair of which is skew, and they are not all parallel to the same plane.

kvantmathematicsolympiad
Kvant Math Problem 989

I begin by examining small natural numbers $a$ to see which of them satisfy the given conditions.

kvantmathematicsolympiad
Kvant Math Problem 988

Consider small values of $n$ and $k$ to build intuition.

kvantmathematicsolympiad
Kvant Math Problem 987

Consider small instances to gain intuition.

kvantmathematicsolympiad
CF 200A - Cinema

We are given a theater with n rows and m seats per row, forming an n × m grid. A line of k people is waiting to buy tickets. Each person has a preferred seat, represented as coordinates (x, y). When a person reaches the box office, they attempt to take their preferred seat.

codeforcescompetitive-programmingbrute-forcedata-structures
CF 200E - Tractor College

We are asked to distribute a fixed scholarship budget among students based on their exam grades. Each student receives a mark of 3, 4, or 5, and students with the same mark must receive the same scholarship.

codeforcescompetitive-programmingimplementationmathnumber-theoryternary-search
CF 200D - Programming Language

We are given a collection of procedure declarations and a collection of variables. Each procedure declaration consists of a name and a list of parameter types. A parameter type may be one of the concrete types int, string, or double, or it may be the wildcard type T.

codeforcescompetitive-programmingbinary-searchbrute-forceexpression-parsingimplementation
CF 200B - Drinks

We are given several drinks, and each drink contains some percentage of orange juice. Vasya mixes equal amounts of every drink into a single cocktail. The question is simple: after mixing them, what percentage of the final cocktail is orange juice?

codeforcescompetitive-programmingimplementationmath
CF 198A - About Bacteria

The problem involves modeling bacterial growth in a test tube according to a discrete-time recurrence. Each bacterium splits into k bacteria every second, and an additional b bacteria are added due to abnormal effects.

codeforcescompetitive-programmingimplementationmath
Kvant Math Problem 986

The inequality is

kvantmathematicsolympiad
CF 198C - Delivering Carcinogen

We are asked to compute the minimum time for Qwerty's ship to intercept a moving planet in a 2D plane. The star Diatar is at the origin, Persephone orbits the star in a perfect circle of radius $R$ at constant linear speed $vp$, and Qwerty's ship starts at some arbitrary…

codeforcescompetitive-programmingbinary-searchgeometry
Kvant Math Problem 985

We are asked to count configurations of three lines through a point in space with prescribed pairwise angles, up to congruence.

kvantmathematicsolympiad
Kvant Math Problem 984

Consider a square $ABCD$ and an arbitrary point $K$ inside it.

kvantmathematicsolympiad
Kvant Math Problem 983

The tournament is a complete directed graph on $16$ vertices.

kvantmathematicsolympiad
Kvant Math Problem 982

Construct triangle $ABC$ on paper and build the external squares $ABB_1A_2$, $BCB_1C_2$, $CAA_1C_2$.

kvantmathematicsolympiad
Kvant Math Problem 981

Consider small repunit numbers of the form $R_n = 11\ldots1$ with $n$ ones.

kvantmathematicsolympiad
Kvant Math Problem 980

Consider first a convex polygon in the plane with vertices $A_1, A_2, \dots, A_n$ and a point $O$ inside it.

kvantmathematicsolympiad
Kvant Math Problem 979

Consider the definition of an exceptional set of $k$ numbers $a_1, a_2, \dots, a_k$, all strictly between 0 and 1.

kvantmathematicsolympiad
Kvant Math Problem 978

The threshold $\sqrt{2/3}$ is suggestive because an equilateral triangle of side $a$ has altitude $\frac{\sqrt3}{2}a$, and when $a=\sqrt{2/3}$ the altitude equals $\frac1{\sqrt2}$.

kvantmathematicsolympiad
Kvant Math Problem 977

The problem asks whether $x$ can be expressed using only addition, subtraction, and multiplication from given polynomials.

kvantmathematicsolympiad
Kvant Math Problem 976

Place the square in coordinates:

kvantmathematicsolympiad
Kvant Math Problem 975

Consider first a simplified scenario: a small $n\times n$ board, say $n=5$, with just a few hypothetical pieces each attacking a limited number of squares.

kvantmathematicsolympiad
Kvant Math Problem 974

Suppose both players start with equal time and make alternating moves.

kvantmathematicsolympiad
Kvant Math Problem 973

Let

kvantmathematicsolympiad
Kvant Math Problem 972

The sequence $(x_n)$ begins with $x_1 = \frac12$ and satisfies the recurrence $x_{n+1} = x_n^2 + x_n$.

kvantmathematicsolympiad
Kvant Math Problem 971

Consider a tournament of $8$ volleyball teams where each team plays every other team exactly once.

kvantmathematicsolympiad
Kvant Math Problem 969

Unusual activity has been detected from your device.

kvantmathematicsolympiad
Kvant Math Problem 967

For small values,

kvantmathematicsolympiad
Kvant Math Problem 966

The statement asks for a dissection of an arbitrary triangle into four pieces such that the pieces can be rearranged into two triangles, each similar to the original triangle.

kvantmathematicsolympiad
Kvant Math Problem 964

The sequence $(a_n)$ consists of distinct positive integers with the growth constraint $a_n < 100n$.

kvantmathematicsolympiad
Kvant Math Problem 961

Let the side length of the square be $6$.

kvantmathematicsolympiad
Kvant Math Problem 959

Consider first small examples.

kvantmathematicsolympiad
Kvant Math Problem 958

Let

kvantmathematicsolympiad
Kvant Math Problem 955

Consider first small numbers of participants.

kvantmathematicsolympiad
Kvant Math Problem 954

Consider first the case of a rectangle inscribed in a triangle.

kvantmathematicsolympiad
Kvant Math Problem 952

Write

kvantmathematicsolympiad
Kvant Math Problem 950

The $25$ plots form the $5\times5$ grid graph.

kvantmathematicsolympiad
Kvant Math Problem 947

Consider first small cases.

kvantmathematicsolympiad
Kvant Math Problem 946

Position two parabolas in the plane with perpendicular axes.

kvantmathematicsolympiad
Kvant Math Problem 942

For $n=1$, the partition is ${1}$ and ${2}$, hence

kvantmathematicsolympiad
Kvant Math Problem 941

Consider first the case $k=2$, which corresponds to a regular decagon.

kvantmathematicsolympiad
Kvant Math Problem 940

For the planar statement, the natural idea is to look at one fixed side of the square, say the left side.

kvantmathematicsolympiad
Kvant Math Problem 939

The problem has two parts.

kvantmathematicsolympiad
Kvant Math Problem 938

Let the angular speed be $\dfrac{360^\circ}{n}$ per second.

kvantmathematicsolympiad
Kvant Math Problem 936

Consider the simplest nontrivial case $n=1$.

kvantmathematicsolympiad
Kvant Math Problem 934

Interpret the $2n$ points as vertices of a graph $G$ with $2n$ vertices and $n^2+1$ edges.

kvantmathematicsolympiad
Kvant Math Problem 933

Let the clans be represented by labels.

kvantmathematicsolympiad
Kvant Math Problem 931

Consider triangle $ABC$ with an incircle touching sides $AB$, $BC$, and $CA$ at points $C_1$, $A_1$, and $B_1$ respectively.

kvantmathematicsolympiad
Kvant Math Problem 929

Consider the equation $a^4 + b^4 + c^4 + d^4 = e^4$ modulo small primes to understand divisibility constraints.

kvantmathematicsolympiad
Kvant Math Problem 928

Consider small values of $N$ to understand the dynamics of the seat-shifting process.

kvantmathematicsolympiad
Kvant Math Problem 925

Consider a small blue region, for example, a disk of radius $r<1$.

kvantmathematicsolympiad
Kvant Math Problem 923

Consider a unit cube in three-dimensional space with edges parallel to the axes.

kvantmathematicsolympiad
CF 198E - Gripping Story

Every gripper is located at a fixed point in space. Qwerty's ship is also fixed. A gripper can pull another gripper into the ship if two conditions hold simultaneously.

codeforcescompetitive-programmingbinary-searchdata-structuressortings
CF 198D - Cube Snake

We are asked to fill an $n times n times n$ cube with numbers from 1 to $n^3$ in such a way that two conditions hold simultaneously. First, the numbers must form a "snake": each consecutive number must occupy a cube that is a face neighbor of the previous number.

codeforcescompetitive-programmingconstructive-algorithms
CF 198B - Jumping on Walls

We have two vertical walls, each represented by a string of length n. Position i on a wall is either safe (-) or blocked (X). The ninja starts at position 0 of the left wall. Every second he may move to one of three positions: 1. One cell upward on the same wall. 2.

codeforcescompetitive-programmingshortest-paths
CF 196E - Opening Portals

We are given a connected network of cities, some of which contain portals. Each road between cities has a positive travel time, and Pavel starts in city 1.

codeforcescompetitive-programmingdsugraphsshortest-paths
CF 196D - The Next Good String

We are asked to find the next string lexicographically larger than a given string s such that no substring of length d or more is a palindrome. A palindrome is a sequence that reads the same forwards and backwards.

codeforcescompetitive-programmingdata-structuresgreedyhashingstrings
CF 196A - Lexicographically Maximum Subsequence

We are given a lowercase string and may choose any non-empty subsequence of its characters while preserving their original order. Among all possible subsequences, we need the one that is lexicographically largest.

codeforcescompetitive-programminggreedystrings
Kvant Math Problem 921

The problem involves a convex quadrilateral $ABCD$ with two given angles, $\angle A = \alpha$ and $\angle B = \beta$, and a special relation between its sides and area: the doubled area satisfies $2S…

kvantmathematicsolympiad
Kvant Math Problem 919

For the first integral equality, the two integrals involve complementary functions: the tangent function on $[0,\pi/4]$ and the arctangent function on $[0,1]$.

kvantmathematicsolympiad
Kvant Math Problem 917

Consider six-digit numbers from $000000$ to $999999$.

kvantmathematicsolympiad
Kvant Math Problem 915

The inequality is cyclic rather than symmetric:

kvantmathematicsolympiad
Kvant Math Problem 913

Consider triangle $ABC$ with circumcircle $\Gamma$.

kvantmathematicsolympiad
Kvant Math Problem 911

Place quadrilateral $ABCD$ in the plane and select points $E$ on $AB$ and $F$ on $CD$.

kvantmathematicsolympiad
Kvant Math Problem 910

Let the regular hexagon be $P_1P_2P_3P_4P_5P_6$, and let the points of the problem be chosen on its sides so that $A_i\in P_iP_{i+1}$, indices modulo $6$.

kvantmathematicsolympiad
Kvant Math Problem 907

Let $A=\widehat A$, $B=\widehat B$, $C=\widehat C$.

kvantmathematicsolympiad
Kvant Math Problem 905

Consider the equation

kvantmathematicsolympiad
Kvant Math Problem 903

A plane section of a convex polyhedron changes combinatorially only when the plane passes through a vertex.

kvantmathematicsolympiad
Kvant Math Problem 901

Consider triangle $ABC$ with bisectors $AK$ and $BM$ intersecting at $O$.

kvantmathematicsolympiad
Kvant Math Problem 898

Consider the given odd natural numbers $a<b<c<d$ satisfying $ad=bc$, $a+d=2^k$, and $b+c=2^m$.

kvantmathematicsolympiad
Kvant Math Problem 896

The condition that the circle with diameter $AB$ is tangent to the line $CD$ has a simple metric interpretation.

kvantmathematicsolympiad
Kvant Math Problem 893

The complete graph on $n$ vertices is $K_n$.

kvantmathematicsolympiad
Kvant Math Problem 892

Write

kvantmathematicsolympiad
Kvant Math Problem 890

The problem concerns connecting 51 cities in a square-shaped country of side 1000 km with 11,000 km of highways.

kvantmathematicsolympiad
Kvant Math Problem 887

Consider a circle $\Gamma_1$ with tangents $CA$ and $CB$ meeting at $C$, so $A$ and $B$ are points of tangency.

kvantmathematicsolympiad
Kvant Math Problem 886

Label the cells on the boundary of the $n\times n$ square cyclically by

kvantmathematicsolympiad
Kvant Math Problem 883

Working

kvantmathematicsolympiad
Kvant Math Problem 880

The sequence begins as $1, 0, 1, 0, 1, 0$ and each subsequent term is defined as the last digit of the sum of the preceding six terms.

kvantmathematicsolympiad
Kvant Math Problem 878

Consider a pyramid with apex $A$ and base $B_1B_2\dots B_n$.

kvantmathematicsolympiad
Kvant Math Problem 877

Consider a smaller version of the problem first.

kvantmathematicsolympiad
Kvant Math Problem 874

We begin by testing small integer values to see whether the equation $(5+3\sqrt{2})^m = (3+5\sqrt{2})^n$ admits any obvious solutions.

kvantmathematicsolympiad
Kvant Math Problem 872

Let $O_1,O_2,O_3$ be the centers of the circles $C_1,C_2,C_3$.

kvantmathematicsolympiad
Kvant Math Problem 870

Let the occupied rooms be represented by the multiset of integer positions of all pianists.

kvantmathematicsolympiad
Kvant Math Problem 867

Let the boys' heights be $b_1,\dots,b_{17}$ and the girls' heights be $g_1,\dots,g_{17}$.

kvantmathematicsolympiad
Kvant Math Problem 864

Consider first a right triangle.

kvantmathematicsolympiad
Kvant Math Problem 863

Consider a small board, $n=3$.

kvantmathematicsolympiad
Kvant Math Problem 861

Consider small values of $n$ to understand the behavior of the sums modulo $1$.

kvantmathematicsolympiad
Kvant Math Problem 860

Consider the triangle $ABC$ with circumcircle $(O)$ and incircle $(Z)$.

kvantmathematicsolympiad
Kvant Math Problem 859

Let

kvantmathematicsolympiad