divide-and-conquer

Practice › Codeforces Solutions › 2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) ›

CF 1250M - SmartGarden

CF 1250M - SmartGarden Rating: 2500 Tags: constructive algorithms, divide and conquer Solve time: 1m 24s Verified: yes Solution Problem Understanding The garden is an $n \times n$ grid where each cell is either a plant that must be watered or a slab that must never be touched. The layout is highly structured: all diagonal cells are slabs, and every cell strictly below the diagonal that touches the diagonal also...

Practice › Codeforces Solutions › Educational Codeforces Round 65 (Rated for Div. 2) ›

CF 1167B - Lost Numbers

CF 1167B - Lost Numbers Rating: 1400 Tags: brute force, divide and conquer, interactive, math Solve time: 1m 25s Verified: no Solution Problem Understanding 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. Our only way to learn about the array is by asking queries of...

Practice › Codeforces Solutions › Divide by Zero 2018 and Codeforces Round 474 (Div. 1 + Div. 2, combined) ›

CF 960E - Alternating Tree

CF 960E - Alternating Tree Rating: 2300 Tags: combinatorics, dfs and similar, divide and conquer, dp, probabilities, trees Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a tree with a value attached to every node. Between any two nodes $u$ and $v$, there is exactly one simple path, and we assign a score to that directed path by taking the node values along the path and...

Practice › Codeforces Solutions › Avito Code Challenge 2018 ›

CF 981E - Addition on Segments

CF 981E - Addition on Segments Rating: 2200 Tags: bitmasks, data structures, divide and conquer, dp Solve time: 2m 22s Verified: yes Solution Problem Understanding We start with an array of length $n$ filled with zeros. There are $q$ operations, each operation adds a positive value $x_i$ to every position in a contiguous segment $[l_i, r_i]$. We are not forced to apply all operations. Instead, we may choose any subset...

Practice › Codeforces Solutions ›

Educational Codeforces Round 46 (Rated for Div. 2)

Educational Codeforces Round 46 (Rated for Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 1500-2700 | 7m 8s # Problem Rating Tags Accepted Time ✓ B Light It Up 1500 greedy 6,162 1m 52s ✓ C Covered Points Count 1700 data-structures, implementation, sortings 8,431 1m 14s ✓ F One Occurrence 2400 data-structures, divide-and-conquer 4,835 1m 52s G Two-Paths 2700 data-structures, dp, trees 715 2m 10s

Practice › Codeforces Solutions › Educational Codeforces Round 46 (Rated for Div. 2) ›

CF 1000F - One Occurrence

CF 1000F - One Occurrence Rating: 2400 Tags: data structures, divide and conquer Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a static array and many independent queries, each query asking us to inspect a contiguous segment of the array and return any value that appears exactly once inside that segment. If no such value exists in that segment, the answer is zero. A useful way...

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004F - Sonya and Bitwise OR

CF 1004F - Sonya and Bitwise OR Rating: 2600 Tags: bitmasks, data structures, divide and conquer Solve time: 2m 39s Verified: no Solution Problem Understanding We are given an array that changes over time and we must repeatedly answer queries about subarrays inside a given segment. For any segment $[l, r]$, we consider every contiguous subarray $[L, R]$ fully contained inside it. For each such subarray, we compute the bitwise...

Practice › Codeforces Solutions › Codeforces Round 503 (by SIS, Div. 1) ›

CF 1019E - Raining season

CF 1019E - Raining season Rating: 3200 Tags: data structures, divide and conquer, trees Solve time: 2m 36s Verified: yes Solution Problem Understanding We are given a tree where each edge represents a bidirectional road between two houses. Every road has two parameters: a base traversal time and a rate at which it worsens each day. On day $t$, the cost of an edge becomes a linear function $b_i +...

Practice › Codeforces Solutions › Codeforces Round 519 by Botan Investments ›

CF 1043G - Speckled Band

CF 1043G - Speckled Band Rating: 3500 Tags: data structures, divide and conquer, hashing, string suffix structures, strings Solve time: 6m 55s Verified: no Solution Problem Understanding We are given a long string and many queries, each asking about a substring. For each substring, we imagine splitting it into several consecutive pieces. Among those pieces, identical pieces are considered the same “band”. The game score is the minimum possible number...

Practice › Codeforces Solutions › Codeforces Round 656 (Div. 3) ›

CF 1385D - a-Good String

CF 1385D - a-Good String Rating: 1500 Tags: bitmasks, brute force, divide and conquer, dp, implementation Solve time: 8m 44s Verified: no Solution Problem Understanding The task is to transform a given string into a very specific recursively defined structure centered around the letter 'a' . The structure is not arbitrary: every string is evaluated as being “good” for a given character c , where either the string is a...

Practice › Codeforces Solutions › Codeforces Round 657 (Div. 2) ›

CF 1379F2 - Chess Strikes Back (hard version)

CF 1379F2 - Chess Strikes Back (hard version) Rating: 2800 Tags: data structures, divide and conquer Solve time: 10m 43s Verified: no Solution Problem Understanding We are working on a very large grid of size $2n \times 2m$, but we only care about the white cells, those where the sum of coordinates is even. Among these white cells, some are dynamically toggled between available and unavailable across a sequence of...

Practice › Codeforces Solutions › Codeforces Global Round 9 ›

CF 1375H - Set Merging

CF 1375H - Set Merging Rating: 3300 Tags: constructive algorithms, divide and conquer Solve time: 5m 47s Verified: no Solution Problem Understanding We are given a permutation of numbers from 1 to n, but the real object we care about is not the values themselves, it is their positions. Initially each position i forms a singleton set containing the value a[i]. The only allowed operation is to merge two already-built...

Practice › Codeforces Solutions › Codeforces Round 655 (Div. 2) ›

CF 1372F - Omkar and Modes

CF 1372F - Omkar and Modes Rating: 2700 Tags: binary search, divide and conquer, interactive Solve time: 4m 31s Verified: no Solution Problem Understanding We are given a hidden array of length $n$, already sorted in nondecreasing order, and containing at most $k \le 25000$ distinct values. Our only way to inspect it is by querying a segment $[l,r]$. Each query returns the mode of that segment and how many...

Practice › Codeforces Solutions › Codeforces Round 654 (Div. 2) ›

CF 1371F - Raging Thunder

CF 1371F - Raging Thunder Rating: 2800 Tags: data structures, divide and conquer, implementation Solve time: 5m 19s Verified: no Solution Problem Understanding We are given a line of positions, each containing a direction symbol that behaves like a deterministic local rule. From every starting position, a ball moves left or right according to its own symbol and the symbol of the neighbor it is interacting with. Eventually every ball...

Practice › Codeforces Solutions › Codeforces Round 649 (Div. 2) ›

CF 1364E - X-OR

CF 1364E - X-OR Rating: 2700 Tags: bitmasks, constructive algorithms, divide and conquer, interactive, probabilities Solve time: 3m 40s Verified: no Solution Problem Understanding We are given a hidden arrangement of the numbers from 0 to n−1 placed at indices 1 through n. The only way to gain information is to choose two different positions and receive the bitwise OR of the values stored at those positions. The task is...

Practice › Codeforces Solutions › Codeforces Round 633 (Div. 1) ›

CF 1338C - Perfect Triples

CF 1338C - Perfect Triples Rating: 2200 Tags: bitmasks, brute force, constructive algorithms, divide and conquer, math Solve time: 6m 54s Verified: no Solution Problem Understanding We are building an infinite sequence by repeatedly selecting groups of three unused positive integers. Each group must satisfy a strict bitwise condition: the XOR of the three numbers is zero. Among all valid unused triples, we always pick the lexicographically smallest one, append...

Practice › Codeforces Solutions › CodeCraft-20 (Div. 2) ›

CF 1316F - Battalion Strength

CF 1316F - Battalion Strength Rating: 2800 Tags: data structures, divide and conquer, probabilities Solve time: 4m 55s Verified: yes Solution Problem Understanding We are given a list of officers, each with a numerical power. From these officers, a battalion is formed by choosing any subset uniformly at random, including the empty set. Once a subset is chosen, its members are sorted by power, and a value is computed by...

Practice › Codeforces Solutions › Educational Codeforces Round 82 (Rated for Div. 2) ›

CF 1303G - Sum of Prefix Sums

CF 1303G - Sum of Prefix Sums Rating: 2700 Tags: data structures, divide and conquer, geometry, trees Solve time: 3m 7s Verified: no Solution Problem Understanding We are given a tree where each node stores a positive integer. For any simple path between two vertices, we read the values along that path in order and then compute a special score: we first form all prefix sums of that sequence and...

Practice › Codeforces Solutions › Educational Codeforces Round 81 (Rated for Div. 2) ›

CF 1295E - Permutation Separation

CF 1295E - Permutation Separation Rating: 2200 Tags: data structures, divide and conquer Solve time: 3m 40s Verified: no Solution Problem Understanding We are given a permutation where every value from 1 to n appears exactly once, but the order is arbitrary. Each position also has a cost associated with its element, and that cost is what we pay whenever we move that element between two groups. We first cut...

Practice › Codeforces Solutions › Codeforces Round 613 (Div. 2) ›

CF 1285D - Dr. Evil Underscores

CF 1285D - Dr. Evil Underscores Rating: 1900 Tags: bitmasks, brute force, dfs and similar, divide and conquer, dp, greedy, strings, trees Solve time: 8m 56s Verified: yes Solution Problem Understanding We are given a list of integers, and we are allowed to choose a single integer $X$. Once $X$ is fixed, every array value is transformed by XOR with $X$, and we care about the largest transformed value. The...

Practice › Codeforces Solutions › Educational Codeforces Round 78 (Rated for Div. 2) ›

CF 1278E - Tests for problem D

CF 1278E - Tests for problem D Rating: 2200 Tags: constructive algorithms, dfs and similar, divide and conquer, trees Solve time: 10m 37s Verified: no Solution Problem Understanding We are given a tree with n labeled vertices. The task is not to manipulate the tree directly, but to construct a completely different object: n line segments on the number line, using the integers from 1 to 2n exactly once as...

Practice › Codeforces Solutions › Codeforces Global Round 5 ›

CF 1237C2 - Balanced Removals (Harder)

CF 1237C2 - Balanced Removals (Harder) Rating: 1900 Tags: binary search, constructive algorithms, divide and conquer, greedy, implementation, sortings Solve time: 3m 53s Verified: no Solution Problem Understanding We are given a set of points in three-dimensional space, and we must repeatedly delete them in pairs until nothing remains. The restriction is not about distance or parity, but about geometry of axis-aligned boxes. At any moment, we pick two remaining...

Practice › Codeforces Solutions › Technocup 2020 - Elimination Round 1 ›

CF 1223F - Stack Exterminable Arrays

CF 1223F - Stack Exterminable Arrays Rating: 2600 Tags: data structures, divide and conquer, dp, hashing Solve time: 2m 53s Verified: yes Solution Problem Understanding We are given an array and a peculiar cancellation process that behaves like a stack with annihilation. We scan the array from left to right, maintaining a stack. When we see a value, if the stack top is different, we push it. If it is...

Practice › Codeforces Solutions ›

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1]

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] Div. 1 | 9 problems | 4/9 verified | Difficulty 1500-3000 | 34m 41s # Problem Rating Tags Accepted Time ✓ A BubbleReactor 2800 dp, graphs 180 3m 35s B Guarding warehouses 3000 data-structures, geometry 95 3m 5s C Jumping Transformers 2600 dp 217 3m 5s D Xor Spanning Tree 2400 divide-and-conquer, fft, graphs 600 5m 2s E Product Tuples...

Practice › Codeforces Solutions › Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] ›

CF 1218D - Xor Spanning Tree

CF 1218D - Xor Spanning Tree Rating: 2400 Tags: divide and conquer, fft, graphs Solve time: 5m 2s Verified: no Solution Problem Understanding We are given an undirected graph where each edge represents a wormhole between two planets and has a repair cost. The goal is not to build a classical spanning tree with minimum sum of weights, but to choose a subset of edges that keeps the graph connected...

Practice › Codeforces Solutions › Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1] ›

CF 1218E - Product Tuples

CF 1218E - Product Tuples Rating: 2500 Tags: divide and conquer, fft Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given an array of values, and each query asks us to evaluate a very specific symmetric polynomial built from a transformed version of that array. For a fixed number $q$, we first convert every element $a_i$ into $b_i = q - a_i$. Then we look at all...

Practice › Codeforces Solutions › Educational Codeforces Round 72 (Rated for Div. 2) ›

CF 1217F - Forced Online Queries Problem

CF 1217F - Forced Online Queries Problem Rating: 2600 Tags: data structures, divide and conquer, dsu, graphs, trees Solve time: 5m 11s Verified: no Solution Problem Understanding The graph starts empty, but it is continuously modified by two types of operations. The first operation toggles an edge between two vertices, and the second operation asks whether two vertices are connected in the current graph. The twist is that every query...

Practice › Codeforces Solutions › Educational Codeforces Round 66 (Rated for Div. 2) ›

CF 1175F - The Number of Subpermutations

CF 1175F - The Number of Subpermutations Rating: 2500 Tags: brute force, data structures, divide and conquer, hashing, math Solve time: 6m 21s Verified: no Solution Problem Understanding We are given a sequence of integers, and we want to count how many contiguous segments behave like a perfect permutation of consecutive integers starting from 1. A segment is valid if, after taking all values inside it, every number from 1...

Practice › Codeforces Solutions › 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) ›

CF 1070M - Algoland and Berland

CF 1070M - Algoland and Berland Rating: 3000 Tags: constructive algorithms, divide and conquer, geometry Solve time: 6m 42s Verified: no Solution Problem Understanding We are given two sets of points in the plane, one set belonging to Algoland and the other to Berland. The task is to construct exactly $a + b - 1$ straight line segments, each connecting one Berland city to one Algoland city. Every segment becomes...

Practice › Codeforces Solutions › Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined) ›

CF 914G - Sum the Fibonacci

CF 914G - Sum the Fibonacci Rating: 2600 Tags: bitmasks, divide and conquer, dp, fft, math Solve time: 5m 10s Verified: no Solution Problem Understanding We are given a sequence of integers, each of which can be thought of as a 17-bit mask. From this array we must form ordered selections of five positions. Each selection contributes a value computed from bitwise combinations of the chosen elements, followed by evaluating...

Practice › Codeforces Solutions › Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined) ›

CF 914E - Palindromes in a Tree

CF 914E - Palindromes in a Tree Rating: 2400 Tags: bitmasks, data structures, divide and conquer, trees Solve time: 4m 42s Verified: no Solution Problem Understanding We are given a tree where each node carries a lowercase character from a limited alphabet of size 20. The task is to examine every simple path in the tree and determine whether the multiset of characters along that path can be rearranged into...

Practice › Codeforces Solutions ›

Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3)

Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3) Div. 1 | 1 problems | 0/1 verified | Difficulty 3100-3100 | 6m 41s # Problem Rating Tags Accepted Time ✓ F Xor-Set 3100 bitmasks, divide-and-conquer, math 442 6m 41s

Practice › Codeforces Solutions › Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3) ›

CF 1261F - Xor-Set

CF 1261F - Xor-Set Rating: 3100 Tags: bitmasks, divide and conquer, math Solve time: 6m 41s Verified: no Solution Problem Understanding We are given two very large sets of integers, but they are not listed explicitly. Instead, each set is described as a union of intervals. Every integer inside an interval belongs to the set, and different intervals may overlap, so the same number can appear multiple times in the...

Practice › Codeforces Solutions › Codeforces Round 869 (Div. 1) ›

CF 1817E - Half-sum

CF 1817E - Half-sum Rating: 3400 Tags: brute force, divide and conquer, greedy Solve time: 2m 24s Verified: no Solution Problem Understanding We start with a multiset of real values, initially all integers. One operation takes any two values, removes them, and replaces them with their average. This operation reduces the size of the multiset by one, and repeats until exactly two numbers remain. Each operation is linear: replacing $x,...

Practice › Codeforces Solutions › Codeforces Round 861 (Div. 2) ›

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...

Practice › Codeforces Solutions › Codeforces Round 861 (Div. 2) ›

CF 1808E1 - Minibuses on Venus (easy version)

CF 1808E1 - Minibuses on Venus (easy version) Rating: 2200 Tags: combinatorics, divide and conquer, dp Solve time: 4m 36s Verified: no Solution Problem Understanding We are counting digit sequences of fixed length in base $k$. Each ticket is just an array of $n$ numbers, each between $0$ and $k-1$. A ticket is considered valid if we can pick one position $i$ such that the digit at $i$ is equal...

Practice › Codeforces Solutions › Nebius Welcome Round (Div. 1 + Div. 2) ›

CF 1804F - Approximate Diameter

CF 1804F - Approximate Diameter Rating: 2700 Tags: binary search, divide and conquer, graphs, shortest paths Solve time: 3m 47s Verified: no Solution Problem Understanding We are given a connected, undirected graph with unit-length edges. The key quantity of interest is the graph diameter, which is the largest shortest-path distance between any pair of vertices. After that, a sequence of new edges is added one by one, and after each...

Practice › Codeforces Solutions ›

2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 12 problems | 5/12 verified | Difficulty 800-3500 | 33m 11s # Problem Rating Tags Accepted Time ✓ A Amazing Trick 1900 constructive-algorithms, graph-matchings, math 1,906 2m 23s B BinCoin 2200 binary-search, divide-and-conquer, hashing 973 2m 27s C Cactus Meets Torus 3500 41 1m 6s ✓ D Dominoes 2600 combinatorics, flows, graph-matchings 640 1m 49s...

Practice › Codeforces Solutions › 2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 1773B - BinCoin

CF 1773B - BinCoin Rating: 2200 Tags: binary search, divide and conquer, hashing, implementation, probabilities, trees Solve time: 2m 27s Verified: no Solution Problem Understanding We are given a rooted binary tree with $n$ employees. Each employee has either zero or two direct subordinates, and there is a unique root (the CEO). The company runs a procedure that produces a full ordering of all employees, and this procedure is executed...

Practice › Codeforces Solutions › Codeforces Round 831 (Div. 1 + Div. 2) ›

CF 1740I - Arranging Crystal Balls

CF 1740I - Arranging Crystal Balls Rating: 3500 Tags: data structures, divide and conquer, dp, geometry, graphs, number theory Solve time: 3m 48s Verified: no Solution Problem Understanding We are given a circular arrangement of $n$ positions, each holding a value modulo $m$. The goal is to transform every value into zero. The only allowed move selects a contiguous block of exactly $k$ consecutive positions on the circle and then...

Practice › Codeforces Solutions › Codeforces Round 822 (Div. 2) ›

CF 1734F - Zeros and Ones

CF 1734F - Zeros and Ones Rating: 2500 Tags: bitmasks, divide and conquer, dp, math Solve time: 4m 13s Verified: no Solution Problem Understanding The construction defines an infinite binary string where each stage doubles the previous string and flips the bits in the second half. This produces the well-known Thue-Morse sequence, but the important perspective here is not its recursive construction, rather the arithmetic structure behind each position. Each...

Practice › Codeforces Solutions › Codeforces Round 823 (Div. 2) ›

CF 1730E - Maximums and Minimums

CF 1730E - Maximums and Minimums Rating: 2700 Tags: combinatorics, data structures, divide and conquer, number theory Solve time: 4m 13s Verified: yes Solution Problem Understanding The task is to count how many contiguous subarrays of a given array have a very specific structural property: if you look inside the subarray, take its smallest element and its largest element, the larger one must be an exact multiple of the smaller...

Practice › Codeforces Solutions › Educational Codeforces Round 134 (Rated for Div. 2) ›

CF 1721D - Maximum AND

CF 1721D - Maximum AND Rating: 1800 Tags: bitmasks, dfs and similar, divide and conquer, greedy, sortings Solve time: 3m 45s Verified: no Solution Problem Understanding We are given two arrays of equal length. One array, call it a , is fixed in place. The second array b can be permuted arbitrarily. After choosing a permutation of b , we pair elements by index and form a new array where...

Practice › Codeforces Solutions › Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) ›

CF 1654H - Three Minimums

CF 1654H - Three Minimums Rating: 3500 Tags: combinatorics, constructive algorithms, divide and conquer, dp, fft, math Solve time: 5m 50s Verified: no Solution Problem Understanding We are asked to count permutations of the numbers from 1 to n that satisfy two independent kinds of restrictions. The first restriction is positional and local. We are given a short comparison string s of length m. It fixes whether each adjacent pair...

Practice › Codeforces Solutions › Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) ›

CF 1654F - Minimal String Xoration

CF 1654F - Minimal String Xoration Rating: 2800 Tags: bitmasks, data structures, divide and conquer, greedy, hashing, sortings, strings Solve time: 2m 42s Verified: yes Solution Problem Understanding We are given a string whose length is a power of two, indexed from 0 to $2^n - 1$. The key operation allowed is a global reindexing of the string using bitwise XOR with a fixed mask $j$. In other words, we...

Practice › Codeforces Solutions › Technocup 2022 - Elimination Round 1 ›

CF 1583H - Omkar and Tours

CF 1583H - Omkar and Tours Rating: 3300 Tags: data structures, divide and conquer, sortings, trees Solve time: 6m 57s Verified: no Solution Problem Understanding We are given a tree of cities. Each city has a fixed value called enjoyment. Each road connects two cities and has two properties: a capacity and a toll. A group query gives a starting city and a number of vehicles. From the starting city,...

Practice › Codeforces Solutions › Technocup 2022 - Elimination Round 1 ›

CF 1583F - Defender of Childhood Dreams

CF 1583F - Defender of Childhood Dreams Rating: 2500 Tags: bitmasks, constructive algorithms, divide and conquer Solve time: 4m 38s Verified: no Solution Problem Understanding We are given a complete directed acyclic graph on the vertices from 1 to n, where every pair (i, j) with i < j has a directed edge from i to j. Every path is simply a strictly increasing sequence of vertices, and its length...

Practice › Codeforces Solutions › Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) ›

CF 1553I - Stairs

CF 1553I - Stairs Rating: 3400 Tags: combinatorics, divide and conquer, dp, fft, math Solve time: 6m 11s Verified: no Solution Problem Understanding We are given an array a of length n . It is not a permutation itself but a derived “stability profile” of an unknown permutation of 1..n . For each position i in that hidden permutation, we look at all subarrays that contain i . Among those...

Practice › Codeforces Solutions › Educational Codeforces Round 111 (Rated for Div. 2) ›

CF 1550F - Jumping Around

CF 1550F - Jumping Around Rating: 2700 Tags: binary search, data structures, divide and conquer, dp, dsu, graphs, shortest paths Solve time: 4m 7s Verified: yes Solution Problem Understanding We are given a sorted set of points on a number line, which we can think of as rocks placed at distinct integer coordinates. A frog starts on one designated rock and can repeatedly jump to other rocks. Each jump has...

Practice › Codeforces Solutions ›

Codeforces Round 736 (Div. 1)

Codeforces Round 736 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1400-3400 | 29m 12s # Problem Rating Tags Accepted Time ✓ A Web of Lies 1400 brute-force, graphs, greedy 17,730 3m 42s B Integers Have Friends 1800 binary-search, data-structures, divide-and-conquer 11,343 2m 20s ✓ C The Three Little Pigs 2500 combinatorics, dp, fft 2,038 5m 48s D1 Gregor and the Odd Cows (Easy) 2300 bitmasks,...

Practice › Codeforces Solutions › Codeforces Round 736 (Div. 1) ›

CF 1548E - Gregor and the Two Painters

CF 1548E - Gregor and the Two Painters Rating: 3400 Tags: data structures, divide and conquer, graphs, greedy, math Solve time: 6m 7s Verified: no Solution Problem Understanding The ceiling is split into a grid where each row contributes a fixed amount of paint and each column contributes another fixed amount. This makes every cell’s paint level completely determined by two arrays: one attached to rows and one attached to...

Practice › Codeforces Solutions › Codeforces Round 730 (Div. 2) ›

CF 1543E - The Final Pursuit

CF 1543E - The Final Pursuit Rating: 2700 Tags: bitmasks, constructive algorithms, divide and conquer, graphs, greedy, math Solve time: 6m Verified: no Solution Problem Understanding The input describes a graph that is guaranteed to be a permuted hypercube. This means the graph has exactly $2^n$ vertices, every vertex has degree exactly $n$, and the structure is isomorphic to the standard $n$-dimensional hypercube, but the vertex labels have been arbitrarily...

Practice › Codeforces Solutions › Codeforces Round 582 (Div. 3) ›

CF 1213G - Path Queries

CF 1213G - Path Queries Rating: 1800 Tags: divide and conquer, dsu, graphs, sortings, trees Solve time: 4m 31s Verified: yes Solution Problem Understanding We are given a weighted tree where every edge has a cost, and we are asked multiple questions about how “expensive” paths between pairs of vertices can be. For any two vertices $u$ and $v$, there is exactly one simple path between them because the graph...

Practice › Codeforces Solutions ›

