#matrices

CF 1252K - Addition Robot

CF 1252K - Addition Robot Rating: 2100 Tags: data structures, math, matrices Solve time: 1m 52s Verified: no Solution Problem Understanding The robot stores a binary instruction string over the alphabet {A, B}. When we process this string with an initial pair of values (A, B) , each character acts like a small transformation step. If the current character is A , the second value is added into the first,...

CF 1106F - Lunar New Year and a Recursive Sequence

CF 1106F - Lunar New Year and a Recursive Sequence Rating: 2400 Tags: math, matrices, number theory Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a sequence that starts from a very simple base and then evolves through a multiplicative recurrence. The first $k-1$ terms are fixed to 1, while the remaining terms are determined by a sliding window rule: each new value is a product...

CF 923E - Perpetual Subtraction Rating: 3100 Tags: fft, math, matrices Model: gpt-5-5 Solve time: 1m 42s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32d5ac-b580-83ec-9756-e063f3b8f5b7 Solution Problem Understanding We start with a random integer between 0 and N, described by a probability distribution P. At each step we erase the current number x and replace it with a uniformly random integer from the interval [0, x]. After performing this operation M times,...

CF 989E - A Trance of Nightfall Rating: 2700 Tags: dp, geometry, matrices, probabilities Model: gpt-5-3-mini Solve time: 1m 39s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33aab1-98b0-83ec-94d4-e77f31c5f365 Solution Problem Understanding We are given a fixed set of points in the plane. From this set, Kanno will repeatedly move between these points using a randomized geometric rule. The randomness does not come from a simple graph structure, but from geometry: at each...

CF 959F - Mahmoud and Ehab and yet another xor task Rating: 2400 Tags: bitmasks, dp, math, matrices Model: gpt-5-3-mini Solve time: 1m 11s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a339f5b-7da0-83ec-9af1-078177c4b240 Solution Problem Understanding We are given an array of integers where each value is treated as a 20-bit number. For every query, we look only at a prefix of the array, specifically the first $l$ elements, and we must count...

CF 946F - Fibonacci String Subsequences

CF 946F - Fibonacci String Subsequences Rating: 2400 Tags: combinatorics, dp, matrices Solve time: 1m 46s Verified: no Solution Problem Understanding We are given a binary pattern string s and we want to measure how often this pattern appears inside many different strings derived from a very specific construction. The large string we care about is not arbitrary. It comes from a Fibonacci-style concatenation process. Starting with F(0) = "0"...

Educational Codeforces Round 39 (Rated for Div. 2)

