brain

Codeforces 2020F: Count Leaves

We are given a set of points on a line, initially completely disconnected. Each operation takes a starting position, a fixed step size, and a length, and then connects all points that lie in that arithmetic progression segment.

We are given three non-negative integers b, c, and d. We must construct a non-negative integer a such that $$(a mid b) - (a & c) = d$$ where The task is not to optimize some value of a. Any valid a is acceptable. If no such value exists, we print -1.

We are given a process on a line of bulbs indexed from $1$ to $n$. Initially every bulb is on. We then repeatedly flip bulbs in a structured way: for each $i$, every multiple of $i$ has its state toggled once.

We are asked to reduce a given integer n to zero by repeatedly subtracting powers of a second integer k. Each subtraction can use any power of k (including k^0 = 1), and the goal is to minimize the number of subtractions.

We are given a connected village represented as a graph. Each node is a house, and edges are internet cables with a latency weight. Some subset of houses specifically need internet.

Let the weights in the first group be

In this problem, we are given a village represented as a connected graph with houses as nodes and internet cables as edges. Each edge has a latency, representing the delay of transmitting data along that cable.

We are given a connected undirected graph representing a village, where nodes are houses and edges are internet cables with latencies. A subset of houses requires internet, and we are allowed to place servers at up to k houses.

We are asked to plan drink sales over several days in a canteen. Each day, there are multiple drink types, each with a projected profit that can be positive or negative. On any day, we must select a contiguous segment of drink types to sell.

We have a fixed permutation a describing the initial order of team members in a line. During the presentation, the person currently at the front presents the next slide.

We are given an initial lineup of people, where each person appears exactly once. A sequence of presentations must be delivered in a fixed order, and each presentation is assigned to a specific person.

We are given an array of positive integers and a process that repeatedly combines two elements into a single new element: we pick two distinct elements, compute the floor of their average, remove the original two, and append the new number.

We start with an array of non-negative integers. The only operation allowed is to pick an element and add x to it. We may repeat this operation any number of times on any element. Adding x repeatedly has a very specific effect.

We are asked to count the number of ways to fill an integer grid with certain cells already preassigned so that the grid is "beautiful." A grid is beautiful if, for any rectangle defined by four corners, the XOR of the corner values equals zero.

Let the route produced by the minimum-greedy algorithm be

We are given a partially specified n × m grid. Some cells already contain integers in the range [0, 2³⁰), while the remaining cells are unknown. A grid is called beautiful if every axis-aligned rectangle satisfies the XOR condition on its four corners.

The task is to find the single Impostor among $n$ players in an interactive game where each player has one of three roles: Knight, Knave, or Impostor. Knights always tell the truth, Knaves always lie, and the Impostor behaves like a Knave from the perspective of all others.

In this problem, we are asked to identify a single Impostor among n players, where every player is either a Knight, a Knave, or the Impostor.

Each bus row contains exactly two seats. We have several families, and family i contains ai people. A person is happy in one of two situations. They sit next to a member of the same family, or they occupy a row alone with the other seat empty.

Each test case describes a dealership with several car models, where model i has ai identical cars that must all be sold.

We are given a voting grid with exactly two rows and n columns, where each cell is labeled either “A” or “J”, representing how that house will vote.

We are given an array of nonzero integers representing a one-dimensional terrain. Positive values mean surplus sand that must be removed, and negative values mean deficits that must be filled.

We are given a tree of n nodes, which are connected by n-1 edges. Each node can be thought of as a source of magical energy, and each edge as a channel through which this energy flows.

The problem presents a casino with multiple games, each offering a chance to win a certain amount. Each game has two parameters: a probability of winning, given as a percentage, and a payout if you win.

Let each square correspond to its center.

We are given a sequence of problems in an olympiad, each with a score and a skip parameter. The competition begins with the first problem.

We are given n arrays, and every array contains exactly two numbers. We may reorder these arrays in any way we want, but inside each array the order of the two elements must remain unchanged. After choosing an order, we concatenate all arrays and obtain one sequence of length 2n.

We are given two directed graphs, each with the same number of vertices. Each graph is already strongly connected, and every directed cycle inside each graph has length divisible by a fixed integer $k$.