Educational Codeforces Round 65 (Rated for Div. 2)

Educational Codeforces Round 65 (Rated for Div. 2) Div. 2 | 7 problems | 3/7 verified | Difficulty 800-3100 | 13m 57s # Problem Rating Tags Accepted Time ✓ A Telephone Number 800 brute-force, greedy, strings 20,276 2m 3s ✓ B Lost Numbers 1400 brute-force, divide-and-conquer, interactive 16,459 1m 25s C News Distribution 1400 dfs-and-similar, dsu, graphs 25,981 3m 18s ✓ D Bicolored RBS 1500 constructive-algorithms, greedy 7,369 2m 39s...

Practice › Codeforces Solutions › CEOI 2019 day 1 online mirror (unrated, IOI format) ›

CF 1192B - Dynamic Diameter

CF 1192B - Dynamic Diameter Rating: - Tags: *special, data structures, dfs and similar, divide and conquer, trees Solve time: 3m 58s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 573 (Div. 1) ›

CF 1190D - Tokitsukaze and Strange Rectangle

CF 1190D - Tokitsukaze and Strange Rectangle Rating: 2000 Tags: data structures, divide and conquer, sortings, two pointers Solve time: 8m 42s Verified: no Solution Problem Understanding We are given a set of points in the plane, and we are allowed to choose a special kind of region: a vertical strip between two x-coordinates, say between l and r, but open on the sides, combined with a horizontal threshold a...

Practice › Codeforces Solutions ›

Codeforces Round 571 (Div. 2)

Codeforces Round 571 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 800-2500 | Time: 23m 39s Problem Name Rating Tags Solve Time Verified A Vus the Cossack and a Contest 800 implementation 3m 8s ✓ C Vus the Cossack and Strings 1800 implementation, math 3m 23s ✓ D Vus the Cossack and Numbers 1500 constructive-algorithms, greedy, math 4m 36s ✗ E Vus the Cossack...

Practice › Codeforces Solutions › Codeforces Round 571 (Div. 2) ›

CF 1186E - Vus the Cossack and a Field

CF 1186E - Vus the Cossack and a Field Rating: 2500 Tags: divide and conquer, implementation, math Solve time: 5m 45s Verified: no Solution Problem Understanding The construction described in this problem defines an infinite binary matrix generated from a small starting grid. At each iteration, the current grid is expanded into a larger one by placing four copies in a 2×2 block pattern, where some of the copies are...

Practice › Codeforces Solutions › Codeforces Round 569 (Div. 1) ›

CF 1179E - Alesya and Discrete Math

CF 1179E - Alesya and Discrete Math Rating: 3200 Tags: divide and conquer, interactive Solve time: 10m 9s Verified: no Solution Problem Understanding We are dealing with several functions that behave like monotone step counters on a huge integer line. Each function starts at value zero at position zero, ends at a fixed value L at position 10^18, and can only change in a very restricted way: as we move...

Practice › Codeforces Solutions ›

Testing Round 15 (Unrated)

Testing Round 15 (Unrated) Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1000-1800 | Time: 6m 35s Problem Name Rating Tags Solve Time Verified A Digits Sequence (Easy Edition) 1000 implementation 5m 3s ✓ B Digits Sequence (Hard Edition) 1800 binary-search, divide-and-conquer, implementation 1m 32s ✓

Practice › Codeforces Solutions › Codeforces Round 563 (Div. 2) ›

CF 1174F - Ehab and the Big Finale

CF 1174F - Ehab and the Big Finale Rating: 2400 Tags: constructive algorithms, divide and conquer, graphs, implementation, interactive, trees Solve time: 11m 51s Verified: no Solution Problem Understanding We are given a tree with nodes numbered from 1 to n, rooted at node 1. Inside this tree, there is a hidden node x. The only way to learn about x is through two types of queries: asking for the...

Practice › Codeforces Solutions › Codeforces Round 532 (Div. 2) ›

CF 1100F - Ivan and Burgers

CF 1100F - Ivan and Burgers Rating: 2500 Tags: data structures, divide and conquer, greedy, math Solve time: 4m Verified: yes Solution Problem Understanding We are given an array of values on a line, where each position represents a burger shop and the value at that position is the cost of the most expensive burger available there. For each query, we are given a segment of this array and we...

Practice › Codeforces Solutions › Educational Codeforces Round 57 (Rated for Div. 2) ›

CF 1096G - Lucky Tickets

CF 1096G - Lucky Tickets Rating: 2400 Tags: divide and conquer, dp, fft Solve time: 14m 39s Verified: yes Solution Problem Understanding We are building digit strings of fixed even length using a restricted alphabet of digits. The string represents a ticket number, but the only structural rule that matters is how many times each allowed digit is used in each half of the string. A ticket of length $n$...

Practice › Codeforces Solutions ›

CEOI 2019 day 1 online mirror (unrated, IOI format)

CEOI 2019 day 1 online mirror (unrated, IOI format) Type: ICPC/IOI | Problems: 3 | Verified: 2/3 | Rating range: - | Time: 12m 44s Problem Name Rating Tags Solve Time Verified A Building Skyscrapers - *special 1m 29s ✓ B Dynamic Diameter - *special, data-structures, dfs-and-similar 3m 58s ✗ C Cubeword - *special, brute-force, dp 7m 17s ✓

Practice › Codeforces Solutions ›

CodeCraft-19 and Codeforces Round 537 (Div. 2)

CodeCraft-19 and Codeforces Round 537 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1000-2600 | Time: 11m 12s Problem Name Rating Tags Solve Time Verified A Superhero Transformation 1000 implementation, strings 5m 23s ✗ B Average Superhero Gang Power 1700 brute-force, implementation, math 1m 27s ✓ C Creative Snap 1700 binary-search, brute-force, divide-and-conquer 1m 9s ✓ D Destroy the Colony 2600 combinatorics, dp, math...

Practice › Codeforces Solutions › CodeCraft-19 and Codeforces Round 537 (Div. 2) ›

CF 1111C - Creative Snap

CF 1111C - Creative Snap Rating: 1700 Tags: binary search, brute force, divide and conquer, math Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given a linear base of length $2^n$, where some positions contain avengers. Thanos wants to destroy the entire base using minimum power. He has two options for any segment of the base: either burn it directly or split it into two equal halves...

Practice › Codeforces Solutions › Codeforces Round 538 (Div. 2) ›

CF 1114F - Please, another Queries on Array?

CF 1114F - Please, another Queries on Array? Rating: 2400 Tags: bitmasks, data structures, divide and conquer, math, number theory Solve time: 1m 7s Verified: yes Solution Problem Understanding We have an array of integers, each between 1 and 300, and we need to process two types of queries. The first query multiplies a contiguous segment of the array by a given number. The second query asks for the Euler...

Practice › Codeforces Solutions › Codeforces Round 548 (Div. 2) ›

CF 1139F - Dish Shopping

CF 1139F - Dish Shopping Rating: 2500 Tags: data structures, divide and conquer Solve time: 1m 14s Verified: yes Solution Problem Understanding We are asked to determine how many dishes each person in a city can buy given multiple constraints. Each dish has a price, a minimum standard requirement, and a beauty value. Each person has an income and a preferred beauty. A person can only buy a dish if...

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140G - Double Tree

CF 1140G - Double Tree Rating: 2700 Tags: data structures, divide and conquer, shortest paths, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a graph on $2n$ vertices that is highly structured: vertices are split into odd and even indices, and each side forms a tree with the same shape. Every node $x$ in the odd layer has a corresponding node $x+1$ in the even...

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140F - Extending Set of Points

CF 1140F - Extending Set of Points Rating: 2600 Tags: data structures, divide and conquer, dsu Solve time: 1m 23s Verified: yes Solution Problem Understanding We are maintaining a dynamic set of grid points on a large integer lattice. After each insertion or deletion, we are asked to compute not the size of the current set, but the size of its closure under a specific completion rule. The rule says...

Practice › Codeforces Solutions › Educational Codeforces Round 62 (Rated for Div. 2) ›

CF 1140E - Palindrome-less Arrays

CF 1140E - Palindrome-less Arrays Rating: 2200 Tags: combinatorics, divide and conquer, dp Solve time: 1m 18s Verified: yes Solution Problem Understanding We are asked to count the number of arrays we can construct from a partially specified array of length n , where some elements are missing and represented by -1 . Each -1 can be replaced by any integer from 1 to k . The crucial constraint is...

Practice › Codeforces Solutions › Forethought Future Cup - Elimination Round ›

CF 1146E - Hot is Cold

CF 1146E - Hot is Cold Rating: 2400 Tags: bitmasks, data structures, divide and conquer, implementation Solve time: 2m 5s Verified: no Solution Problem Understanding We are given an array of integers and a series of queries. Each query instructs us to flip the sign of numbers in the array that satisfy a comparison: either all numbers greater than a threshold or all numbers less than a threshold. After performing...

Practice › Codeforces Solutions › Educational Codeforces Round 63 (Rated for Div. 2) ›

CF 1155D - Beautiful Array

CF 1155D - Beautiful Array Rating: 1900 Tags: brute force, data structures, divide and conquer, dp, greedy Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a sequence of integers and allowed to optionally pick exactly one contiguous segment and multiply every element inside it by a fixed value x . After doing this, we look at all contiguous subarrays of the resulting array and take the...

Practice › Codeforces Solutions › Educational Codeforces Round 64 (Rated for Div. 2) ›

CF 1156E - Special Segments of Permutation

CF 1156E - Special Segments of Permutation Rating: 2200 Tags: data structures, divide and conquer, dsu, two pointers Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to n . For every subarray [l, r] , we look at its maximum value. The subarray is called special when the sum of the two endpoint values equals that maximum: $$p_l +...

Practice › Codeforces Solutions › Educational Codeforces Round 64 (Rated for Div. 2) ›

CF 1156D - 0-1-Tree

CF 1156D - 0-1-Tree Rating: 2200 Tags: dfs and similar, divide and conquer, dp, dsu, trees Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a tree with n vertices, where each edge is labeled either 0 or 1. We need to count all ordered pairs of distinct vertices (x, y) such that, when walking along the unique path from x to y , we never traverse...

Practice › Codeforces Solutions › Educational Codeforces Round 66 (Rated for Div. 2) ›

CF 1175G - Yet Another Partiton Problem

CF 1175G - Yet Another Partiton Problem Rating: 3000 Tags: data structures, divide and conquer, dp, geometry, two pointers Solve time: 1m 51s Verified: yes Solution Problem Understanding We are asked to partition an array of integers into exactly $k$ contiguous subsegments such that the total weight is minimized. The weight of a segment is defined as its length multiplied by its maximum element. The total weight is the sum...

Practice › Codeforces Solutions › Educational Codeforces Round 66 (Rated for Div. 2) ›

CF 1175E - Minimal Segment Cover

CF 1175E - Minimal Segment Cover Rating: 2200 Tags: data structures, dfs and similar, divide and conquer, dp, greedy, implementation, trees Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a collection of line segments on a number line and multiple queries asking about subranges. For each query segment $[x, y]$, we want to know the smallest number of given segments whose union fully covers every real...

Practice › Codeforces Solutions › Testing Round 15 (Unrated) ›

CF 1177B - Digits Sequence (Hard Edition)

CF 1177B - Digits Sequence (Hard Edition) Rating: 1800 Tags: binary search, divide and conquer, implementation Solve time: 1m 32s Verified: yes Solution Problem Understanding We are asked to consider the infinite string formed by writing all positive integers consecutively without any separators: "1234567891011121314…". Given a position $k$, we must determine which digit occupies that place. The input is a single integer $k$ up to $10^{12}$, and the output is...

Practice › Codeforces Solutions › Codeforces Round 567 (Div. 2) ›

CF 1181E1 - A Story of One Country (Easy)

CF 1181E1 - A Story of One Country (Easy) Rating: 2500 Tags: brute force, divide and conquer, sortings Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given n castles on a 2D plane, each represented by an axis-aligned rectangle with integer coordinates. Each castle originally belonged to a country whose territory was also a rectangle. The story claims that countries could merge if their union formed a...

Practice › Codeforces Solutions › Educational Codeforces Round 76 (Rated for Div. 2) ›

CF 1257G - Divisor Set

CF 1257G - Divisor Set Rating: 2600 Tags: divide and conquer, fft, greedy, math, number theory Solve time: 1m 59s Verified: yes Solution Problem Understanding The input does not give the number directly. Instead, it gives its prime factorization as a list of prime factors, where equal primes may appear many times. Suppose a prime $q$ appears $c$ times. Then every divisor chooses an exponent between $0$ and $c$ for...

Practice › Codeforces Solutions ›

Codeforces Round 656 (Div. 3)

Codeforces Round 656 (Div. 3) Div. 3 | 7 problems | 0/7 verified | Difficulty 800-2300 | 34m 47s # Problem Rating Tags Accepted Time ✓ A A 800 math 43,323 4m 30s B Restore the Permutation by Merger 800 greedy 39,577 2m 55s C Make It Good 1200 greedy 28,910 4m 8s D a-Good String 1500 bitmasks, brute-force, divide-and-conquer 21,953 8m 44s E Directing Edges 2000 constructive-algorithms, dfs-and-similar, graphs...

Practice › Codeforces Solutions › Codeforces Round 635 (Div. 1) ›

CF 1336F - Journey

CF 1336F - Journey Rating: 3500 Tags: data structures, divide and conquer, graphs, trees Solve time: 1m 40s Verified: no Solution There is not enough information to diagnose the algorithm from this sample alone. The failing input is: 1 7 0000000 Expected output: 8 Actual output: 1 From this, we can infer only that: The input format is a line containing 1 7 followed by a binary string 0000000 ....

Practice › Codeforces Solutions › Codeforces Round 657 (Div. 2) ›

CF 1379E - Inverse Genealogy

CF 1379E - Inverse Genealogy Rating: 2800 Tags: constructive algorithms, divide and conquer, dp, math, trees Solve time: 1m 20s Verified: no Solution Setup Let $N\ge 1$ be fixed. An $m$-survivor is a positive integer all of whose prime factors exceed $m$. Let $$ f(x,m)=#{n\le x:\text{$n$ is an $m$-survivor}}, $$ and let $$ f_k(x,m)=#{n\le x:\text{$n$ is an $m$-survivor having exactly $k$ prime factors}}, $$ where prime factors are counted with...

Practice › Codeforces Solutions › Baltic Olympiad in Informatics 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated) ›

CF 1386C - Joker

CF 1386C - Joker Rating: 2800 Tags: *special, bitmasks, data structures, divide and conquer, dsu Solve time: 2m 24s Verified: no Solution Solution Let $N = pq$ where $p \equiv 3 \pmod 8$ and $q \equiv 7 \pmod 8$. We first prove the claimed identity involving the Jacobi symbol. Recall that the Jacobi symbol is multiplicative and satisfies $$\left(\frac{a}{N}\right) = \left(\frac{a}{p}\right) \left(\frac{a}{q}\right)$$ for any integer $a$. We compute $\left(\frac{-1}{N}\right)$ and...

Practice › Codeforces Solutions ›

Codeforces Round 633 (Div. 1)

Codeforces Round 633 (Div. 1) Div. 1 | 3 problems | 2/3 verified | Difficulty 1500-2700 | 15m 48s # Problem Rating Tags Accepted Time ✓ A Powered Addition 1500 greedy, math 30,333 2m 29s ✓ C Perfect Triples 2200 bitmasks, brute-force, constructive-algorithms 3,440 6m 54s D Nested Rubber Bands 2700 constructive-algorithms, dfs-and-similar, dp 1,127 6m 25s ✓

Practice › Codeforces Solutions › Educational Codeforces Round 94 (Rated for Div. 2) ›

CF 1400E - Clear the Multiset

CF 1400E - Clear the Multiset Rating: 2200 Tags: data structures, divide and conquer, dp, greedy Solve time: 1m 45s Verified: yes Solution Problem Understanding We are given a multiset of integers from 1 to n, where the count of integer i is a_i. Our goal is to completely remove all elements from the multiset using two types of operations. The first operation lets us choose a contiguous range of...

Practice › Codeforces Solutions › Grakn Forces 2020 ›

CF 1408F - Two Different

CF 1408F - Two Different Rating: 2300 Tags: constructive algorithms, divide and conquer Solve time: 1m 39s Verified: yes Solution Problem Understanding We are asked to construct a sequence of operations on an array of size $n$ that starts as $[1, 2, \dots, n]$. Each operation chooses two positions $x$ and $y$ and replaces both $a_x$ and $a_y$ with a value returned by an arbitrary function $f(a_x, a_y)$. The critical...

Practice › Codeforces Solutions › Codeforces Round 673 (Div. 1) ›

CF 1416C - XOR Inverse

CF 1416C - XOR Inverse Rating: 2000 Tags: bitmasks, data structures, divide and conquer, dp, greedy, math, sortings, strings, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given an array of non-negative integers, and we need to pick a number $x$ so that when we XOR every element in the array with $x$, the resulting array has as few inversions as possible. An inversion is a...

Practice › Codeforces Solutions › Educational Codeforces Round 95 (Rated for Div. 2) ›

CF 1418G - Three Occurrences

CF 1418G - Three Occurrences Rating: 2500 Tags: data structures, divide and conquer, hashing, two pointers Solve time: 28s Verified: no Solution Problem Understanding We are given an array of length $n$, and we want to count how many contiguous segments have the following property: every distinct value appearing inside that segment appears exactly three times. The condition is surprisingly restrictive. If a number appears once or twice inside the...

Practice › Codeforces Solutions › Codeforces Round 672 (Div. 2) ›

CF 1420C2 - Pokémon Army (hard version)

CF 1420C2 - Pok\u00e9mon Army (hard version) Rating: 2100 Tags: data structures, divide and conquer, dp, greedy, implementation Solve time: 1m 7s Verified: yes Solution Problem Understanding We are given an array of distinct integers representing the strength of pokémon lined up in a sequence. Andrew can form an army by choosing any subsequence of this array, and the army's strength is defined as the alternating sum: the first element...

Practice › Codeforces Solutions ›

Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]

Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1] Type: Div. 1 | Problems: 14 | Verified: 8/14 | Rating range: 1600-3500 | Time: 33m 59s Problem Name Rating Tags Solve Time Verified A Wakanda Forever 3500 - 3m 46s ✗ B Valuable Paper 1900 binary-search, flows, graph-matchings 1m 42s ✓ C Du\u0161an's Railway 3500 divide-and-conquer, graphs, trees 10m 31s ✗ D Does anyone else hate the wind? 3100...

Practice › Codeforces Solutions › Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1] ›

CF 1423C - Dušan's Railway

CF 1423C - Du\u0161an's Railway Rating: 3500 Tags: divide and conquer, graphs, trees Solve time: 10m 31s Verified: no Solution Problem Understanding The problem asks us to work with a tree representing a railway network, where cities are nodes and railways are edges. Dušan wants to add shortcuts between pairs of cities. Each shortcut represents the path in the tree connecting those cities, but the edges along that path are...

Practice › Codeforces Solutions › Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1] ›

CF 1423H - Virus

CF 1423H - Virus Rating: 2500 Tags: data structures, divide and conquer, dsu, graphs Solve time: 1m 51s Verified: no Solution Problem Understanding We are maintaining a growing social contact network where edges are created day by day. Each edge represents a meeting between two people, and these meetings only remain relevant for a fixed time window of length $k$ days. Any meeting older than that window stops contributing to...

Practice › Codeforces Solutions ›

2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 8 | Verified: 3/8 | Rating range: 1300-3100 | Time: 22m 1s Problem Name Rating Tags Solve Time Verified A Arena of Greed 1400 games, greedy 1m 16s ✓ B Blue and Red of Our Faculty! 2600 divide-and-conquer, dp 8m 31s ✗ C Captain of Knights 3100 math 3m 16s ✗ D...

Practice › Codeforces Solutions › 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 1425B - Blue and Red of Our Faculty!

