#dp
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 1553B - Reverse String
CF 1553B - Reverse String Rating: 1300 Tags: brute force, dp, hashing, implementation, strings Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a string that represents a line of characters. A chip starts on some chosen position in this string. After placing it, we repeatedly move it and each time we record the character at the chip’s current position. The movement has a strict structure: the...
CF 1387C - Viruses
CF 1387C - Viruses Rating: 2900 Tags: *special, dp, shortest paths, string suffix structures Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a system where each “gene” is an integer label, and every gene greater than 1 can expand into a sequence of genes according to a fixed mutation rule. Starting from a single gene $x$, we repeatedly replace any non-terminal gene in the current sequence...
CF 1305G - Kuroni and Antihype
CF 1305G - Kuroni and Antihype Rating: 3500 Tags: bitmasks, brute force, dp, dsu, graphs Solve time: 3m 16s Verified: no Solution Problem Understanding We are given a group of people, each with an associated integer value that can be interpreted as a bitmask. These people can form a network by joining a system where actions produce profit: once someone has joined, they can “invite” a person who has not...
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 1250G - Discarding Game
CF 1250G - Discarding Game Rating: 2300 Tags: dp, greedy, two pointers Solve time: 1m 59s Verified: no Solution Problem Understanding We are given two sequences that evolve in lockstep over time. In each round, the human gains some amount of points while the computer also gains points. Both totals accumulate independently across rounds. The game ends as soon as one of the players reaches or exceeds a threshold value...
CF 1250D - Conference Problem
CF 1250D - Conference Problem Rating: 3000 Tags: dp Solve time: 1m 42s Verified: no Solution Problem Understanding We are given several scientists, each staying at the conference for a time interval from day $l_i$ to $r_i$, inclusive. Some scientists explicitly belong to a known country $c_i > 0$, while others have no country assigned ($c_i = 0$). A scientist becomes upset if, during their entire stay, they never meet...
CF 1040B - Shashlik Cooking Rating: 1300 Tags: dp, greedy, math Model: gpt-5-3-mini Solve time: 1m 25s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33b8ae-772c-83ec-a3d7-73b862c99c7f Solution Problem Understanding We are given a line of $n$ skewers arranged from left to right. Each skewer has a binary state: either it is still in its initial state or it has been flipped. A single operation is performed by choosing a position $i$. That operation...
CF 958E2 - Guard Duty (medium) Rating: 2200 Tags: binary search, dp, greedy, sortings Model: gpt-5-3-mini Solve time: 3m 26s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339e66-d274-83ec-9c8a-9aa9396149de Solution Problem Understanding We are given a strictly increasing sequence of time moments when Heidi temporarily leaves hyperspace. These moments are the only valid endpoints at which meetings can begin or end. Heidi must organize exactly $K$ disjoint meetings, where each meeting is defined...
CF 1210G - Mateusz and Escape Room Rating: 3500 Tags: dp Model: gpt-5-3-mini Solve time: 2m 1s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a338500-4e6c-83ec-8288-071c55186398 Solution Problem Understanding We are given a cycle of positions, each position initially holding some number of coins. We are allowed to move coins one step at a time along the cycle, and each such unit move costs one operation. After performing any sequence of moves, every...
CF 958C3 - Encryption (hard) Rating: 2500 Tags: data structures, dp Model: gpt-5-3-mini Solve time: 4m 21s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339db1-3c50-83ec-9b14-c27aeee268ad Solution Problem Understanding We are given a long sequence of positive integers and asked to cut it into exactly k contiguous segments. Each segment must be non-empty and every element must belong to exactly one segment. For any segment, we compute its sum, then reduce that sum...
CF 960F - Pathwalks Rating: 2100 Tags: data structures, dp, graphs Model: gpt-5-3-mini Solve time: 4m 24s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a06c-a550-83ec-baf9-e569323b4a6a Solution Problem Understanding We are given a directed graph where each edge has an associated weight and also an implicit position given by its order in the input. A valid path is not constrained to be simple; vertices may repeat, and we may traverse edges multiple times...
CF 932D - Tree Rating: 2200 Tags: binary search, dp, trees Model: gpt-5-3-mini Solve time: 1m 28s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327666-dc20-83ec-bfaf-a06758f8815b Solution Problem Understanding We maintain a rooted tree that grows over time. The root is node 1 with weight 0. Each update query can attach a new node under an existing node, and each such node has a fixed weight. Over time, the structure becomes a rooted...
CF 932E - Team Work Rating: 2400 Tags: combinatorics, dp, math Model: gpt-5-3-mini Solve time: 1m 26s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3276bd-8288-83ec-a06b-8326cbcd5f3b Solution Problem Understanding We are asked to evaluate a combinatorial sum over all non-empty subsets of a set of size $N$. Every subset contributes a cost that depends only on its size: if a subset contains $x$ elements, its cost is $x^k$. The final answer is the...
CF 932G - Palindrome Partition Rating: 2900 Tags: dp, string suffix structures, strings Model: gpt-5-3-mini Solve time: 2m 10s Verified: yes (1/1 samples) Solution Problem Understanding We are given a string and asked to count how many ways we can cut it into a sequence of contiguous pieces such that the sequence of pieces reads the same forwards and backwards, and the number of pieces is even. In other words,...
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 958C2 - Encryption (medium)
CF 958C2 - Encryption (medium) Rating: 2000 Tags: dp Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a sequence of integers and asked to cut it into exactly $k$ contiguous non-empty segments. Each element must belong to exactly one segment, and the order of elements is preserved. For any segment, we take the sum of its elements, then reduce that sum modulo $p$. The total score...
CF 960G - Bandit Blues
CF 960G - Bandit Blues Rating: 2900 Tags: combinatorics, dp, fft, math Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to N, and we simulate a simple “record-breaking” process on it. We start with a virtual value 0. Scanning from left to right, we maintain the maximum value seen so far; every time we encounter a number larger than...
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...
CF 963B - Destruction of a Tree
CF 963B - Destruction of a Tree Rating: 2000 Tags: constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a tree where each vertex has an associated current degree that changes as vertices are removed. A vertex is eligible for removal only when its degree is even at the moment we choose it. When a vertex is removed, all...
CF 983C - Elevator
CF 983C - Elevator Rating: 2400 Tags: dp, graphs, shortest paths Solve time: 2m 11s Verified: no Solution Problem Understanding We are controlling a single elevator in a small building with nine floors, and we must serve a sequence of people in a fixed arrival order. Each person starts on some floor and wants to reach another floor. The elevator can carry at most four people at any time, and...
CF 983B - XOR-pyramid
CF 983B - XOR-pyramid Rating: 1800 Tags: dp Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given an array and many queries over its segments. Each query asks us to look at a contiguous part of the array, consider every possible subsegment inside it, and compute a special function on each subsegment. That function repeatedly replaces a sequence with pairwise XORs of neighbors until only one number...
CF 1025D - Recovering BST
CF 1025D - Recovering BST Rating: 2100 Tags: brute force, dp, math, number theory, trees Solve time: 3m 32s Verified: yes Solution Problem Understanding We are given a sorted list of distinct integers, and we want to build a binary search tree using exactly these values as node keys. The in-order traversal of any valid BST with these keys is fixed and already matches the given order, so the only...
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 1725J - Journey
CF 1725J - Journey Rating: 2500 Tags: dp, trees Solve time: 4m 34s Verified: no Solution Problem Understanding We are given a weighted tree where each node represents a city and each edge represents a bidirectional road with a travel time. The traveler must design a walk that eventually visits every city at least once. Movement is not restricted to simple paths, so revisiting nodes and edges is allowed, and...
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 1553D - Backspace
CF 1553D - Backspace Rating: 1500 Tags: dp, greedy, strings, two pointers Solve time: 6m 1s Verified: no Solution Problem Understanding We are simulating a typing process where we scan a source string s from left to right. At each position, we either append the current character to an evolving text buffer or press backspace, which deletes the most recently added character if it exists. The question is whether there...
CF 1387A - Graph
CF 1387A - Graph Rating: 2100 Tags: *special, binary search, dfs and similar, dp, math, ternary search Solve time: 6m 59s Verified: no Solution Problem Understanding We are given an undirected graph where every edge enforces a linear constraint between its endpoints. Each vertex must be assigned a real value, and every edge says exactly what the sum of its two endpoint values must be. Black edges force a sum...
CF 1323A - Even Subset Sum Problem
CF 1323A - Even Subset Sum Problem Rating: 800 Tags: brute force, dp, greedy, implementation Solve time: 3m 48s Verified: yes Solution Problem Understanding We are given several independent arrays of positive integers. For each array, we must select a non-empty group of positions such that the sum of the chosen values is even. If no such group exists, we report failure. The output is not the subset itself but...
CF 1322F - Assigning Fares
CF 1322F - Assigning Fares Rating: 3500 Tags: dp, trees Solve time: 5m 18s Verified: yes Solution Problem Understanding We are given a tree with $n$ stations and $n-1$ tunnels, so between any two stations there is exactly one simple path. On this tree, we are also given $m$ special routes. Each route is just a simple path between two endpoints, but we are allowed to choose its direction later,...
CF 1315B - Homecoming
CF 1315B - Homecoming Rating: 1300 Tags: binary search, dp, greedy, strings Solve time: 2m 35s Verified: no Solution Problem Understanding We are given a one-dimensional town represented as a line of crossroads indexed from 1 to n. Each position has exactly one type of transport station: either type A (bus-compatible segment marker) or type B (tram-compatible segment marker). The string s encodes this layout. Petya starts at position 1...
CF 1276A - As Simple as One and Two
CF 1276A - As Simple as One and Two Rating: 1400 Tags: dp, greedy Solve time: 5m 49s Verified: no Solution Problem Understanding We are given a string consisting of lowercase letters. Certain length-3 patterns are considered “bad”: specifically, the substrings "one" and "two" . A string becomes unacceptable if any such bad triple appears anywhere inside it. Our operation is that we may choose some positions in the string...
CF 1252J - Tiling Terrace
CF 1252J - Tiling Terrace Rating: 2300 Tags: brute force, dp Solve time: 6m 44s Verified: yes Solution Problem Understanding We are given a one-dimensional yard of length $N$, where each position is either usable soil or blocked by a rock. We want to place tiles on this line to maximize total “ghost repelling power”. Each tile type covers a fixed pattern of consecutive cells and contributes a fixed score,...
CF 1214D - Treasure Island
CF 1214D - Treasure Island Rating: 1900 Tags: dfs and similar, dp, flows, hashing Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid that represents a map. Each cell is either blocked or free. We start at the top-left cell $(1,1)$ and want to reach the bottom-right cell $(n,m)$. Movement is highly restricted: from any cell we can only go either one...
CF 1209E2 - Rotate Columns (hard version)
CF 1209E2 - Rotate Columns (hard version) Rating: 2500 Tags: bitmasks, dp, greedy, sortings Solve time: 4m 14s Verified: no Solution Problem Understanding We are given a grid with a small number of rows and a potentially large number of columns. The only operation allowed is to take any single column and rotate it cyclically any number of times. After performing these rotations independently for each column, we look at...
CF 1208F - Bits And Pieces
CF 1208F - Bits And Pieces Rating: 2600 Tags: bitmasks, dfs and similar, dp, greedy Solve time: 2m 39s Verified: yes Solution Problem Understanding We are given a sequence of integers and asked to choose three indices $i < j < k$. For each such triple, we take the value of the first element OR the bitwise AND of the other two elements. The goal is to maximize this expression...
CF 1070J - Streets and Avenues in Berhattan
CF 1070J - Streets and Avenues in Berhattan Rating: 2300 Tags: dp Solve time: 9m 13s Verified: no Solution Problem Understanding We are given a grid-like city structure formed by two independent labelings. There are horizontal streets and vertical avenues, and every street intersects every avenue, so each intersection corresponds to a pair consisting of one street and one avenue. We must assign names to all streets and all avenues....
CF 1070G - Monsters and Potions
CF 1070G - Monsters and Potions Rating: 2300 Tags: brute force, dp, greedy, implementation Solve time: 3m Verified: yes Solution Problem Understanding We are given a one-dimensional board of length $n$. Each cell can contain a monster with some HP, a potion that increases HP, or be empty. In addition, there are $m$ heroes initially placed on distinct empty cells, each hero starting with its own HP. We must choose...
CF 1070A - Find a Number
CF 1070A - Find a Number Rating: 2200 Tags: dp, graphs, number theory, shortest paths Solve time: 5m 57s Verified: yes Solution Problem Understanding We are looking for a positive integer that satisfies two simultaneous constraints. First, it must be divisible by a given integer $d$. Second, when written in decimal form, the sum of its digits must equal a given value $s$. Among all such integers, we want the...
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...
CF 1060F - Shrinking Tree
CF 1060F - Shrinking Tree Rating: 2900 Tags: combinatorics, dp Solve time: 4m 9s Verified: no Solution Problem Understanding We are given a tree with up to 50 vertices, and we repeatedly compress it until only one vertex remains. Each operation picks an edge uniformly at random. The two endpoints of that edge disappear, and they are replaced by a single merged vertex. This new vertex inherits all edges that...
CF 1060E - Sergey and Subway
CF 1060E - Sergey and Subway Rating: 2000 Tags: dfs and similar, dp, trees Solve time: 6m 55s Verified: no Solution Problem Understanding We start with a tree of subway stations. Every station is a node, and every tunnel is an edge, so there is exactly one simple path between any two stations. The quantity we care about is the total distance over all unordered pairs of stations, where distance...
CF 1773L - Lisa's Sequences
CF 1773L - Lisa's Sequences Rating: 3500 Tags: dp Solve time: 4m 37s Verified: no Solution Problem Understanding We are given a sequence of integers and a fixed length $k$. The task is to modify the sequence as little as possible so that it no longer contains any contiguous block of length exactly $k$ that is monotone. A block is monotone if it is either entirely non-decreasing or entirely non-increasing....
CF 1725M - Moving Both Hands
CF 1725M - Moving Both Hands Rating: 1800 Tags: dp, graphs, shortest paths Solve time: 3m 2s Verified: yes Solution Problem Understanding We are given a directed weighted graph where every edge allows movement in only one direction and has a cost in time. Two tokens, or “hands”, start on different vertices: one is fixed at vertex 1, and the other starts at some vertex p. In each move, we...
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...
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 1556F - Sports Betting
CF 1556F - Sports Betting Rating: 2500 Tags: bitmasks, combinatorics, dp, graphs, math, probabilities Solve time: 5m 15s Verified: yes Solution Problem Understanding We are given a complete tournament where every pair of teams plays exactly one match. The result of each match is random, but biased: team $i$ beats team $j$ with probability proportional to its strength, specifically $\frac{a_i}{a_i + a_j}$. Each match outcome is independent. From all match...
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...
CF 1322D - Reality Show Rating: 2800 Tags: bitmasks, dp Model: gpt-5-3-mini Solve time: 3m 5s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2deb92-56ac-83ec-ba70-95f7be671fa1 Solution Problem Understanding We are given a sequence of candidates that arrive in a fixed order. Each candidate has an initial aggressiveness level and a cost to recruit them. We may choose some of them, but with a constraint tied to the maximum aggressiveness we have already accepted:...
CF 1276D - Tree Elimination Rating: 2900 Tags: dp, trees Model: gpt-5-5 Solve time: 2m 50s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2d9860-5d9c-83ec-ad25-63a95925ff60 Solution Problem Understanding We are given a tree where every edge has a fixed order from 1 to n − 1. Initially every vertex holds its own label as a token. We process edges strictly in increasing index order, and at each edge we may remove exactly one...
CF 1320E - Treeland and Viruses Rating: 3000 Tags: data structures, dfs and similar, dp, shortest paths, trees Model: gpt-5-5 Solve time: 7m 20s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2de8a4-e50c-83ec-a13a-1c80b9179d39 Solution Problem Understanding The process happens on a tree of cities. In each scenario, several infection sources are placed on different nodes, each source belonging to a distinct virus type and having a propagation strength. Viruses spread in rounds, and...
CF 1320A - Journey Planning Rating: 1400 Tags: data structures, dp, greedy, math, sortings Model: gpt-5-5 Solve time: 4m 27s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2de6ec-99fc-83ec-9276-106005ae8eca Solution Problem Understanding We are given a line of cities, each with an index from left to right and an associated beauty value. We need to choose a sequence of cities to visit such that indices strictly increase. The key restriction is that consecutive...
CF 1089A - Alice the Fan
CF 1089A - Alice the Fan Rating: 2200 Tags: dp Solve time: 9m 32s Verified: no Solution Problem Understanding A volleyball match here is a short sequence of sets, with at most five sets played, and the first team to win three sets takes the match. Each set has a fixed structure: in the early sets the target is 25 points, in a potential fifth set the target is 15...
CF 914H - Ember and Storm's Tree Game
CF 914H - Ember and Storm's Tree Game Rating: 3400 Tags: combinatorics, dp, games, trees Solve time: 10m 4s Verified: yes Solution Problem Understanding The game begins with Ember choosing a tree on $n$ labeled vertices, with the restriction that no vertex has degree exceeding $d$. After that, Storm selects an ordered pair of vertices $(u, v)$, which determines a simple path in the tree. Writing the vertex labels along...
CF 914C - Travelling Salesman and Special Numbers
CF 914C - Travelling Salesman and Special Numbers Rating: 1800 Tags: brute force, combinatorics, dp Solve time: 4m Verified: yes Solution Problem Understanding We are given an upper bound n , but n is not provided as a decimal integer. Instead, it is given directly as a binary string whose length can be as large as 1000 bits. We consider the following operation on a positive integer: Take the number...
CF 906E - Reverses
CF 906E - Reverses Rating: 3300 Tags: dp, string suffix structures, strings Solve time: 4m 49s Verified: no Solution Problem Understanding We are given two strings of equal length. The first string, s , is the original string. The second string, t , is obtained after several pairwise disjoint substrings of s were reversed. The hurricane has already performed those reversals and produced t . Our task is to recover...
CF 906C - Party
CF 906C - Party Rating: 2400 Tags: bitmasks, brute force, dp, graphs Solve time: 7m 24s Verified: yes Solution Problem Understanding We have a connected friendship graph. Choosing a vertex means that all of its neighbors become pairwise adjacent. In graph theory language, we are allowed to pick a vertex and turn its open neighborhood into a clique. The process continues until the whole graph becomes a complete graph. We...
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 1120D - Power Tree
CF 1120D - Power Tree Rating: 2500 Tags: dfs and similar, dp, dsu, graphs, greedy, trees Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a rooted tree with n vertices, where each vertex has a non-negative price. The root is vertex 1. Leaves are non-root vertices with degree one. Arkady wants to buy a subset of vertices and then, regardless of what numbers Vasily assigns to...
CF 1120C - Compress String
CF 1120C - Compress String Rating: 2100 Tags: dp, strings Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given a string and two costs. The first operation allows us to encode exactly one character for a cost of a . The second operation allows us to encode any non-empty substring for a fixed cost of b , but only if that substring has already appeared somewhere in...
CF 1209E1 - Rotate Columns (easy version)
CF 1209E1 - Rotate Columns (easy version) Rating: 2000 Tags: bitmasks, brute force, dp, greedy, sortings Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a matrix with n rows and m columns, where each entry is a positive integer. We can pick any column and rotate it cyclically any number of times. After performing such rotations, we consider each row and take the maximum value in...
CF 1252B - Cleaning Robots
CF 1252B - Cleaning Robots Rating: 2300 Tags: dp, trees Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a tree with $N$ junctions and $N-1$ roads connecting them. A tree means that every pair of junctions is connected by exactly one path. The problem asks us to count the number of ways to assign “cleaning robots” to subsets of junctions such that each robot cleans a...
CF 1387B1 - Village (Minimum)
CF 1387B1 - Village (Minimum) Rating: 2100 Tags: *special, dp, greedy, trees Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given a village consisting of N houses connected by N-1 roads in a tree structure, so every house is reachable from any other via exactly one simple path. Each house initially has one villager. The villagers want to move so that no one remains in their original...
CF 1402C - Star Trek
CF 1402C - Star Trek Rating: 2600 Tags: *special, combinatorics, dfs and similar, dp, games, graphs, matrices, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a tree of $N$ planets. Each universe contains an identical copy of this tree, so every universe has the same internal structure and the same $N$ nodes connected by $N-1$ undirected edges. There are $D+1$ universes indexed from $0$ to...
CF 1403C - Chess Rush
CF 1403C - Chess Rush Rating: 3200 Tags: *special, combinatorics, dp, implementation, math Solve time: 4m 8s Verified: yes Solution What is actually going wrong Let’s trace what the wrong behavior implies. Input: 3 4 #.## #### ##.. Grid: #.## #### ##.. There are only 4 # cells total. But the output is 9 , which is suspiciously close to “counting something per cell plus neighbors” or “counting all 2x2...
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...
CF 1425D - Danger of Mad Snakes
CF 1425D - Danger of Mad Snakes Rating: 2300 Tags: combinatorics, dp, math Solve time: 1m 12s Verified: yes Solution Problem Understanding The problem gives a set of points on a 2D grid, each point representing a snake with a weight called its danger level. We choose exactly M distinct snakes as attack targets. Each chosen target defines a square influence region centered at that snake, where all other snakes...
CF 1442E - Black, White and Grey Tree
CF 1442E - Black, White and Grey Tree Rating: 3000 Tags: binary search, constructive algorithms, dfs and similar, dp, greedy, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a tree in which each node is coloured white, black, or grey. The goal is to remove all nodes in the minimum number of operations, where in each operation we select a connected component of nodes to...
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 1442A - Extreme Subtraction
CF 1442A - Extreme Subtraction Rating: 1800 Tags: constructive algorithms, dp, greedy Solve time: 1m 35s Verified: no Solution Problem Understanding We are given an array of positive integers and a very specific way to reduce it. Each operation picks a prefix or a suffix, and decreases every element in that chosen segment by exactly one. The goal is to determine whether we can reduce all values to zero using...
CF 1443B - Saving the City
CF 1443B - Saving the City Rating: 1300 Tags: dp, greedy, math, sortings Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given a city represented as a line of buildings, each of which may or may not have a mine. The city map is a string of zeros and ones, where "1" indicates a mine and "0" indicates a safe building. The sapper has two operations: he...
CF 1456E - XOR-ranges
CF 1456E - XOR-ranges Rating: 3500 Tags: dp, greedy Solve time: 1m 51s Verified: no Solution Problem Understanding We are asked to construct an array of length $n$ such that each element lies within a given segment $[l_i, r_i]$ and the sum of costs of consecutive XOR differences is minimized. Each number $x$ has a cost defined by its set bits: the $i$-th bit contributes $c_i$ to the cost. The...
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 1500F - Cupboards Jumps
CF 1500F - Cupboards Jumps Rating: 3500 Tags: dp Solve time: 1m 18s Verified: no Solution Problem Understanding We are asked to reconstruct a sequence of cupboard heights based on partial information. Specifically, Krosh remembers the difference between the tallest and shortest cupboard for every consecutive triple. Formally, for a sequence of heights $h_1, h_2, \dots, h_n$, he recalls $w_i = \max(h_i, h_{i+1}, h_{i+2}) - \min(h_i, h_{i+1}, h_{i+2})$ for all...
CF 1501B - Napoleon Cake
CF 1501B - Napoleon Cake Rating: 900 Tags: dp, implementation, sortings Solve time: 2m 15s Verified: no Solution Problem Understanding We build the cake layer by layer. After placing the i -th layer, we pour a[i] units of cream onto the top. That cream spreads downward and covers the top a[i] layers currently present. If there are fewer than a[i] layers, every existing layer becomes covered. For each layer, we...
CF 1510D - Digits
CF 1510D - Digits Rating: 2100 Tags: dp, math, number theory Solve time: 23m 14s Verified: no Solution Problem Understanding We have n cards. Each card contains a positive integer. We may choose any non-empty subset of cards and multiply all chosen numbers. The goal is not merely to obtain a product whose last decimal digit equals d . Among all such subsets, we want the subset whose product value...
CF 1510H - Hard Optimization
CF 1510H - Hard Optimization Rating: 3200 Tags: dp Solve time: 3m 6s Verified: no Solution Problem Understanding We are asked to select a subsegment from each of a set of laminar segments on the integer line in order to maximize the total length. Each input segment is defined by its left and right endpoints, and all endpoints are distinct. Laminarity here means that any two segments are either completely...
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 1523F - Favorite Game
CF 1523F - Favorite Game Rating: 3300 Tags: bitmasks, dp Solve time: 2m 24s Verified: no Solution Problem Understanding We are asked to maximize the number of quests William can complete in a 2D grid game with two interacting mechanics: movement and fast travel towers. The game world is infinite in size, but William’s movement is constrained to orthogonal moves-up, down, left, or right-by one unit per turn. He can...
CF 1523E - Crypto Lights
CF 1523E - Crypto Lights Rating: 2600 Tags: combinatorics, dp, math, probabilities Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to compute the expected number of lights that turn on in a line of $n$ lights, given a stopping condition based on consecutive segments of length $k$. Each light starts off, and in each step, one random light that is still off is turned on. The...
CF 1523D - Love-Hate
CF 1523D - Love-Hate Rating: 2400 Tags: bitmasks, brute force, dp, probabilities Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a set of n friends, each with their own preferences over m currencies. Each friend likes at most p currencies, so the like-lists are sparse. The goal is to find the largest set of currencies such that at least half of the friends like all the...
CF 1530F - Bingo
CF 1530F - Bingo Rating: 2600 Tags: bitmasks, combinatorics, dp, math, probabilities Solve time: 2m 2s Verified: no Solution Problem Understanding We are asked to compute the probability that a square table of events is "winning." Each cell of an $n \times n$ table contains an event that may happen with a given probability. Rows, columns, the main diagonal, and the antidiagonal are considered lines. A table is winning if...
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 1553C - Penalty
CF 1553C - Penalty Rating: 1200 Tags: bitmasks, brute force, dp, greedy Solve time: 2m 51s Verified: yes Solution Problem Understanding We are simulating a penalty shootout between two football teams, each taking alternating kicks up to five each, for a total of ten kicks. Each kick either succeeds (scores a goal), fails, or is unknown. The input gives a string of ten characters representing these outcomes: '1' for a...
CF 1558B - Up the Strip
CF 1558B - Up the Strip Rating: 1900 Tags: brute force, dp, math, number theory, two pointers Solve time: 6m 35s Verified: yes Solution Problem Understanding We are given a token placed at position $n$ on a vertical line of cells labeled from $1$ at the top to $n$ at the bottom. The goal is to count how many distinct sequences of moves can bring the token from $n$ down...
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 1575H - Holiday Wall Ornaments
CF 1575H - Holiday Wall Ornaments Rating: 2200 Tags: dp, strings Solve time: 37s Verified: no Solution Problem Understanding We are given a binary string representing a wall, where each character is either 0 or 1. This string, a , is of length n . Mr. Chanek wants to place his nephew’s favorite pattern, another binary string b of length m , onto the wall. The task is to determine,...
CF 1575D - Divisible by Twenty-Five
CF 1575D - Divisible by Twenty-Five Rating: 1800 Tags: brute force, dfs and similar, dp Solve time: 2m 1s Verified: yes Solution Problem Understanding We are given a very short string, at most length 8, that represents a partially unknown integer. Some positions contain fixed digits, some contain a wildcard underscore meaning “any digit is allowed here”, and some contain the character X meaning all X positions must share the...