We are given two types of bank deposits and a number of coins Alice has. The "Profitable" deposit requires at least a certain amount, b, to open, while the "Unprofitable" deposit has no minimum.

Let $D_{16}$ denote the closed disk of radius $16$ centered at the origin, and suppose $650$ points $P_1, \dots, P_{650}$ are placed in $D_{16}$.

Let the convex pentagon be $A_1A_2A_3A_4A_5$, with indices taken modulo $5$.

The core issue is not a boundary bug or a missing case. The previous approach was fundamentally overconstrained: it tried to force both segments to be aligned with axes and also tied them to a single corner or a simplistic placement rule.

The problem models a turn-based battle between a dragon and an army of heroes protected by artifacts. Each hero has a health value and each artifact has a durability value. A hero can hold at most one artifact, and artifacts can only protect heroes while they are active.

We are given a sequence of game records where each element represents either acquiring an attribute point or encountering an attribute check. The character starts with Strength and Intelligence at zero.

We are given two screens that can each display sequences of uppercase letters. Initially both screens are empty. At each second, we can either append a single letter to one of the screens, or copy the entire sequence from one screen to the other, replacing what was on the…

Let $\triangle ABC$ be arbitrary.

We are managing a growing family of stores, where each store contains a multiset of ice cream types. Each type has two attributes: a cost and a tastiness value. Stores are not independent.

We are given an integer array a of length n. From a, we can generate a much larger array b that contains all possible contiguous subarray sums of a, listed in a specific order: first all sums starting at index 1, then all sums starting at index 2, and so on.

We are given several independent test cases. In each test case we start with an array of integers, and we are allowed to choose any subsequence of it, meaning we may delete elements but cannot reorder what remains.

We are given a sequence of action figures numbered from 1 to n. Figure i costs i coins, but it cannot be bought immediately on day 1; it only becomes available starting from day i. After day n, everything is available.

The problem asks us to construct two line segments on a 2D integer grid. We are given a rectangular area defined by $X$ and $Y$ and a minimum length $K$. Each segment must have integer endpoints within the rectangle, and both must have lengths at least $K$.

We are given a one-dimensional strip of cells numbered from 0 up to $10^{18}$. Initially all cells are white. We are required to paint certain cells black, and we are allowed to choose pairs of white cells whose distance is at most $k$ to paint them black simultaneously.

We are asked to analyze a multi-pile turn-based game between Alice and Bob. Each pile has a fixed maximum move size, denoted $ai$, and a maximum number of stones, $bi$.

Each test case gives us several independent piles of stones. Every pile behaves like a small game on its own: on your turn you pick a pile and remove some positive number of stones from it, but the move is heavily constrained.

Let

We are given several axis-aligned rectangles, each with fixed integer width and height. Every rectangle must be placed somewhere on an infinite grid, and when placed it paints exactly the cells inside that rectangle black.

We are given a sequence of integers and we are allowed to insert either addition or multiplication operators between consecutive elements. Multiplication has higher precedence than addition, so the expression is evaluated as a sum of several multiplicative blocks.

We are asked to determine how many operations it takes to turn a linearly generated array into a permutation of integers from 0 to n−1. The array is defined by three numbers n, b, and c, and follows the formula ai = b (i - 1) + c for 1 ≤ i ≤ n.

We are given a tree with n vertices where vertex 1 is considered the exit of the rabbit hole, and Alice starts at some vertex v. Each turn a fair coin is flipped. On heads, Alice chooses an adjacent vertex to move to.

The problem can be viewed as a graph traversal on a set of n card types. Alice starts with card 1 and wants to acquire card n by trading with three other players: Queen, King, and Jack.

Alice starts at the origin on a two-dimensional grid and can move in the four cardinal directions. She has a fixed sequence of moves that she repeats indefinitely.

We are given a long sheet cake divided into n sections, each with a tastiness value. Alice is at a party with m creatures, and she wants to cut the cake into m + 1 contiguous pieces. Each creature will only be happy if its piece has tastiness at least v.

We are given an integer array and a fixed value $k$. We are allowed to perform an operation that selects a contiguous segment and adds $k$ to every element inside it.