Educational Codeforces Round 39 (Rated for Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 800-2400 | 6m 7s # Problem Rating Tags Accepted Time ✓ A Partition 800 greedy 18,155 1m 22s ✓ C String Transformation 1300 greedy, strings 9,379 1m 16s ✓ E Largest Beautiful Number 2200 greedy, implementation 1,244 1m 43s F Fibonacci String Subsequences 2400 combinatorics, dp, matrices 645 1m 46s

CF 954F - Runner's Problem

CF 954F - Runner's Problem Rating: 2100 Tags: dp, matrices, sortings Solve time: 3m 11s Verified: yes Solution Problem Understanding We are given a 3 by m grid where movement is always one column to the right and can also shift vertically by at most one row. The journey starts in the middle row of the first column and must end in the same middle row at the last column....

CF 1012B - Chemical table

CF 1012B - Chemical table Rating: 1900 Tags: constructive algorithms, dfs and similar, dsu, graphs, matrices Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid where each cell is a distinct chemical element. Some of these cells are already available in the laboratory. From any three elements forming three corners of an axis-aligned rectangle, the scientists can always synthesize the fourth corner....

CF 1023E - Down or Right

CF 1023E - Down or Right Rating: 2100 Tags: constructive algorithms, interactive, matrices Solve time: 2m 14s Verified: no Solution Problem Understanding We are given an unknown $n \times n$ grid where each cell is either open or blocked. Movement is only allowed from a cell to its right neighbor or its bottom neighbor, and only if the destination cell is open. The goal is to determine any valid path...

CF 1025E - Colored Cubes

CF 1025E - Colored Cubes Rating: 2700 Tags: constructive algorithms, implementation, matrices Solve time: 5m 51s Verified: yes Solution Problem Understanding We are given an $n \times n$ grid and $m$ identical-sized cubes, each having a unique color. Each cube starts on a distinct cell, and each also has a target cell where it must eventually be placed. Some cubes may already start on their destination, but otherwise every cube...

CF 1538E - Funny Substrings

CF 1538E - Funny Substrings Rating: 2100 Tags: data structures, hashing, implementation, matrices, strings Solve time: 6m 39s Verified: yes Solution Problem Understanding We are given a very small “programming language” where variables store strings. Each variable is either assigned a literal string of length at most five, or defined as the concatenation of two previously defined variables. The program is a sequence of such assignments, and only the value...

CF 1344F - Piet's Palette

CF 1344F - Piet's Palette Rating: 3200 Tags: matrices Solve time: 6m 2s Verified: no Solution Problem Understanding We are given a hidden initial configuration of a length-n array. Each position contains either one of three primary colors or is empty. We never observe this initial array directly. Instead, we observe a sequence of operations applied to it over time. Some operations are “global transformations” that swap two colors inside...

CF 1335F - Robots on a Grid

CF 1335F - Robots on a Grid Rating: 2200 Tags: data structures, dfs and similar, dsu, graphs, greedy, matrices Solve time: 1m 11s Verified: no Solution Problem Understanding Each cell in the grid behaves like a deterministic state in a directed graph. From every cell, there is exactly one outgoing edge pointing to one of its four neighbors, as dictated by the arrow in that cell. Because of the boundary...

CF 1332E - Height All the Same

CF 1332E - Height All the Same Rating: 2100 Tags: combinatorics, constructive algorithms, math, matrices Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given a rectangular grid with $n \times m$ cells, and each cell starts with some integer height $a_{i,j}$. The game allows two types of moves that increase heights: either we add one cube to two adjacent cells at the same time, or we add...

CF 1808E2 - Minibuses on Venus (medium version)

CF 1808E2 - Minibuses on Venus (medium version) Rating: 2500 Tags: combinatorics, divide and conquer, dp, matrices Solve time: 2m 45s Verified: no Solution Problem Understanding We are counting sequences of length n , where each position holds a digit in base k . So each ticket is just an array of length n with values from 0 to k-1 . A ticket is considered valid if there exists at...

CF 1557C - Moamen and XOR

CF 1557C - Moamen and XOR Rating: 1700 Tags: bitmasks, combinatorics, dp, math, matrices Solve time: 5m 29s Verified: yes Solution Problem Understanding We are counting how many arrays of length n can be formed when each element is an integer in the range [0, 2^k - 1] , with the additional constraint that a certain bitwise inequality holds. For any such array, we compute two aggregate values over all...

CF 1511F - Chainword

CF 1511F - Chainword Rating: 2700 Tags: brute force, data structures, dp, matrices, string suffix structures, strings Solve time: 5m 50s Verified: no Solution Problem Understanding We are building strings of length $m$, but the string itself is not the only object we care about. Along with the string, we also choose two independent ways to split it into consecutive segments. Each segment must correspond exactly to one of the...

CF 1286D - LCC Rating: 3100 Tags: data structures, math, matrices, probabilities Model: gpt-5-5 Solve time: 4m 42s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2db171-0f54-83ec-a4ab-893275f60814 Solution Problem Understanding We are given a set of particles placed on a number line at distinct positions. Each particle starts at its own position at time zero and immediately chooses a direction: right with probability $p_i$ and left with probability $1 - p_i$. Once directions...

CF 1375I - Cubic Lattice Rating: 3500 Tags: geometry, math, matrices, number theory Model: gpt-5-3-mini Solve time: 7m 52s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e6119-32e0-83ec-8265-d13b0e9c273b Solution Problem Understanding We are given a finite set of integer points in 3D space. The task is to construct a special geometric object, a cubic lattice, that contains all these points. A cubic lattice here is generated by three integer vectors that behave like...

CF 1197F - Coloring Game

CF 1197F - Coloring Game Rating: 2700 Tags: dp, games, matrices Solve time: 5m 41s Verified: no Solution Problem Understanding Each strip can be viewed as a line of positions, and each position holds a chip. A chip starts at the rightmost cell of its strip, and players alternately move exactly one chip per turn, pushing it left by 1, 2, or 3 positions, as long as the move stays...

CF 1184D2 - Parallel Universes (Hard)

CF 1184D2 - Parallel Universes (Hard) Rating: 3100 Tags: math, matrices Solve time: 2m 28s Verified: yes Solution Problem Understanding We are simulating a probabilistic system that evolves a one-dimensional structure of length l , where a distinguished position called the Doctor’s current universe is fixed inside this structure. At every step, the system randomly either grows by inserting a new universe or shrinks by cutting a connection and discarding...

CF 1182E - Product Oriented Recurrence

CF 1182E - Product Oriented Recurrence Rating: 2300 Tags: dp, math, matrices, number theory Solve time: 3m 41s Verified: no Solution Problem Understanding We are given a sequence defined by a multiplicative recurrence. The first three values are known, and every later value is built from the previous three by multiplying them together and then scaling by a power of a constant. The exponent of that constant grows linearly with...

CF 1101G - (Zero XOR Subset)-less

CF 1101G - (Zero XOR Subset)-less Rating: 2300 Tags: math, matrices Solve time: 10m 19s Verified: no Solution Problem Understanding We are given a sequence of integers, and we want to cut it into consecutive chunks. Every element must belong to exactly one chunk, and every chunk must be non-empty. After splitting, we look at all possible non-empty collections of these chunks. For each such collection, we compute the XOR...

CF 1266H - Red-Blue Graph Rating: 3400 Tags: dp, graphs, math, matrices, meet-in-the-middle Model: gpt-5-3-mini Solve time: 4m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d882b-4204-83ec-8de7-91488c63d3c1 Solution Problem Understanding We are given a directed graph where every vertex except the last one has exactly two outgoing edges, one red and one blue. At any moment, each vertex is in one of two internal states, which decides which of its two edges...

CF 917D - Stranger Trees

CF 917D - Stranger Trees Rating: 2600 Tags: dp, math, matrices, trees Solve time: 9m 19s Verified: no Solution Problem Understanding We are asked to examine variations of a given labeled tree with $n$ vertices, counting how many labeled trees share exactly $k$ edges with the given one for each $k$ from 0 to $n-1$. The input is the number of vertices followed by $n-1$ edges that define Will's tree....

CF 917C - Pollywog

CF 917C - Pollywog Rating: 2900 Tags: combinatorics, dp, matrices Solve time: 6m 26s Verified: no Solution Problem Understanding We are asked to move a group of x pollywogs from the first x stones in a line to the last x stones. The stones are numbered 1 through n , and each pollywog occupies exactly one stone. A pollywog can jump at most k stones to the right at a...

Codeforces Round 572 (Div. 1)

Codeforces Round 572 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 4/6 | Rating range: 1600-3300 | Time: 24m 42s Problem Name Rating Tags Solve Time Verified A1 Add on a Tree 1600 trees 1m 48s ✓ A2 Add on a Tree: Revolution 2500 constructive-algorithms, dfs-and-similar, implementation 6m 56s ✗ B Count Pairs 2300 math, matrices, number-theory 3m 35s ✓ C Array Beauty 2500 dp 4m 40s ✗...

CF 1117D - Magic Gems

CF 1117D - Magic Gems Rating: 2100 Tags: dp, math, matrices Solve time: 1m 24s Verified: no Solution Problem Understanding We are counting ways to build a final sequence of unit-sized positions whose total length is exactly $N$. Each position can be either a normal gem or the result of splitting a magic gem. A normal gem always contributes exactly one unit and is indistinguishable except by position in the...

CF 1151F - Sonya and Informatics

CF 1151F - Sonya and Informatics Rating: 2300 Tags: combinatorics, dp, matrices, probabilities Solve time: 1m 58s Verified: no Solution Problem Understanding We are asked to determine the probability that an array consisting of zeros and ones becomes sorted in non-decreasing order after performing a fixed number of random swaps. Each swap selects two distinct positions in the array uniformly at random and exchanges their values. The array length is...

CF 1152F2 - Neko Rules the Catniverse (Large Version)

CF 1152F2 - Neko Rules the Catniverse (Large Version) Rating: 3000 Tags: bitmasks, dp, matrices Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to count sequences of planet visits with strong structural constraints. A path starts at any planet from 1 to n, and then performs exactly k − 1 moves. Each move goes from the current planet x to a new planet y that has...

CF 1152F1 - Neko Rules the Catniverse (Small Version)

CF 1152F1 - Neko Rules the Catniverse (Small Version) Rating: 2800 Tags: bitmasks, dp, matrices Solve time: 58s Verified: yes Solution Problem Understanding We are asked to count ordered sequences of distinct planets visited by a character who starts on any planet and then makes exactly $k-1$ moves. Each move goes from the current planet $x$ to a new planet $y$, with two restrictions: $y$ must not have been visited...

CF 1188B - Count Pairs

CF 1188B - Count Pairs Rating: 2300 Tags: math, matrices, number theory, two pointers Solve time: 3m 35s Verified: yes Solution Problem Understanding We are given a prime number $p$, an array of $n$ distinct integers $a_1, a_2, \ldots, a_n$ modulo $p$, and an integer $k$. Our task is to count how many pairs of indices $(i, j)$ with $i < j$ satisfy the congruence $(a_i + a_j)(a_i^2 + a_j^2)...

CF 1380F - Strange Addition

CF 1380F - Strange Addition Rating: 2600 Tags: data structures, dp, matrices Solve time: 2m 24s Verified: no Solution Correctness The revised submission correctly identifies the structure of the problem: it must first maximize the number of leading digits equal to $d$, then select the largest 50-digit prime with that prefix. It explicitly acknowledges that the solution requires actual computation of 50-digit primes, because theoretical arguments alone cannot determine the...

CF 1402C - Star Trek

CF 1402C - Star Trek Rating: 2600 Tags: *special, combinatorics, dfs and similar, dp, games, graphs, matrices, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a tree of $N$ planets. Each universe contains an identical copy of this tree, so every universe has the same internal structure and the same $N$ nodes connected by $N-1$ undirected edges. There are $D+1$ universes indexed from $0$ to...

CF 1411G - No Game No Life

CF 1411G - No Game No Life Rating: 2700 Tags: bitmasks, games, math, matrices Solve time: 1m 22s Verified: yes Solution Problem Understanding We are asked to calculate the probability that Alice wins a two-player chip-moving game on a directed acyclic graph. Each vertex can hold any number of chips, and players take turns moving a single chip along an outgoing edge. Alice starts first, and the player who cannot...

CF 1427E - Xum

CF 1427E - Xum Rating: 2500 Tags: bitmasks, constructive algorithms, math, matrices, number theory Solve time: 1m 34s Verified: yes Solution Problem Understanding We start from a single odd integer placed on a board. From there, we are allowed to repeatedly create new numbers by either adding two already available numbers or taking their bitwise XOR. Every time we perform an operation, the original numbers remain available, so the set...

Codeforces Round 691 (Div. 1)

Codeforces Round 691 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1600-3500 | Time: 22m 51s Problem Name Rating Tags Solve Time Verified A Row GCD 1600 math, number-theory 4m 24s ✓ B Glass Half Spilled 2000 dp 2m 10s ✓ C Latin Square 2700 math, matrices 5m 56s ✗ D Flip and Reverse 3100 data-structures, graphs, greedy 2m 3s ✗ E Nim Shortcuts...

CF 1458C - Latin Square

CF 1458C - Latin Square Rating: 2700 Tags: math, matrices Solve time: 5m 56s Verified: no Solution Problem Understanding We start with an (n \times n) Latin square. Every row is a permutation of (1 \ldots n), and every column is also a permutation of (1 \ldots n). A sequence of operations modifies the matrix. Four operations perform cyclic shifts of rows or columns. The other two operations are more...

CF 1474F - 1 2 3 4 ...

CF 1474F - 1 2 3 4 ... Rating: 3000 Tags: dp, math, matrices Solve time: 5m 1s Verified: no Solution Problem Understanding We are given a starting integer $x$ and a sequence of integers $d_1, d_2, \dots, d_n$. From these, we generate a new sequence $p$ by repeatedly adding or subtracting 1 from the last element, depending on the sign of $d_i$, and repeating this $|d_i|$ times for each...

CF 1513C - Add One

CF 1513C - Add One Rating: 1600 Tags: dp, matrices Solve time: 5m 58s Verified: no Solution Problem Understanding We are given an integer n and a number of operations m . In each operation, every digit d of n is incremented by 1, and if this results in a two-digit number (which only happens for 9), it is replaced by two digits 1 and 0 . The problem asks...

CF 1540E - Tasty Dishes

CF 1540E - Tasty Dishes Rating: 3500 Tags: math, matrices Solve time: 6m 31s Verified: no Solution Problem Understanding We are given a small directed system of chefs, where each chef holds a value. The structure is acyclic in the sense that chef $i$ can only interact with chefs of higher index. This allows information to flow only from right to left. Each chef has an initial value, and two...

CF 1599E - Two Arrays

CF 1599E - Two Arrays Rating: 3200 Tags: data structures, matrices Solve time: 2m 32s Verified: no Solution Problem Understanding 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. The modification queries either clamp values to a minimum or maximum, or add a...

CF 1609E - William The Oblivious

CF 1609E - William The Oblivious Rating: 2400 Tags: bitmasks, data structures, dp, matrices Solve time: 1m 55s Verified: no Solution Problem Understanding We are working with a mutable string consisting only of the characters a , b , and c . After each update, we must answer a structural question about the string: how many positions must be changed so that the string no longer contains abc as a...

CF 1616F - Tricolor Triangles

CF 1616F - Tricolor Triangles Rating: 2900 Tags: brute force, graphs, math, matrices Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a small undirected graph where every edge is supposed to end up painted with one of three colors. Some edges are already fixed with a color, while others start uncolored and must be assigned a value in {1, 2, 3} . The constraint is not...

Codeforces Round 772 (Div. 2)

Codeforces Round 772 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-2800 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A Min Or Sum 800 bitmasks, greedy 1m 9s ✓ B Avoid Local Maximums 800 greedy 2m 2s ✗ C Differential Sorting 1200 constructive-algorithms, greedy 1m 53s ✗ D Infinite Set 1800 bitmasks, dp, math 2m 41s ✗ E Cars 2200...

CF 1635D - Infinite Set

CF 1635D - Infinite Set Rating: 1800 Tags: bitmasks, dp, math, matrices, number theory, strings Solve time: 2m 41s Verified: no Solution This problem is rated 3500 and its solution relies on a fairly deep structural characterization of graphs whose cycle space admits a consistent cyclic orientation. Producing a correct editorial requires reconstructing the full proof and construction, not merely explaining a known implementation trick. I do not currently have...

Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1400-3500 | Time: 13m 49s Problem Name Rating Tags Solve Time Verified A Weird Sum 1400 combinatorics, data-structures, geometry 1m 12s ✓ B Integral Array 1800 brute-force, constructive-algorithms, data-structures 6m 6s ✗ C Tyler and Strings 1900 combinatorics, data-structures, implementation 57s ✓ D Serious Business 2800...

CF 1648A - Weird Sum

CF 1648A - Weird Sum Rating: 1400 Tags: combinatorics, data structures, geometry, math, matrices, sortings Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given a 2D grid of size $n \times m$ where each cell contains a color represented by an integer. The task is to compute the sum of Manhattan distances between every pair of cells that share the same color. The Manhattan distance between two...

CF 1662C - European Trip

CF 1662C - European Trip Rating: - Tags: dp, graphs, math, matrices Solve time: 5m 17s Verified: no Solution Problem Understanding We are asked to count special trips on a graph of cities. Each city is a node, and each road is an undirected edge connecting two cities. A trip of length k is a sequence of k+1 cities such that each consecutive pair is connected by a road. A...

CF 1672G - Cross Xor

CF 1672G - Cross Xor Rating: 3200 Tags: constructive algorithms, graphs, math, matrices Solve time: 1m 33s Verified: yes Solution Problem Understanding We are asked to construct a binary grid of size $r \times c$ by applying a specific row-column flip operation multiple times starting from an all-zero grid. The operation allows us to pick any cell and flip all values in its row and column using XOR with 1....

CF 1681E - Labyrinth Adventures

CF 1681E - Labyrinth Adventures Rating: 2600 Tags: data structures, dp, matrices, shortest paths Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a labyrinth structured as concentric layers in an $n \times n$ grid. Each layer is a contiguous set of cells surrounding the previous layer. The first layer is just the bottom-left corner. Every subsequent layer is connected to the previous by exactly two doors:...

CF 1698G - Long Binary String

CF 1698G - Long Binary String Rating: 2900 Tags: bitmasks, math, matrices, meet-in-the-middle, number theory Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a small binary string s of length up to 35, and we need to manipulate a conceptual binary string t of length $10^{100}$, which is initially all zeros. The operation allowed is selecting a contiguous substring of t of the same length as...

Codeforces Round 804 (Div. 2)

Codeforces Round 804 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 0/5 | Rating range: 800-2600 | Time: 18m 44s Problem Name Rating Tags Solve Time Verified A The Third Three Number Problem 800 constructive-algorithms, math 2m 3s ✗ B Almost Ternary Matrix 900 bitmasks, constructive-algorithms, matrices 8m 9s ✗ C The Third Problem 1700 combinatorics, constructive-algorithms, math 3m 2s ✗ D Almost Triple Deletions 2300 data-structures, dp,...

CF 1699B - Almost Ternary Matrix

CF 1699B - Almost Ternary Matrix Rating: 900 Tags: bitmasks, constructive algorithms, matrices Solve time: 8m 9s Verified: no Solution Problem Understanding We are asked to construct a binary matrix of size $n \times m$ where $n$ and $m$ are guaranteed to be even. The constraint is that each cell must have exactly two neighbors with a value different from its own. Neighbors are defined as the four cells directly...

CF 1701F - Points

CF 1701F - Points Rating: 2500 Tags: combinatorics, data structures, implementation, math, matrices Solve time: 9m 47s Verified: no Solution Problem Understanding We are given a dynamic set of points on a number line and a fixed parameter $d$. A triple $(i,j,k)$ is called beautiful if the points satisfy $i < j < k$ and the distance between the endpoints $k - i$ is at most $d$. Initially the set...

CF 1713E - Cross Swapping

CF 1713E - Cross Swapping Rating: 2400 Tags: 2-sat, data structures, dsu, greedy, matrices Solve time: 2m 32s Verified: no Solution Problem Understanding We are given a square matrix of integers, and we are allowed to perform a specific swap operation: for a chosen index k , we swap the k -th row with the k -th column, leaving the diagonal element at (k, k) unchanged. The goal is to...

CF 1743F - Intersection and Union

CF 1743F - Intersection and Union Rating: 2300 Tags: data structures, dp, matrices, probabilities Solve time: 1m 37s Verified: no Solution Problem-Type Check This problem is Type A. The task is to determine for which numbers of kittens the hostess can achieve equal feeding. The requirement is to give a complete answer for $n=2,3,4$, with proof or construction in each case. The proposed solution attempts exactly this. The type check...

CF 1761E - Make It Connected

CF 1761E - Make It Connected Rating: 2400 Tags: binary search, brute force, constructive algorithms, dsu, graphs, greedy, matrices, trees, two pointers Solve time: 11m 43s Verified: no Solution Problem Understanding We are given an undirected graph and a special operation. Choosing a vertex flips all of its incident edges: every neighbor becomes a non-neighbor, and every non-neighbor becomes a neighbor. Viewed another way, choosing vertex u replaces its adjacency...

CF 1814E - Chain Chips

CF 1814E - Chain Chips Rating: 2300 Tags: data structures, dp, matrices Solve time: 2m Verified: no Solution Problem Understanding We are given a line of vertices labeled from 1 to n, where each consecutive pair i and i+1 is connected by an edge with a given weight. Initially, every vertex i holds a chip labeled i, so everything is perfectly aligned. In one move, we can pick any chip...

CF 1844G - Tree Weights

CF 1844G - Tree Weights Rating: 3000 Tags: bitmasks, constructive algorithms, data structures, dfs and similar, implementation, math, matrices, number theory, trees Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a tree with n nodes and n-1 edges, where the edges are unlabeled with weights. Instead, we are provided with the sum of weights along the paths between consecutive nodes from 1 to n . Our...

CF 2078F - Binary Subsequence Value Sum

CF 2078F - Binary Subsequence Value Sum Rating: 2300 Tags: combinatorics, data structures, dp, fft, math, matrices Solve time: 1m 43s Verified: no Solution Problem Understanding We are working with a binary string that changes over time through flip operations. After every flip, we consider all non-empty subsequences of the current string. Each subsequence is assigned a score based on how it can be split into two parts. For any...

CF 2004G - Substring Compression

CF 2004G - Substring Compression Rating: 3200 Tags: data structures, dp, matrices Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a digit string. For every substring of length exactly k , we must compute the minimum possible length after performing one compression operation. A compression is defined by splitting the string into an even number of non-empty pieces $$t_1,t_2,t_3,t_4,\dots$$ and replacing each pair $(t_{2i-1},t_{2i})$ by the...

CF 1972E - Fenwick Tree

CF 1972E - Fenwick Tree Rating: 2300 Tags: combinatorics, data structures, math, matrices Solve time: 2m 6s Verified: no Solution Problem Understanding The problem asks us to reverse-engineer a Fenwick tree, or binary indexed tree, operation. A Fenwick tree s is derived from an array a by summing a specific range for each index k . The range starts at k - lowbit(k) + 1 and ends at k ,...

CF 1864H - Asterism Stream

CF 1864H - Asterism Stream Rating: 3200 Tags: dp, math, matrices Solve time: 1m 26s Verified: no Solution Problem Understanding We are asked to compute the expected number of moves to reach or exceed a target integer n starting from x = 1 when in each move you either increment x by 1 or double it, each with probability 1/2. Each test case gives a value of n up to...

CF 1895F - Fancy Arrays

CF 1895F - Fancy Arrays Rating: 2600 Tags: combinatorics, dp, math, matrices Solve time: 2m 19s Verified: yes Solution Problem Understanding We are counting arrays of length n consisting of non-negative integers. Adjacent values may move by at most k in either direction. An array is considered fancy if at least one element belongs to the interval $$[x, x+k-1].$$ The task is to count all such arrays modulo $10^9+7$. The...

CF 1916H2 - Matrix Rank (Hard Version)

CF 1916H2 - Matrix Rank (Hard Version) Rating: 2700 Tags: combinatorics, dp, math, matrices, string suffix structures Solve time: 1m 7s Verified: yes Solution Problem Understanding We are asked to count the number of $n \times n$ matrices over a finite field of size $p$ (integers modulo a prime $p$) that have an exact rank $r$, for every $r$ from 0 to $k$. The key detail is that $n$ can...

CF 1916H1 - Matrix Rank (Easy Version)

CF 1916H1 - Matrix Rank (Easy Version) Rating: 2700 Tags: brute force, combinatorics, dp, math, matrices Solve time: 1m 25s Verified: yes Solution Problem Understanding We are working over an $n \times n$ matrix whose entries lie in a finite field of size $p$, meaning every entry is an integer modulo $p$ and arithmetic behaves like linear algebra over a field. For each possible rank $r$, we want to count...

CF 1919F2 - Wine Factory (Hard Version)

CF 1919F2 - Wine Factory (Hard Version) Rating: 2800 Tags: data structures, dp, flows, greedy, matrices Solve time: 43s Verified: no Solution Problem Understanding We are tasked with simulating a sequence of water towers, each containing an initial amount of water. In front of each tower stands a wizard who can convert a limited number of liters into wine. Between consecutive towers there are valves that allow a limited amount...

CF 1924C - Fractal Origami

CF 1924C - Fractal Origami Rating: 2400 Tags: geometry, math, matrices Solve time: 3m 21s Verified: no Solution Problem Understanding We repeatedly perform the same fold on a square sheet. Every fold takes the current square, folds all four corners to its center, and produces a smaller square whose side length is multiplied by $1/\sqrt2$. After performing the operation $N$ times and unfolding the paper, every crease is either a...

Educational Codeforces Round 174 (Rated for Div. 2)

Educational Codeforces Round 174 (Rated for Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2800 | 10m 15s # Problem Rating Tags Accepted Time ✓ A Was there an Array? 800 graph-matchings, greedy 26,547 1m 28s ✓ B Set of Strangers 1200 greedy, matrices 18,806 1m 33s C Beautiful Sequence 1500 combinatorics, dp, greedy 14,813 1m 38s D Palindrome Shuffle 1800 binary-search, greedy, hashing 7,047 1m...

Codeforces Round 984 (Div. 3)

Codeforces Round 984 (Div. 3) Div. 3 | 7 problems | 4/7 verified | Difficulty 800-2200 | 12m 48s # Problem Rating Tags Accepted Time ✓ A Quintomania 800 implementation 40,685 1m 1s ✓ B Startup 800 greedy, sortings 29,738 2m 4s C Anya and 1100 1100 brute-force, implementation 22,192 1m 5s ✓ D I Love 1543 1300 brute-force, implementation, matrices 15,983 3m 4s ✓ E Reverse the Rivers 1600...

CF 1970E3 - Trails (Hard)

CF 1970E3 - Trails (Hard) Rating: 2200 Tags: dp, matrices Solve time: 2m 16s Verified: no Solution Problem Understanding We are asked to count the number of possible sequences of trails Harry can take over n days starting from cabin 1. Each day consists of two moves: first from his current cabin to the lake, then from the lake to any cabin. Each cabin has a given number of short...

CF 1970E2 - Trails (Medium)

CF 1970E2 - Trails (Medium) Rating: 2000 Tags: dp, matrices Solve time: 1m 39s Verified: yes Solution Problem Understanding The problem describes a scenario where Harry Potter moves between a set of cabins and a central lake along trails. Each cabin has a number of short and long trails connecting it to the lake. Each day, Harry makes exactly two moves: first from his current cabin to the lake, then...

CF 1980E - Permutation of Rows and Columns

CF 1980E - Permutation of Rows and Columns Rating: 1600 Tags: constructive algorithms, data structures, greedy, hashing, implementation, math, matrices, sortings Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given two rectangular grids of numbers, both of size $n \times m$, and together they contain exactly the numbers from $1$ to $n \cdot m$, each appearing once. So each matrix is just a rearrangement of the same...

CF 1995E2 - Let Me Teach You a Lesson (Hard Version)

CF 1995E2 - Let Me Teach You a Lesson (Hard Version) Rating: 2900 Tags: data structures, dp, matrices, two pointers Solve time: 4m 3s Verified: no Solution Problem Understanding We have $2n$ knights sitting at $n$ desks arranged in a circle. Each desk has exactly two knights, the first at position $2i-1$ and the second at $2i$. Each knight has an integer intelligence value. Arthur can swap the knight at...

CF 1995E1 - Let Me Teach You a Lesson (Easy Version)

CF 1995E1 - Let Me Teach You a Lesson (Easy Version) Rating: 2700 Tags: 2-sat, data structures, dp, matrices, two pointers Solve time: 2m 39s Verified: no Solution Problem Understanding We have 2n knights arranged around a circle. Desk i contains knights (2i-1, 2i) , so every desk contributes a sum of two intelligence values. The only operation allowed is swapping opposite positions in the circle. For every k from...

CF 2018D - Max Plus Min Plus Size

CF 2018D - Max Plus Min Plus Size Rating: 2200 Tags: data structures, dp, dsu, greedy, implementation, matrices, sortings Solve time: 1m 55s Verified: no Solution Problem Understanding We are given a one-dimensional array of positive integers and the ability to color some elements red. The restriction is that no two consecutive elements can be red. Our goal is to choose a subset of the elements to color red such...

CF 2023F - Hills and Pits

CF 2023F - Hills and Pits Rating: 3500 Tags: data structures, greedy, math, matrices Solve time: 1m 35s Verified: no Solution Problem Understanding 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. A truck starts empty, can carry unlimited sand, and moves along adjacent positions in unit time. At...

CF 2097D - Homework

CF 2097D - Homework Rating: 2800 Tags: bitmasks, math, matrices Solve time: 1m 42s Verified: no Solution Problem Understanding We are given two binary strings of the same length, and we are allowed to repeatedly apply a very specific transformation that acts on halves of substrings and mixes corresponding bits using XOR-like behavior. Each operation either replaces one half of a split string with the bitwise XOR of the two...

CF 2036D - I Love 1543

CF 2036D - I Love 1543 Rating: 1300 Tags: brute force, implementation, matrices Solve time: 3m 4s Verified: yes Solution Problem Understanding The input describes several rectangular grids of digits. Each grid is split conceptually into concentric “rings” or layers, starting from the outer border and moving inward. Every layer forms a closed cycle if you walk along its border clockwise. For each such cycle, we imagine reading the digits...

CF 2042F - Two Subarrays

CF 2042F - Two Subarrays Rating: 2600 Tags: data structures, dp, implementation, matrices Solve time: 2m 29s Verified: no Solution Problem Understanding We have two arrays, a and b . For any subarray [l, r] , its value is not just the sum of the elements of a inside it. We also add b_l and b_r , the values attached to the two endpoints. If the subarray consists of a...

CF 2057D - Gifts Order

CF 2057D - Gifts Order Rating: 2000 Tags: data structures, greedy, implementation, math, matrices Solve time: 1m 54s Verified: no Solution Problem Understanding We are given an array of integers representing sweater sizes. From any contiguous segment of this array, we define a score that depends on how spread out the values are and how long the segment is. Concretely, for a segment from index $l$ to $r$, the score...

CF 2065H - Bro Thinks He's Him

CF 2065H - Bro Thinks He's Him Rating: 2200 Tags: combinatorics, data structures, divide and conquer, dp, math, matrices Solve time: 1m 51s Verified: no Solution Problem Understanding The problem asks us to work with a binary string and queries that flip individual bits. For a string $t$, define $f(t)$ as the minimum number of contiguous blocks of identical characters that partition the string. For example, for 00110001 , the...

CF 2069B - Set of Strangers

CF 2069B - Set of Strangers Rating: 1200 Tags: greedy, matrices Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a rectangular grid of size $n \times m$ where each cell has a color represented by an integer. We can perform painting operations where in a single step we choose a set of cells that are strangers-that is, no two of them share a side-and all have...

CF 2077C - Binary Subsequence Value Sum

CF 2077C - Binary Subsequence Value Sum Rating: 2300 Tags: combinatorics, data structures, dp, fft, math, matrices Solve time: 1m 58s Verified: yes Solution Problem Understanding Every character of the string contributes either +1 or -1 . If we define $$w(c)= \begin{cases} +1,&c='1'\ -1,&c='0' \end{cases}$$ then for any segment of a binary string, the function $F$ is simply the sum of these values over that segment. For a binary string...

CF 2081C - Quaternary Matrix

CF 2081C - Quaternary Matrix Rating: 2700 Tags: bitmasks, constructive algorithms, greedy, implementation, matrices Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a matrix of size $n \times m$ where each element is an integer from 0 to 3. The goal is to transform this matrix into a "good" matrix. A good matrix is defined by two simultaneous XOR constraints: each row must XOR to zero,...

CF 2138E2 - Determinant Construction (Hard Version)

CF 2138E2 - Determinant Construction (Hard Version) Rating: 3100 Tags: brute force, constructive algorithms, math, matrices, number theory Solve time: 1m 32s Verified: no Solution Problem Understanding We are asked to construct a square matrix with small integer entries, limited non-zero elements per row and column, and a determinant equal to a given target number. Each test case provides a non-negative integer $x$, and we must output a matrix $M$...

CF 2138E1 - Determinant Construction (Easy Version)

CF 2138E1 - Determinant Construction (Easy Version) Rating: 3100 Tags: brute force, constructive algorithms, math, matrices, number theory Solve time: 2m 11s Verified: no Solution Approaches The determinant can be written using the Leibniz formula: $$\det(M)=\sum_{\sigma} \operatorname{sgn}(\sigma)\prod_i M_{i,\sigma(i)}.$$ A brute force viewpoint is to think of each permutation as choosing one outgoing edge from every row and one incoming edge into every column. In graph language this corresponds to a...

CF 2145F - Long Journey

CF 2145F - Long Journey Rating: 2500 Tags: dfs and similar, divide and conquer, dp, graphs, greedy, math, matrices, number theory Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a very long one-dimensional strip of cells, numbered from 0 up to m. A chip starts at cell 0 and wants to reach cell m in as few turns as possible. Each turn, the chip either stays...

CF 2152G - Query Jungle

CF 2152G - Query Jungle Rating: 2900 Tags: data structures, implementation, math, matrices, trees Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a rooted tree with root fixed at vertex 1. Some vertices are marked as “active” (contain a monster), others are not. The task is to cover all active vertices using a collection of root-starting paths, where each path is a simple path that begins...

CF 2180F2 - Control Car (Hard Version)

CF 2180F2 - Control Car (Hard Version) Rating: 3200 Tags: combinatorics, dp, matrices, probabilities Solve time: 1m 46s Verified: no Solution Problem Understanding We are asked to count the number of ways to assign directions to the corners of an $n \times m$ grid so that a simulated car starting at the top-left cell eventually stops inside the grid. Each intersection point between the grid lines can point in one...

CF 2181K - Knit the Grid

CF 2181K - Knit the Grid Rating: 3500 Tags: 2-sat, constructive algorithms, graphs, matrices Solve time: 2m 47s Verified: no Solution Problem Understanding The canvas is a rectangular grid of cells, but the real structure lives on its grid graph: vertices are grid intersection points and edges connect adjacent intersections horizontally or vertically. Initially, some collection of simple cycles is drawn along these edges. The cycles are vertex-disjoint, and every...

CF 2204G - Grid Path

CF 2204G - Grid Path Rating: 2700 Tags: dp, graphs, matrices Solve time: 1m 42s Verified: no Solution Problem Understanding We are working on a rectangular grid where we start from the top-left cell and are allowed to walk using three moves: left, right, or down. There is no upward movement, which is the key structural restriction. Every walk generates a set of visited cells, and two walks are considered...

CF 2208D1 - Tree Orientation (Easy Version)

CF 2208D1 - Tree Orientation (Easy Version) Rating: 1800 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, matrices, trees Solve time: 3m 24s Verified: no Solution Problem Understanding We are given a binary reachability matrix for a directed graph on $n$ nodes. The matrix tells us, for every ordered pair $(i, j)$, whether node $i$ can reach node $j$ through directed edges. The underlying graph that produced this matrix...

CF 351C - Jeff and Brackets

CF 351C - Jeff and Brackets Rating: 2500 Tags: dp, matrices Solve time: 1m 29s Verified: yes Solution Problem Understanding We are asked to construct a bracket sequence of length n·m , where n is a small number up to 20 and m is much larger, up to 10^7, and is even. Each position in the sequence can be either an opening bracket ( or a closing bracket ) ....

CF 348D - Turtles

CF 348D - Turtles Rating: 2500 Tags: dp, matrices Solve time: 2m 5s Verified: no Solution Problem Understanding We are given a rectangular grid of size n by m , where each cell is either free or blocked. Two turtles start at the top-left corner, cell (1,1), and both want to reach the bottom-right corner, cell ( n , m ). The turtles can only move down or right at...

Codeforces Round 139 (Div. 2)

Codeforces Round 139 (Div. 2) Div. 2 | 5 problems | 0/5 verified | Difficulty 1100-2200 | 15m 45s # Problem Rating Tags Accepted Time ✓ A Dice Tower 1100 constructive-algorithms, greedy 14,238 2m 18s B Well-known Numbers 1600 binary-search, greedy, number-theory 3,394 3m 27s C Barcode 1700 dp, matrices 10,162 5m 19s D Snake 2200 bitmasks, dfs-and-similar, graphs 1,049 2m 19s E Unsolvable 2100 math, number-theory 902 2m 22s

CF 267C - Berland Traffic

CF 267C - Berland Traffic Rating: 2700 Tags: math, matrices Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a directed system of roads connecting a small number of intersections. Each road has a capacity, meaning there is a maximum amount of traffic that can be assigned to it in total, regardless of direction. The key freedom is that traffic on a road can be split in...

CF 225C - Barcode

CF 225C - Barcode Rating: 1700 Tags: dp, matrices Solve time: 5m 19s Verified: no Solution

CF 222E - Decoding Genome

CF 222E - Decoding Genome Rating: 1900 Tags: dp, matrices Solve time: 1m 55s Verified: yes Solution Problem Understanding We have an alphabet of size m , consisting of the first m symbols from the sequence a..zA..Z . Some ordered pairs of symbols are forbidden. If pair (x, y) is forbidden, then symbol y cannot appear immediately after symbol x in the DNA string. The task is to count how...

CF 193C - Hamming Distance

CF 193C - Hamming Distance Rating: 2400 Tags: constructive algorithms, greedy, math, matrices Solve time: 2m 30s Verified: no Solution Problem Understanding We are asked to reconstruct four binary strings consisting only of letters a and b , given the Hamming distances between every pair of strings. The Hamming distance between two strings counts the positions where the strings differ. The input gives six integers, corresponding to the distances between...

CF 193E - Fibonacci Number

CF 193E - Fibonacci Number Rating: 2900 Tags: brute force, math, matrices Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a single number $f$, and we consider the infinite sequence generated by Fibonacci rules, but taken modulo 1013. The sequence starts with 0 and 1, and every next value is the sum of the previous two, reduced modulo 1013. So the sequence is fully determined and...

CF 177G2 - Fibonacci Strings

CF 177G2 - Fibonacci Strings Rating: 2600 Tags: matrices, strings Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a very large Fibonacci-like string, but we are never asked to construct it directly. Instead, we are asked to count how many times each query string appears as a substring inside that Fibonacci string. The Fibonacci strings start from two base cases, then each next string is formed...

Codeforces Round 276 (Div. 2)

Codeforces Round 276 (Div. 2) Div. 2 | 2 problems | 0/2 verified | Difficulty 1300-1400 | 16m 31s # Problem Rating Tags Accepted Time ✓ A Factory 1400 implementation, math, matrices 8,767 5m 22s B Valuable Resources 1300 brute-force, greedy 6,791 11m 9s

CF 485A - Factory

CF 485A - Factory Rating: 1400 Tags: implementation, math, matrices Solve time: 5m 22s Verified: no Solution

CF 453D - Little Pony and Elements of Harmony

CF 453D - Little Pony and Elements of Harmony Rating: 3000 Tags: dp, matrices Solve time: 2m 30s Verified: yes Solution Problem Understanding We have a vector of energies indexed by all bitmasks of length m . Since n = 2^m , every vertex can be identified with an m -bit number. One transformation step is linear. For every pair of vertices u and v , the contribution from v...

CF 472F - Design Tutorial: Change the Goal

CF 472F - Design Tutorial: Change the Goal Rating: 2700 Tags: constructive algorithms, math, matrices Solve time: 1m 27s Verified: no Solution Problem Understanding We are given two arrays of integers, x and y , each of length n . The array x is the starting state, and y is the desired target state. The only operation allowed is x[i] ^= x[j] , which replaces x[i] with the bitwise XOR...

Codeforces Testing Round 5

Codeforces Testing Round 5 Special | 3 problems | 2/3 verified | Difficulty 900-2700 | 6m 13s # Problem Rating Tags Accepted Time ✓ A Subtractions 900 math, number-theory 9,557 2m 41s ✓ B Dominoes 2000 dfs-and-similar, graphs 753 1m 39s ✓ C Berland Traffic 2700 math, matrices 253 1m 53s

Codeforces Round 140 (Div. 1)

Codeforces Round 140 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1400-2900 | 14m 33s # Problem Rating Tags Accepted Time ✓ A Flying Saucer Segments 1400 math 4,351 5m 43s ✓ B Naughty Stone Piles 1900 greedy 1,708 2m 22s ✓ C Anniversary 2400 data-structures, implementation, math 1,017 2m 19s ✓ D The table 2100 constructive-algorithms, greedy 1,126 2m 58s E Noble Knight's Path 2900...

Codeforces Testing Round 4

Codeforces Testing Round 4 Special | 2 problems | 2/2 verified | Difficulty 1300-2500 | 2m 45s # Problem Rating Tags Accepted Time ✓ A Punctuation 1300 implementation, strings 4,235 1m 18s ✓ B Smile House 2500 binary-search, graphs, matrices 919 1m 27s ✓

CF 446E - DZY Loves Bridges

CF 446E - DZY Loves Bridges Rating: 3100 Tags: math, matrices Solve time: 1m 25s Verified: no Solution Problem Understanding We are dealing with a very large directed walk-counting problem on a graph that is heavily structured but too large to ever build explicitly. There are $2m$ islands, and DZY starts from a home node. From home, he can move to island $i$ in $a_i$ different ways. After that first...

CF 167E - Wizards and Bets

CF 167E - Wizards and Bets Rating: 2900 Tags: dfs and similar, graphs, math, matrices Solve time: 3m 52s Verified: yes Solution Problem Understanding We are given a directed acyclic graph. Some vertices are sources, meaning no edge enters them. Some vertices are sinks, meaning no edge leaves them. The number of sources and sinks is guaranteed to be equal. A valid configuration consists of vertex-disjoint directed paths such that...

CF 446D - DZY Loves Games

CF 446D - DZY Loves Games Rating: 2800 Tags: math, matrices, probabilities Solve time: 1m 41s Verified: no Solution Problem Understanding We are given an undirected connected graph representing a maze of rooms. DZY starts at room 1 with a fixed number of lives. Each time he is in a room, he randomly chooses one of its outgoing corridors uniformly and moves to the adjacent room. Every time he enters...

CF 147B - Smile House

CF 147B - Smile House Rating: 2500 Tags: binary search, graphs, matrices Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given a set of rooms connected by doors, where each door has two mood values: one for each direction. Petya can move from room to room, and every move adds to his mood according to the direction-specific value. The task is to determine whether Petya can increase...

CF 166E - Tetrahedron

CF 166E - Tetrahedron Rating: 1500 Tags: dp, math, matrices Solve time: 3m Verified: yes Solution Problem Understanding We are asked to count the number of ways an ant can start at vertex D of a tetrahedron and return to D after exactly n steps, moving along edges at every step. The tetrahedron has four vertices labeled A, B, C, D, and each vertex is connected to the other three....

CF 226C - Anniversary

CF 226C - Anniversary Rating: 2400 Tags: data structures, implementation, math, matrices, number theory Solve time: 2m 19s Verified: yes Solution Problem Understanding We are asked to work with a contiguous range of integers from l to r , and for every possible subset of size k within this range, we consider the Fibonacci numbers at positions given by the subset elements. Among all subsets, we must find the maximum...

Codeforces Beta Round 76 (Div. 1 Only)

Codeforces Beta Round 76 (Div. 1 Only) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-2600 | 10m 8s # Problem Rating Tags Accepted Time ✓ A Frames 1700 implementation 2,071 1m 51s ✓ B End of Exams 1900 greedy 988 1m 43s C Azembler 2500 brute-force, implementation 450 2m 1s ✓ D Flags 2500 dp, math, matrices 444 3m 28s E Lostborn 2600 dp, math, number-theory 540...

CF 93D - Flags

CF 93D - Flags Rating: 2500 Tags: dp, math, matrices Solve time: 3m 28s Verified: no Solution Problem Understanding We need to count stripe sequences built from four colors: black, red, white, and yellow. A sequence is valid if it satisfies several local restrictions. Equal adjacent colors are forbidden. White cannot touch yellow. Red cannot touch black. The length-3 patterns BWR and RWB are forbidden as well. Two flags are...

CF 60E - Mushroom Gnomes

CF 60E - Mushroom Gnomes Rating: 2600 Tags: math, matrices Solve time: 3m 13s Verified: yes Solution Problem Understanding We are given a line of mushrooms, each with a weight, initially sorted in non-decreasing order. Every minute, new mushrooms grow between every pair of neighboring mushrooms, and the weight of each new mushroom equals the sum of the two neighboring mushrooms. After some minutes x , the gnomes sort the...

CF 86E - Long sequence

CF 86E - Long sequence Rating: 2700 Tags: brute force, math, matrices Solve time: 1m 38s Verified: yes Solution Problem Understanding We are asked to construct a special kind of binary sequence, called a recurrent binary sequence. Each term in this sequence is either 0 or 1, and for a given integer k , there exist coefficients c₁, c₂, …, cₖ , also 0 or 1, such that every term...

CF 113D - Museum

CF 113D - Museum Rating: 2700 Tags: math, matrices, probabilities Solve time: 1m 55s Verified: yes Solution Problem Understanding We are asked to model the random movements of two friends inside a museum represented as an undirected connected graph with n rooms and m corridors. Each room has a probability of staying in place for a minute, and otherwise the person moves uniformly to a neighboring room. The task is...

CF 107D - Crime Management

CF 107D - Crime Management Rating: 2400 Tags: dp, graphs, matrices Solve time: 2m 6s Verified: yes Solution Problem Understanding Zeyad wants to commit exactly n crimes in a sequence so that he avoids any punishment. Each crime type is represented by a capital letter, and for some crimes there are conditions describing multiplicities: committing that crime a number of times divisible by its multiplicity results in no punishment for...

15. Linear and Multilinear Algebra; Matrix Theory

This volume develops vector spaces, linear maps, matrices, and multilinear structures. It serves as a core toolkit for nearly all areas of mathematics, physics, and computation. Part I. Vector Spaces Chapter 1. Vector Spaces 1.1 Definitions and examples 1.2 Subspaces 1.3 Linear combinations 1.4 Span and generation 1.5 Linear independence Chapter 2. Bases and Dimension 2.1 Bases 2.2 Existence of bases 2.3 Dimension 2.4 Coordinate representations 2.5 Change of basis...

Tiling

Array Tiling Array tiling divides a multidimensional array into small rectangular regions called tiles. Each tile is processed before moving to the next tile. You use it when matrix or grid operations touch nearby elements repeatedly and cache locality affects performance. Problem Given a matrix $A$ with $r$ rows and $c$ columns, process all elements in tiles of size: $$ t_r \times t_c $$ where $t_r$ is the tile height...