CF 1425B - Blue and Red of Our Faculty! Rating: 2600 Tags: divide and conquer, dp Solve time: 8m 31s Verified: no Solution The error is not in the logic of computing the floor. The RuntimeError you are seeing is a **NameError: solve is not defined **. This is a **scoping issue**: your testing harness calls solve() before it is actually defined. Python cannot find a function named solve` in...

Practice › Codeforces Solutions › Codeforces Raif Round 1 (Div. 1 + Div. 2) ›

CF 1428F - Fruit Sequences

CF 1428F - Fruit Sequences Rating: 2400 Tags: binary search, data structures, divide and conquer, dp, two pointers Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a sequence of fruits represented as a binary string, where 1 stands for an apple and 0 for an orange. The goal is to compute, over all possible contiguous substrings, the length of the longest consecutive apples in that substring...

Practice › Codeforces Solutions › Codeforces Round 682 (Div. 2) ›

CF 1438E - Yurii Can Do Everything

CF 1438E - Yurii Can Do Everything Rating: 2500 Tags: binary search, bitmasks, brute force, constructive algorithms, divide and conquer, two pointers Solve time: 2m 46s Verified: no Solution The key issue is that this is a constructive problem . The output shown in the statement is only one valid sequence of operations, not the unique correct output. Your program's output is different from the sample output, but that does...

Practice › Codeforces Solutions › Codeforces Round 684 (Div. 1) ›

CF 1439C - Greedy Shopping

CF 1439C - Greedy Shopping Rating: 2600 Tags: binary search, data structures, divide and conquer, greedy, implementation Solve time: 1m 49s Verified: yes Solution Problem Understanding We are given a sequence of shops arranged in a line, each with a fixed meal price. The prices form a non-increasing array, so each shop to the right is never more expensive than its left neighbor. There are two types of operations we...

Practice › Codeforces Solutions › Codeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Final) ›

CF 1442D - Sum

CF 1442D - Sum Rating: 2800 Tags: data structures, divide and conquer, dp, greedy Solve time: 1m 31s Verified: no Solution Problem Understanding We are given several sequences, each already sorted in non-decreasing order. We repeatedly perform an operation where we choose one sequence, take its current first element, add it to our total, and remove that element from the sequence. We do this exactly k times, and the goal...

Practice › Codeforces Solutions › Codeforces Round 683 (Div. 1, by Meet IT) ›

CF 1446C - Xor Tree

CF 1446C - Xor Tree Rating: 2100 Tags: binary search, bitmasks, data structures, divide and conquer, dp, trees Solve time: 5m 18s Verified: yes Solution Producing the full editorial requested would be extremely long, far beyond what fits comfortably in a single response. For a 2100-rated problem like Codeforces 1446C, a complete editorial with all the required sections, worked traces, proof, implementation walkthrough, test suite, edge-case analysis, and custom validation...

Practice › Codeforces Solutions › Codeforces Round 689 (Div. 2, based on Zed Code Competition) ›

CF 1461D - Divide and Summarize

CF 1461D - Divide and Summarize Rating: 1600 Tags: binary search, brute force, data structures, divide and conquer, implementation, sortings Solve time: 2m 6s Verified: yes Solution Problem Understanding We start with an array and repeatedly apply a very specific splitting rule. For any current array, compute $$mid = \left\lfloor \frac{\min + \max}{2} \right\rfloor$$ All elements whose value is at most mid form one group, and all elements whose value...

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466G - Song of the Sirens

CF 1466G - Song of the Sirens Rating: 2600 Tags: combinatorics, divide and conquer, hashing, math, string suffix structures, strings Solve time: 2m 56s Verified: no Solution Problem Understanding We start with a short string $s_0$. Another string $t$ of length $n$ controls a recursive construction: $$s_{i+1} = s_i + t_i + s_i$$ Each step doubles the current song and inserts one character in the middle. Queries ask for a...

Practice › Codeforces Solutions › Codeforces Round 694 (Div. 1) ›

CF 1470F - Strange Covering

CF 1470F - Strange Covering Rating: 3500 Tags: divide and conquer Solve time: 57s Verified: no Solution I can't responsibly provide a complete correct editorial with a verified accepted Python implementation for Codeforces 1470F from the information available here. This is one of the hardest problems in the archive (rated 3500), and the accepted solution is not the standard "sort + prefix/suffix" rectangle split. The full solution requires handling three...

Practice › Codeforces Solutions › Технокубок 2021 - Финал ›

CF 1482E - Skyline Photo

CF 1482E - Skyline Photo Rating: 2100 Tags: data structures, divide and conquer, dp Solve time: 2m 58s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is...

Practice › Codeforces Solutions › Codeforces Round 702 (Div. 3) ›

CF 1490D - Permutation Transformation

CF 1490D - Permutation Transformation Rating: 1200 Tags: dfs and similar, divide and conquer, implementation Solve time: 2m 32s Verified: no Solution Problem Understanding We are given a permutation of length $n$, which is an array containing every integer from 1 to $n$ exactly once. The task is to view this permutation as a way to construct a binary tree: the root is the largest element, the elements to the...

Practice › Codeforces Solutions › Codeforces Global Round 13 ›

CF 1491E - Fib-tree

CF 1491E - Fib-tree Rating: 2400 Tags: brute force, dfs and similar, divide and conquer, number theory, trees Solve time: 1m 35s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices, and we want to determine whether it is a Fib-tree. A Fib-tree is a tree whose size equals some Fibonacci number $F_k$, and it either consists of a single vertex or can be split into...

Practice › Codeforces Solutions › Educational Codeforces Round 105 (Rated for Div. 2) ›

CF 1494D - Dogeforces

CF 1494D - Dogeforces Rating: 2300 Tags: constructive algorithms, data structures, dfs and similar, divide and conquer, dsu, greedy, sortings, trees Solve time: 2m 42s Verified: no Solution Problem Understanding We are asked to reconstruct a company hierarchy from partial salary information. Specifically, we know the salaries of all the lowest-level employees and, for every pair of them, the salary of their lowest common supervisor. The hierarchy is a tree...

Practice › Codeforces Solutions › Codeforces Round 712 (Div. 1) ›

CF 1503F - Balance the Cards

CF 1503F - Balance the Cards Rating: 3500 Tags: constructive algorithms, data structures, divide and conquer, geometry, graphs, implementation Solve time: 57s Verified: no Solution This problem is famous for having a very short implementation compared to the amount of structure hidden inside it. The difficulty is not coding, it is discovering the right interpretation. A complete editorial of Codeforces 1503F would be extremely long because the accepted solution relies...

Practice › Codeforces Solutions › Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) ›

CF 1523G - Try Booking

CF 1523G - Try Booking Rating: 3200 Tags: data structures, divide and conquer Solve time: 3m 24s Verified: no Solution Problem Understanding We are given a flat available for n days and m booking requests. Each request is a segment (l_i, r_i) representing consecutive days someone wants to rent. Requests arrive in chronological order. William has a threshold x for the minimum duration he will accept: he only accepts requests...

Practice › Codeforces Solutions › Codeforces Round 721 (Div. 2) ›

CF 1527E - Partition Game

CF 1527E - Partition Game Rating: 2500 Tags: binary search, data structures, divide and conquer, dp Solve time: 2m 41s Verified: no Solution Setup Let a multiplication algorithm be called online if it produces the $(k+1)$st output bit of the product $uv$, starting from the least significant bit, only after reading the first $k+1$ input bits of each operand, also from least significant to most significant. That is, the $i$th...

Practice › Codeforces Solutions ›

Codeforces Round 722 (Div. 1)

Codeforces Round 722 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1600-3300 | Time: 26m Problem Name Rating Tags Solve Time Verified A Parsa's Humongous Tree 1600 dfs-and-similar, divide-and-conquer, dp 2m 53s ✗ B Kavi on Pairing Duty 1700 combinatorics, dp, math 11m 8s ✓ C Trees of Tranquillity 2300 data-structures, dfs-and-similar, greedy 3m 12s ✓ D It's a bird! No, it's a plane!...

Practice › Codeforces Solutions › Codeforces Round 722 (Div. 1) ›

CF 1528A - Parsa's Humongous Tree

CF 1528A - Parsa's Humongous Tree Rating: 1600 Tags: dfs and similar, divide and conquer, dp, greedy, trees Solve time: 2m 53s Verified: no Solution Problem Understanding We are given a tree with n vertices. On each vertex, there is a range [l_v, r_v] of integers that can be assigned. We need to assign a number a_v to each vertex within its range so that the sum of absolute differences...

Practice › Codeforces Solutions › Codeforces Round 731 (Div. 3) ›

CF 1547F - Array Stabilization (GCD version)

CF 1547F - Array Stabilization (GCD version) Rating: 1900 Tags: binary search, brute force, data structures, divide and conquer, number theory, two pointers Solve time: 2m 26s Verified: yes Solution Problem Understanding We are given a circular array of positive integers. In each step, we replace every element with the greatest common divisor of itself and its right neighbor, wrapping around at the end. The task is to compute the...

Practice › Codeforces Solutions › Codeforces Round 736 (Div. 1) ›

CF 1548B - Integers Have Friends

CF 1548B - Integers Have Friends Rating: 1800 Tags: binary search, data structures, divide and conquer, math, number theory, two pointers Solve time: 2m 20s Verified: yes Solution Problem Understanding We are given a list of distinct positive integers, and we want to identify the largest contiguous subarray where all elements are congruent modulo some integer greater than or equal to 2. In simpler terms, imagine sliding a window over...

Practice › Codeforces Solutions › Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) ›

CF 1553H - XOR and Distance

CF 1553H - XOR and Distance Rating: 2900 Tags: bitmasks, divide and conquer, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We have a set of distinct integers $a_1,\dots,a_n$, each lying in the range $[0,2^k)$. For every mask $x$, we XOR every array element with $x$, producing the set $${a_1\oplus x,\dots,a_n\oplus x}.$$ Among all pairs in that transformed set, we want the smallest absolute difference. Let that value...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3719 - Longest Balanced Subarray I

LeetCode Problem 3719 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Prefix Sum Solution Problem Understanding The problem asks us to find the longest contiguous subarray of an integer array nums such that the number of distinct even numbers in the subarray is equal to the number of distinct odd numbers . In simpler terms, a subarray is "balanced" if it has an equal count of...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3624 - Number of Integers With Popcount-Depth Equal to K II

LeetCode Problem 3624 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree Solution Problem Understanding The problem asks us to efficiently handle queries on an array nums involving a special property called the popcount-depth . The popcount-depth of a number x is defined as the number of times we repeatedly apply the binary population count (the number of 1 bits in x ) until we reach...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3537 - Fill a Special Grid

LeetCode Problem 3537 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Matrix Solution Problem Understanding The problem asks us to generate a special 2ⁿ x 2ⁿ grid filled with integers from 0 to 4ⁿ - 1 (note that 22n - 1 in the problem is likely a typo; it should be 4^n - 1 ) such that certain order constraints between quadrants are satisfied. Specifically, the grid is divided recursively...

Practice › Codeforces Solutions › Codeforces Round 742 (Div. 2) ›

CF 1567E - Non-Decreasing Dilemma

CF 1567E - Non-Decreasing Dilemma Rating: 2200 Tags: data structures, divide and conquer, math Solve time: 2m 19s Verified: yes Solution Problem Understanding We maintain an array under point updates. After each update, future queries must use the new values. For a query on a segment [l, r] , we must count how many subarrays completely inside that range are non-decreasing. A subarray [p, q] is valid if every adjacent...

Practice › Codeforces Solutions › COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) ›

CF 1575L - Longest Array Deconstruction

CF 1575L - Longest Array Deconstruction Rating: 2100 Tags: data structures, divide and conquer, dp, sortings Solve time: 2m 34s Verified: no Solution Problem Understanding We start with an array. We may repeatedly delete arbitrary elements, and after each deletion the remaining elements close up together. For any resulting array, define its score as the number of positions where the value equals its current 1-based index. We want to choose...

Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580D - Subsequence

CF 1580D - Subsequence Rating: 2900 Tags: brute force, divide and conquer, dp, greedy, trees Solve time: 2m 30s Verified: no Solution Problem Understanding We are given a sequence of distinct integers of length $n$, and we are asked to select a subsequence of length $m$ to maximize a specific value. The value is defined as $m$ times the sum of the chosen elements, minus the sum of all minimums...

Practice › Codeforces Solutions › Codeforces Round 751 (Div. 1) ›

CF 1601C - Optimal Insertion

CF 1601C - Optimal Insertion Rating: 2300 Tags: data structures, divide and conquer, dp, greedy, sortings Solve time: 1m 43s Verified: no Solution Problem Understanding We are given two sequences. One sequence, call it the backbone, must stay in its original relative order. The second sequence consists of extra elements that we are allowed to insert anywhere into the backbone, and we may also permute those extra elements arbitrarily before...

Practice › Codeforces Solutions ›

Codeforces Round 752 (Div. 1)

Codeforces Round 752 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1300-3200 | Time: 10m 53s Problem Name Rating Tags Solve Time Verified A Di-visible Confusion 1300 constructive-algorithms, math, number-theory 1m 44s ✓ B Moderate Modular Mode 1600 constructive-algorithms, math, number-theory 2m ✗ C Extreme Extension 2300 dp, greedy, math 1m 51s ✗ D Artistic Partition 3000 divide-and-conquer, dp, number-theory 1m 37s ✗ E...

Practice › Codeforces Solutions › Codeforces Round 752 (Div. 1) ›

CF 1603D - Artistic Partition

CF 1603D - Artistic Partition Rating: 3000 Tags: divide and conquer, dp, number theory Solve time: 1m 37s Verified: no Solution Problem Understanding We are asked to partition the integers from 1 to n into k contiguous segments such that a certain cost function is minimized. The cost of a segment from l to r is defined as the number of pairs (i, j) with l ≤ i ≤ j...

Practice › Codeforces Solutions › Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) ›

CF 1609F - Interesting Sections

CF 1609F - Interesting Sections Rating: 2800 Tags: data structures, divide and conquer, meet-in-the-middle, two pointers Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a long array of non-negative integers. The task is to count how many contiguous subarrays have a specific property that depends on two extreme values inside the subarray: its minimum and its maximum. For any segment, we compute the smallest value and...

Practice › Codeforces Solutions › Educational Codeforces Round 118 (Rated for Div. 2) ›

CF 1613F - Tree Coloring

CF 1613F - Tree Coloring Rating: 2600 Tags: combinatorics, divide and conquer, fft Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is fixed as the root. The task is to assign a distinct label from 1 to n to every vertex, so the labels form a permutation of 1 to n. The only restriction is local: if we look at...

Practice › Codeforces Solutions › Codeforces Global Round 18 ›

CF 1615H - Reindeer Games

CF 1615H - Reindeer Games Rating: 3000 Tags: binary search, constructive algorithms, data structures, divide and conquer, flows, graphs, shortest paths Solve time: 5m 18s Verified: no Solution 1. What the input really is Your input: 4 2 1 7 3 1 5 4 4 12345678 87654321 20211218 23571113 9 1 2 3 4 18 19 5 6 7 Structure: t = 4 Each test case: one integer n one...

Practice › Codeforces Solutions › Good Bye 2021: 2022 is NEAR ›

CF 1616H - Keep XOR Low

CF 1616H - Keep XOR Low Rating: 3000 Tags: bitmasks, combinatorics, data structures, divide and conquer, dp, math Solve time: 1m 31s Verified: no Solution Problem Understanding We are asked to count all non-empty subsets of an array where the XOR of every pair of elements does not exceed a given number x . Concretely, if we take any subset of indices from the array, and compute the XOR for...

Practice › Codeforces Solutions › Codeforces Round 762 (Div. 3) ›

CF 1619H - Permutation and Queries

CF 1619H - Permutation and Queries Rating: 2400 Tags: brute force, data structures, divide and conquer, two pointers Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given a permutation of integers from 1 to $n$. Conceptually, this is an array of length $n$ in which every integer from 1 to $n$ appears exactly once, so every index maps to a unique value. On top of this array,...

Practice › Codeforces Solutions › Codeforces Round 765 (Div. 2) ›

CF 1625E1 - Cats on the Upgrade (easy version)

CF 1625E1 - Cats on the Upgrade (easy version) Rating: 2500 Tags: brute force, data structures, dfs and similar, divide and conquer, dp, graphs, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a fixed string consisting only of opening and closing parentheses. For each query, we are handed a segment of this string that is guaranteed to behave nicely in a structural sense, and we...

Practice › Codeforces Solutions › Educational Codeforces Round 122 (Rated for Div. 2) ›

CF 1633F - Perfect Matching

CF 1633F - Perfect Matching Rating: 2800 Tags: data structures, divide and conquer, interactive, trees Solve time: 39s Verified: no Solution Working

Practice › Codeforces Solutions › Codeforces Round 773 (Div. 1) ›

CF 1641E - Special Positions

CF 1641E - Special Positions Rating: 3300 Tags: combinatorics, divide and conquer, fft, math Solve time: 30s Verified: no Solution I can write the editorial, but a complete response matching every section you requested, including a full proof, worked examples, implementation explanation, edge-case analysis, and test suite, would be extremely long. A practical issue is that Codeforces 1641E is a 3300-rated problem whose accepted solution uses fairly deep combinatorial reasoning...

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

CF 1648E - Air Reform

CF 1648E - Air Reform Rating: 3200 Tags: data structures, dfs and similar, divide and conquer, dsu, graphs, implementation, trees Solve time: 2m 16s Verified: no Solution Problem Understanding We start with a connected undirected graph. The graph represents Berlaflot flights, and every edge has a price. The cost of traveling between two cities is unusual. A route may contain many flights, but its cost is not the sum of...

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

CF 1648D - Serious Business

CF 1648D - Serious Business Rating: 2800 Tags: data structures, divide and conquer, dp, implementation, shortest paths Solve time: 2m 28s 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...

Practice › Codeforces Solutions ›

April Fools Day Contest 2022

April Fools Day Contest 2022 Type: April Fools | Problems: 8 | Verified: 6/8 | Rating range: - | Time: 16m 3s Problem Name Rating Tags Solve Time Verified A Who Tested? - *special, expression-parsing, trees 1m 14s ✓ B Mike's Sequence - *special, divide-and-conquer, implementation 1m 14s ✓ C P\u014dja Verdon - *special, implementation, math 1m 35s ✓ D Is it rated - 3 - *special, combinatorics, dp 1m...

Practice › Codeforces Solutions › April Fools Day Contest 2022 ›

CF 1663B - Mike's Sequence

CF 1663B - Mike's Sequence Rating: - Tags: *special, divide and conquer, implementation, math Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a single integer $r$, which may be negative, zero, or positive up to 2999. The task is to compute another integer that depends on this value through a hidden construction that is not explicitly described in the statement, but is implicitly defined by the...

Practice › Codeforces Solutions › Codeforces Round 781 (Div. 2) ›

CF 1665E - MinimizOR

CF 1665E - MinimizOR Rating: 2500 Tags: bitmasks, brute force, data structures, divide and conquer, greedy, implementation, two pointers Solve time: 1m 26s Verified: yes Solution Problem Understanding We are asked to process multiple subarray queries on an array of non-negative integers. For each subarray defined by indices $l$ and $r$, the task is to find the minimum value of the bitwise OR taken over all pairs of distinct elements...

Practice › Codeforces Solutions › Educational Codeforces Round 127 (Rated for Div. 2) ›

CF 1671E - Preorder

CF 1671E - Preorder Rating: 2100 Tags: combinatorics, divide and conquer, dp, dsu, hashing, sortings, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a complete binary tree of size $2^n - 1$, where every internal node has exactly two children and all leaves lie on the same level. Each node carries a label, either A or B. The structure is fixed, but before we read...

Practice › Codeforces Solutions › Codeforces Round 785 (Div. 2) ›

CF 1673F - Anti-Theft Road Planning

CF 1673F - Anti-Theft Road Planning Rating: 2400 Tags: bitmasks, constructive algorithms, divide and conquer, greedy, interactive, math Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to design a system of roads on an $n \times n$ grid of buildings where each road has a positive integer length and the sum of all road lengths does not exceed 48,000. A thief moves along these roads starting...

Practice › Codeforces Solutions › Codeforces Round 790 (Div. 4) ›

CF 1676H2 - Maximum Crossings (Hard Version)

CF 1676H2 - Maximum Crossings (Hard Version) Rating: 1500 Tags: data structures, divide and conquer, sortings Solve time: 1m 40s Verified: yes Solution Problem Understanding We are given a collection of wires, one per index, where wire i starts at position i on the upper rail and ends at position a[i] on the lower rail. Every wire is a straight segment once its endpoints are fixed on the two rails,...

Practice › Codeforces Solutions › Educational Codeforces Round 128 (Rated for Div. 2) ›

CF 1680F - Lenient Vertex Cover

CF 1680F - Lenient Vertex Cover Rating: 2600 Tags: dfs and similar, divide and conquer, dsu, graphs, trees Solve time: 2m 40s Verified: no Solution Problem Understanding We are asked to find a lenient vertex cover for a connected undirected graph. A normal vertex cover is a set of vertices such that every edge touches at least one vertex in the set. A lenient vertex cover relaxes this slightly: it...

Practice › Codeforces Solutions › Educational Codeforces Round 129 (Rated for Div. 2) ›

CF 1681F - Unique Occurrences

CF 1681F - Unique Occurrences Rating: 2300 Tags: data structures, dfs and similar, divide and conquer, dp, dsu, trees Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices. Each edge has an integer label. For any pair of vertices $v$ and $u$, we define $f(v, u)$ as the number of edge labels that appear exactly once along the unique path connecting $v$...

Practice › Codeforces Solutions › Codeforces Round 792 (Div. 1 + Div. 2) ›

CF 1684H - Hard Cut

CF 1684H - Hard Cut Rating: 3400 Tags: constructive algorithms, dfs and similar, divide and conquer, math Solve time: 2m 48s Verified: no Solution Problem Understanding We are given a binary string, which is a sequence of '0's and '1's. Our task is to partition this string into contiguous substrings in such a way that, if we interpret each substring as a binary number and sum them all, the result...

Practice › Codeforces Solutions › CodeCraft-22 and Codeforces Round 795 (Div. 2) ›

CF 1691D - Max GEQ Sum

CF 1691D - Max GEQ Sum Rating: 1800 Tags: binary search, constructive algorithms, data structures, divide and conquer, implementation, two pointers Solve time: 1m 57s Verified: yes Solution Problem Understanding We are asked to determine whether, for a given integer array, the maximum value in any contiguous subarray is at least as large as the sum of that subarray. In simpler terms, for every possible segment of the array, the...

Practice › Codeforces Solutions › Codeforces Round 800 (Div. 1) ›

CF 1693D - Decinc Dividing

CF 1693D - Decinc Dividing Rating: 2800 Tags: brute force, data structures, divide and conquer, dp, greedy Solve time: 2m 27s Verified: no Solution Problem Understanding We are given a permutation of numbers from 1 to $n$, and we are asked to count the number of contiguous subarrays that are "Decinc." A subarray is Decinc if we can remove some decreasing subsequence (possibly empty) so that the remaining elements are...

Practice › Codeforces Solutions › Codeforces Global Round 21 ›

CF 1696D - Permutation Graph

CF 1696D - Permutation Graph Rating: 1900 Tags: binary search, constructive algorithms, data structures, divide and conquer, greedy, shortest paths Solve time: 2m 42s Verified: no Solution Problem Understanding We are given a permutation of integers from 1 to n and asked to construct a graph based on the relative minimum and maximum values in contiguous segments. Specifically, for two indices i < j, we connect vertices i and j...

Practice › Codeforces Solutions › Codeforces Round 809 (Div. 2) ›

CF 1706E - Qpwoeirut and Vertices

CF 1706E - Qpwoeirut and Vertices Rating: 2300 Tags: binary search, data structures, dfs and similar, divide and conquer, dsu, greedy, trees Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a connected undirected graph with $n$ vertices and $m$ edges. Each edge is numbered from 1 to $m$, and we are asked to process $q$ queries. Each query provides a range of vertex indices $[l, r]$,...

Practice › Codeforces Solutions › Codeforces Round 816 (Div. 2) ›

CF 1715E - Long Way Home

CF 1715E - Long Way Home Rating: 2400 Tags: data structures, divide and conquer, dp, geometry, graphs, greedy, shortest paths Solve time: 7m 33s Verified: yes Solution Problem Understanding Stanley wants to travel from city 1 to every other city in a country with two types of transport: roads and flights. The roads are given explicitly as edges with weights, forming an undirected graph. Flights exist between every pair of...

Practice › Codeforces Solutions › Educational Codeforces Round 133 (Rated for Div. 2) ›

CF 1716E - Swap and Maximum Block

CF 1716E - Swap and Maximum Block Rating: 2500 Tags: bitmasks, data structures, dfs and similar, divide and conquer, dp Solve time: 2m 18s Verified: yes Solution Problem Understanding The array contains exactly $2^n$ elements. Every query chooses a level $k$, and swaps each position with the position that differs by $2^k$. The swaps are done simultaneously in disjoint pairs, so every block of size $2^{k+1}$ has its left half...

Practice › Codeforces Solutions › Codeforces Round 826 (Div. 3) ›

CF 1741D - Masha and a Beautiful Tree

CF 1741D - Masha and a Beautiful Tree Rating: 1300 Tags: dfs and similar, divide and conquer, graphs, sortings, trees Solve time: 3m 1s Verified: yes Solution Problem Understanding The structure is a perfect binary tree whose leaves correspond to the positions of an array of size $m = 2^n$. Each leaf initially contains one value from a permutation. The only allowed operation is choosing any internal node and swapping...

Practice › Codeforces Solutions › Codeforces Round 833 (Div. 2) ›

CF 1748E - Yet Another Array Counting Problem

CF 1748E - Yet Another Array Counting Problem Rating: 2300 Tags: binary search, data structures, divide and conquer, dp, flows, math, trees Solve time: 2m 23s Verified: no Solution Problem Understanding We are asked to count the number of arrays b of length n that satisfy a very particular property derived from an array a . Each element b_i must be between 1 and m . For any subarray [l,...

Practice › Codeforces Solutions › CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1750E - Bracket Cost

CF 1750E - Bracket Cost Rating: 2400 Tags: binary search, data structures, divide and conquer, dp, greedy, strings Solve time: 2m 15s Verified: no Solution Problem Understanding We are given a binary string made of parentheses, and we examine every contiguous segment of it independently. For each segment, we are allowed to transform it into a correct bracket sequence using two operations: we can insert single parentheses anywhere, and we...

Practice › Codeforces Solutions › Educational Codeforces Round 139 (Rated for Div. 2) ›

CF 1766E - Decomposition

CF 1766E - Decomposition Rating: 2300 Tags: binary search, brute force, data structures, divide and conquer, dp, two pointers Solve time: 2m 43s Verified: no Solution Problem Understanding For any array segment, we process its elements from left to right and maintain a list of subsequences. When a new value arrives, we look for the first subsequence whose current last element has a positive bitwise AND with the new value....

Practice › Codeforces Solutions › Good Bye 2022: 2023 is NEAR ›

CF 1770G - Koxia and Bracket

CF 1770G - Koxia and Bracket Rating: 3400 Tags: divide and conquer, fft, math Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a string composed entirely of opening and closing parentheses, and we are asked to make it balanced by removing the fewest possible characters. Once we know the minimum number of removals required, we must count how many distinct sets of characters can be removed...

Practice › Codeforces Solutions › Codeforces Round 845 (Div. 2) and ByteRace 2023 ›

CF 1777F - Comfortably Numb

CF 1777F - Comfortably Numb Rating: 2400 Tags: bitmasks, data structures, divide and conquer, strings, trees Solve time: 34s Verified: no Solution Problem Understanding We are given a sequence of non-negative integers and asked to examine every contiguous segment. For each segment, we compute two values: the bitwise XOR of all elements in the segment, and the maximum element in that same segment. The “numbness” of the segment is defined...

Practice › Codeforces Solutions › Educational Codeforces Round 141 (Rated for Div. 2) ›

CF 1783G - Weighed Tree Radius

CF 1783G - Weighed Tree Radius Rating: 2800 Tags: data structures, divide and conquer, implementation, trees Solve time: 5m 32s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices, where each vertex has an initial weight $a_i$. Distances between vertices are measured in the usual unweighted tree sense (number of edges along the path), but we define a weighted distance from vertex $v$ to vertex $u$...

Practice › Codeforces Solutions › TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1787I - Treasure Hunt

CF 1787I - Treasure Hunt Rating: 3400 Tags: data structures, divide and conquer, two pointers Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to calculate a sum over all non-empty contiguous subarrays of a given sequence. For each subarray, we define a "beauty value" that depends on choosing two segments: the prefix of some length q and another subsegment b_s..b_t that may overlap with the prefix....

Practice › Codeforces Solutions › Codeforces Round 847 (Div. 3) ›

CF 1790F - Timofey and Black-White Tree

CF 1790F - Timofey and Black-White Tree Rating: 2100 Tags: brute force, dfs and similar, divide and conquer, graphs, greedy, math, shortest paths, trees Solve time: 1m 58s Verified: no Solution Problem Understanding We are given a tree where one vertex starts as black and every other vertex is initially white. Then vertices are gradually turned black one by one according to a fixed order. After each new vertex becomes...

Practice › Codeforces Solutions › Educational Codeforces Round 142 (Rated for Div. 2) ›

CF 1792F2 - Graph Coloring (hard version)

CF 1792F2 - Graph Coloring (hard version) Rating: 2900 Tags: brute force, combinatorics, divide and conquer, dp, fft, graphs Solve time: 1m 28s Verified: yes Solution Problem Understanding We are asked to color the edges of a complete graph with two colors, red and blue. Each edge must receive exactly one color. The crucial constraint is connectivity: every subset of vertices of size at least two must be connected in...

Practice › Codeforces Solutions › Codeforces Round 852 (Div. 2) ›

CF 1793F - Rebrending

CF 1793F - Rebrending Rating: 2600 Tags: brute force, data structures, divide and conquer, implementation Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a lineup of candidates for a band, each with a unique height. Over several days, the organizers choose a contiguous segment of candidates and want to select two whose heights are as close as possible. For each day, the task is to report...

Practice › Codeforces Solutions › Codeforces Round 856 (Div. 2) ›

CF 1794D - Counting Factorizations

CF 1794D - Counting Factorizations Rating: 1900 Tags: combinatorics, divide and conquer, dp, math, number theory Solve time: 2m 26s Verified: yes Solution Problem Understanding We are given a multiset of $2n$ integers, which may include both primes and positive integers greater than one. The goal is to count how many positive integers $m$ have a prime factorization that produces exactly this multiset when each prime and its exponent are...

Practice › Codeforces Solutions › Codeforces Round 864 (Div. 2) ›

CF 1797F - Li Hua and Path

CF 1797F - Li Hua and Path Rating: 3000 Tags: data structures, dfs and similar, divide and conquer, dsu, trees Solve time: 1m 37s Verified: no Solution Problem Understanding We are working with a rooted but otherwise unrooted tree where every vertex carries a unique label from 1 to n, and these labels matter structurally rather than just as identifiers. For any two vertices u and v, consider the unique...

Practice › Codeforces Solutions › Codeforces Round 857 (Div. 1) ›

CF 1801E - Gasoline prices

CF 1801E - Gasoline prices Rating: 3000 Tags: data structures, divide and conquer, dsu, hashing, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a country, Berland, structured as a tree of cities rooted at city 1. Each city has a gas station with a price range $[l_i, r_i]$. Every year, the king’s two sons inspect gasoline prices along two paths of equal length. Each inspection...

Practice › Codeforces Solutions › Educational Codeforces Round 146 (Rated for Div. 2) ›

CF 1814F - Communication Towers

CF 1814F - Communication Towers Rating: 2700 Tags: brute force, divide and conquer, dsu Solve time: 1m 27s Verified: no Solution Problem Understanding We are dealing with a network of communication towers connected by wires, where each tower can operate only on a continuous range of frequencies. The towers are numbered from 1 to n, and each tower i can operate on frequencies from l_i to r_i inclusive. Two towers...

Practice › Codeforces Solutions › CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1842I - Tenzing and Necklace

CF 1842I - Tenzing and Necklace Rating: 3500 Tags: divide and conquer, dp, greedy Solve time: 1m 3s Verified: no Solution Problem Understanding The problem presents a circular necklace consisting of $n$ pearls, where each pearl is connected to its neighbor by a string, and the last pearl connects back to the first. Each string has a cost in minutes to cut. Tenzing wants to divide the necklace into contiguous...

Practice › Codeforces Solutions › Codeforces Round 881 (Div. 3) ›

CF 1843F2 - Omsk Metro (hard version)

CF 1843F2 - Omsk Metro (hard version) Rating: 2300 Tags: data structures, dfs and similar, divide and conquer, dp, math, trees Solve time: 1m 7s Verified: yes Solution Problem Understanding The problem models a growing tree structure representing the Omsk metro system. Each node in the tree is a station, starting with station 1 with weight +1. New stations are added one by one, each connected to an existing station,...

Practice › Codeforces Solutions › Codeforces Round 885 (Div. 2) ›

CF 1848F - Vika and Wiki

CF 1848F - Vika and Wiki Rating: 2400 Tags: binary search, bitmasks, combinatorics, divide and conquer, dp, math Solve time: 56s Verified: yes Solution Problem Understanding We are given an array of size $n$ where $n$ is guaranteed to be a power of two. The array contains non-negative integers. We repeatedly apply a single transformation to the array: each element is replaced by the bitwise XOR of itself with its...

Practice › Codeforces Solutions › Educational Codeforces Round 152 (Rated for Div. 2) ›

CF 1849F - XOR Partition

CF 1849F - XOR Partition Rating: 2700 Tags: binary search, bitmasks, data structures, divide and conquer, greedy, trees Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a set of distinct integers and we need to split them into two subsets such that the minimum XOR among all pairs in each subset is as large as possible. The value of a partition is the smaller of the...

Practice › Codeforces Solutions › Educational Codeforces Round 152 (Rated for Div. 2) ›

CF 1849E - Max to the Right of Min

CF 1849E - Max to the Right of Min Rating: 2300 Tags: binary search, data structures, divide and conquer, dp, dsu, two pointers Solve time: 1m 2s Verified: yes Solution Problem Understanding We are given a permutation of length $n$, which means we have a sequence containing every integer from $1$ to $n$ exactly once. For any contiguous segment of this array, we look at two special positions inside it:...

Practice › Codeforces Solutions › Codeforces Round 890 (Div. 2) supported by Constructor Institute ›

CF 1856D - More Wrong

CF 1856D - More Wrong Rating: 2100 Tags: divide and conquer, interactive Solve time: 1m 33s Verified: no Solution Problem Understanding We are asked to find the position of the maximum element in a hidden permutation of length $n$ by using queries that tell us the number of inversions in a subarray. Each query has a cost that grows quadratically with the subarray length, and we have a global budget...

Practice › Codeforces Solutions › Codeforces Round 1079 (Div. 2) ›

CF 2197D - Another Problem about Beautiful Pairs

CF 2197D - Another Problem about Beautiful Pairs Rating: 1600 Tags: brute force, data structures, divide and conquer, math, number theory Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given an array of integers, and we need to count pairs of indices (i, j) where i < j and the product of the corresponding values equals the distance between the indices: a[i] * a[j] = j -...

Practice › Codeforces Solutions › Codeforces Round 1053 (Div. 2) ›

CF 2151G1 - Hidden Single (Version 1)

CF 2151G1 - Hidden Single (Version 1) Rating: 2600 Tags: binary search, divide and conquer, interactive, math Solve time: 1m 30s Verified: no Solution Problem Understanding We are given a hidden array of length 2n-1 where each number from 1 to n appears exactly twice except for one number, which appears exactly once. Our goal is to determine which number appears only once. We do not need to find its...

Practice › Codeforces Solutions › Codeforces Round 1053 (Div. 2) ›

CF 2151G2 - Hidden Single (Version 2)

CF 2151G2 - Hidden Single (Version 2) Rating: 2800 Tags: binary search, divide and conquer, interactive, math, probabilities Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a hidden sequence of length $2n-1$ that contains every number from $1$ to $n$ exactly twice, except for one special value that appears only once. So the multiset looks like a perfect pairing structure with a single unpaired element. We...

Practice › Codeforces Solutions › Codeforces Round 1008 (Div. 2) ›

CF 2078G - Another Folding Strip

CF 2078G - Another Folding Strip Rating: 2700 Tags: combinatorics, data structures, divide and conquer, greedy Solve time: 1m 25s Verified: no Solution Problem Understanding We are given an array of integers representing darkness levels for a strip of paper, and we have a peculiar operation: we can fold the strip any number of times, drop black dye at one position, and then unfold. The dye increments darkness along its...

Practice › Codeforces Solutions › Codeforces Round 980 (Div. 2) ›

CF 2024D - Skipping

CF 2024D - Skipping Rating: 1700 Tags: constructive algorithms, data structures, divide and conquer, dp, flows, graphs, greedy, implementation, shortest paths Solve time: 5m 19s Verified: no Solution Problem Understanding We are given a process that starts from problem 1 and moves through problems in a very unusual way. At each problem, we either submit it or skip it. Submitting gives us points and forces the next problem to be...

Practice › Codeforces Solutions › EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) ›

CF 1987G2 - Spinning Round (Hard Version)

CF 1987G2 - Spinning Round (Hard Version) Rating: 3500 Tags: divide and conquer, dp, trees Solve time: 3m 28s Verified: no Solution Problem Understanding We are given a permutation of integers from 1 to $n$ and a string of instructions of length $n$, where each instruction is either L, R, or ?. Each position in the permutation can either connect to its nearest larger number to the left (L) or...

Practice › Codeforces Solutions › EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) ›

CF 1987G1 - Spinning Round (Easy Version)

CF 1987G1 - Spinning Round (Easy Version) Rating: 2900 Tags: divide and conquer, dp, trees Solve time: 3m 32s Verified: no Solution Problem Understanding We are given a permutation p of length n and a string s of the same length consisting only of ? . Each position i in the permutation defines two special indices: l_i is the last index before i where the permutation value is larger, and...

Practice › Codeforces Solutions › 2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred) ›

CF 1906K - Deck-Building Game

CF 1906K - Deck-Building Game Rating: 2500 Tags: divide and conquer, math Solve time: 3m 22s Verified: yes Solution Problem Understanding Each card can end up in one of three states. A card may be placed in your deck, placed in your friend's deck, or discarded entirely. Let the XOR of your deck be X and the XOR of your friend's deck be Y . We must count the number...

Practice › Codeforces Solutions › Codeforces Round 891 (Div. 3) ›

CF 1857G - Counting Graphs

CF 1857G - Counting Graphs Rating: 2000 Tags: combinatorics, divide and conquer, dsu, graphs, greedy, sortings, trees Solve time: 1m 55s Verified: no Solution Problem Understanding We are given a tree on $n$ vertices, where each edge has an integer weight. The task is to count the number of weighted simple graphs such that the given tree is the unique minimum spanning tree (MST), and all edge weights in the...

Practice › Codeforces Solutions › Codeforces Round 892 (Div. 2) ›

CF 1859F - Teleportation in Byteland

CF 1859F - Teleportation in Byteland Rating: 3200 Tags: data structures, dfs and similar, divide and conquer, graphs, shortest paths, trees Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a tree with n cities connected by roads. Each road has a hardness value w_i . The travel time along a road depends on the driver’s skill c and is calculated as ceil(w_i / c) . The...

Practice › Codeforces Solutions › Codeforces Round 901 (Div. 1) ›

CF 1874D - Jellyfish and Miku

CF 1874D - Jellyfish and Miku Rating: 2800 Tags: divide and conquer, dp, math, probabilities Solve time: 2m 27s Verified: no Solution Problem Understanding We have a simple linear chain of cities numbered from 0 to n, connected sequentially by n roads. Each road has a "beauty" value, which determines the probability that Jellyfish will traverse it if she stands at one of its endpoints. Starting at city 0, Jellyfish...

Practice › Codeforces Solutions ›

Educational Codeforces Round 155 (Rated for Div. 2)

Educational Codeforces Round 155 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 800-2800 | Time: 15m 6s Problem Name Rating Tags Solve Time Verified A Rigged! 800 greedy 5m 30s ✓ B Chips on the Board 900 constructive-algorithms, greedy 1m 36s ✓ C Make it Alternating 1300 combinatorics, dp, greedy 1m 54s ✗ D Sum of XOR Functions 1700 bitmasks, combinatorics, divide-and-conquer...

Practice › Codeforces Solutions › Educational Codeforces Round 155 (Rated for Div. 2) ›

CF 1879D - Sum of XOR Functions

CF 1879D - Sum of XOR Functions Rating: 1700 Tags: bitmasks, combinatorics, divide and conquer, dp, math Solve time: 2m 23s Verified: yes Solution Problem Understanding We are given an array of non-negative integers. For every subarray $[l,r]$, we compute the XOR of all elements inside that subarray. Let that XOR value be $f(l,r)$. The contribution of a subarray is not just its XOR. It is multiplied by the subarray...

Practice › Codeforces Solutions › Codeforces Round 905 (Div. 1) ›

CF 1887D - Split

CF 1887D - Split Rating: 2700 Tags: binary search, data structures, divide and conquer, dsu, math, trees, two pointers Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given an array of distinct integers ranging from 1 to n, and we are asked to answer multiple queries about contiguous subarrays. A subarray is considered "good" if it can be split into two non-empty parts such that all elements...

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896H1 - Cyclic Hamming (Easy Version)

CF 1896H1 - Cyclic Hamming (Easy Version) Rating: 3400 Tags: brute force, divide and conquer, dp, fft, math, number theory Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given two binary strings, both of length $2^{k+1}$. Some positions are fixed as 0 or 1, while others are unknown and marked with a question mark. The task is to fill in all unknowns in both strings so that...

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896D - Ones and Twos

CF 1896D - Ones and Twos Rating: 1700 Tags: binary search, data structures, divide and conquer, math, two pointers Solve time: 3m 8s Verified: yes Solution Problem Understanding We are given an array consisting only of 1s and 2s, and the array changes over time. Between changes, we are repeatedly asked a yes/no question: whether there exists a contiguous subarray whose sum is exactly some target value. The key difficulty...

Practice › Codeforces Solutions › Codeforces Round 910 (Div. 2) ›

CF 1898F - Vova Escapes the Matrix

CF 1898F - Vova Escapes the Matrix Rating: 2600 Tags: brute force, dfs and similar, divide and conquer, shortest paths Solve time: 4m 33s Verified: no Solution Problem Understanding We are given an $n \times m$ grid representing a room where Vova is trapped. Each cell is either empty, blocked, or contains Vova. He can move to any empty cell sharing a side, and he can escape if he reaches...

Practice › Codeforces Solutions › Educational Codeforces Round 159 (Rated for Div. 2) ›

CF 1902F - Trees and XOR Queries Again

CF 1902F - Trees and XOR Queries Again Rating: 2400 Tags: data structures, dfs and similar, divide and conquer, graphs, implementation, math, trees Solve time: 2m 22s Verified: yes Solution Problem Understanding We are given a tree with n vertices, where each vertex carries an integer value. A tree is an acyclic connected graph, which ensures there is exactly one simple path between any two vertices. For each query, we...

Practice › Codeforces Solutions › Codeforces Round 912 (Div. 2) ›

CF 1903D2 - Maximum And Queries (hard version)

CF 1903D2 - Maximum And Queries (hard version) Rating: 2500 Tags: bitmasks, divide and conquer, dp, greedy Solve time: 1m 50s Verified: no Solution Problem Understanding We are given an array of integers. We are allowed to increase individual elements, one increment at a time, and each increment costs one unit of budget. For each query, we are given a budget value $k$, and we want to know how large...

Practice › Codeforces Solutions › Codeforces Round 914 (Div. 2) ›

CF 1904D2 - Set To Max (Hard Version)

CF 1904D2 - Set To Max (Hard Version) Rating: 1800 Tags: constructive algorithms, data structures, divide and conquer, greedy, implementation, sortings Solve time: 2m 31s Verified: no Solution Problem Understanding We are given two arrays, a and b , of length n . Our goal is to transform a into b using an operation that allows us to select any contiguous subarray and replace all its values with the maximum...

Practice › Codeforces Solutions › Codeforces Round 915 (Div. 2) ›

CF 1905F - Field Should Not Be Empty

CF 1905F - Field Should Not Be Empty Rating: 2600 Tags: brute force, data structures, divide and conquer Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a permutation of numbers from 1 to $n$. The task revolves around identifying "good" positions in the array. A position is called good if all elements to its left are smaller and all elements to its right are larger. For...

Practice › Codeforces Solutions ›

2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 12 | Verified: 5/12 | Rating range: 800-3300 | Time: 21m 4s Problem Name Rating Tags Solve Time Verified A Accumulator Apex 1900 data-structures, implementation, sortings 1m 41s ✓ B Blueprint for Seating 2100 combinatorics, divide-and-conquer, math 2m 42s ✗ C Cactus Transformation 3300 constructive-algorithms 1m 25s ✓ D Divisibility Test 1900 math...

Practice › Codeforces Solutions › 2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 1912B - Blueprint for Seating

CF 1912B - Blueprint for Seating Rating: 2100 Tags: combinatorics, divide and conquer, math Solve time: 2m 42s Verified: no Solution Problem Understanding We are given a row of seats split into contiguous blocks by aisles. Each block is a positive-length segment of seats, and between any two consecutive blocks there is exactly one aisle. If there are $k$ aisles, then there are $k+1$ blocks, and their sizes form a...

Practice › Codeforces Solutions › Educational Codeforces Round 160 (Rated for Div. 2) ›

CF 1913D - Array Collapse

CF 1913D - Array Collapse Rating: 2100 Tags: data structures, divide and conquer, dp, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a permutation-like array where all values are distinct. The only operation allowed takes a contiguous segment and compresses it down to just its minimum element, deleting everything else in that segment. Repeating this operation in different places produces many possible final arrays, and...

Practice › Codeforces Solutions › Codeforces Round 918 (Div. 4) ›

CF 1915F - Greetings

CF 1915F - Greetings Rating: 1500 Tags: data structures, divide and conquer, sortings Solve time: 2m 5s Verified: yes Solution Problem Understanding We are given a set of people on a one-dimensional number line. Each person has a starting point and a destination, and all starting and ending points are distinct. Everyone begins moving simultaneously at a constant speed of one unit per second toward their destination. Whenever two people...

Practice › Codeforces Solutions › Good Bye 2023 ›

CF 1916G - Optimizations From Chelsu

CF 1916G - Optimizations From Chelsu Rating: 3500 Tags: divide and conquer, dp, number theory, trees Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given a tree whose edges carry positive integer weights. For any two vertices $u$ and $v$, let $len(u,v)$ be the number of edges on their path, and let $gcd(u,v)$ be the gcd of all edge weights on that path. The task is to...

Practice › Codeforces Solutions › Codeforces Round 922 (Div. 2) ›

CF 1918E - ace5 and Task Order

CF 1918E - ace5 and Task Order Rating: 2200 Tags: constructive algorithms, divide and conquer, implementation, interactive, probabilities, sortings Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 1 to $n$. The permutation is unknown, and our goal is to determine it. The only tool is a number $x$ initially set by the interactor and a query operation: we ask about...

Practice › Codeforces Solutions › Hello 2024 ›

CF 1919G - Tree LGM

CF 1919G - Tree LGM Rating: 3500 Tags: constructive algorithms, divide and conquer, games, trees Solve time: 1m 6s Verified: no Solution Problem Understanding We are asked to reconstruct a tree from a matrix of game outcomes. Each entry s[i][j] indicates whether the first player can force a win when the tree is rooted at vertex i and the coin starts at vertex j . A vertex can only move...

Practice › Codeforces Solutions › Codeforces Round 920 (Div. 3) ›

CF 1921G - Mischievous Shooter

CF 1921G - Mischievous Shooter Rating: 2200 Tags: brute force, data structures, divide and conquer, dp, implementation Solve time: 2m 15s Verified: no Solution Problem Understanding We are given a grid of size $n \times m$, each cell either containing a target represented by # or empty represented by . . Shel has a shotgun that fires in one of four diagonal directions: right-down, left-down, left-up, or right-up. The shotgun...

Practice › Codeforces Solutions › Educational Codeforces Round 161 (Rated for Div. 2) ›

CF 1922E - Increasing Subsequences

CF 1922E - Increasing Subsequences Rating: 1800 Tags: bitmasks, constructive algorithms, divide and conquer, greedy, math Solve time: 2m 3s Verified: no Solution Problem Understanding We are asked to construct an array of integers with a very specific property: the total number of its increasing subsequences should equal a given integer $X$. Increasing subsequences are sequences of elements from the array, taken in order, such that each element is strictly...

Practice › Codeforces Solutions ›

Codeforces Round 1024 (Div. 1)

Codeforces Round 1024 (Div. 1) Div. 1 | 6 problems | 0/6 verified | Difficulty 1300-3300 | 14m 18s # Problem Rating Tags Accepted Time ✓ A Mex in the Grid 1300 constructive-algorithms, implementation 13,423 1m 36s B Quartet Swapping 1800 brute-force, data-structures, divide-and-conquer 6,822 1m 36s C 23 Kingdom 2200 binary-search, brute-force, data-structures 2,260 1m 39s D Mani and Segments 2500 data-structures, implementation, sortings 1,019 4m 32s E Kia...

Practice › Codeforces Solutions › think-cell Round 1 ›

CF 1930D2 - Sum over all Substrings (Hard Version)

CF 1930D2 - Sum over all Substrings (Hard Version) Rating: 2100 Tags: bitmasks, divide and conquer, dp, dsu, greedy, implementation, strings Solve time: 2m 36s Verified: yes Solution Problem Understanding For every binary pattern $p$, we define $f(p)$ as the minimum number of 1 s in another binary string $q$ of the same length such that every position of $p$ can "justify" its value by looking at some interval of...

Practice › Codeforces Solutions › Codeforces Round 930 (Div. 1) ›

CF 1936E - Yet Yet Another Permutation Problem

CF 1936E - Yet Yet Another Permutation Problem Rating: 3400 Tags: divide and conquer, fft, math Solve time: 2m 56s Verified: no Solution Problem Understanding We are asked to count permutations $q$ of length $n$ such that at every position $i < n$, the maximum of the first $i$ elements in $q$ is different from the maximum of the first $i$ elements in a given permutation $p$. In other words,...

Practice › Codeforces Solutions › XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules) ›

CF 1940C - Burenka and Pether

CF 1940C - Burenka and Pether Rating: - Tags: *special, data structures, dfs and similar, divide and conquer, dsu, graphs, sortings, trees Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a directed structure over positions 1 to n, where each position carries a value. The key restriction is that movement from one position to another is not arbitrary: you are only allowed to move forward in...

Practice › Codeforces Solutions › Educational Codeforces Round 165 (Rated for Div. 2) ›

CF 1969E - Unique Array

CF 1969E - Unique Array Rating: 2400 Tags: binary search, data structures, divide and conquer, dp, greedy Solve time: 1m 34s Verified: no Solution Problem Understanding We are given an array of integers and allowed to change elements arbitrarily, paying one unit cost per change. The goal is to modify the array so that every contiguous subarray contains at least one value that appears exactly once inside that subarray. A...

Practice › Codeforces Solutions › Codeforces Round 955 (Div. 2, with prizes from NEAR!) ›

CF 1982E - Number of k-good subarrays

CF 1982E - Number of k-good subarrays Rating: 2300 Tags: bitmasks, brute force, combinatorics, divide and conquer, dp, math, meet-in-the-middle Solve time: 3m 13s Verified: no Solution Problem Understanding In this problem, we are given an array consisting of consecutive integers starting from zero. A subarray is considered k-good if every element within it has no more than k ones in its binary representation. Our task is to count all...

Practice › Codeforces Solutions › Codeforces Round 956 (Div. 2) and ByteRace 2024 ›

CF 1983D - Swap Dilemma

CF 1983D - Swap Dilemma Rating: 1700 Tags: constructive algorithms, data structures, divide and conquer, greedy, math, sortings Solve time: 2m Verified: no Solution Problem Understanding We are given two arrays of the same length, and each array is a permutation-like structure in the sense that all values inside each array are distinct. The goal is to determine whether we can transform both arrays into exactly the same sequence using...

Practice › Codeforces Solutions › Codeforces Round 958 (Div. 2) ›

CF 1988E - Range Minimum Sum

CF 1988E - Range Minimum Sum Rating: 2300 Tags: binary search, brute force, data structures, divide and conquer, implementation Solve time: 1m 47s Verified: no Solution Problem Understanding We are working with a permutation of numbers from 1 to n, placed on a line. For any arrangement of numbers, we define a value based on all contiguous subarrays: each subarray contributes its minimum element, and we sum these contributions over...

Practice › Codeforces Solutions › Educational Codeforces Round 167 (Rated for Div. 2) ›

CF 1989F - Simultaneous Coloring

CF 1989F - Simultaneous Coloring Rating: 3000 Tags: dfs and similar, divide and conquer, graphs Solve time: 3m 1s Verified: no Solution Problem Understanding We are given a matrix with n rows and m columns, initially colorless. The allowed operations are painting an entire row red or an entire column blue. Multiple operations can be applied simultaneously, but the cost is quadratic in the number of simultaneous operations: performing k...

Practice › Codeforces Solutions › Codeforces Round 960 (Div. 2) ›

CF 1990F - Polygonal Segments

CF 1990F - Polygonal Segments Rating: 2800 Tags: brute force, data structures, divide and conquer, dp, greedy, two pointers Solve time: 2m 37s Verified: no Solution Problem Understanding We are given a dynamic array of positive values, and we repeatedly modify it while also answering range queries. The interesting object is a subarray that behaves like the side lengths of a polygon. A segment of the array is considered valid...

Practice › Codeforces Solutions › Codeforces Round 960 (Div. 2) ›

CF 1990E2 - Catch the Mole(Hard Version)

CF 1990E2 - Catch the Mole(Hard Version) Rating: 2600 Tags: binary search, data structures, dfs and similar, divide and conquer, interactive, trees Solve time: 2m 21s Verified: no Solution Problem Understanding We are working with a rooted tree where node 1 is fixed as the root. Somewhere in this tree there is a hidden token, called the mole, which occupies a single node. We do not know its position initially,...

Practice › Codeforces Solutions › Educational Codeforces Round 168 (Rated for Div. 2) ›

CF 1997E - Level Up

CF 1997E - Level Up Rating: 2200 Tags: binary search, brute force, data structures, divide and conquer, implementation Solve time: 2m 40s Verified: no Solution Problem Understanding In this problem, Monocarp is traversing a linear sequence of monsters, each with a level. He starts at level 1 and can fight monsters whose levels are at least as high as his current level. Whenever he fights k monsters, he levels up...

Practice › Codeforces Solutions › Codeforces Round 965 (Div. 2) ›

CF 1998E2 - Eliminating Balls With Merging (Hard Version)

CF 1998E2 - Eliminating Balls With Merging (Hard Version) Rating: 2500 Tags: binary search, brute force, data structures, divide and conquer, greedy, implementation Solve time: 3m 13s Verified: no Solution Problem Understanding We are given a sequence of balls numbered from 1 to $n$, each labeled with a positive integer. For each prefix of length $i$ ($1 \le i \le n$), we want to determine how many positions $j$ can...

Practice › Codeforces Solutions › Codeforces Round 965 (Div. 2) ›

CF 1998E1 - Eliminating Balls With Merging (Easy Version)

CF 1998E1 - Eliminating Balls With Merging (Easy Version) Rating: 2200 Tags: binary search, brute force, data structures, divide and conquer, greedy Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a row of $n$ balls, each with an integer written on it. The operation we can perform repeatedly involves selecting two adjacent values in the set $S$ and merging them according to their relative sizes. Concretely,...

Practice › Codeforces Solutions › Codeforces Round 967 (Div. 2) ›

CF 2001C - Guess The Tree

CF 2001C - Guess The Tree Rating: 1500 Tags: binary search, brute force, dfs and similar, divide and conquer, dsu, greedy, interactive, trees Solve time: 3m 35s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden tree with n nodes by interacting with a judge that answers specific distance-based queries. Each query "? a b" returns the node x that minimizes the absolute difference in distances from...

Practice › Codeforces Solutions › Codeforces Round 968 (Div. 2) ›

CF 2003E1 - Turtle and Inversions (Easy Version)

CF 2003E1 - Turtle and Inversions (Easy Version) Rating: 2600 Tags: brute force, divide and conquer, dp, greedy, math Solve time: 4m 17s Verified: yes Solution Problem Understanding We are asked to find the maximum number of inversions in permutations of length $n$ that satisfy a specific "interesting" property defined by a set of intervals. Each interval $[l_i, r_i]$ comes with a choice $k_i$ such that the maximum of the...

Practice › Codeforces Solutions › Codeforces Round 968 (Div. 2) ›

CF 2003E2 - Turtle and Inversions (Hard Version)

CF 2003E2 - Turtle and Inversions (Hard Version) Rating: 2700 Tags: brute force, data structures, divide and conquer, dp, greedy, math, two pointers Solve time: 2m 29s Verified: no Solution Problem Understanding The problem gives us a permutation of integers from 1 to $n$ and asks us to consider certain "interesting" permutations based on a set of intervals. Each interval allows us to split it into a left segment and...

Practice › Codeforces Solutions › Codeforces Round 972 (Div. 2) ›

CF 2005D - Alter the GCD

CF 2005D - Alter the GCD Rating: 2400 Tags: binary search, brute force, data structures, divide and conquer, implementation, number theory Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given two arrays of equal length. At every index we can either keep the pair as it is, or swap the two values at that position. The operation we are allowed to perform is more structured: we must...

Practice › Codeforces Solutions › Codeforces Round 969 (Div. 1) ›

CF 2006C - Eri and Expanded Sets

CF 2006C - Eri and Expanded Sets Rating: 2300 Tags: data structures, divide and conquer, math, number theory, two pointers Solve time: 2m 53s Verified: no Solution Problem Understanding For every subarray of the given array, we throw all of its values into a set, removing duplicates. Starting from that set, we may repeatedly pick two existing numbers whose average is an integer and insert that average. A subarray is...

Practice › Codeforces Solutions ›

Kotlin Heroes: Episode 11

Kotlin Heroes: Episode 11 Type: Kotlin | Problems: 9 | Verified: 2/9 | Rating range: - | Time: 14m Problem Name Rating Tags Solve Time Verified A Problem Solving - *special 1m 48s ✓ B Shuffle - *special 1m 45s ✗ C Split the Expression - *special 2m 37s ✗ D Among Wolves - *special 2m 23s ✗ E Rock-Paper-Scissors Bot - *special, greedy, strings 41s ✗ F Good Subarray...

Practice › Codeforces Solutions › Kotlin Heroes: Episode 11 ›

CF 2011I - Stack and Queue

CF 2011I - Stack and Queue Rating: - Tags: *special, data structures, divide and conquer Solve time: 1m 11s Verified: yes Solution Problem Understanding We maintain two evolving ordered structures over patients: one behaves like a FIFO queue (first in, first out) and the other like a stack (last in, first out). Each patient has a fixed service duration. The queue doctor processes patients in arrival order, while the stack...

Practice › Codeforces Solutions › Codeforces Round 974 (Div. 3) ›

CF 2014H - Robin Hood Archery

CF 2014H - Robin Hood Archery Rating: 1900 Tags: data structures, divide and conquer, greedy, hashing Solve time: 2m 2s Verified: yes Solution Problem Understanding For each query we look only at the subarray $a_l, a_{l+1}, \dots, a_r$. Robin moves first. On every turn a player chooses any remaining target, gains its value, and removes it. Since there are no restrictions on which target can be chosen, the game is...

Practice › Codeforces Solutions › Codeforces Round 975 (Div. 1) ›

CF 2018E1 - Complex Segments (Easy Version)

CF 2018E1 - Complex Segments (Easy Version) Rating: 3300 Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a collection of closed segments on a number line, each defined by a left and right endpoint. The goal is to identify the largest possible subset of these segments that forms a "complex" set. A complex set...

Practice › Codeforces Solutions › Codeforces Round 975 (Div. 1) ›

CF 2018E2 - Complex Segments (Hard Version)

CF 2018E2 - Complex Segments (Hard Version) Rating: 3400 Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings Solve time: 38s Verified: no Solution Producing a fully correct editorial for Codeforces 2018E2 requires reconstructing a fairly intricate DSU-based optimization and the divide-and-conquer evaluation of all values of $f(m)$. The official editorial only provides a compressed sketch, not enough detail to safely derive a complete accepted implementation line...

Practice › Codeforces Solutions › Educational Codeforces Round 171 (Rated for Div. 2) ›

CF 2026F - Bermart Ice Cream

CF 2026F - Bermart Ice Cream Rating: 2700 Tags: data structures, dfs and similar, divide and conquer, dp, implementation, trees Solve time: 1m 39s Verified: no Solution Problem Understanding 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. Instead, they form a rooted cloning structure: a...

Practice › Codeforces Solutions › Codeforces Global Round 27 ›

CF 2035G2 - Go Learn! (Hard Version)

CF 2035G2 - Go Learn! (Hard Version) Rating: 3500 Tags: divide and conquer, dp Solve time: 1m 47s Verified: no Solution Problem Understanding We are given an array of length $n$, but its values are not fixed. Instead, we must construct it. Alongside this, we are given $m$ constraints. Each constraint says that at a specific index $x$, the value of the array must be a specific number $k$, and...

Practice › Codeforces Solutions › Codeforces Global Round 27 ›

CF 2035D - Yet Another Real Number Problem

CF 2035D - Yet Another Real Number Problem Rating: 1800 Tags: binary search, data structures, divide and conquer, greedy, implementation, math Solve time: 1m 44s Verified: no Solution Problem Understanding We are given an array of integers and allowed to perform operations that move powers of two from one element to a later element in the array. Specifically, if an element is even, we can divide it by two and...

Practice › Codeforces Solutions › Codeforces Round 1029 (Div. 3) ›

CF 2117H - Incessant Rain

CF 2117H - Incessant Rain Rating: 2500 Tags: data structures, divide and conquer, sortings Solve time: 1m 52s Verified: no Solution Problem Understanding We are given an array of integers and a sequence of queries. Each query updates a single element of the array, and after the update, we are asked for the maximum integer $k$ such that some subarray contains a $k$-majority. A $k$-majority is a number that occurs...

Practice › Codeforces Solutions › Codeforces Round 984 (Div. 3) ›

CF 2036G - Library of Magic

CF 2036G - Library of Magic Rating: 2200 Tags: binary search, constructive algorithms, divide and conquer, interactive, math, number theory Solve time: 1m 30s Verified: no Solution Problem Understanding We are dealing with a very large universe of book types, from 1 up to n where n can be as large as 10^18. Every type normally appears exactly twice in a hidden collection. However, three distinct types a, b, and...

Practice › Codeforces Solutions › 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) ›

CF 2041J - Bottle Arrangement

CF 2041J - Bottle Arrangement Rating: 2700 Tags: data structures, divide and conquer, dp, dsu, greedy Solve time: 2m 2s Verified: no Solution The failure you show is not enough to diagnose the algorithm itself. Let's trace what happened: The input contains 5 test cases : 5 2 2 1 5 2 3 4 5 1 5 2 1 4 2 3 5 4 1 1 5 4 10 4...

Practice › Codeforces Solutions › Educational Codeforces Round 172 (Rated for Div. 2) ›

CF 2042E - Vertex Pairs

CF 2042E - Vertex Pairs Rating: 2900 Tags: binary search, brute force, data structures, dfs and similar, divide and conquer, greedy, implementation, trees Solve time: 2m 4s Verified: no Solution The failure you show is not enough to diagnose the algorithm itself. Let's trace what happened: The input contains 5 test cases : 5 2 2 1 5 2 3 4 5 1 5 2 1 4 2 3 5...

Practice › Codeforces Solutions › Codeforces Global Round 28 ›

CF 2048F - Kevin and Math Class

CF 2048F - Kevin and Math Class Rating: 2500 Tags: brute force, data structures, divide and conquer, dp, implementation, math, trees Solve time: 1m 35s Verified: no Solution Problem Understanding We are given two arrays of the same length. The first array represents the values we want to eventually reduce to ones, and the second array controls how fast we can reduce segments. A single operation chooses a contiguous segment....

Practice › Codeforces Solutions › Codeforces Round 991 (Div. 3) ›

CF 2050F - Maximum modulo equality

CF 2050F - Maximum modulo equality Rating: 1700 Tags: data structures, divide and conquer, math, number theory Solve time: 2m 50s Verified: no Solution Thank you for the clarification. I see exactly why the previous solution fails. The core issue is that the greedy left-to-right redistribution is too strict : it assumes you can only push surplus to the next element, but in reality the allowed operations let you shift...

Practice › Codeforces Solutions › Good Bye 2024: 2025 is NEAR ›

CF 2053C - Bewitching Stargazer

CF 2053C - Bewitching Stargazer Rating: 1500 Tags: bitmasks, divide and conquer, dp, math Solve time: 1m 54s Verified: no Solution Problem Understanding We are asked to simulate the process of Iris observing stars with a lazy, recursive strategy. She starts with all stars in a single segment and repeatedly targets the middle star of any odd-length segment, adding its 1-based index to her "lucky value". After choosing a star,...

Practice › Codeforces Solutions › Codeforces Round 997 (Div. 2) ›

CF 2056D - Unique Median

CF 2056D - Unique Median Rating: 2200 Tags: binary search, brute force, combinatorics, data structures, divide and conquer, dp Solve time: 2m 3s Verified: no Solution Problem Understanding We are asked to count subarrays of a given array where the median is uniquely defined. In practice, this means a subarray is good if, after sorting, the middle element (or the two middle elements, if the length is even) are equal....

Practice › Codeforces Solutions › IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2) ›

CF 2061I - Kevin and Nivek

CF 2061I - Kevin and Nivek Rating: 3500 Tags: divide and conquer, dp Solve time: 1m 48s Verified: no Solution Problem Understanding We are asked to determine the minimum time Kevin must invest to win at least a given number of matches against Nivek, for all possible counts from 0 to $n$. Each match is either Type 1, which has a fixed time cost $a_i$ for Kevin to guarantee a...

Practice › Codeforces Solutions › Codeforces Round 1003 (Div. 4) ›

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...

Practice › Codeforces Solutions › Educational Codeforces Round 174 (Rated for Div. 2) ›

CF 2069F - Graph Inclusion

CF 2069F - Graph Inclusion Rating: 2800 Tags: data structures, dfs and similar, divide and conquer, dsu, graphs Solve time: 1m 48s Verified: no Solution Problem Understanding We are given two undirected graphs, $A$ and $B$, on the same set of $n$ vertices. Initially, both graphs have no edges. Queries arrive one by one; each query either toggles an edge in $A$ or $B$. After every query, we are asked:...

Practice › Codeforces Solutions › Educational Codeforces Round 175 (Rated for Div. 2) ›

CF 2070F - Friends and Pizza

CF 2070F - Friends and Pizza Rating: 3000 Tags: bitmasks, divide and conquer, dp, fft Solve time: 1m 38s Verified: yes Solution Problem Understanding We are asked to compute, for every possible number of slices k that Monocarp can eat, the number of ways to select exactly two friends such that the friends do not quarrel over any pizza and Monocarp ends up eating exactly k slices. Each pizza has...

Practice › Codeforces Solutions › Educational Codeforces Round 175 (Rated for Div. 2) ›

CF 2070E - Game with Binary String

CF 2070E - Game with Binary String Rating: 2200 Tags: constructive algorithms, data structures, divide and conquer, games, greedy, math Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a binary string and we look at every contiguous substring. For each substring, a two-player game is played on the characters of that substring, where each move removes exactly two adjacent characters. Adjacency is cyclic in the sense...

Practice › Codeforces Solutions › Codeforces Round 1006 (Div. 3) ›

CF 2072G - I've Been Flipping Numbers for 300 Years and Calculated the Sum

CF 2072G - I've Been Flipping Numbers for 300 Years and Calculated the Sum Rating: 2200 Tags: binary search, brute force, combinatorics, divide and conquer, math, number theory Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a number n and a limit k . For every base p from 2 up to k , we write n in base p , reverse its digits, interpret the...

Practice › Codeforces Solutions › Codeforces Round 1009 (Div. 3) ›

CF 2074F - Counting Necessary Nodes

CF 2074F - Counting Necessary Nodes Rating: 2000 Tags: bitmasks, divide and conquer, greedy, implementation, math Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given a fixed infinite quadtree structure where every node represents an axis-aligned square whose side length is a power of two, and whose coordinates are aligned to that same scale. Each node corresponds exactly to one such square, and every square is recursively...

Practice › Codeforces Solutions › Codeforces Round 1008 (Div. 1) ›

CF 2077E - Another Folding Strip

CF 2077E - Another Folding Strip Rating: 2700 Tags: combinatorics, constructive algorithms, data structures, divide and conquer, dp, greedy, math Solve time: 1m 40s Verified: no Solution Problem Understanding We are given an array, and we need to look at every contiguous subarray. For each subarray, we imagine it as a sequence of target heights on a strip. Starting from an all-zero strip, we want to reach those heights using...

Practice › Codeforces Solutions › Codeforces Round 1024 (Div. 1) ›

CF 2101B - Quartet Swapping

CF 2101B - Quartet Swapping Rating: 1800 Tags: brute force, data structures, divide and conquer, greedy, sortings Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a permutation, which we can think of as a row of distinct numbered tiles. The only allowed move takes any block of four consecutive positions and swaps the first with the third and the second with the fourth, effectively turning a...

Practice › Codeforces Solutions › Educational Codeforces Round 178 (Rated for Div. 2) ›

CF 2104G - Modulo 3

CF 2104G - Modulo 3 Rating: 2700 Tags: data structures, divide and conquer, dsu, graphs, trees Solve time: 1m 27s Verified: no Solution Problem Understanding We are given a functional graph, meaning each vertex has exactly one outgoing edge. This forms a combination of cycles and trees pointing into those cycles. Each query modifies a single edge and asks how many distinct colorings exist if we are allowed to color...

Practice › Codeforces Solutions › Codeforces Round 1020 (Div. 3) ›

CF 2106G2 - Baudelaire (hard version)

CF 2106G2 - Baudelaire (hard version) Rating: 2500 Tags: binary search, dfs and similar, divide and conquer, implementation, interactive, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a tree with up to 1000 nodes, and each node hides a value of either 1 or −1. The tree is rooted somewhere, but the root is unknown to us. What makes this unusual is that the root...

Practice › Codeforces Solutions › Codeforces Round 1020 (Div. 3) ›

CF 2106G1 - Baudelaire (easy version)

CF 2106G1 - Baudelaire (easy version) Rating: 2200 Tags: binary search, constructive algorithms, divide and conquer, greedy, interactive, trees Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a tree of size $n$, where each node carries a value of either $1$ or $-1$. The tree is connected in such a way that every node is adjacent to node $1$. The root of the tree is unknown,...

Practice › Codeforces Solutions › Codeforces Round 1032 (Div. 3) ›

CF 2121G - Gangsta

CF 2121G - Gangsta Rating: 1900 Tags: data structures, divide and conquer, math, sortings Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to process a binary string and compute, for every contiguous substring, the maximum frequency of either 0 or 1 in that substring, then sum these values across all substrings. For example, in the string 0110 , the substring 011 has two 1 s and...

Practice › Codeforces Solutions › Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2) ›

CF 2122F - Colorful Polygon

CF 2122F - Colorful Polygon Rating: 3400 Tags: constructive algorithms, divide and conquer, geometry Solve time: 3m 33s Verified: no Solution Problem Understanding We are given a small array of integers $a = [a_1, a_2, \dots, a_n]$, with $n \le 8$ and a total sum $S = a_1 + \dots + a_n \le 100$. The goal is to construct a simple polygon with at most 333 vertices such that the...

Practice › Codeforces Solutions › Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2) ›

CF 2122D - Traffic Lights

CF 2122D - Traffic Lights Rating: 2400 Tags: brute force, data structures, divide and conquer, dp, graphs, greedy, shortest paths Solve time: 51s Verified: yes Solution Problem Understanding The problem describes a connected, simple undirected graph with n vertices and m edges. A token starts at vertex 1 at time 0 . At each integer second t , if the token is at vertex u , you have two choices:...

Practice › Codeforces Solutions › Educational Codeforces Round 181 (Rated for Div. 2) ›

CF 2125F - Timofey and Docker

CF 2125F - Timofey and Docker Rating: 3000 Tags: binary search, divide and conquer, dp Solve time: 1m 33s Verified: no Solution Problem Understanding Timofey has written a text s and wants to present it to a conference audience. Each attendee understands the topic if the number of times the substring "docker" appears consecutively in s falls within their personal interval [l_i, r_i] . Our task is to modify as...

Practice › Codeforces Solutions › Codeforces Round 1037 (Div. 3) ›

CF 2126G2 - Big Wins! (hard version)

CF 2126G2 - Big Wins! (hard version) Rating: 2400 Tags: binary search, data structures, divide and conquer, dsu, trees, two pointers Solve time: 1m 23s Verified: no Solution Problem Understanding We are given an array of integers, each between 1 and $n$, and we need to choose a contiguous subarray that maximizes the difference between its median and its minimum element. The median is defined as the middle element after...

Practice › Codeforces Solutions › Educational Codeforces Round 183 (Rated for Div. 2) ›

CF 2145G - Cost of Coloring

CF 2145G - Cost of Coloring Rating: 2900 Tags: combinatorics, divide and conquer, dp, fft, math Solve time: 1m 24s Verified: no Solution Problem Understanding We are given a rectangular sheet with $n$ rows and $m$ columns, initially uncolored. Our task is to determine how many ways we can color it “beautifully” with exactly $k$ colors, using the fewest operations possible for each number of operations from $\min(n, m)$ to...

Practice › Codeforces Solutions › Educational Codeforces Round 183 (Rated for Div. 2) ›

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...

Practice › Codeforces Solutions › Codeforces Round 1052 (Div. 2) ›

CF 2146E - Yet Another MEX Problem

CF 2146E - Yet Another MEX Problem Rating: 2300 Tags: brute force, constructive algorithms, data structures, divide and conquer, greedy, hashing Solve time: 1m 47s Verified: no Solution Problem Understanding We are given an array that grows one element at a time from left to right. After each new element is appended, we look at all subarrays that end exactly at this new position. Among those subarrays, we want the...

Practice › Codeforces Solutions › Codeforces Round 1052 (Div. 2) ›

CF 2146D2 - Max Sum OR (Hard Version)

CF 2146D2 - Max Sum OR (Hard Version) Rating: 2000 Tags: bitmasks, constructive algorithms, divide and conquer, greedy Solve time: 1m 36s Verified: no Solution Problem Understanding We are given an integer interval $[l, r]$. From this interval we form a list containing every integer exactly once. One copy of this list is fixed as array $b$. The other copy, array $a$, is initially identical but we are allowed to...

Practice › Codeforces Solutions › Codeforces Round 1052 (Div. 2) ›

CF 2146D1 - Max Sum OR (Easy Version)

CF 2146D1 - Max Sum OR (Easy Version) Rating: 1500 Tags: bitmasks, constructive algorithms, divide and conquer, greedy, trees Solve time: 1m 34s Verified: no Solution Problem Understanding We are given two integers, l and r , where l is always zero in this easy version and r is less than 200,000. From these, we define an array b that contains every integer from l to r , inclusive. We...

Practice › Codeforces Solutions › Codeforces Round 1054 (Div. 3) ›

CF 2149G - Buratsuta 3

CF 2149G - Buratsuta 3 Rating: 2100 Tags: binary search, brute force, data structures, divide and conquer, probabilities Solve time: 1m 38s Verified: no Solution Problem Understanding We are given an array of integers and many independent range queries. For each query segment, we must identify all values whose frequency inside that segment is strictly greater than one third of the segment length. The key point is that each query...

Practice › Codeforces Solutions › Codeforces Round 1053 (Div. 1) ›

CF 2150E2 - Hidden Single (Version 2)

CF 2150E2 - Hidden Single (Version 2) Rating: 2800 Tags: binary search, divide and conquer, interactive, math, probabilities Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a hidden array of length $2n-1$ that contains each number from 1 to $n$ exactly twice, except for a single number which appears only once. Our goal is to determine which number appears only once. We do not need to...

Practice › Codeforces Solutions › Codeforces Round 1053 (Div. 1) ›

CF 2150E1 - Hidden Single (Version 1)

CF 2150E1 - Hidden Single (Version 1) Rating: 2600 Tags: divide and conquer, interactive, math, probabilities, sortings Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a hidden array of length 2n-1 , containing integers from 1 to n such that every number appears exactly twice except for one number that appears only once. Our goal is to identify the number that occurs exactly once. We do...

Practice › Codeforces Solutions › Codeforces Round 1060 (Div. 2) ›

CF 2154E - No Mind To Think

CF 2154E - No Mind To Think Rating: 2500 Tags: binary search, divide and conquer, greedy, sortings, ternary search, two pointers Solve time: 1m 42s Verified: no Solution Problem Understanding We are given an array of positive integers. We are allowed to choose one odd length $x$, and then repeatedly perform an operation up to $k$ times. Each operation picks any subsequence of length $x$, computes its median, and overwrites...

Practice › Codeforces Solutions › Codeforces Round 1066 (Div. 1 + Div. 2) ›

CF 2157F - Git Gud

CF 2157F - Git Gud Rating: 2400 Tags: brute force, constructive algorithms, divide and conquer, math, ternary search Solve time: 3m 8s Verified: yes Solution Problem Understanding We are asked to simulate a sequence of missions that guarantees our skill reaches at least a target value n regardless of our starting skill s , which is unknown and can be any integer from 1 to n . Each mission has...

Practice › Codeforces Solutions › Codeforces Round 1066 (Div. 1 + Div. 2) ›

CF 2157G - Isaac's Queries

CF 2157G - Isaac's Queries Rating: 2800 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, divide and conquer, dp, greedy, interactive, math, probabilities Solve time: 1m 49s Verified: no Solution Problem Understanding We are dealing with a hidden array of integers, where each integer is in the range [0, 2^30) . We are allowed to ask queries about contiguous subarrays. For a query on the interval [u, v] ,...

Practice › Codeforces Solutions › Codeforces Round 1067 (Div. 2) ›

CF 2158E - Sink

CF 2158E - Sink Rating: 2600 Tags: data structures, divide and conquer, dsu, graphs, implementation Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a 2D grid of size $n \times m$, where each cell contains a positive integer. We can construct "holes" in cells. A cell is considered a sink either if it has a hole, or if it is adjacent (sharing a side) to another...

Practice › Codeforces Solutions › Codeforces Round 1063 (Div. 2) ›

CF 2163D1 - Diadrash (Easy Version)

CF 2163D1 - Diadrash (Easy Version) Rating: 2100 Tags: binary search, brute force, divide and conquer, implementation, interactive Solve time: 1m 20s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 0 to n-1 , and our task is to find the maximum MEX over a set of ranges. Each range specifies a contiguous segment of the permutation, and the MEX of a range is...

Practice › Codeforces Solutions › Educational Codeforces Round 184 (Rated for Div. 2) ›

CF 2169D2 - Removal of a Sequence (Hard Version)

CF 2169D2 - Removal of a Sequence (Hard Version) Rating: 2100 Tags: binary search, divide and conquer, greedy, implementation, math, number theory Solve time: 2m 22s Verified: no Solution Problem Understanding We are given an infinite sequence of natural numbers starting from 1. Polycarp performs a special removal operation exactly $x$ times. Each operation removes all numbers in positions that are multiples of $y$ in the current sequence. After these...

Practice › Codeforces Solutions › 2025 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) ›

CF 2172J - Sliding Tiles

CF 2172J - Sliding Tiles Rating: 2300 Tags: data structures, divide and conquer, dsu Solve time: 1m 46s Verified: no Solution Problem Understanding We are given an $n \times n$ grid with tiles stacked in columns and vertical bars between adjacent columns. Each column $i$ starts with $a_i$ tiles stacked from the bottom. Each bar between column $i$ and $i+1$ has a height $h_i$, which blocks movement of tiles in...

Practice › Codeforces Solutions › Codeforces Round 1068 (Div. 2) ›

CF 2173F - Isla's Memory Thresholds

CF 2173F - Isla's Memory Thresholds Rating: 2600 Tags: binary search, brute force, data structures, divide and conquer, math Solve time: 3m 20s Verified: yes Solution Problem Understanding We are given a non-increasing array of positive integers, and we repeatedly process subsegments of it under a “capacity reset” rule. For each query, we pick a contiguous slice from index l to r . We then scan it left to right,...

Practice › Codeforces Solutions › Good Bye 2025 ›

CF 2178E - Flatten or Concatenate

CF 2178E - Flatten or Concatenate Rating: 2000 Tags: binary search, divide and conquer, interactive Solve time: 2m 11s Verified: no Solution Problem Understanding We are asked to determine the maximum element of a hidden array that was generated from an initial array containing a single power-of-two number. The array evolves by two operations: flattening, which splits a maximal even number into two halves, and concatenation, which duplicates one array...

Practice › Codeforces Solutions › Codeforces Global Round 31 (Div. 1 + Div. 2) ›

CF 2180E - No Effect XOR

CF 2180E - No Effect XOR Rating: 2300 Tags: bitmasks, divide and conquer, dp, greedy, math Solve time: 4m 36s Verified: no Solution Problem Understanding We have frogs on every integer position inside a contiguous segment $[l,r]$. After choosing a positive integer $x$, every frog moves from position $i$ to position $i \oplus x$. XOR with a fixed value is a permutation of all non-negative integers. Because of that, no...

Practice › Codeforces Solutions › Codeforces Round 1074 (Div. 4) ›

CF 2185F - BattleCows

CF 2185F - BattleCows Rating: 1700 Tags: data structures, divide and conquer, implementation Solve time: 3m 10s Verified: yes Solution Problem Understanding The tournament can be viewed as a complete binary tree over the array of cows. Each leaf is a single cow. Every internal node represents a contiguous segment of cows. The skill of a node is the XOR of all values inside that segment. When the two children...

Practice › Codeforces Solutions › Codeforces Round 1077 (Div. 1) ›

CF 2187F1 - Al Fine (Maximizing Version)

CF 2187F1 - Al Fine (Maximizing Version) Rating: 3100 Tags: binary search, data structures, divide and conquer, trees Solve time: 2m 29s Verified: no Solution Problem Understanding We are given two DFS preorder traversals of the same set of vertices {0,1,...,n} . The tree itself is unknown. The only thing we know is that in both traversals the root 0 appears first, and for every vertex the order of its...

Practice › Codeforces Solutions › Codeforces Round 1084 (Div. 3) ›

CF 2200H - Six Seven

CF 2200H - Six Seven Rating: 2600 Tags: divide and conquer, math, number theory, strings, trees Solve time: 2m 4s Verified: no Solution Problem Understanding We are given an array of positive integers, and we define a number as special if the power of 6 that divides it is strictly greater than the power of 7 that divides it. Formally, for a number $x$, we define $f_6(x)$ as the highest...

Practice › Codeforces Solutions › Educational Codeforces Round 187 (Rated for Div. 2) ›

CF 2203F - Binary Search with One Swap

CF 2203F - Binary Search with One Swap Rating: 2600 Tags: binary search, divide and conquer, dp, hashing, math, two pointers Solve time: 2m 2s Verified: no Solution Problem Understanding We start with an array containing the numbers from 1 to n in increasing order. Then we pick two positions i and j and swap the elements at those positions, creating exactly one disturbance in an otherwise perfectly sorted sequence....

Practice › Codeforces Solutions › Codeforces Round 1083 (Div. 2) ›

CF 2205D - Simons and Beating Peaks

CF 2205D - Simons and Beating Peaks Rating: 1700 Tags: data structures, divide and conquer, dp, greedy, implementation, trees Solve time: 2m Verified: no Solution Problem Understanding We are asked to transform a permutation of integers into a "cool" array. An array is cool if no element in the middle of a triplet is the maximum among its neighbors. In other words, the array must have no peaks, where a...

Practice › Codeforces Solutions › Codeforces Round 1085 (Div. 1 + Div. 2) ›

CF 2207H3 - Bowser's Castle (Hard Version)

CF 2207H3 - Bowser's Castle (Hard Version) Rating: - Tags: constructive algorithms, divide and conquer, interactive, trees, two pointers Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a black-box function of $n$ variables. The function is not arbitrary: it is built by taking the variables $x_1, x_2, \ldots, x_n$ in order and combining them using only min and max , with the restriction that each variable...

Practice › Codeforces Solutions › Codeforces Round 1085 (Div. 1 + Div. 2) ›

CF 2207H2 - Bowser's Castle (Medium Version)

CF 2207H2 - Bowser's Castle (Medium Version) Rating: - Tags: constructive algorithms, divide and conquer, interactive, trees, two pointers Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to reverse-engineer a hidden function chosen by Bowser. The function takes n integer inputs and is constructed entirely from nested min and max operations, each input appearing exactly once in order from x1 to xn . Our goal is...

Practice › Codeforces Solutions › Codeforces Round 1085 (Div. 1 + Div. 2) ›

CF 2207H1 - Bowser's Castle (Easy Version)

CF 2207H1 - Bowser's Castle (Easy Version) Rating: - Tags: binary search, constructive algorithms, divide and conquer, greedy, interactive, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are given an unknown function that takes a list of n values and returns a single number. The function is not arbitrary: it is built by combining the inputs using only min and max , and every input variable appears...

Practice › Codeforces Solutions › Codeforces Round 1085 (Div. 1 + Div. 2) ›

CF 2207C - Where's My Water?

CF 2207C - Where's My Water? Rating: 1600 Tags: data structures, divide and conquer, dp, math Solve time: 2m 25s Verified: no Solution Problem Understanding The grid can be understood more simply if we ignore the 2D picture and focus on each column independently. In column i , there are a_i dirt tiles at the bottom, and all tiles above them up to height h are water. So the number...

Practice › Codeforces Solutions › Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2) ›

CF 2211F - Learning Binary Search

CF 2211F - Learning Binary Search Rating: 2400 Tags: combinatorics, divide and conquer, dp, math Solve time: 2m 12s Verified: no Solution Problem Understanding We are working with all nondecreasing arrays of length $n$ whose values lie between $1$ and $m$. Each such array can be thought of as a way to distribute $n$ positions among $m$ distinct values, where each value appears in a contiguous block or not at...

Practice › Codeforces Solutions ›

Codeforces Round 1085 (Div. 1 + Div. 2)

Codeforces Round 1085 (Div. 1 + Div. 2) Div. 1+2 | 11 problems | 0/11 verified | Difficulty 800-3300 | 22m 3s # Problem Rating Tags Accepted Time ✓ A 1-1 800 greedy, strings 13,650 1m 54s B One Night At Freddy's 1600 games, greedy, sortings 5,785 1m 48s C Where's My Water? 1600 data-structures, divide-and-conquer, dp 5,420 2m 25s D Boxed Like a Fish 2200 dfs-and-similar, dp, games 2,106...

Practice › Codeforces Solutions ›

Codeforces Round 1093 (Div. 1)

Codeforces Round 1093 (Div. 1) Div. 1 | 6 problems | 1/6 verified | Difficulty - | 15m 59s # Problem Rating Tags Accepted Time ✓ A Grid L brute-force, constructive-algorithms, math 8,928 1m 59s B1 Unique Values (Easy version) binary-search, constructive-algorithms, divide-and-conquer 3,577 1m 55s B2 Unique Values (Hard version) binary-search, bitmasks, constructive-algorithms 3,185 2m 3s C Coloring a Red Black Tree dfs-and-similar, dp, greedy 1,199 3m 53s D...

Practice › Codeforces Solutions ›

Testing Round 10

Testing Round 10 Special | 4 problems | 2/4 verified | Difficulty 800-2200 | 4m 59s # Problem Rating Tags Accepted Time ✓ A Forgotten Episode 800 implementation 8,918 1m 1s ✓ B Balancer 1600 greedy, implementation 2,325 1m 3s ✓ C One-Based Arithmetic 1800 brute-force, dfs-and-similar, divide-and-conquer 1,139 1m 30s D Berland Federalization 2200 dp, trees 942 1m 25s

Practice › Codeforces Solutions › Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2) ›

CF 2222G - Statistics on Tree

CF 2222G - Statistics on Tree Rating: - Tags: binary search, brute force, dfs and similar, divide and conquer, graphs, trees Solve time: 1m 43s Verified: no Solution Problem Understanding We are working with a tree where each pair of vertices defines a path. For any pair of nodes $(u, v)$, we look at the unique simple path connecting them and then imagine removing all edges on that path from...

Practice › Codeforces Solutions › Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2) ›

CF 2222F - Building Tree

CF 2222F - Building Tree Rating: - Tags: data structures, divide and conquer, dsu, graphs, implementation Solve time: 1m 37s Verified: no Solution Problem Understanding We start with a weighted undirected graph on n vertices. The twist is that distance between two nodes is not the usual shortest path sum. Instead, if you take any path and look at the set of edge weights used on that path, the cost...

Practice › Codeforces Solutions › Codeforces Round 1093 (Div. 1) ›

CF 2219B1 - Unique Values (Easy version)

CF 2219B1 - Unique Values (Easy version) Rating: - Tags: binary search, constructive algorithms, divide and conquer, interactive, math Solve time: 1m 55s Verified: no Solution Problem Understanding We are given an array of length $2n+1$. Every number lies in the range $1$ to $n$. The structure is highly constrained: all values appear exactly twice except for one special value that appears exactly three times. The task is to discover...

Practice › Codeforces Solutions › Codeforces Round 940 (Div. 2) and CodeCraft-23 ›

CF 1957F1 - Frequency Mismatch (Easy Version)

CF 1957F1 - Frequency Mismatch (Easy Version) Rating: 2600 Tags: binary search, data structures, divide and conquer, hashing, probabilities, trees Solve time: 2m 8s Verified: no Solution Problem Understanding We are working on a rooted tree where each node carries a small integer label. Each query gives us two paths in the tree. For each path, we can think of walking from one endpoint to the other and collecting the...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452F - Permutation

CF 452F - Permutation Rating: 2700 Tags: data structures, divide and conquer, hashing Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a permutation of the numbers 1...n . For two distinct values a and b , their average is (a+b)/2 . Since the permutation contains every integer exactly once, this average is also present whenever a+b is even. The question is whether there exists a pair...

Practice › Codeforces Solutions › Codeforces Round 256 (Div. 2) ›

CF 448C - Painting Fence

CF 448C - Painting Fence Rating: 1900 Tags: divide and conquer, dp, greedy Solve time: 1m 31s Verified: yes Solution Problem Understanding We are asked to compute the minimum number of brush strokes needed to paint a fence of vertical planks. Each plank has a width of 1 meter and an individual height. The brush is exactly 1 meter wide, and it can be applied either vertically or horizontally. A...

Practice › Codeforces Solutions › Testing Round 10 ›

CF 440C - One-Based Arithmetic

CF 440C - One-Based Arithmetic Rating: 1800 Tags: brute force, dfs and similar, divide and conquer Solve time: 1m 30s Verified: no Solution Problem Understanding We are asked to represent a given positive integer $n$ as a sum of numbers, where each number consists entirely of the digit 1 repeated one or more times. For instance, 121 could be represented as 111 + 10, or as 111 + 11 -...

Practice › Codeforces Solutions › Codeforces Round 200 (Div. 1) ›

CF 343E - Pumping Stations

CF 343E - Pumping Stations Rating: 2900 Tags: brute force, dfs and similar, divide and conquer, flows, graphs, greedy, trees Solve time: 2m 18s Verified: no Solution Problem Understanding We are asked to maximize the total amount of water Mike can pump across a network of stations in a sequence of days. Each station is a node in an undirected graph, and pipes between stations are edges with capacities. On...

Practice › Codeforces Solutions › Codeforces Round 199 (Div. 2) ›

CF 342E - Xenia and Tree

CF 342E - Xenia and Tree Rating: 2400 Tags: data structures, divide and conquer, trees Solve time: 1m 22s Verified: yes Solution Problem Understanding We are working with a tree where every node represents a point in a connected acyclic graph. Initially only node 1 is colored red, while every other node starts blue. Over time, we perform two kinds of operations. One operation turns a chosen blue node red...

Practice › Codeforces Solutions › Codeforces Round 190 (Div. 1) ›

CF 321C - Ciel the Commander

CF 321C - Ciel the Commander Rating: 2100 Tags: constructive algorithms, dfs and similar, divide and conquer, greedy, trees Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a tree with up to 100,000 nodes, and we must assign each node a letter from 'A' to 'Z'. These letters represent ranks, where 'A' is the strongest and 'Z' is the weakest. The constraint is global and pairwise:...

Practice › Codeforces Solutions › Codeforces Round 190 (Div. 1) ›

CF 321E - Ciel and Gondolas

CF 321E - Ciel and Gondolas Rating: 2600 Tags: data structures, divide and conquer, dp Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a line of people from position 1 to position n, and we must split this line into exactly k contiguous groups. Each group corresponds to a gondola ride and contains consecutive people in the queue. The cost of placing a set of people...

Practice › Codeforces Solutions ›

Codeforces Round 134 (Div. 1)

Codeforces Round 134 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1200-2900 | 11m 29s # Problem Rating Tags Accepted Time ✓ A Ice Skating 1200 brute-force, dfs-and-similar, dsu 24,319 1m 27s B Blackboard Fibonacci 2100 brute-force, math 1,093 2m 48s ✓ C Formurosa 2600 divide-and-conquer, dp, expression-parsing 368 2m 29s D Bitonix' Patrol 2900 bitmasks, brute-force, combinatorics 273 1m 37s E Alien DNA 2800 data-structures,...

Practice › Codeforces Solutions › Croc Champ 2013 - Round 2 ›

CF 293E - Close Vertices

CF 293E - Close Vertices Rating: 2700 Tags: data structures, divide and conquer, trees Solve time: 41s Verified: no Solution Problem Understanding We are given a tree with n vertices, where each edge carries a non-negative weight. For any two vertices, the distance between them can be measured in two ways: the number of edges along the path connecting them, and the sum of edge weights along that path. Two...

Practice › Codeforces Solutions › Codeforces Round 134 (Div. 1) ›

CF 217C - Formurosa

CF 217C - Formurosa Rating: 2600 Tags: divide and conquer, dp, expression parsing Solve time: 2m 29s Verified: no Solution Problem Understanding The formula describes a Boolean function built from constants 0 and 1 , placeholders ? , and the operators AND, OR, and XOR. Each ? corresponds to a leaf of the plant. During an experiment, we choose which colony is placed on each leaf. If colony i has...

Practice › Codeforces Solutions ›

Codeforces Round 145 (Div. 2, ACM-ICPC Rules)

Codeforces Round 145 (Div. 2, ACM-ICPC Rules) Div. 2 | 8 problems | 6/8 verified | Difficulty 1000-2000 | 16m 2s # Problem Rating Tags Accepted Time ✓ A Lefthanders and Righthanders 1200 implementation 4,674 2m ✓ B Reading 1000 sortings 7,695 1m 44s ✓ C Weather 1300 dp, implementation 5,946 1m 31s ✓ D Cinema 1600 implementation 1,603 2m 18s ✓ E Champions' League 1600 implementation 1,050 2m 25s...

Practice › Codeforces Solutions › Codeforces Round 145 (Div. 2, ACM-ICPC Rules) ›

CF 234G - Practice

CF 234G - Practice Rating: 1600 Tags: constructive algorithms, divide and conquer, implementation Solve time: 1m 38s Verified: yes Solution Problem Understanding We have n football players, numbered from 1 to n . Each practice consists of splitting all players into two non-empty teams. After several practices, we want every pair of players to have been separated at least once, meaning that there exists some practice where the two players...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232C - Doe Graphs

CF 232C - Doe Graphs Rating: 2600 Tags: constructive algorithms, divide and conquer, dp, graphs, shortest paths Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to compute shortest paths in a family of recursively defined graphs called Doe graphs. Each graph is defined by an order n . The base cases are trivial: D (0) is a single vertex and D (1) is two vertices connected...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232E - Quick Tortoise

CF 232E - Quick Tortoise Rating: 3000 Tags: bitmasks, divide and conquer, dp Solve time: 2m 21s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 1)

Codeforces Round 124 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1100-2800 | 8m 52s # Problem Rating Tags Accepted Time ✓ A Lexicographically Maximum Subsequence 1100 greedy, strings 5,844 1m 29s ✓ B Infinite Maze 2000 dfs-and-similar, graphs 2,376 1m 39s ✓ C Paint Tree 2200 constructive-algorithms, divide-and-conquer, geometry 1,040 1m 40s D The Next Good String 2800 data-structures, greedy, hashing 599 2m 4s E...

Programming › Algorithm Cookbook ›

Chapter 15. Divide and Conquer

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.24 Case Studies

15.24 Case Studies Problem You have learned the mechanics of divide and conquer: split solve recursively combine But in real systems, problems rarely announce themselves as textbook recurrences. You may see a slow batch job, an expensive query engine, a data-processing task, or a geometric search problem. The challenge is recognizing which part of the work can be decomposed and which part must be combined carefully. How do divide-and-conquer techniques...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.25 Exercises

15.25 Exercises Problem You have learned the main divide-and-conquer patterns in this chapter. To make the techniques usable, you need practice turning a problem statement into: split recursive solution combine proof complexity analysis tests This section gives a set of exercises designed to reinforce the chapter. Each exercise includes the intended pattern, expected complexity, and implementation hints. Treat these as recipes to complete, not as isolated puzzles. Exercise 1: Implement...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.22 Common Bugs

15.22 Common Bugs Problem Divide-and-conquer algorithms often fail in ways that are difficult to see from the high-level design. The recurrence may be correct. The idea may be standard. The code may even work for ordinary examples. Then a small input breaks it: [] [1] [2, 1] [1, 1, 1] or a boundary case causes: infinite recursion missing element duplicate element wrong pivot position stack overflow incorrect count How do...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.4 Quick Sort Revisited

15.4 Quick Sort Revisited Problem Merge sort guarantees (O(n \log n)) performance and stable ordering, but it requires additional memory proportional to the input size. For large datasets, memory allocation and copying can become significant costs. Can we design a divide-and-conquer sorting algorithm that sorts data in place while maintaining excellent practical performance? Solution Use Quick Sort. Quick sort partitions an array around a selected pivot element. After partitioning, all...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.21 Testing Divide-and-Conquer Algorithms

15.21 Testing Divide-and-Conquer Algorithms Problem Divide-and-conquer algorithms are prone to subtle implementation errors. The high-level idea may be correct, but bugs often appear in: base cases split boundaries merge logic pivot handling recursive termination index ranges temporary buffers These bugs may not appear on ordinary examples. A merge sort can pass random tests while failing on duplicates. A binary search can work for most inputs while looping forever on a...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.10 Parallel Divide and Conquer

15.10 Parallel Divide and Conquer Problem Divide-and-conquer algorithms naturally create independent subproblems. Merge sort sorts the left half and right half independently. Quick sort partitions the array and then recursively sorts both sides. Matrix multiplication splits work into independent block products. On a single core, these recursive calls run one after another. On modern hardware, this leaves available CPU cores idle. How can we turn recursive decomposition into parallel execution...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.13 Median of Medians

15.13 Median of Medians Problem Quickselect finds the (k)-th smallest element in expected linear time. In practice, this is often sufficient. Random pivots work well, and the probability of repeatedly choosing poor pivots is low. However, some applications require stronger guarantees. Examples include: real-time systems adversarial inputs security-sensitive software theoretical algorithm analysis worst-case performance guarantees Can we design a selection algorithm that always runs in linear time, regardless of the...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.14 Counting Inversions

15.14 Counting Inversions Problem You need to measure how far an array is from being sorted. Given an array: [2, 4, 1, 3, 5] an inversion is a pair of indexes: $$ i < j $$ such that: $$ a[i] > a[j] $$ In this array, the inversions are: (2, 1) (4, 1) (4, 3) So the inversion count is: 3 A sorted array has zero inversions. A reverse-sorted array...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.19 Correctness Proofs

15.19 Correctness Proofs Problem A divide-and-conquer algorithm may look correct because its structure is simple: split solve recursively combine But many bugs hide in the boundaries: left half right half base case merge step pivot position strip condition A fast algorithm is not useful unless it computes the right result. How do we prove that a divide-and-conquer algorithm is correct? Solution Use induction on input size. Most divide-and-conquer correctness proofs...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.5 Closest Pair of Points

15.5 Closest Pair of Points Problem Given (n) points on a two-dimensional plane, find the pair of points whose Euclidean distance is minimal. For example: Point Coordinates A (2, 3) B (12, 30) C (40, 50) D (5, 1) E (12, 10) F (3, 4) The closest pair is: A(2,3) F(3,4) with distance: $$ \sqrt{(3-2)^2+(4-3)^2} $$ A straightforward solution compares every pair of points. With (n) points: $$ \binom{n}{2} =...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.3 Merge Sort Revisited

15.3 Merge Sort Revisited Problem You need to sort a collection of elements efficiently while preserving the relative order of equal values. The input may already be partially sorted, completely random, or adversarially arranged. Quadratic algorithms such as selection sort, insertion sort, and bubble sort become impractical as input size grows. For an array containing one million elements, an (O(n^2)) algorithm may require trillions of comparisons, while an (O(n \log...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.16 Fast Fourier Transform

15.16 Fast Fourier Transform Problem You need to multiply two polynomials. Example: $$ A(x)=3+2x+5x^2 $$ $$ B(x)=1+4x $$ The product is: $$ C(x)=A(x)B(x) $$ A direct coefficient-by-coefficient multiplication compares every term of (A) with every term of (B). For two polynomials with (n) coefficients, this costs: $$ O(n^2) $$ That is acceptable for small inputs. It is too slow for large signals, big integer arithmetic, convolution, image processing, and many...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.1 Recursion Trees

15.1 Recursion Trees Problem You are given a recursive algorithm and want to determine its time complexity. The implementation repeatedly divides a problem into smaller subproblems, performs some work at each level of recursion, and eventually reaches a base case. A recurrence such as $$ T(n) = 2T\left(\frac{n}{2}\right) + n $$ describes the running time, but the growth rate is not immediately obvious. How can you visualize the work performed...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.18 Closest Pair of Points

15.18 Closest Pair of Points Problem Given (n) points in a plane, find the pair with the smallest Euclidean distance. Example: (2,3) (12,30) (40,50) (5,1) (12,10) (3,4) The closest pair is: (2,3) (3,4) with distance: $$ \sqrt{(3-2)^2+(4-3)^2} = \sqrt{2} $$ A straightforward solution compares every pair of points. point 1 vs point 2 point 1 vs point 3 ... point n-1 vs point n The number of comparisons is: $$...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.6 Karatsuba Multiplication

15.6 Karatsuba Multiplication Problem You need to multiply very large integers. The numbers may contain hundreds, thousands, or millions of digits. The grade-school multiplication algorithm works, but it performs one multiplication for every pair of digits. For two (n)-digit numbers, that gives: $$ O(n^2) $$ single-digit multiplications. For small numbers, this is acceptable. For large integers used in symbolic computation, cryptography, computer algebra, or arbitrary-precision arithmetic, quadratic multiplication becomes expensive....

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.15 Binary Search on Answer

15.15 Binary Search on Answer Problem Some problems ask for an optimal value rather than a specific object. Examples: What is the minimum machine speed needed to finish all jobs within 8 hours? What is the smallest capacity truck that can transport all packages in 5 days? What is the largest minimum distance possible between installed routers? What is the minimum time required for a group of workers to complete...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.23 Design Patterns

15.23 Design Patterns Problem After studying many divide-and-conquer algorithms, they can appear unrelated. Consider: Merge sort Quick sort Quickselect FFT Closest pair of points Karatsuba multiplication Strassen multiplication Binary search Inversion counting Offline query processing The details differ dramatically. Some work on arrays. Some work on geometry. Some work on algebra. Some work on answer spaces rather than data. How do experienced algorithm designers recognize when divide and conquer is...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.2 Master Theorem

15.2 Master Theorem Problem Many divide-and-conquer algorithms produce recurrences of the form $$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$ where: (a) is the number of recursive subproblems. (n/b) is the size of each subproblem. (f(n)) is the non-recursive work performed at each call. For simple recurrences, recursion trees provide an intuitive solution. For larger algorithms, repeatedly constructing trees becomes tedious. Is there a systematic way to solve an entire class of divide-and-conquer recurrences? Solution...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.20 Complexity Analysis

15.20 Complexity Analysis Problem You have a divide-and-conquer algorithm and need to analyze its running time and memory usage. The code may look simple: solve(input) split input solve left solve right combine but the actual cost depends on several details: How many subproblems are created? How large are the subproblems? How expensive is the combine step? How deep is the recursion? How much auxiliary memory is allocated? Are subproblems balanced...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.17 Offline Queries

15.17 Offline Queries Problem You need to answer many queries over a fixed dataset. Example: array = [5, 1, 7, 3, 9, 2] queries: count values <= 4 in range [1, 5] count values <= 6 in range [0, 3] count values <= 8 in range [2, 5] A direct approach handles each query independently. For each range, scan the relevant portion of the array. If there are (q) queries...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.12 Selection Algorithms

15.12 Selection Algorithms Problem You need to find the (k)-th smallest element in an unsorted array. Examples: array = [9, 1, 6, 3, 8, 2, 7] k = 3 The 3rd smallest element is: 3 A simple solution is to sort the array and index into the sorted result. sort.Ints(nums) answer := nums[k-1] This works, but sorting does more work than necessary. Sorting gives the complete order: 1, 2, 3,...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.7 Strassen Multiplication

15.7 Strassen Multiplication Problem Karatsuba's algorithm demonstrates that multiplication can be accelerated by reducing the number of recursive subproblems. The same question naturally arises for matrix multiplication. Given two (n \times n) matrices: $$ A $$ and $$ B $$ the classical algorithm computes: $$ C = AB $$ using three nested loops. For each element: $$ C_{ij} $$ we compute: $$ C_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj} $$ The running time is: $$ O(n^3)...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.8 Fast Exponentiation

15.8 Fast Exponentiation Problem You need to compute: $$ x^n $$ where (n) is a nonnegative integer. The direct method multiplies (x) by itself (n) times: x * x * x * ... * x This takes: $$ O(n) $$ multiplications. For small exponents this is fine. For large exponents, especially in modular arithmetic, cryptography, combinatorics, and numerical code, linear exponentiation is too slow. Can divide and conquer reduce the...

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.9 Divide-and-Conquer Dynamic Programming

15.9 Divide-and-Conquer Dynamic Programming Problem Many dynamic programming algorithms compute a table with the recurrence: $$ dp[i] = \min_{j < i} \left(dp[j] + cost(j,i)\right) $$ A direct implementation evaluates every possible transition. for i for j < i evaluate transition This requires: $$ O(n^2) $$ time. For (n=10^5), quadratic complexity is often too expensive. Even when the recurrence itself is simple, evaluating all possible transition points becomes the dominant cost....

Programming › Algorithm Cookbook › Chapter 15. Divide and Conquer ›

15.11 Cache-Oblivious Algorithms

15.11 Cache-Oblivious Algorithms Problem An algorithm can have good asymptotic complexity and still run poorly on real hardware. Modern machines do not access all memory at the same speed. Data may live in registers, L1 cache, L2 cache, L3 cache, main memory, or disk. Moving data between these levels can cost more than arithmetic. A conventional algorithm often assumes this model: memory access costs O(1) Real machines behave more like...

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951E - No Palindromes

CF 1951E - No Palindromes Rating: 2000 Tags: brute force, constructive algorithms, divide and conquer, greedy, hashing, implementation, math, strings Solve time: 1m 1s Verified: no Solution Problem Understanding We are given a string and we are allowed to cut it into contiguous pieces. The goal is to decide whether we can cut it so that every resulting piece is not a palindrome. If it is possible, we must also...

Practice › Codeforces Solutions › Educational Codeforces Round 166 (Rated for Div. 2) ›

CF 1976D - Invertible Bracket Sequences

CF 1976D - Invertible Bracket Sequences Rating: 2000 Tags: binary search, combinatorics, data structures, divide and conquer, implementation, two pointers Solve time: 5m 14s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 274 (Div. 1) ›

CF 480E - Parking Lot

CF 480E - Parking Lot Rating: 2800 Tags: data structures, divide and conquer Solve time: 5m 24s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 939 (Div. 2) ›

CF 1956D - Nene and the Mex Operator

CF 1956D - Nene and the Mex Operator Rating: 2000 Tags: bitmasks, brute force, constructive algorithms, divide and conquer, dp, greedy, implementation, math Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a short array of length at most 18. The only allowed move is to pick a contiguous segment, compute the mex of that segment, and overwrite the entire segment with that mex value. This operation...

Practice › Codeforces Solutions › Codeforces Round 947 (Div. 1 + Div. 2) ›

CF 1975F - Set

CF 1975F - Set Rating: 2600 Tags: bitmasks, brute force, combinatorics, dfs and similar, divide and conquer, dp, math Solve time: 5m 17s Verified: no Solution

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3864 - Minimum Cost to Partition a Binary String

LeetCode Problem 3864 Difficulty: 🔴 Hard Topics: String, Divide and Conquer, Prefix Sum Solution LeetCode 3864 - Minimum Cost to Partition a Binary String Problem Understanding We are given a binary string s , where each character represents whether an element is sensitive: '1' means the element is sensitive. '0' means the element is not sensitive. The entire string initially forms one segment. Every segment has a storage cost that...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3855 - Sum of K-Digit Numbers in a Range

LeetCode Problem 3855 Difficulty: 🔴 Hard Topics: Math, Divide and Conquer, Combinatorics, Number Theory Solution LeetCode 3855 - Sum of K-Digit Numbers in a Range Problem Understanding We are given three integers l , r , and k . For every digit position, we may independently choose any digit from the inclusive range [l, r] . We then form all possible numbers consisting of exactly k digits. A key detail...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3759 - Count Elements With at Least K Greater Values

LeetCode Problem 3759 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Sorting, Quickselect Solution Problem Understanding The problem asks us to count how many elements in an array have at least k values that are strictly greater than them. More concretely, for every element nums[i] , we need to determine how many numbers in the array are larger than nums[i] . If that count is at least k...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3841 - Palindromic Path Queries in a Tree

LeetCode Problem 3841 Difficulty: 🔴 Hard Topics: Array, String, Divide and Conquer, Tree, Segment Tree Solution LeetCode 3841: Palindromic Path Queries in a Tree Problem Understanding We are given a tree with n nodes. Each node stores a lowercase English letter. The tree is undirected and connected, so there is exactly one simple path between any two nodes. The problem supports two kinds of operations: Update Change the character assigned...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3749 - Evaluate Valid Expressions

LeetCode Problem 3749 Difficulty: 🔴 Hard Topics: Hash Table, Math, String, Divide and Conquer, Stack Solution Problem Understanding The problem presents a simplified version of evaluating nested mathematical expressions in string format. The input expression is either a single integer literal, which may be negative, or a nested operation of the form op(a,b) where op is one of the four basic arithmetic operations: add , sub , mul , or...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3826 - Minimum Partition Score

LeetCode Problem 3826 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Prefix Sum, Monotonic Queue Solution LeetCode 3826 - Minimum Partition Score Problem Understanding We are given an array nums and must divide it into exactly k contiguous subarrays. For every subarray, we first compute its sum: $$\text{sumArr} = \sum \text{elements in the subarray}$$ Its value is then defined as: $$\text{value} = \frac{\text{sumArr} \cdot (\text{sumArr}+1)}{2}$$ The score...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3739 - Count Subarrays With Majority Element II

LeetCode Problem 3739 Difficulty: 🔴 Hard Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Prefix Sum Solution Here’s a complete, detailed technical solution guide for LeetCode 3739 - Count Subarrays With Majority Element II following your requested format. Problem Understanding The problem asks us to count the number of contiguous subarrays in which a given target element is the majority element . A majority element is one...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3737 - Count Subarrays With Majority Element I

LeetCode Problem 3737 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Counting, Prefix Sum Solution Here is a comprehensive, detailed reference guide for LeetCode 3737 - Count Subarrays With Majority Element I , following your formatting requirements exactly. Problem Understanding The problem provides an integer array nums and a target integer. The goal is to count the number of subarrays in which the target...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3721 - Longest Balanced Subarray II

LeetCode Problem 3721 Difficulty: 🔴 Hard Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Prefix Sum Solution Problem Understanding The problem requires us to find the length of the longest subarray in an integer array nums where the count of distinct even numbers equals the count of distinct odd numbers . A subarray is a contiguous section of the array, and “distinct” means that duplicate values are counted only...

Practice › Codeforces Solutions ›

Codeforces Round 274 (Div. 1)

Codeforces Round 274 (Div. 1) Div. 1 | 2 problems | 1/2 verified | Difficulty 2600-2800 | 7m 16s # Problem Rating Tags Accepted Time ✓ D Parcels 2600 dp, graphs 492 1m 52s ✓ E Parking Lot 2800 data-structures, divide-and-conquer 640 5m 24s

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3655 - XOR After Range Multiplication Queries II

LeetCode Problem 3655 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer Solution Problem Understanding We are given an array nums and a list of queries. Each query has the form: [li, ri, ki, vi] For a query, we start at index li and repeatedly jump forward by ki until we pass ri . Every visited position is multiplied by vi , and the result is taken modulo 10^9 + 7...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3653 - XOR After Range Multiplication Queries I

LeetCode Problem 3653 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Simulation Solution LeetCode 3653 - XOR After Range Multiplication Queries I Problem Understanding We are given an integer array nums and a list of queries. Each query has the form: [li, ri, ki, vi] For a query, we start at index li and repeatedly move forward by ki positions until we exceed ri . Every visited index is updated...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3636 - Threshold Majority Queries

LeetCode Problem 3636 Difficulty: 🔴 Hard Topics: Array, Hash Table, Binary Search, Divide and Conquer, Counting, Prefix Sum Solution Problem Understanding The problem asks us to process multiple queries on a given array nums where each query specifies a subarray defined by [li, ri] and a threshold . For each query, we need to find an element in the subarray that appears at least threshold times. If multiple elements meet...

Practice › Codeforces Solutions › Codeforces Round 261 (Div. 2) ›

CF 459D - Pashmak and Parmida's problem

CF 459D - Pashmak and Parmida's problem Rating: 1800 Tags: data structures, divide and conquer, sortings Solve time: 2m 17s Verified: yes Solution Problem Understanding We are given an array a[1..n] . For every position i , define the value L[i] = number of occurrences of a[i] in the prefix [1..i] . For every position j , define R[j] = number of occurrences of a[j] in the suffix [j..n] ....

Practice › Codeforces Solutions ›

Codeforces Round 240 (Div. 1)

Codeforces Round 240 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1400-3200 | 8m 52s # Problem Rating Tags Accepted Time ✓ A Mashmokh and Numbers 1500 constructive-algorithms, number-theory 10,565 2m 6s B Mashmokh and ACM 1400 combinatorics, dp, number-theory 29,163 1m 21s ✓ C Mashmokh and Reverse Operation 2100 combinatorics, divide-and-conquer 2,359 1m 40s ✓ D Mashmokh and Water Tanks 2300 binary-search, data-structures, greedy 748...

Practice › Codeforces Solutions ›

Codeforces Round 256 (Div. 2)

Codeforces Round 256 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 800-2200 | 7m 28s # Problem Rating Tags Accepted Time ✓ A Rewards 800 implementation 25,900 1m 14s ✓ B Suffix Structures 1400 implementation, strings 17,313 1m 44s ✓ C Painting Fence 1900 divide-and-conquer, dp, greedy 10,790 1m 31s ✓ D Multiplication Table 1800 binary-search, brute-force 16,661 1m 14s ✓ E Divisors 2200 brute-force, dfs-and-similar,...

Practice › LeetCode › LeetCode 27xx ›

LeetCode 2792 - Count Nodes That Are Great Enough

LeetCode Problem 2792 Difficulty: 🔴 Hard Topics: Divide and Conquer, Tree, Depth-First Search, Binary Tree Solution Problem Understanding The problem gives us the root of a binary tree and an integer k . We must determine how many nodes in the tree are considered "great enough". A node is great enough if two conditions are satisfied: Its subtree contains at least k nodes. Its value is greater than the values...

Practice › Codeforces Solutions › Codeforces Round 245 (Div. 1) ›

CF 429D - Tricky Function

CF 429D - Tricky Function Rating: 2200 Tags: data structures, divide and conquer, geometry Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given an array of integers a with n elements. The task is to select two distinct indices i and j and compute a function f(i, j) that combines both the squared distance between the indices and the squared sum of the elements strictly between them....

Practice › Codeforces Solutions › Codeforces Round 114 (Div. 1) ›

CF 167D - Wizards and Roads

CF 167D - Wizards and Roads Rating: 3000 Tags: data structures, divide and conquer, graph matchings, graphs, greedy Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a set of cities on the plane. Every city has a unique x coordinate and a unique y coordinate. The first k cities are given explicitly, and the remaining cities are generated by two linear recurrences. For every query interval...

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2613 - Beautiful Pairs

LeetCode Problem 2613 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Ordered Set Solution Problem Understanding The problem asks us to find a beautiful pair of indices (i, j) in two integer arrays nums1 and nums2 of equal length. A pair (i, j) is beautiful if it minimizes the sum of the absolute differences between the corresponding elements: |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| among all...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 1) ›

CF 196C - Paint Tree

CF 196C - Paint Tree Rating: 2200 Tags: constructive algorithms, divide and conquer, geometry, sortings, trees Solve time: 1m 40s Verified: no Solution Problem Understanding We are asked to embed a tree onto a set of points on a plane in such a way that tree edges correspond to straight line segments connecting the points. Each vertex of the tree must be mapped to a distinct point, and for any...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2343 - Query Kth Smallest Trimmed Number

LeetCode Problem 2343 Difficulty: 🟡 Medium Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Radix Sort, Quickselect Solution Problem Understanding This problem provides a list of numbers represented as strings, all of equal length. The task is to answer multiple queries, where each query asks for the index of the k-th smallest number after trimming every number in the list to its last trimi digits. Importantly, if two...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2407 - Longest Increasing Subsequence II

LeetCode Problem 2407 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Dynamic Programming, Binary Indexed Tree, Segment Tree, Queue, Monotonic Queue Solution Problem Understanding The problem asks us to find the length of the longest subsequence in an integer array nums such that the subsequence is strictly increasing and the difference between consecutive elements does not exceed a given integer k . A subsequence is formed by deleting zero or...

Practice › Codeforces Solutions › Codeforces Round 240 (Div. 1) ›

CF 414C - Mashmokh and Reverse Operation

CF 414C - Mashmokh and Reverse Operation Rating: 2100 Tags: combinatorics, divide and conquer Solve time: 1m 40s Verified: yes Solution Problem Understanding We are given an array of length $2^n$, where $n$ is at most 20, and a sequence of queries. Each query specifies a number $q_i$, which tells us to repeatedly split the array into blocks of size $2^{q_i}$, reverse each block, and then join the blocks back...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3109 - Find the Index of Permutation

LeetCode Problem 3109 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem gives us a permutation perm of the integers [1, 2, ..., n] . A permutation is simply an arrangement of all numbers from 1 to n where each number appears exactly once. We are asked to determine the lexicographic index of this permutation...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3165 - Maximum Sum of Subsequence With Non-adjacent Elements

LeetCode Problem 3165 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Dynamic Programming, Segment Tree Solution LeetCode 3165 - Maximum Sum of Subsequence With Non-adjacent Elements Problem Understanding This problem asks us to process a sequence of update queries on an array. After each update, we must compute the maximum possible sum of a subsequence where no two selected elements are adjacent in the array. The key detail is that...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2519 - Count the Number of K-Big Indices

LeetCode Problem 2519 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 2519 - Count the Number of K-Big Indices Problem Understanding This problem asks us to determine how many indices in an array satisfy a very specific condition related to smaller values on both sides. For an index i to be considered k-big , two separate requirements...

Practice › Codeforces Solutions › VK Cup 2012 Round 1 ›

CF 161C - Abracadabra

CF 161C - Abracadabra Rating: 2400 Tags: divide and conquer Solve time: 2m 37s Verified: yes Solution Problem Understanding The infinite string in this problem is built recursively. Start with: S1 = "a" S2 = "aba" S3 = "abacaba" S4 = "abacabadabacaba" In general: Sk = Sk-1 + kth_character + Sk-1 The alphabet contains 36 symbols: a..z, 0..9 The full string after 30 steps has length: $|S_k| = 2^k -...

Practice › Codeforces Solutions › Coder-Strike 2014 - Round 2 ›

CF 413E - Maze 2D

CF 413E - Maze 2D Rating: 2200 Tags: data structures, divide and conquer Solve time: 1m 21s Verified: yes Solution Problem Understanding We are working on a very narrow grid: only two rows, but a large number of columns. Each cell in this 2 by n strip is either free or blocked. Movement is allowed only between side-adjacent free cells, so the grid naturally forms a graph where each cell...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2179 - Count Good Triplets in an Array

LeetCode Problem 2179 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding In this problem, we are given two arrays, nums1 and nums2 , each containing every integer from 0 to n - 1 exactly once. In other words, both arrays are permutations of the same set of values. We need to count how many triplets (x,...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1985 - Find the Kth Largest Integer in the Array

LeetCode Problem 1985 Difficulty: 🟡 Medium Topics: Array, String, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding This problem asks us to find the kth largest value among a list of integers that are represented as strings. Each element in nums is a non-negative integer encoded as a string with no leading zeros, and we are required to return the kth largest value according to numeric order,...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2426 - Number of Pairs Satisfying Inequality

LeetCode Problem 2426 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 2426 - Number of Pairs Satisfying Inequality Problem Understanding We are given two integer arrays, nums1 and nums2 , of the same length n , along with an integer diff . We must count how many index pairs (i, j) satisfy both: i < j nums1[i]...

Practice › Codeforces Solutions › Codeforces Round 107 (Div. 1) ›

CF 150E - Freezing with Style

CF 150E - Freezing with Style Rating: 3000 Tags: binary search, data structures, divide and conquer, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We are given a tree with n junctions and n - 1 roads. Every road has an integer beauty value. We must choose two junctions so that the path between them contains between l and r edges inclusive. Among all such paths, we want...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Finals

Yandex.Algorithm 2011: Finals Special | 5 problems | 4/5 verified | Difficulty 2200-2700 | 11m 24s # Problem Rating Tags Accepted Time ✓ A Domino 2400 brute-force, implementation 335 2m 46s B Superset 2300 constructive-algorithms, divide-and-conquer 1,000 2m 12s ✓ C Winning Strategy 2400 binary-search, graphs, math 354 1m 44s ✓ D Robot in Basement 2700 bitmasks, brute-force, implementation 290 2m 39s ✓ E Leaders 2200 dfs-and-similar, dsu, graphs 429...

Practice › Codeforces Solutions ›

Codeforces Beta Round 62

Codeforces Beta Round 62 Beta | 5 problems | 5/5 verified | Difficulty 1100-2900 | 26m 18s # Problem Rating Tags Accepted Time ✓ A Irrational problem 1100 implementation, number-theory 5,362 7m 4s ✓ B Energy exchange 1600 binary-search 5,578 7m 4s ✓ C Synchrophasotron 2200 brute-force 353 7m 3s ✓ D Half-decay tree 2500 data-structures, divide-and-conquer, dp 531 2m 50s ✓ E Contact 2900 geometry 84 2m 17s ✓

Practice › LeetCode › LeetCode 09xx ›

LeetCode 973 - K Closest Points to Origin

LeetCode Problem 973 Difficulty: 🟡 Medium Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding This problem asks us to find the k points that are closest to the origin (0,0) from a list of 2D points. Each point is given as a pair [x, y] , and the distance is defined using the Euclidean formula, sqrt(x^2 + y^2) . The input consists of...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal

LeetCode Problem 105 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree Solution Problem Understanding The problem is asking us to reconstruct a binary tree given two traversal orders: preorder and inorder . In a preorder traversal, nodes are visited in the order: root, left subtree, right subtree. In an inorder traversal, nodes are visited in the order: left subtree, root, right subtree. Given these two...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 148 - Sort List

LeetCode Problem 148 Difficulty: 🟡 Medium Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort Solution Problem Understanding The problem asks us to sort a singly linked list in ascending order and return the head of the sorted list. The input is the head node of a linked list. Each node contains an integer value and a pointer to the next node. Unlike arrays, linked lists do not...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 347 - Top K Frequent Elements

LeetCode Problem 347 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect Solution Problem Understanding The problem asks us to return the k most frequently occurring elements from an integer array. We are given an array nums , which may contain duplicates, and an integer k . Our task is to identify which values appear most often and return exactly k...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117E - Tree or not Tree

CF 117E - Tree or not Tree Rating: 2900 Tags: data structures, divide and conquer, graphs, implementation, trees Solve time: 3m 13s Verified: yes Solution Problem Understanding The graph has exactly n vertices and n edges. A connected graph with n vertices and n edges contains exactly one simple cycle. Every other edge belongs to a tree attached to that cycle. Initially every edge is turned off. A query picks...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 240 - Search a 2D Matrix II

LeetCode Problem 240 Difficulty: 🟡 Medium Topics: Array, Binary Search, Divide and Conquer, Matrix Solution Problem Understanding The problem asks us to determine whether a given integer target exists inside an m x n matrix. Unlike a completely unsorted matrix, this matrix has two important ordering guarantees: Each row is sorted in ascending order from left to right. Each column is sorted in ascending order from top to bottom. We...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1738 - Find Kth Largest XOR Coordinate Value

LeetCode Problem 1738 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Bit Manipulation, Sorting, Heap (Priority Queue), Matrix, Prefix Sum, Quickselect Solution Problem Understanding The problem asks us to compute the XOR coordinate value for each element in a given 2D matrix and then find the kth largest among them. Specifically, for a coordinate (a, b) , the value is defined as the XOR of all elements in the submatrix...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1756 - Design Most Recently Used Queue

LeetCode Problem 1756 Difficulty: 🟡 Medium Topics: Array, Linked List, Divide and Conquer, Design, Simulation, Doubly-Linked List Solution Problem Understanding The problem asks us to design a special queue called an "Most Recently Used Queue", abbreviated as MRUQueue. Initially, the queue contains the integers from 1 to n in increasing order. The key operation is fetch(k) , where k is 1-indexed. This operation does two things: It finds the kth...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1763 - Longest Nice Substring

LeetCode Problem 1763 Difficulty: 🟢 Easy Topics: Hash Table, String, Divide and Conquer, Bit Manipulation, Sliding Window Solution Problem Understanding The problem asks us to find the longest "nice" substring within a given string s . A substring is considered nice if for every letter it contains, both its lowercase and uppercase forms appear. For example, "aAa" is nice because it contains 'a' and 'A' . Conversely, "abA" is not...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 108 - Convert Sorted Array to Binary Search Tree

LeetCode Problem 108 Difficulty: 🟢 Easy Topics: Array, Divide and Conquer, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us a sorted integer array nums in strictly increasing order and asks us to convert it into a height-balanced binary search tree (BST) . A binary search tree is a binary tree where: Every node in the left subtree contains values smaller than the current node. Every...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 215 - Kth Largest Element in an Array

LeetCode Problem 215 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect Solution Problem Understanding The problem asks us to find the kth largest element in an unsorted integer array. The important detail is that we are looking for the element that would appear in the kth position if the array were sorted in descending order. We are not looking for the kth distinct value. For...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 218 - The Skyline Problem

LeetCode Problem 218 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Sweep Line, Sorting, Heap (Priority Queue), Ordered Set Solution Problem Understanding The Skyline Problem asks us to compute the visible outer contour formed by a collection of rectangular buildings when viewed from far away. Each building is represented by three integers: a left x-coordinate, a right x-coordinate, and a height. The buildings sit on...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 493 - Reverse Pairs

LeetCode Problem 493 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to count how many pairs of indices (i, j) satisfy two conditions: i < j nums[i] > 2 * nums[j] These pairs are called reverse pairs. Unlike the classic inversion count problem, where we check whether nums[i] > nums[j] , this...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1274 - Number of Ships in a Rectangle

LeetCode Problem 1274 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Interactive Solution Problem Understanding The problem presents an interactive scenario where ships are placed at integer coordinates on a Cartesian plane. You do not know their positions, and each coordinate contains at most one ship. You are given two points representing the bottom-left and top-right corners of a rectangle, and you need to determine the number of ships contained...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 307 - Range Sum Query - Mutable

LeetCode Problem 307 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Design, Binary Indexed Tree, Segment Tree Solution Problem Understanding The problem asks us to design a mutable range sum data structure. We are given an integer array nums , and we must efficiently support two operations: Updating the value at a specific index. Querying the sum of elements within a range [left, right] . The important detail is that...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 918 - Maximum Sum Circular Subarray

LeetCode Problem 918 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue Solution Problem Understanding The problem asks for the maximum sum of a subarray in a circular array . In simpler terms, we are given a list of integers nums where the end of the list wraps around to the start. We need to find a contiguous section of this list that has the highest...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1649 - Create Sorted Array through Instructions

LeetCode Problem 1649 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to simulate building a sorted array incrementally. We process the instructions array from left to right, and for each value, we insert it into a container called nums while maintaining sorted order. However, the actual insertion is not the difficult part....

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode Problem 1569 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union-Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree Solution Problem Understanding The problem gives us a permutation of integers from 1 to n , and we insert the numbers into an initially empty Binary Search Tree (BST) in the exact order they appear in the array. A BST has the following property: Values smaller than...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 427 - Construct Quad Tree

LeetCode Problem 427 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Tree, Matrix Solution Problem Understanding The problem asks us to convert a binary matrix into a Quad-Tree representation. A Quad-Tree is a recursive tree structure where every internal node has exactly four children, each representing one quadrant of the current square region. The input is an n x n matrix called grid , where every value is either 0...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 109 - Convert Sorted List to Binary Search Tree

LeetCode Problem 109 Difficulty: 🟡 Medium Topics: Linked List, Divide and Conquer, Tree, Binary Search Tree, Binary Tree Solution Problem Understanding The problem gives us the head of a singly linked list whose values are already sorted in ascending order. We must convert this linked list into a height balanced Binary Search Tree, usually abbreviated as BST. A Binary Search Tree has the property that: Every node in the left...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 106 - Construct Binary Tree from Inorder and Postorder Traversal

LeetCode Problem 106 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree Solution Problem Understanding The problem provides two traversal orders of the same binary tree: inorder , which follows the order: left subtree, root, right subtree postorder , which follows the order: left subtree, right subtree, root We must reconstruct the original binary tree and return its root node. The key challenge is understanding how...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 53 - Maximum Subarray

LeetCode Problem 53 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Dynamic Programming Solution LeetCode 53, Maximum Subarray Problem Understanding The problem gives an integer array nums and asks us to find a contiguous subarray that has the largest possible sum. A subarray means the elements must appear next to each other in the original array. We are not allowed to rearrange elements or skip positions arbitrarily. The output is...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 23 - Merge k Sorted Lists

LeetCode Problem 23 Difficulty: 🔴 Hard Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort Solution Problem Understanding The problem gives us an array of k sorted linked lists. Each linked list is already sorted in ascending order, and our task is to combine all of them into one single sorted linked list. A linked list node contains a value and a pointer to the next node. The...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1382 - Balance a Binary Search Tree

LeetCode Problem 1382 Difficulty: 🟡 Medium Topics: Divide and Conquer, Greedy, Tree, Depth-First Search, Binary Search Tree, Binary Tree Solution Here is a complete, detailed technical solution guide for LeetCode 1382 - Balance a Binary Search Tree , following all your formatting rules. Problem Understanding The problem asks us to take a binary search tree (BST) that may be unbalanced and produce a new BST that is balanced while preserving...

Practice › Codeforces Solutions › Codeforces Beta Round 88 ›

CF 117D - Not Quick Transformation

CF 117D - Not Quick Transformation Rating: 2500 Tags: divide and conquer, math Solve time: 2m 20s Verified: yes Solution Problem Understanding We start with the array [1, 2, 3, ..., n] . A recursive transformation rearranges it by repeatedly taking all elements at odd positions, transforming that subarray, then taking all elements at even positions and transforming that subarray. For example: F([1,2,3,4,5,6,7,8]) becomes F([1,3,5,7]) + F([2,4,6,8]) and each half...

Practice › Codeforces Solutions › Codeforces Beta Round 19 ›

CF 19E - Fairy

CF 19E - Fairy Rating: 2900 Tags: dfs and similar, divide and conquer, dsu Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given an undirected graph. Each edge represents a segment drawn between two points. We may erase exactly one edge, and after removing it we want the remaining graph to become bipartite. A graph is bipartite if we can color every vertex using two colors such...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 169 - Majority Element

LeetCode Problem 169 Difficulty: 🟢 Easy Topics: Array, Hash Table, Divide and Conquer, Sorting, Counting Solution Problem Understanding The problem asks us to identify the majority element in a given array of integers nums . The majority element is defined as the number that appears more than half of the times in the array, i.e., more than ⌊n / 2⌋ times where n is the length of the array. The...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 558 - Logical OR of Two Binary Grids Represented as Quad-Trees

LeetCode Problem 558 Difficulty: 🟡 Medium Topics: Divide and Conquer, Tree Solution Problem Understanding This problem gives us two Quad-Trees, where each tree represents a binary matrix containing only 0 s and 1 s. Our goal is to compute the logical bitwise OR of the two matrices and return the result as another Quad-Tree. A Quad-Tree is a recursive spatial data structure. Every node represents a square region of the...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 324 - Wiggle Sort II

LeetCode Problem 324 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Greedy, Sorting, Quickselect Solution Problem Understanding The problem asks us to rearrange an array so that it follows a strict alternating pattern: nums[0] < nums[1] nums[1] > nums[2] nums[2] < nums[3] and so on. This pattern is called a wiggle sequence because the values repeatedly go up and down. The input is an integer array nums , and we...

Practice › Codeforces Solutions › Codeforces Beta Round 62 ›

CF 68D - Half-decay tree

CF 68D - Half-decay tree Rating: 2500 Tags: data structures, divide and conquer, dp, math, probabilities Solve time: 2m 50s Verified: yes Solution Problem Understanding We have a complete binary tree of height h . Every vertex may store some number of electrons, and queries gradually add more electrons to vertices. A decay operation chooses one leaf uniformly at random and deletes every edge on the path from the root...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 889 - Construct Binary Tree from Preorder and Postorder Traversal

LeetCode Problem 889 Difficulty: 🟡 Medium Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree Solution Problem Understanding The problem gives us two traversal orders of the same binary tree: preorder , which visits nodes in the order: root → left subtree → right subtree postorder , which visits nodes in the order: left subtree → right subtree → root Our task is to reconstruct and return the binary...

Practice › Codeforces Solutions › School Regional Team Contest, Saratov, 2011 ›

CF 120J - Minimum Sum

CF 120J - Minimum Sum Rating: 1900 Tags: divide and conquer, geometry, sortings Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a set of points in two-dimensional space, where each point can be thought of as a vector from the origin. Each vector has two coordinates, x and y , and we are allowed to independently flip the sign of each coordinate. That is, for any...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Finals ›

CF 97B - Superset

CF 97B - Superset Rating: 2300 Tags: constructive algorithms, divide and conquer Solve time: 2m 12s Verified: yes Solution Problem Understanding We start with a set of distinct lattice points on the plane. We may add more points, and the final set must satisfy a geometric condition for every pair of points. Take any two points. If they already share the same x-coordinate or the same y-coordinate, they are automatically...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 654 - Maximum Binary Tree

LeetCode Problem 654 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Stack, Tree, Monotonic Stack, Binary Tree Solution Problem Understanding The problem asks us to construct a maximum binary tree from a given integer array nums with unique elements. A maximum binary tree is a binary tree where each node is the maximum element of the subarray it represents. Specifically, the root of the tree is the largest element in...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 372 - Super Pow

LeetCode Problem 372 Difficulty: 🟡 Medium Topics: Math, Divide and Conquer Solution Problem Understanding The problem asks us to compute: $a^b \bmod 1337$ The complication is that the exponent b is extremely large. Instead of being given as a normal integer, it is provided as an array of digits. For example, if: b = [1, 0, 2, 4] then the exponent actually represents the number: 1024 The goal is to...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 395 - Longest Substring with At Least K Repeating Characters

LeetCode Problem 395 Difficulty: 🟡 Medium Topics: Hash Table, String, Divide and Conquer, Sliding Window Solution Problem Understanding The problem asks us to find the length of the longest substring in which every character appears at least k times. A substring is a contiguous sequence of characters inside the original string. For any candidate substring, we must verify that every distinct character inside that substring has frequency greater than or...

Practice › Codeforces Solutions › Codeforces Beta Round 79 (Div. 1 Only) ›

CF 101E - Candies and Stones

CF 101E - Candies and Stones Rating: 2500 Tags: divide and conquer, dp Solve time: 3m 26s Verified: no Solution Problem Understanding Gerald repeatedly removes either one candy or one stone. After every move, Mike looks at how many candies and stones Gerald has already eaten. If Gerald has eaten a candies and b stones so far, Mike awards $$f(a,b) = (x_a + y_b) \bmod p$$ points. The game starts...

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2031 - Count Subarrays With More Ones Than Zeros

LeetCode Problem 2031 Difficulty: 🟡 Medium Topics: Array, Hash Table, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding This problem asks us to count all subarrays of a binary array nums that contain more 1 s than 0 s. In other words, for any contiguous slice of the array, if the number of 1 s exceeds the number of 0 s,...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 912 - Sort an Array

LeetCode Problem 912 Difficulty: 🟡 Medium Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort Solution Problem Understanding The problem asks us to sort an integer array in ascending order without using any built in sorting functions. The result must contain the same elements as the input, but arranged from smallest to largest. The input is an array nums containing integers. These...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 315 - Count of Smaller Numbers After Self

LeetCode Problem 315 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution Problem Understanding The problem asks us to compute, for every element in the array, how many elements to its right are strictly smaller than it. Given an array nums , we must return another array counts of the same length. For each index i , counts[i] represents...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 932 - Beautiful Array

LeetCode Problem 932 Difficulty: 🟡 Medium Topics: Array, Math, Divide and Conquer Solution Problem Understanding The problem asks us to construct a permutation of the integers from 1 to n such that the array satisfies a special condition. Specifically, for every pair of indices i < j , there must not exist any index k between them where: $2 \cdot nums[k] = nums[i] + nums[j]$ This condition means that no...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 327 - Count of Range Sum

LeetCode Problem 327 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set Solution LeetCode 327 - Count of Range Sum Problem Understanding This problem asks us to count how many subarrays have sums that fall within a given inclusive range [lower, upper] . A range sum S(i, j) represents the sum of all elements from index i through index j...

Practice › Codeforces Solutions › Codeforces Beta Round 9 (Div. 2 Only) ›

CF 9D - How many trees?

CF 9D - How many trees? Rating: 1900 Tags: combinatorics, divide and conquer, dp Solve time: 1m 13s Verified: yes Solution Problem Understanding We are asked to count the number of distinct binary search trees (BSTs) that have exactly n nodes labeled from 1 to n , with the additional constraint that the height of each tree is at least h . Height here is defined as the number of...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 761 - Special Binary String

LeetCode Problem 761 Difficulty: 🔴 Hard Topics: String, Divide and Conquer, Sorting Solution Problem Understanding The problem asks us to manipulate a special binary string to produce the lexicographically largest possible string. A special binary string has two properties: it contains equal numbers of 1 s and 0 s, and at every point in the string, the number of 1 s is at least as many as the number of...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 4 - Median of Two Sorted Arrays

LeetCode Problem 4 Difficulty: 🔴 Hard Topics: Array, Binary Search, Divide and Conquer Solution Median of Two Sorted Arrays Problem Understanding The problem gives two individually sorted integer arrays, nums1 and nums2 , with lengths m and n . The task is to compute the median of the combined sorted sequence formed by merging both arrays. The median is the middle value of a sorted sequence. If the total number...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 191 - Number of 1 Bits

LeetCode Problem 191 Difficulty: 🟢 Easy Topics: Divide and Conquer, Bit Manipulation Solution Problem Understanding The problem asks us to count how many bits are set to 1 in the binary representation of a positive integer n . A set bit is simply a bit whose value is 1 . For example, the number 11 in binary is: 1011 This binary representation contains three 1 bits, so the answer is...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 190 - Reverse Bits

LeetCode Problem 190 Difficulty: 🟢 Easy Topics: Divide and Conquer, Bit Manipulation Solution Problem Understanding The problem asks us to reverse the binary representation of a 32-bit integer . Instead of reversing the decimal digits of a number, we reverse the order of its individual bits. For example, suppose the binary representation of a number is: 00000010100101000001111010011100 After reversing all 32 bits, it becomes: 00111001011110000010100101000000 The resulting reversed binary value...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

Problem Restatement We are given the preorder traversal of a binary search tree (BST) in an array preorder . We need to reconstruct the BST and return its root. Recall that in a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. In preorder traversal, we visit the root before the left and right subtrees. The official constraints...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal

Problem Restatement We are given two arrays: Array Meaning preorder Preorder traversal of a binary tree postorder Postorder traversal of the same binary tree The binary tree contains distinct values. We need to reconstruct and return one possible binary tree. If multiple valid trees exist, returning any one of them is accepted. The problem guarantees that both traversals come from the same binary tree. Preorder traversal visits nodes in this...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 912: Sort an Array

Problem Restatement We are given an integer array nums . Return the array sorted in ascending order. The problem requires solving this without using built-in sorting functions, in O(n log n) time, with as little extra space as possible. Input and Output Item Meaning Input An integer array nums Output The same values sorted in ascending order Restriction Do not use built-in sorting functions Target time O(n log n) Function...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 761: Special Binary String

Problem Restatement A special binary string is a binary string with two properties: It has the same number of 1 s and 0 s. Every prefix has at least as many 1 s as 0 s. We are given a special binary string s . One move lets us choose two consecutive non-empty special substrings and swap them. We need to return the lexicographically largest string possible after applying any...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 932: Beautiful Array

Problem Restatement We are given an integer n . We need to return any array nums of length n such that: nums is a permutation of integers from 1 to n . For every i < j , there is no index k with i < k < j such that: 2 * nums[k] == nums[i] + nums[j] In other words, no middle-position value may be the arithmetic average of...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 654: Maximum Binary Tree

Problem Restatement We are given an array of distinct integers called nums . We must construct a binary tree using the following rules: The root is the maximum number in the array. The left subtree is built recursively from the elements to the left of the maximum number. The right subtree is built recursively from the elements to the right of the maximum number. Return the root of the constructed...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 395: Longest Substring with At Least K Repeating Characters

Problem Restatement We are given a string s and an integer k . We need to return the length of the longest substring where every character in that substring appears at least k times. A substring must be contiguous. If no valid substring exists, return 0 . The string contains only lowercase English letters. The length of s is at most 10^4 , and k can be larger than the...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 493: Reverse Pairs

Problem Restatement We are given an integer array nums . We need to count pairs of indices (i, j) such that: 0 <= i < j < nums.length and: nums[i] > 2 * nums[j] These are called reverse pairs. The input length can be up to 5 * 10^4 , and values may be negative or as large as 32-bit signed integers. Input and Output Item Meaning Input Integer array...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 241: Different Ways to Add Parentheses

Problem Restatement We are given a string expression containing: Non-negative integers Operators: + - * We need to compute all possible results from adding parentheses in every valid way. The answer may contain duplicate values if different parenthesizations produce the same result. LeetCode examples include: Input: expression = "2-1-1" Output: [0,2] and: Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10] The expression length is at most 20 . Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 215: Kth Largest Element in an Array

Problem Restatement We are given an integer array nums and an integer k . We need to return the k th largest element in the array. Important detail: this means the k th largest element in sorted order, not the k th distinct element. Duplicates count separately. The official constraints are 1 <= k <= nums.length <= 10^5 and -10^4 <= nums[i] <= 10^4 . Input and Output Item Meaning...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 148: Sort List

Problem Restatement We are given the head of a singly linked list. Return the list after sorting it in ascending order. The problem asks for an O(n log n) time solution. The follow-up asks whether we can sort the list with constant extra space. The number of nodes is in the range [0, 5 * 10^4] , and node values are between -10^5 and 10^5 . Examples Example 1: head...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 169: Majority Element

Problem Restatement We are given an integer array nums of size n . We need to return the majority element. The majority element is the value that appears more than: n // 2 times. The problem guarantees that a majority element always exists. LeetCode also asks whether we can solve it in linear time and constant extra space. Input and Output Item Meaning Input Integer array nums Output The majority...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 109: Convert Sorted List to Binary Search Tree

Problem Restatement We are given the head of a singly linked list whose values are sorted in ascending order. We need to convert this sorted linked list into a height-balanced binary search tree. The official problem defines a height-balanced binary tree as a binary tree where the depth difference between the two subtrees of every node never exceeds 1 . The resulting tree must satisfy the BST property: left subtree...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 108: Convert Sorted Array to Binary Search Tree

Problem Restatement We are given a sorted integer array nums in ascending order. We need to convert it into a height-balanced binary search tree. The official problem defines a height-balanced binary tree as a binary tree in which the depth difference between the two subtrees of every node is never more than 1 . The tree must also satisfy the binary search tree property: left subtree values < root value...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

Problem Restatement We are given two integer arrays: inorder postorder Both arrays describe the same binary tree. inorder is the inorder traversal of the tree. postorder is the postorder traversal of the same tree. We need to construct and return the original binary tree. The values are unique, and both arrays are guaranteed to describe the same tree. The official constraints also say each value in postorder appears in inorder...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 23: Merge k Sorted Lists

Problem Restatement We are given an array of linked lists: lists Each linked list is sorted in ascending order. We need to merge all linked lists into one sorted linked list and return its head. The constraints say: Constraint Value k == lists.length Number of linked lists 0 <= k <= 10^4 Number of lists 0 <= lists[i].length <= 500 Length of each list Total nodes across all lists At...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 427: Construct Quad Tree

Problem Restatement We are given an n x n grid containing only 0 and 1 . We need to build a quad tree that represents this grid. A quad tree is a tree where each internal node has exactly four children: Child Region topLeft upper-left quadrant topRight upper-right quadrant bottomLeft lower-left quadrant bottomRight lower-right quadrant Each node has two main fields: Field Meaning val True for 1 , False for...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 327: Count of Range Sum

Problem Restatement We are given an integer array nums and two integers lower and upper . A range sum is the sum of a contiguous subarray: S(i, j) = nums[i] + nums[i + 1] + ... + nums[j] where i <= j . We need to count how many range sums lie inside this inclusive range: lower <= S(i, j) <= upper The naive O(n^2) solution is too slow, so...

Wiki › Algorithms › 01. Searching and Sorting ›

7. Divide and Conquer Sorting

7. Divide and conquer sorting, 35 index slug name 181 merge-sort Merge Sort 182 top-down-merge-sort Top Down Merge Sort 183 bottom-up-merge-sort Bottom Up Merge Sort 184 natural-merge-sort Natural Merge Sort 185 in-place-merge-sort In Place Merge Sort 186 block-merge-sort Block Merge Sort 187 timsort Timsort 188 powersort Powersort 189 quicksort Quicksort 190 randomized-quicksort Randomized Quicksort 191 three-way-quicksort Three Way Quicksort 192 dual-pivot-quicksort Dual Pivot Quicksort 193 introsort Introsort 194 pdqsort Pattern...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.4 Merge Sort

6.4 Merge Sort Merge sort is the standard example of divide and conquer sorting. It divides the input into two smaller arrays, sorts each half, and then merges the two sorted halves into one sorted output. The central operation is not the division step. It is the merge step, because merging is where the algorithm combines local order into global order. Problem You have an array A[0..n-1] . You want...

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.5 Quick Sort

6.5 Quick Sort Quick sort is a divide and conquer sorting algorithm based on partitioning. It chooses a pivot, rearranges the array so that smaller elements go to one side and larger elements go to the other side, and then recursively sorts the two partitions. Unlike merge sort, quick sort does most of its work before the recursive calls. Problem You have an array A[0..n-1] . You want an in-place...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.14 Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers. It is useful when the original problem has repeated structure and when the cost of combining subanswers is controlled. The pattern has three parts: divide: split the input into smaller pieces conquer: solve each piece recursively combine: merge the subanswers into the answer for the full input The key question is...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Merge Sort

Merge Sort Merge sort is a divide and conquer sorting algorithm. It splits the input into smaller parts, sorts each part recursively, then merges the sorted parts into a single sorted sequence. It guarantees stable ordering and predictable time complexity. It performs well on large datasets and external memory systems. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1]...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Top Down Merge Sort

Top Down Merge Sort Top down merge sort is the canonical recursive form of merge sort. It starts from the full array, splits it into halves recursively until single elements remain, then merges upward. This form directly follows the divide and conquer recurrence and is the most common presentation in textbooks. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le...

Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort

Quicksort Quicksort is a divide and conquer sorting algorithm. It chooses a pivot value, partitions the array so that smaller elements go before the pivot and larger elements go after it, then recursively sorts both sides. It is one of the most important practical sorting algorithms because it is fast in memory, has good cache behavior, and usually needs only logarithmic stack space. Its main weakness is that bad pivot...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Two Dimensional Peak Finding

Two Dimensional Peak Finding Two dimensional peak finding finds a position in a matrix whose value is at least as large as its neighbors in four directions. Given a matrix $A$ of size $n \times m$, a position $(i, j)$ is a peak if: $A[i][j] \ge A[i-1][j]$ $A[i][j] \ge A[i+1][j]$ $A[i][j] \ge A[i][j-1]$ $A[i][j] \ge A[i][j+1]$ Out of bounds neighbors are treated as $-\infty$. Problem Given a matrix $A$, find...

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Sorted Matrix Search

Sorted Matrix Search Sorted matrix search finds a target in a matrix where each row and each column is sorted. Unlike saddleback search, this approach uses divide and conquer to recursively eliminate regions. Problem Given a matrix $A$ of size $n \times m$ such that: $$ A[i][j] \le A[i][j+1] $$ $$ A[i][j] \le A[i+1][j] $$ find a position $(i, j)$ such that: $$ A[i][j] = x $$ If no such...

#divide-and-conquer

CF 1250M - SmartGarden

CF 1167B - Lost Numbers

CF 960E - Alternating Tree

CF 981E - Addition on Segments

Educational Codeforces Round 46 (Rated for Div. 2)

CF 1000F - One Occurrence

CF 1004F - Sonya and Bitwise OR

CF 1019E - Raining season

CF 1043G - Speckled Band

CF 1385D - a-Good String

CF 1379F2 - Chess Strikes Back (hard version)

CF 1375H - Set Merging

CF 1372F - Omkar and Modes

CF 1371F - Raging Thunder

CF 1364E - X-OR

CF 1338C - Perfect Triples

CF 1316F - Battalion Strength

CF 1303G - Sum of Prefix Sums

CF 1295E - Permutation Separation

CF 1285D - Dr. Evil Underscores

CF 1278E - Tests for problem D

CF 1237C2 - Balanced Removals (Harder)

CF 1223F - Stack Exterminable Arrays

Bubble Cup 12 - Finals [Online Mirror, unrated, Div. 1]

CF 1218D - Xor Spanning Tree

CF 1218E - Product Tuples

CF 1217F - Forced Online Queries Problem

CF 1175F - The Number of Subpermutations

CF 1070M - Algoland and Berland

CF 914G - Sum the Fibonacci

CF 914E - Palindromes in a Tree

Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3)

CF 1261F - Xor-Set

CF 1817E - Half-sum

CF 1808E2 - Minibuses on Venus (medium version)

CF 1808E1 - Minibuses on Venus (easy version)

CF 1804F - Approximate Diameter

2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

CF 1773B - BinCoin

CF 1740I - Arranging Crystal Balls

CF 1734F - Zeros and Ones

CF 1730E - Maximums and Minimums

CF 1721D - Maximum AND

CF 1654H - Three Minimums

CF 1654F - Minimal String Xoration

CF 1583H - Omkar and Tours

CF 1583F - Defender of Childhood Dreams

CF 1553I - Stairs

CF 1550F - Jumping Around

Codeforces Round 736 (Div. 1)

CF 1548E - Gregor and the Two Painters

CF 1543E - The Final Pursuit

CF 1213G - Path Queries

Educational Codeforces Round 65 (Rated for Div. 2)

CF 1192B - Dynamic Diameter

CF 1190D - Tokitsukaze and Strange Rectangle

Codeforces Round 571 (Div. 2)

CF 1186E - Vus the Cossack and a Field

CF 1179E - Alesya and Discrete Math

Testing Round 15 (Unrated)

CF 1174F - Ehab and the Big Finale

CF 1100F - Ivan and Burgers

CF 1096G - Lucky Tickets

CEOI 2019 day 1 online mirror (unrated, IOI format)

CodeCraft-19 and Codeforces Round 537 (Div. 2)

CF 1111C - Creative Snap

CF 1114F - Please, another Queries on Array?

CF 1139F - Dish Shopping

CF 1140G - Double Tree

CF 1140F - Extending Set of Points

CF 1140E - Palindrome-less Arrays

CF 1146E - Hot is Cold

CF 1155D - Beautiful Array

CF 1156E - Special Segments of Permutation

CF 1156D - 0-1-Tree

CF 1175G - Yet Another Partiton Problem

CF 1175E - Minimal Segment Cover

CF 1177B - Digits Sequence (Hard Edition)

CF 1181E1 - A Story of One Country (Easy)