We are given a small undirected graph where each edge has a probability of appearing on any given day. Initially, only vertex 1 knows a message.

We are asked to maximize a weighted sum over an array of integers that starts as all zeros. The array has length $n$ and receives $m$ initial operations, each of which increases a prefix or suffix of the array by 1.

We are asked to find a number $x ge 2$ such that every number in a given array $a$ can be generated from $x$ using a special additive rule. The rule allows us to repeatedly add to $x$ one of its divisors that is at least 2, until we reach the target number.

We are given a cycle graph with $n$ vertices labeled $0$ to $n-1$. Each edge in the cycle has a color, either red or blue.

Ah, now I see the subtle mistake. The previous logic assumed that putting the maximum first and subtracting each element from the maximum works, but that is not correct for the actual score definition: the score is $$sum{i=1}^n (ci - bi)$$ where $ci$ is the prefix maximum up…

We are given a simple undirected graph with $n$ vertices and $m$ edges. The graph can be arbitrary but contains no self-loops or multiple edges. We are allowed to perform a "triangle flip" operation on any three distinct vertices $a$, $b$, $c$.

We are given a binary string s of length n and another binary string r of length n-1. The problem describes a game where we repeatedly shorten s by replacing any adjacent pair of differing bits with the next character in r. On each turn, we must pick an index k such that s[k] !

We are asked to consider a contiguous set of integers $S$ from $l$ to $r$ and repeatedly remove numbers from $S$ according to a simple rule. A number $x$ can only be removed if there are at least $k$ multiples of $x$ in $S$, counting $x$ itself.

We are asked to consider a universe of planets, each defined by an interval of vulnerability [li, ri]. A set of planets can be destroyed simultaneously if their intervals overlap at at least one point.

I can write the editorial, but I cannot reliably produce a correct solution/editorial from the problem statement alone for a 3100-rated combinatorics problem without reconstructing the full proof and implementation details.

We are given an array, and each query asks whether a contiguous segment of it can be completely deleted using a very specific rule. The rule works with a set of “available values” initially containing every distinct number in the segment.

The problem gives us a permutation of numbers from $1$ to $n$ and a string of directions, L and R, associated with each position in the permutation.

We are given an array and we look at all of its non-empty subsequences. For each chosen subsequence, we are allowed to split its elements into any number of groups, where each group is a multiset.

We are given an array and we are allowed to reorder it before processing. Once fixed, we scan it from left to right and maintain two running values: the smallest element seen so far and the largest element seen so far.

We are given a binary string where each character is a fixed boolean value. The players do not change these values. Their only action is deciding where to place binary operators between adjacent positions, specifically choosing either AND or OR for each gap.

Working

The original problem is interactive: there is a hidden permutation, and we must locate the positions of the two middle values, namely $frac n2$ and $frac n2 + 1$, using median queries. For the hack version used in the archive, the interaction is removed.

The problem gives us a rooted tree constructed by Penchick with n vertices and asks us to determine the minimum depth d of a perfect binary tree that Chloe can construct, so that after performing a sequence of "node removal and child promotion" operations, Chloe’s tree…

We are given a line of trees, each with a height. A rabbit starts at some position and can move between trees using a very specific rule that depends on both position and height. From a tree at index i, the rabbit can jump in two directions.

We have a permutation of the numbers $1$ through $n$. The target is the sorted permutation $[1,2,dots,n]$. The only allowed operation swaps two neighboring positions when the values differ by exactly $1$. For example, $3$ and $4$ may be swapped, but $3$ and $5$ may not.

We are asked to assign a value to each position in an array of length $n$. These values represent “fillings” placed on buns arranged in a line. The same filling may appear multiple times, but only under two strict rules.

The problem presents a monument made of $n$ pillars, each with a height $hi$, where the heights are initially in non-increasing order. Penchick wants to modify the monument so that the pillar heights are in non-decreasing order.

We are given a sequence of pockets, each containing a positive number of peanuts. Alice can partition the sequence into contiguous boxes of pockets.

