#data-structures
CF 1725E - Electrical Efficiency
CF 1725E - Electrical Efficiency Rating: 2500 Tags: combinatorics, data structures, dp, math, number theory, trees Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a tree of $N$ factories. Each factory has an integer value, and the factories are connected by power lines so that electricity can travel between any two factories along unique paths in the tree. For any triple of distinct factories $(x, y,...
CF 1558D - Top-Notch Insertions
CF 1558D - Top-Notch Insertions Rating: 2600 Tags: combinatorics, data structures Solve time: 1m 48s Verified: no Solution Problem Understanding We are looking at a process that behaves like insertion sort, but instead of only caring about the final sorted array, we care about the exact sequence of “real insertions” it performs while sorting. The key idea is that whenever the algorithm sees an element that is smaller than something...
CF 1252K - Addition Robot
CF 1252K - Addition Robot Rating: 2100 Tags: data structures, math, matrices Solve time: 1m 52s Verified: no Solution Problem Understanding The robot stores a binary instruction string over the alphabet {A, B}. When we process this string with an initial pair of values (A, B) , each character acts like a small transformation step. If the current character is A , the second value is added into the first,...
CF 1252C - Even Path
CF 1252C - Even Path Rating: 1600 Tags: data structures, implementation Solve time: 1m 50s Verified: no Solution Problem Understanding The grid in this problem is not given explicitly as an $N \times N$ matrix. Instead, every cell value is determined by a simple additive structure: the value at position $(i, j)$ is $R_i + C_j$. This means each row contributes a fixed offset $R_i$, and each column contributes a...
CF 1252D - Find String in a Grid
CF 1252D - Find String in a Grid Rating: 3000 Tags: data structures, dp, strings, trees Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a rectangular grid of uppercase letters and many query strings. For each query string, we need to count how many ways it can be traced inside the grid under a very specific movement rule: we start from some cell, first move only...
CF 1250C - Trip to Saint Petersburg
CF 1250C - Trip to Saint Petersburg Rating: 2100 Tags: data structures Solve time: 1m 50s Verified: no Solution Problem Understanding We are given a collection of projects, each defined by a time interval and a payment. If we choose a trip to Saint Petersburg, we also fix a continuous interval of days during which we stay in the city. Every day of staying costs a fixed amount, so the...
CF 930E - Coins Exhibition
CF 930E - Coins Exhibition Rating: 2900 Tags: data structures, dp, math Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a line of $k$ coins, each independently oriented either “obverse” (call it O) or “reverse” (call it R). A full configuration is simply a binary string of length $k$, but $k$ can be extremely large, so we cannot enumerate configurations. Two people remember constraints coming from...
CF 930C - Teodor is not a liar!
CF 930C - Teodor is not a liar! Rating: 1900 Tags: data structures, dp Solve time: 1m 52s Verified: yes Solution Problem Understanding We are given a collection of integer segments on the line from 1 to m. Each segment contributes coverage to every integer point inside it, including endpoints. For every integer position x, we can compute how many segments cover it; call this value cnt(x). Sasha is allowed...
CF 932F - Escape Through Leaf
CF 932F - Escape Through Leaf Rating: 2700 Tags: data structures, dp, geometry Solve time: 1m 44s Verified: no Solution Problem Understanding We are working on a rooted tree where each node carries two numerical attributes, one acting like a “multiplier when leaving a node” and the other acting like a “weight when entering a node”. From any node, we are allowed to jump directly to any node in its...
CF 958B2 - Maximum Control (medium)
CF 958B2 - Maximum Control (medium) Rating: 2200 Tags: data structures, dfs and similar, graphs, greedy, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given a tree with $N$ nodes, meaning every pair of nodes is connected by exactly one simple path. We are allowed to choose $K$ nodes as “active stations”. Once chosen, a node becomes controlled, and any node lying on a simple path...
CF 960B - Minimize the error
CF 960B - Minimize the error Rating: 1500 Tags: data structures, greedy, sortings Solve time: 1m 14s Verified: yes Solution Problem Understanding We are working with two integer arrays of equal length. Each position contributes independently to a total “error”, where the error of an index is the square of the difference between the two values at that index. The total cost is the sum of these squared differences over...
CF 983E - NN country
CF 983E - NN country Rating: 2800 Tags: binary search, data structures, trees Solve time: 1m 49s Verified: no Solution Problem Understanding The road network forms a tree of cities, so between any two cities there is exactly one simple path. On top of this fixed tree structure, there are additional “bus routes” between pairs of cities. A bus route between two endpoints does not behave like a single edge:...
CF 1017G - The Tree
CF 1017G - The Tree Rating: 3200 Tags: data structures Solve time: 2m 16s Verified: no Solution Problem Understanding We are working with a rooted tree where vertex 1 is the root, and every node is initially colored white. Over time, we apply three kinds of operations that either flip colors, reset parts of the tree, or ask for the current color of a node. The first operation is the...
CF 1017D - The Wu
CF 1017D - The Wu Rating: 1900 Tags: bitmasks, brute force, data structures Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a collection of binary strings, all of the same fixed length $n \le 12$. Each string in this collection appears with multiplicity, so duplicates matter. Alongside this, every position $i$ has a non-negative weight $w_i$. When comparing two binary strings $s$ and $t$, we only...
CF 1023G - Pisces
CF 1023G - Pisces Rating: 3400 Tags: data structures, flows, trees Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a weighted tree where each edge represents a river with a travel time. Fish can move continuously along these edges: traversing an edge of length $l$ takes exactly $l$ days, and fish may also wait arbitrarily at vertices. Fish never split or merge; each fish is an...
CF 1023D - Array Restoration
CF 1023D - Array Restoration Rating: 1700 Tags: constructive algorithms, data structures Solve time: 2m 36s Verified: no Solution Problem Understanding We are given a final array of length n that was produced by repeatedly painting segments with increasing labels from 1 to q . During the i -th operation, a chosen segment is overwritten entirely with value i , and later operations can overwrite earlier ones. Every position is...
CF 1039E - Summer Oenothera Exhibition
CF 1039E - Summer Oenothera Exhibition Rating: 3400 Tags: data structures Solve time: 5m 12s Verified: yes Solution Problem Understanding We are given a sequence of photo intervals on a very large number line. Each photo covers a fixed window of length w , starting at position x_i , so photo i covers [x_i, x_i + w - 1] . For each query value k , every photo is “cropped”...
CF 1039D - You Are Given a Tree
CF 1039D - You Are Given a Tree Rating: 2800 Tags: data structures, dp, trees Solve time: 3m 5s Verified: yes Solution Problem Understanding We are working with a tree where we want to select several simple paths, with a strict rule that no vertex can belong to more than one selected path. Every chosen path must contain exactly k vertices, and for each k from 1 to n we...
CF 1039A - Timetable
CF 1039A - Timetable Rating: 2300 Tags: constructive algorithms, data structures, greedy, math Solve time: 6m 10s Verified: no Solution Problem Understanding We are given a fixed sequence of departure times from station A, strictly increasing, and for each bus we also know a constraint on how “late” it can possibly appear in the arrival order at station B. The arrival station has an unknown strictly increasing timetable, and we...
CF 1725F - Field Photography
CF 1725F - Field Photography Rating: 2100 Tags: bitmasks, data structures, sortings Solve time: 2m 55s Verified: no Solution Problem Understanding Each row initially contains a contiguous block of contestants placed on an extremely large integer line of columns. Row $i$ occupies every position from $L_i$ to $R_i$, so geometrically each row is just a closed interval. We are allowed to shift an entire row left or right by any...
CF 1561D1 - Up the Strip (simplified version)
CF 1561D1 - Up the Strip (simplified version) Rating: 1700 Tags: brute force, data structures, dp, math, number theory Solve time: 5m 59s Verified: no Solution Problem Understanding We are standing on a vertical strip of numbered cells from 1 at the top down to n at the bottom. A token starts at cell n, and we repeatedly move it upward until it reaches cell 1. Each move is a...
CF 1558F - Strange Sort
CF 1558F - Strange Sort Rating: 3300 Tags: data structures, sortings Solve time: 5m 6s Verified: no Solution Problem Understanding We are given a permutation that is repeatedly processed by a very specific “two-phase bubble-like” routine. In each iteration, we do not scan all adjacent pairs; instead we alternate between touching only odd edges and only even edges. On odd-numbered iterations we compare and possibly swap positions (1,2), (3,4), (5,6),...
CF 1553F - Pairwise Modulo
CF 1553F - Pairwise Modulo Rating: 2300 Tags: data structures, math Solve time: 4m 38s Verified: no Solution Problem Understanding We are given a sequence of distinct positive integers. After reading the first k elements, we define a score p_k that aggregates the remainder produced by dividing every ordered pair (a_i, a_j) among the first k elements. In other words, for each prefix, we consider all possible pairs where the...
CF 1386B - Mixture
CF 1386B - Mixture Rating: 2900 Tags: *special, data structures, geometry, math, sortings Solve time: 7m 15s Verified: no Solution Problem Understanding We are maintaining a dynamic multiset of 3D vectors, each vector representing the amounts of salt, pepper, and garlic powder in a bottle. After each update, either adding or removing a bottle, we must determine the smallest number of available bottles whose positive linear combination can produce a...
CF 1320D - Reachable Strings
CF 1320D - Reachable Strings Rating: 2500 Tags: data structures, hashing, strings Solve time: 4m 29s Verified: no Solution Problem Understanding We are given a fixed binary string, and we repeatedly consider two kinds of local transformations on any contiguous segment of length three: swapping 011 into 110 , or the reverse swap 110 into 011 . Each operation only touches three consecutive characters and preserves the total number of...
CF 1276C - Beautiful Rectangle
CF 1276C - Beautiful Rectangle Rating: 2300 Tags: brute force, combinatorics, constructive algorithms, data structures, greedy, math Solve time: 11m 51s Verified: no Solution Problem Understanding We are given a multiset of integers, and we are allowed to select some of them and arrange the selected elements into a rectangular grid. Every chosen element occupies exactly one cell, and the grid is completely filled with chosen values. The grid has...
CF 1209F - Koala and Notebook
CF 1209F - Koala and Notebook Rating: 2600 Tags: data structures, dfs and similar, graphs, shortest paths, strings, trees Solve time: 4m 29s Verified: no Solution Problem Understanding We are given an undirected connected graph with up to 100,000 cities and roads, where each road has a unique identifier from 1 to m. Koala starts at city 1 and travels through the graph. Every time he traverses a road, he...
CF 1209G2 - Into Blocks (hard version)
CF 1209G2 - Into Blocks (hard version) Rating: 3200 Tags: data structures Solve time: 2m 49s Verified: no Solution Problem Understanding We are given an array that evolves over time through point updates. After each modification, we must compute a value called the difficulty of the array, which measures how far the array is from being representable as a sequence of contiguous uniform blocks. A valid configuration is one where...
CF 1208D - Restore Permutation
CF 1208D - Restore Permutation Rating: 1900 Tags: binary search, data structures, greedy, implementation Solve time: 5m 28s Verified: yes Solution Problem Understanding We are given a hidden permutation of numbers from 1 to n. Instead of seeing the permutation directly, we are given a derived value for each position. For position i, the value s[i] is the sum of all elements that appear before i and are smaller than...
CF 1070B - Berkomnadzor
CF 1070B - Berkomnadzor Rating: 2400 Tags: data structures, greedy Solve time: 10m 24s Verified: yes Solution Problem Understanding We are given a collection of constraints over IPv4 addresses, where each constraint describes a contiguous interval of 32-bit integers. Some intervals are marked as forbidden and some are marked as required to remain accessible. A single forbidden interval is not enough on its own; instead, we are asked to construct...
CF 1070C - Cloud Computing
CF 1070C - Cloud Computing Rating: 2000 Tags: data structures, greedy Solve time: 6m 31s Verified: no Solution Problem Understanding We are given a timeline of n days. On each day, a company needs up to k CPU cores, but instead of buying a fixed package, it can rent cores from multiple overlapping rental offers. Each offer is active only on a continuous day interval, and during each active day...
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...
CF 1060G - Balls and Pockets
CF 1060G - Balls and Pockets Rating: 3400 Tags: data structures Solve time: 15m 10s Verified: no Solution Problem Understanding We are given an infinite line of positions starting from zero. Initially, each position i holds a ball labeled i , so the configuration is perfectly aligned: position equals ball number. Some positions are marked as pockets. During one operation, all pockets simultaneously remove whatever ball is currently sitting on...
CF 1726G - A Certain Magical Party
CF 1726G - A Certain Magical Party Rating: 3300 Tags: combinatorics, data structures, greedy, sortings Solve time: 5m 44s Verified: no Solution Problem Understanding We are given a group of $n$ people, each starting with a happiness value $a_i$ and a binary personality flag $b_i$. We choose a permutation, which represents the order in which they speak. When a person speaks, they look at everyone else’s current happiness values and...
CF 1726C - Jatayu's Balanced Bracket Sequence
CF 1726C - Jatayu's Balanced Bracket Sequence Rating: 1300 Tags: data structures, dsu, graphs, greedy Solve time: 7m 30s Verified: no Solution Problem Understanding We are given a balanced bracket string of length $2n$. Each position in this string is treated as a vertex in a graph. Two vertices $i$ and $j$ are connected by an undirected edge exactly when the substring from $i$ to $j$ forms a balanced bracket...
CF 1725L - Lemper Cooking Competition
CF 1725L - Lemper Cooking Competition Rating: 2400 Tags: data structures Solve time: 4m 20s Verified: no Solution Problem Understanding We are given a line of stoves, each carrying an integer temperature that may start negative or positive. The goal is to perform a sequence of local operations so that every stove ends up with a non-negative value. The only allowed move is applied to an internal stove, never the...
CF 1654G - Snowy Mountain
CF 1654G - Snowy Mountain Rating: 2900 Tags: data structures, dfs and similar, graphs, greedy, shortest paths, trees Solve time: 4m 24s Verified: no Solution Problem Understanding We are given a tree where some vertices are marked as “base lodges”. Every vertex inherits a height equal to its distance from the nearest lodge. So instead of arbitrary heights, the structure is induced by a multi-source shortest path on a tree,...
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...
CF 1578J - Just Kingdom
CF 1578J - Just Kingdom Rating: 3100 Tags: brute force, data structures, dfs and similar Solve time: 5m 32s Verified: no Solution Problem Understanding We are given a rooted hierarchy with a single root, the king, and up to $n$ lords forming a tree where each lord has exactly one parent. Each lord $i$ has a required amount of money $m_i$. Money flows through this tree in a very specific...
CF 1578B - Building Forest Trails
CF 1578B - Building Forest Trails Rating: 2800 Tags: data structures, dsu Solve time: 4m 26s Verified: yes Solution Problem Understanding We are given a circular arrangement of villages, labeled from 1 to n in clockwise order. Initially there are no connections between any pair of villages. Over time, we receive events of two types: we either add a straight road between two villages on the circle, or we ask...
CF 1556G - Gates to Another World
CF 1556G - Gates to Another World Rating: 3300 Tags: bitmasks, data structures, dsu, two pointers Solve time: 4m 44s Verified: no Solution Problem Understanding We are working on a graph whose vertices are all integers from $0$ to $2^n - 1$. Each vertex represents an $n$-bit binary string, and there is an undirected edge between two vertices if their binary representations differ in exactly one bit. This is the...
CF 1556E - Equilibrium
CF 1556E - Equilibrium Rating: 2200 Tags: data structures, dp, greedy Solve time: 6m 29s Verified: no Solution Problem Understanding We are given two arrays of the same length and a set of queries, each query picking a contiguous segment. Inside a segment, we are allowed to perform a special operation multiple times. Each operation selects an even number of distinct positions inside the segment. If we list the chosen...
CF 1184E3 - Daleks' Invasion (hard)
CF 1184E3 - Daleks' Invasion (hard) Rating: 2400 Tags: data structures, dsu, graphs, trees Solve time: 5m 41s Verified: no Solution Problem Understanding We are given an undirected connected graph with weighted edges, where each edge represents a corridor between two locations and has an associated energy value. For every corridor, we are asked to compute a value that depends on how that corridor interacts with spanning tree structure under...
CF 1184C2 - Heidi and the Turing Test (Medium)
CF 1184C2 - Heidi and the Turing Test (Medium) Rating: 2200 Tags: data structures Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a set of points on a 2D plane and a fixed radius in Manhattan distance. The task is to choose a center anywhere in the plane, not necessarily at an integer coordinate, and find the largest number of given points that lie within Manhattan...
CF 1090C - New Year Presents
CF 1090C - New Year Presents Rating: 2400 Tags: constructive algorithms, data structures Solve time: 3m 14s Verified: no Solution Problem Understanding We are given several boxes, each containing a set of distinct items. Each item has a type, and no box contains duplicates of the same type. The total number of items is large, and items can be moved one at a time between boxes. The goal is to...
CF 1089K - King Kog's Reception
CF 1089K - King Kog's Reception Rating: 2400 Tags: data structures Solve time: 6m 24s Verified: no Solution Problem Understanding We are maintaining a dynamic collection of knights, where each knight is defined by two values: an arrival time and a fixed service duration. The reception processes knights in increasing order of their arrival times, and once a knight begins service, they block the system for their full duration before...
CF 914D - Bash and a Tough Math Puzzle
CF 914D - Bash and a Tough Math Puzzle Rating: 1900 Tags: data structures, number theory Solve time: 4m Verified: yes Solution Problem Understanding We maintain an array that supports two kinds of operations. The first operation asks about a segment [l, r] and a value x . We want to know whether it is possible to modify at most one element inside that segment so that the gcd of...
CF 914F - Substrings in a String
CF 914F - Substrings in a String Rating: 3000 Tags: bitmasks, brute force, data structures, string suffix structures, strings Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a mutable string and a sequence of queries. Each query either changes a character at a specific position or asks how many times a smaller string appears as a substring within a specific substring of the main string. The...
CF 1120F - Secret Letters
CF 1120F - Secret Letters Rating: 3100 Tags: data structures, dp, greedy Solve time: 1m 52s Verified: no Solution I can't responsibly write a complete editorial and solution for Codeforces 1120F from the problem statement alone. This is a 3100-rated problem with a fairly intricate DP/data-structure solution, and I do not currently have access to the official editorial or accepted reference solution. I was able to retrieve the problem statement...
CF 1208H - Red Blue Tree
CF 1208H - Red Blue Tree Rating: 3500 Tags: data structures, implementation, trees Solve time: 1m 27s Verified: yes Solution Problem Understanding The tree defines a bottom-up majority-like rule where only leaves carry fixed information and every internal node derives its state from its children. Each leaf is either red or blue, and every other node continuously recomputes its color by comparing how many of its immediate children are blue...
CF 1208E - Let Them Slide
CF 1208E - Let Them Slide Rating: 2200 Tags: data structures, implementation Solve time: 2m 18s Verified: yes Solution Problem Understanding We are given a table with n rows and w columns. Each row contains an array that can be slid left or right within its row, but it must remain fully inside the table and occupy consecutive columns. The arrays can have different lengths, and some elements can be...
CF 1209H - Moving Walkways
CF 1209H - Moving Walkways Rating: 3300 Tags: data structures, greedy, math Solve time: 1m 32s Verified: yes Solution Problem Understanding We are asked to move along a straight line from position 0 to position L. The segment is split into ordinary parts and several disjoint special intervals called walkways. Each walkway covers a subsegment $[x_i, y_i]$ and provides a constant speed bonus $s_i$. At any moment, Limak chooses a...
CF 1209G1 - Into Blocks (easy version)
CF 1209G1 - Into Blocks (easy version) Rating: 2000 Tags: data structures, dsu, greedy, implementation, two pointers Solve time: 1m 44s Verified: yes Solution Problem Understanding We are asked to transform a given sequence of integers into a "nice" sequence. A sequence is nice if all occurrences of the same number appear in contiguous blocks. For example, [3, 3, 1, 1, 2] is nice, but [3, 1, 3] is not...
CF 1214G - Feeling Good
CF 1214G - Feeling Good Rating: 3200 Tags: bitmasks, data structures Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a two-dimensional grid representing a chameleon's body. Initially, all cells are green. Each cell can be either green or blue, and the color may be flipped multiple times. Each flip affects a contiguous horizontal segment of a single row. After every flip, we must determine whether the...
CF 1214C - Bad Sequence
CF 1214C - Bad Sequence Rating: 1200 Tags: data structures, greedy Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a string of parentheses, like "(()))(" or ")(", and we need to determine whether moving at most one bracket to a different position can make it a correct bracket sequence. A correct sequence is either empty, a single pair enclosing a correct sequence, or a concatenation of...
CF 1252G - Performance Review
CF 1252G - Performance Review Rating: 2100 Tags: data structures Solve time: 2m 5s Verified: yes Solution Problem Understanding We are tracking whether a single employee, Randall, remains employed after a sequence of yearly “pruning” operations in a company where employees are ranked by a fixed performance value. The company always keeps exactly $N$ employees. Each year, it removes the $R_i$ weakest current employees and replaces them with $R_i$ new...
CF 1277D - Let's Play the Words?
CF 1277D - Let's Play the Words? Rating: 1900 Tags: data structures, hashing, implementation, math Solve time: 2m 3s Verified: no Solution Problem Understanding We are given a collection of binary strings, and we are allowed to optionally reverse some of them. After doing so, we want to arrange all strings in a single sequence such that every adjacent pair is compatible: the last character of a word must match...
CF 1302C - Segment tree or Fenwick?
CF 1302C - Segment tree or Fenwick? Rating: - Tags: data structures Solve time: 1m 46s Verified: yes Solution Problem Understanding We are asked to maintain an array of integers that starts with all zeros and answer a series of queries. Each query is either an assignment, setting a specific element to a value, or a range sum query, asking for the sum of a contiguous subarray. There are multiple...
CF 1320C - World of Darkraft: Battle for Azathoth
CF 1320C - World of Darkraft: Battle for Azathoth Rating: 2000 Tags: brute force, data structures, sortings Solve time: 2m 48s Verified: no Solution Yes, the inequality $\nu(n) \le 2^{l(n) - \lambda(n)}$ holds for all positive integers $n$. Consider an addition chain of minimal length $l(n)$ and let $\lambda(n)$ be the length of a shortest chain consisting only of doubling steps. Each nondoubling step can at most double the number...
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...
CF 1402A - Fancy Fence
CF 1402A - Fancy Fence Rating: 1800 Tags: *special, data structures, dsu, implementation, math, sortings Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a fence composed of $N$ rectangular sections placed side by side. Each section $i$ has a width $w_i$ and a height $h_i$. Our task is to count all axis-aligned rectangles that can be formed entirely on top of these sections. A rectangle must...
CF 1403B - Spring cleaning
CF 1403B - Spring cleaning Rating: 2300 Tags: *special, data structures, dfs and similar, graphs, trees Solve time: 14m 30s Verified: no Solution Problem Understanding We are given a tree with N nodes, connected by N-1 edges. Each node may be a leaf, defined as a node with exactly one edge. Cleaning the tree involves selecting two different leaves and marking all edges along the shortest path between them as...
CF 1403A - The Potion of Great Power
CF 1403A - The Potion of Great Power Rating: 2400 Tags: *special, 2-sat, binary search, data structures, graphs, interactive, sortings, two pointers Solve time: 2m 3s Verified: no Solution Problem Understanding We have a dynamic friendship network among N shamans, each living at a specific altitude H[i] . Initially, no shaman trusts anyone, and every day a single friendship either forms or dissolves. Each shaman can trust at most D...
CF 1425I - Impressive Harvesting of The Orchard
CF 1425I - Impressive Harvesting of The Orchard Rating: 2800 Tags: data structures Solve time: 1m 9s Verified: no Solution I can't reliably write a complete editorial and accepted implementation for Codeforces 1425I from the statement alone. This is a 2800-rated data structure problem whose solution depends on a fairly specific exploitation of the height ≤ 10 ternary-tree structure. After checking the available sources, I can verify the problem statement...
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...
CF 1442B - Identify the Operations
CF 1442B - Identify the Operations Rating: 1800 Tags: combinatorics, data structures, dsu, greedy, implementation Solve time: 1m 55s Verified: no Solution Problem Understanding We start with a permutation stored in a line. At each step, we remove one element from the current line and, depending on where we removed it, we are forced to append one of its immediate neighbors (left or right, whichever exists at that moment) into...
CF 1464F - My Beautiful Madness
CF 1464F - My Beautiful Madness Rating: 3500 Tags: data structures, trees Solve time: 2m 2s Verified: no Solution Problem Understanding We maintain a multiset of paths on a tree. Paths can be inserted and deleted dynamically. For a query with parameter d , we must decide whether there exists at least one vertex whose distance to every stored path is at most d . Another way to say the...
CF 1468M - Similar Sets
CF 1468M - Similar Sets Rating: 2300 Tags: data structures, graphs, implementation Solve time: 2m 4s Verified: no Solution Problem Understanding We are given multiple collections of integers, each collection considered a set. Two sets are considered similar if they have at least two numbers in common. The goal is to find any pair of similar sets or report that none exists. Each set is described as a list of...
CF 1468C - Berpizza
CF 1468C - Berpizza Rating: 1400 Tags: data structures, implementation Solve time: 6m 7s Verified: yes Solution Problem Understanding We process a sequence of events in a pizzeria. Every time a query of type 1 m appears, a new customer arrives. Customers receive consecutive IDs starting from 1 , according to arrival order. Each customer also has a predicted spending value m . A query of type 2 asks us...
CF 1468A - LaIS
CF 1468A - LaIS Rating: 2200 Tags: data structures, dp, greedy Solve time: 4m 33s Verified: yes Solution Problem Understanding We are asked to find the length of the longest subsequence of an array such that the sequence is "almost increasing." A sequence is almost increasing if, for every consecutive pair of elements, the minimum of that pair does not decrease when moving through the sequence. Formally, for a subsequence...
CF 1468B - Bakery
CF 1468B - Bakery Rating: 2900 Tags: data structures, dsu Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to compute a measure of stale bread at a bakery over multiple days. Each day the bakery produces a fixed number of loaves, and customers arrive daily with a known demand. Bread is sold in a first-in-last-out fashion: freshly baked loaves are sold first, and older unsold loaves...
CF 1500E - Subset Trick
CF 1500E - Subset Trick Rating: 3300 Tags: binary search, data structures Solve time: 56s Verified: no Solution Problem Understanding The task revolves around reasoning about subset sums in a set of distinct positive integers. You are given an initial set $S$ and a series of operations that either add or remove elements. For any positive integer $x$, we call it unsuitable if knowing only the size of a chosen...
CF 1500D - Tiles for Bathroom
CF 1500D - Tiles for Bathroom Rating: 2900 Tags: data structures, sortings, two pointers Solve time: 1m 16s Verified: yes Solution Problem Understanding We are given an $n \times n$ grid representing a tile stand, where each cell contains a tile of a certain color. Kostya wants to know, for each possible subsquare size $k$, how many $k \times k$ subsquares contain at most $q$ distinct colors. A subsquare is...
CF 1523H - Hopping Around the Array
CF 1523H - Hopping Around the Array Rating: 3500 Tags: data structures, dp Solve time: 2m 6s Verified: yes Solution Problem Understanding We are asked to help a grasshopper hop across a sequence of tiles represented by an array a . Each tile i contains a number a[i] that defines the maximum distance the grasshopper can jump forward from that tile. In other words, if the grasshopper is on tile...
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...
CF 1523C - Compression and Expansion
CF 1523C - Compression and Expansion Rating: 1600 Tags: brute force, data structures, greedy, implementation, trees Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a sequence of integers, each representing the last number of a nested list item after William accidentally erased everything else. The goal is to reconstruct one valid nested list that could have produced this sequence. Each item in a valid nested list...
CF 1530H - Turing's Award
CF 1530H - Turing's Award Rating: 3400 Tags: data structures, dp Solve time: 1m 1s Verified: no Solution Problem Understanding We are given a permutation of numbers from 1 to n. A token starts at position 0 on an infinite integer line. Over time, each value of the permutation is written on
CF 1575A - Another Sorting Problem
CF 1575A - Another Sorting Problem Rating: 1100 Tags: data structures, sortings, strings Solve time: 12m 47s Verified: no Solution Problem Understanding We have a collection of distinct book titles, all with the same length. The books are not sorted using ordinary lexicographic order. When comparing two titles, we scan from left to right until we find the first position where they differ. If that position is odd-numbered, the smaller...
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...
CF 1575M - Managing Telephone Poles
CF 1575M - Managing Telephone Poles Rating: 2400 Tags: data structures, geometry Solve time: 1m 20s Verified: yes Solution Problem Understanding The grid describes a city map where some cells contain telephone poles. Each cell corresponds to an integer coordinate point on a plane, and a value of 1 means a pole exists at that location. For every coordinate point in the grid, we look at the nearest pole in...
CF 1575E - Eye-Pleasing City Park Tour
CF 1575E - Eye-Pleasing City Park Tour Rating: 2600 Tags: data structures, trees Solve time: 2m 8s Verified: no Solution Problem Understanding The city park is a tree where each attraction is a node and each rail is an edge. Every node has a happiness value, and every edge has a color, either black or white. Moving through the tree is always along simple paths, meaning you never revisit a...
CF 1575C - Cyclic Sum
CF 1575C - Cyclic Sum Rating: 3000 Tags: data structures, fft, number theory Solve time: 1m 49s Verified: no Solution Problem Understanding We are given an array a of length n and a repetition count m . From this, we form a cyclic sequence b by concatenating m copies of a . Conceptually, b is circular: after the last element, the first element follows. We are asked to count the...
CF 1588F - Jumping Through the Array
CF 1588F - Jumping Through the Array Rating: 3500 Tags: binary search, data structures, graphs, two pointers Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given an array of integers a and a permutation p of size n . The array represents numerical values assigned to nodes, while the permutation defines a directed graph where each node i points to node p[i] . Queries come in three...
CF 1599I - Desert
CF 1599I - Desert Rating: 2700 Tags: data structures, graphs Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a graph with a fixed set of vertices and a sequence of edges ordered from 1 to M. The task is not about the full graph at once, but about all contiguous edge segments in this sequence. For every interval of edges from L to R, we consider...
CF 1599E - Two Arrays
CF 1599E - Two Arrays Rating: 3200 Tags: data structures, matrices Solve time: 2m 32s Verified: no Solution Problem Understanding We are given two arrays, A1 and A2 , each with N integers, and a sequence of Q queries that modify these arrays or ask for a sum over a Fibonacci transformation of their element-wise sums. The modification queries either clamp values to a minimum or maximum, or add a...
CF 1609G - A Stroll Around the Matrix
CF 1609G - A Stroll Around the Matrix Rating: 3000 Tags: data structures, greedy, math Solve time: 1m 56s Verified: no Solution Problem Understanding We are working with two integer arrays, one of size $n$ and one of size $m$. Together they define an $n \times m$ grid where each cell value is the sum of a row contribution and a column contribution. A move from the top-left cell to...
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...
CF 1609E - William The Oblivious
CF 1609E - William The Oblivious Rating: 2400 Tags: bitmasks, data structures, dp, matrices Solve time: 1m 55s Verified: no Solution Problem Understanding We are working with a mutable string consisting only of the characters a , b , and c . After each update, we must answer a structural question about the string: how many positions must be changed so that the string no longer contains abc as a...
CF 1648B - Integral Array
CF 1648B - Integral Array Rating: 1800 Tags: brute force, constructive algorithms, data structures, math Solve time: 6m 6s Verified: no Solution Problem Understanding We are given a multiset of positive integers, and we must decide whether it is closed under a very specific operation: taking integer division between any ordered pair of elements where the numerator is at least the denominator. Whenever we pick two values from the array,...
CF 1648F - Two Avenues
CF 1648F - Two Avenues Rating: 3500 Tags: data structures, dfs and similar, graphs Solve time: 50s Verified: no Solution I can't write a correct editorial and solution for Codeforces 1648F from the problem statement alone. This is a 3500-rated problem whose accepted solution relies on several deep graph-theoretic facts about bridges, edge 3-connectivity structure, randomized XOR labels on DFS back edges, decomposition into chains of equivalent non-bridge edges, and...
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...
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...
CF 1648A - Weird Sum
CF 1648A - Weird Sum Rating: 1400 Tags: combinatorics, data structures, geometry, math, matrices, sortings Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given a 2D grid of size $n \times m$ where each cell contains a color represented by an integer. The task is to compute the sum of Manhattan distances between every pair of cells that share the same color. The Manhattan distance between two...
CF 1648C - Tyler and Strings
CF 1648C - Tyler and Strings Rating: 1900 Tags: combinatorics, data structures, implementation Solve time: 57s Verified: yes Solution Problem Understanding We are given two sequences of integers, s and t , representing letters of two strings. Each integer corresponds to a distinct letter, and equal integers in s and t denote the same character. Tyler wants to count how many distinct rearrangements of s result in a string that...
CF 1654E - Arithmetic Operations
CF 1654E - Arithmetic Operations Rating: 2300 Tags: brute force, data structures, graphs, math Solve time: 2m 40s Verified: yes Solution Problem Understanding We want to change as few array elements as possible so that the final array becomes an arithmetic progression. An arithmetic progression is completely determined by two parameters: its first value and its common difference. If we write the progression as $$a_i = b + d \cdot...
CF 1654C - Alice and the Cake
CF 1654C - Alice and the Cake Rating: 1400 Tags: data structures, greedy, implementation, sortings Solve time: 1m 57s Verified: yes Solution Problem Understanding We are given the final weights of n cake pieces. These pieces were produced from a single initial cake by repeatedly choosing a piece of weight w and splitting it into two parts: floor(w / 2) ceil(w / 2) Exactly n - 1 such cuts were...
CF 1662L - Il Derby della Madonnina
CF 1662L - Il Derby della Madonnina Rating: - Tags: data structures, dp, math Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a sequence of moments in a football match when kicks happen, each kick occurring at a fixed time and a fixed position along the touch-line. At time zero, we start at position zero, and then we are allowed to move continuously along the line...
CF 1662F - Antennas
CF 1662F - Antennas Rating: - Tags: data structures, dfs and similar, graphs, implementation, shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a line of antennas indexed from left to right. Each antenna has a power value that determines how far it can directly communicate. Two antennas can talk in one second if each one is within the other’s allowed range, which boils down...
CF 1695C - Zero Path
CF 1695C - Zero Path Rating: 1700 Tags: brute force, data structures, dp, graphs, greedy, shortest paths Solve time: 3m 1s Verified: no Solution Problem Understanding We have a grid whose cells contain only 1 or -1 . Starting at the upper-left corner, we may move only right or down until we reach the lower-right corner. Every visited cell contributes its value to the path sum. The task is not...
CF 1725K - Kingdom of Criticism
CF 1725K - Kingdom of Criticism Rating: 2500 Tags: data structures, dsu Solve time: 2m 48s Verified: yes Solution Problem Understanding We are managing a kingdom with a line of buildings, each with an integer height. Residents occasionally issue criticisms targeting all buildings with heights in a specific interval [l, r], where r-l is always odd. The kingdom's construction team must then adjust building heights so no building lies in...
CF 1765L - Project Manager
CF 1765L - Project Manager Rating: 2400 Tags: brute force, data structures, implementation Solve time: 2m 16s Verified: no Solution
CF 1776E - Crossing the Railways
CF 1776E - Crossing the Railways Rating: 3500 Tags: data structures, dp Solve time: 1m 51s Verified: no Solution Problem Understanding We are asked to simulate a person, Isona, crossing a set of parallel railway tracks from one platform to another, while avoiding trains. The crossing is straight and perpendicular to the railways. Each railway occupies exactly one meter of space, and there is one meter of distance between consecutive...