We are given a circular array of odd length $n$, where each element is an integer. We can perform an operation on any index $i$ which increases the element at $i$ by 2 and its immediate neighbors by 1. The goal is to transform the array so that all elements are equal.

We are tasked with reconstructing the parent array of a tree rooted at node 0, under a very specific structure. Each node is numbered from 0 to n-1, and for each node i ≥ 1, we want to find its parent node pi. The twist is that we do not see the tree directly.

We are given an array of integers representing potential triangle sides, and the allowed operation is to copy one element over another. The ultimate goal is to make every distinct triplet of elements form a non-degenerate triangle.

The problem describes a circuit with $n$ lights and $2n$ switches. Each light is connected to exactly two switches, and each switch is connected to exactly one light.

We start with an array that is simply the numbers from 1 to n in increasing order, where n is guaranteed to be odd. We are allowed to cut this array into several contiguous pieces. Every piece must also have odd length, and the number of pieces itself must be odd.

We are asked to analyze movement on a rooted tree. The tree has $n$ vertices, with vertex $1$ as the root. Chefir, starting at a given vertex $vi$, has a limited stamina $ki$.

For a fixed integer $k$, look at the Fibonacci sequence and mark every position whose Fibonacci value is divisible by $k$. For example, when $k=2$: $$1,1,mathbf{2},3,5,mathbf{8},13,21,mathbf{34},dots$$ The marked positions are $3,6,9,dots$.

We are given a permutation of numbers from 1 to n. We are allowed to repeatedly swap any two positions. After performing some swaps, we want the permutation to satisfy a structural condition on every index i.

We are given an array of integers and need to identify subarrays, or contiguous segments, whose sum is zero. These segments are called beautiful. The task is not just to find all beautiful segments but to maximize the number of them without overlaps.

We are given a line of students, each associated with a topic of interest, represented by an integer. The disturbance of the line is counted as the number of adjacent pairs of students who share the same topic.

We are asked to determine the winner of a turn-based game where two players move a dot along a number line starting at position zero. Sakurako always moves left by increasing odd numbers of units on her turn: -1, -5, -9, and so on.

The arrangement of the lines is a simple arrangement: every pair of lines intersects and no three are concurrent.

We are given an $n times n$ grid of integers, where each cell represents a height. Negative values represent “bad” cells that we want to eliminate by increasing values.

We are given a set of distinct positive integers. We want the largest subset with the property that no chosen number can be expressed as an integer linear combination of the remaining chosen numbers. For integers, the subgroup generated by a collection of numbers is very simple.

We are given a set of warriors, each assigned a watch interval defined by integer start and end times. At every integer moment covered by at least one warrior, we must ensure that among the warriors present, there is at least one color that occurs exactly once.

We are simulating a random process where a bag is filled by repeatedly drawing items from a multiset containing two types of objects: red items worth 2 units and blue items worth 1 unit.

We are given a set of closed intervals on the real line. Each interval represents the active time of one warrior. We must assign a color to every interval. At every real time moment covered by at least one interval, we look at all intervals containing that moment.

We are asked to compute the expected total value of a collection of gems after a stochastic process with multiplicative bonuses. Khayyam starts with a chest containing n red rubies, each worth 2, and m blue sapphires, each worth 1.

We need to construct $k$ distinct permutations of length $n$ such that if we look at any position $i$, the sum of the values appearing at that position across all $k$ permutations is the same for every position.

We are given a sequence of stone columns, each with a base and a small number of inscriptions on top: either 0, 1, or 2. We can think of the sequence as an array of integers a[i] representing the number of inscriptions on the i-th column.

We are given a grid where each cell either forces movement in one of four directions or is still undecided. Starting from any cell, a token follows arrows step by step, leaving the grid immediately if it goes outside.

The problem models Rakhsh's body as a line of $n$ spots, where each spot is either weak ($0$) or strong ($1$). Rostam wants to ensure that in any consecutive interval of $m$ spots, at least one spot is strong.

The problem asks us to find a number that satisfies two properties relative to two given numbers, $a$ and $b$. Specifically, we want the smallest integer $m$ such that $m$ is at least as large as one of the two numbers and the remainder of $m$ when divided by $a$ equals the…