#probabilities

CF 1267G - Game Relics

CF 1267G - Game Relics Rating: 3000 Tags: math, probabilities Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a collection of $n$ distinct items called relics. Each relic $i$ can be obtained in two ways: either by directly purchasing it at a fixed cost $c_i$, or by paying a fixed cost $x$ to receive a uniformly random relic among all $n$, where duplicates do not help...

CF 1264C - Beautiful Mirrors with queries

CF 1264C - Beautiful Mirrors with queries Rating: 2400 Tags: data structures, probabilities Solve time: 3m 40s Verified: no Solution Problem Understanding Each mirror acts like a probabilistic “step” in a process that either advances forward or forces a restart. Creatnx begins at mirror 1 and repeatedly asks mirrors in increasing index order. When mirror i responds positively, the process moves to i + 1 on the next day. When...

Codeforces Round 604 (Div. 1)

Codeforces Round 604 (Div. 1) Div. 1 | 6 problems | 2/6 verified | Difficulty 1500-3500 | 12m 26s # Problem Rating Tags Accepted Time ✓ A Beautiful Regional Contest 1500 greedy, implementation 10,440 1m 27s B Beautiful Sequence 1900 brute-force, constructive-algorithms, greedy 6,046 2m 35s C Beautiful Mirrors with queries 2400 data-structures, probabilities 1,322 3m 40s D1 Beautiful Bracket Sequence (easy version) 2600 combinatorics, dp, probabilities 1,525 1m 21s...

CF 1264D2 - Beautiful Bracket Sequence (hard version)

CF 1264D2 - Beautiful Bracket Sequence (hard version) Rating: 2900 Tags: combinatorics, probabilities Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a string made of three types of characters: left brackets, right brackets, and question marks. Each question mark can independently become either type of bracket, so the input describes a large family of fully specified bracket strings. For any fully specified string, we are not...

CF 1264D1 - Beautiful Bracket Sequence (easy version)

CF 1264D1 - Beautiful Bracket Sequence (easy version) Rating: 2600 Tags: combinatorics, dp, probabilities Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a string of length up to 2000, consisting of three kinds of characters: opening brackets, closing brackets, and wildcards. Each wildcard can independently be replaced by either an opening or closing bracket, so the string represents a family of up to $2^{k}$ concrete bracket...

CF 1254D - Tree Queries

CF 1254D - Tree Queries Rating: 2700 Tags: data structures, probabilities, trees Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a tree with values stored on vertices, initially all zero. The system processes two kinds of operations. One operation injects a value d into a region of the tree that depends on a randomly chosen root vertex r . The other asks for the expected accumulated...

CF 1210F2 - Marek and Matching (hard version)

CF 1210F2 - Marek and Matching (hard version) Rating: 3200 Tags: brute force, probabilities Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a complete bipartite structure between two sets of size $n$, where every potential edge $(\ell_i, r_j)$ exists independently with some probability $p_{ij}/100$. The randomness is over the presence or absence of each edge, and all edges are independent. The question is not about constructing...

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

CF 1045D - Interstellar battle Rating: 2200 Tags: math, probabilities, trees Model: gpt-5-3-mini Solve time: 5m 14s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33be72-3674-83ec-a75f-4dce1447204e Solution Problem Understanding We are given a tree of planets where each planet can independently be destroyed during an enemy attack. When a planet falls, it is removed along with all incident edges, so the remaining structure becomes a forest. The number we care about after an...

CF 930B - Game with String Rating: 1600 Tags: implementation, probabilities, strings Model: gpt-5-3-mini Solve time: 2m 11s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339406-73a4-83ec-9c03-b248d932d6fb Solution Problem Understanding We are given a string that is conceptually placed on a circle. Kolya rotates this circle by a random shift, and Vasya observes only the first character of the rotated string. After seeing that character, Vasya is allowed to reveal exactly one additional...

CF 952D - I'm Feeling Lucky! Rating: 1800 Tags: *special, probabilities Model: gpt-5-3-mini Solve time: 49s Verified: yes (0/0 samples) Share: https://chatgpt.com/share/6a327c22-62b0-83ec-b164-c33b4c8eb756 Solution Problem Understanding The setting is a roulette-style board where the surface is divided into equal square cells. You are given a betting chip and must place it on the board in such a way that it lies strictly inside a single square, meaning it cannot touch any...

CF 896C - Willem, Chtholly and Seniorious Rating: 2600 Tags: data structures, probabilities Model: gpt-5-3-mini Solve time: 4m 17s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32b526-b83c-83ec-9899-997a323cb749 Solution Problem Understanding We are working with a dynamic array of up to 100,000 integers, and we must support a sequence of 100,000 operations. Each operation modifies a contiguous segment or queries information about a segment. There are two update operations: one adds a value...

CF 949F - Astronomy

CF 949F - Astronomy Rating: 3300 Tags: geometry, probabilities Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given 2n lattice points in the plane, each representing a star. Somewhere in the original astronomical configuration there existed a special point, the Moon, with integer coordinates, such that the stars could be partitioned into n pairs with a very rigid geometric property: for every pair, the line through the...

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 1009E - Intercity Travelling

CF 1009E - Intercity Travelling Rating: 2000 Tags: combinatorics, math, probabilities Solve time: 3m 58s Verified: yes Solution Problem Understanding We are given a road split into $n$ unit segments, and each segment has a “base fatigue cost” $a_i$ that applies when Leha starts a fresh driving session. The key twist is that fatigue does not depend only on the kilometer index, but also on how many kilometers have been...

CF 1039B - Subway Pursuit

CF 1039B - Subway Pursuit Rating: 2100 Tags: binary search, interactive, probabilities Solve time: 11m 23s Verified: no Solution Problem Understanding We are dealing with a single moving target on a very large numbered line of stations from 1 to n. At any moment there is exactly one station where the train is located, but after every query the train is allowed to move up to k stations left or...

CF 1042E - Vasya and Magic Matrix

CF 1042E - Vasya and Magic Matrix Rating: 2300 Tags: dp, math, probabilities Solve time: 2m 49s Verified: no Solution Problem Understanding We are given a grid where every cell has a numeric value, and a chip starts at a specific cell. From its current position, the chip can only move to cells that have strictly smaller values than the current one. Among all such eligible cells, the next position...

CF 1380G - Circular Dungeon

CF 1380G - Circular Dungeon Rating: 2600 Tags: greedy, math, probabilities Solve time: 6m 14s Verified: yes Solution Problem Understanding We are placing a multiset of values into a circular array of rooms. Each room contains exactly one item, and each item is either a regular chest with a reward value or a mimic that immediately stops the run when entered. A player starts from a uniformly random room and...

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

CF 1354G - Find a Gift

CF 1354G - Find a Gift Rating: 2600 Tags: binary search, interactive, probabilities Solve time: 5m 29s Verified: no Solution Problem Understanding We are given a row of boxes, each box hiding either a valuable gift or a stone. Exactly k boxes contain gifts, and every other box contains stones. The key structural property is about weights. Every stone box has the same weight, and that weight is strictly larger...

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

CF 1310D - Tourism

CF 1310D - Tourism Rating: 2300 Tags: dp, graphs, probabilities Solve time: 14m 40s Verified: no Solution Problem Understanding We are given a complete directed graph of cities where every ordered pair of distinct cities has a travel cost. Starting from city 1, we must perform exactly $k$ moves, and end again at city 1. Each move is just choosing a directed edge and paying its cost. Revisiting cities and...

CF 1245E - Hyakugoku and Ladders

CF 1245E - Hyakugoku and Ladders Rating: 2300 Tags: dp, probabilities, shortest paths Solve time: 3m 29s Verified: no Solution Problem Understanding The game can be viewed as a directed line of states arranged along a fixed serpentine path on a 10 by 10 grid. Each cell corresponds to a position on this path, starting from the bottom-left cell and ending at the top-left cell. Movement along the path is...

CF 1236F - Alice and the Cactus

CF 1236F - Alice and the Cactus Rating: 3000 Tags: dfs and similar, graphs, math, probabilities Solve time: 5m 7s Verified: no Solution Problem Understanding We are given a connected undirected graph with a special structure: it is a cactus, meaning every edge belongs to at most one simple cycle. On this graph, each vertex independently survives with probability $1/2$, otherwise it is deleted together with all incident edges. After...

CF 1210F1 - Marek and Matching (easy version)

CF 1210F1 - Marek and Matching (easy version) Rating: 3100 Tags: brute force, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding We are given a complete bipartite structure with $n$ vertices on the left and $n$ vertices on the right. For every possible pair $(i, j)$, the edge between left vertex $i$ and right vertex $j$ exists independently with probability $p_{ij}/100$. The randomness only affects whether edges appear....

CF 1172C2 - Nauuo and Pictures (hard version)

CF 1172C2 - Nauuo and Pictures (hard version) Rating: 2600 Tags: dp, probabilities Solve time: 4m 21s Verified: no Solution Problem Understanding We are given a collection of pictures, each with a positive weight. These weights determine how likely each picture is shown when Nauuo visits the website: a picture is selected with probability proportional to its current weight, so picture $i$ is chosen with probability $w_i / \sum_j w_j$....

CF 1096F - Inversion Expectation

CF 1096F - Inversion Expectation Rating: 2300 Tags: dp, math, probabilities Solve time: 4m 15s Verified: no Solution Problem Understanding We are given a sequence of length $n$ that is supposed to be a permutation, except some positions are unknown and marked with $-1$. The missing values are precisely the numbers that do not appear among the fixed entries, and every completion of the array that forms a valid permutation...

CF 1067D - Computer Game

CF 1067D - Computer Game Rating: 3100 Tags: dp, greedy, math, probabilities Solve time: 5m 2s Verified: no Solution Problem Understanding We are given a collection of quests, each with two reward values and a success probability. Every second, Ivan chooses one quest and attempts it. If the attempt succeeds, he receives the base reward for that quest and also gains the ability to upgrade any single quest once, which...

CF 1061F - Lost Root

CF 1061F - Lost Root Rating: 2400 Tags: interactive, probabilities Solve time: 8m 41s Verified: no Solution Problem Understanding We are given a tree that is known to be a perfect $k$-ary tree, meaning it has a root, every internal node has exactly $k$ children, and all leaves are at the same depth. The structure of the tree is fixed, but the vertex labels from $1$ to $n$ are arbitrarily...

CF 1081G - Mergesort Strikes Back

CF 1081G - Mergesort Strikes Back Rating: 3200 Tags: math, probabilities Solve time: 1m 16s Verified: no Solution Stopped thinking

CF 1600F - Party Organization

CF 1600F - Party Organization Rating: 2300 Tags: brute force, math, probabilities Solve time: 2m 22s Verified: yes Solution Problem Understanding We are given a simple undirected graph where people are vertices and friendships are edges. A valid party is a selection of exactly five distinct vertices such that the induced subgraph on these five vertices is either completely empty of edges or completely full, meaning it is a 5-vertex...

Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 2)

Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 2) Div. 2 | 3 problems | 3/3 verified | Difficulty 1400-2300 | 5m 40s # Problem Rating Tags Accepted Time ✓ E Array Game 1900 games, greedy, two-pointers 2,382 1m 34s ✓ F Party Organization 2300 brute-force, math, probabilities 615 2m 22s ✓ J Robot Factory 1400 bitmasks, dfs-and-similar 4,417 1m 44s ✓

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

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

CF 1773A - Amazing Trick

CF 1773A - Amazing Trick Rating: 1900 Tags: constructive algorithms, graph matchings, math, probabilities Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a permutation $a$ of size $n$, meaning every number from $1$ to $n$ appears exactly once. We are allowed to apply two permutations $q$ first and then $p$, so that the final position $i$ receives the value originally at position $p[q[i]]$. In other words,...

CF 1729E - Guess the Cycle Size

CF 1729E - Guess the Cycle Size Rating: 1800 Tags: interactive, probabilities Solve time: 6m 14s Verified: no Solution Problem Understanding We are interacting with a hidden structure that is guaranteed to be a simple cycle on $n$ vertices, where $n$ can be as large as $10^{18}$. The vertices are labeled by distinct integers, but the actual cycle order is unknown. The only way to extract information is by querying...

CF 1726D - Edge Split

CF 1726D - Edge Split Rating: 2000 Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, probabilities, trees Solve time: 3m 56s Verified: no Solution Problem Understanding We are given a connected undirected graph with a small number of extra edges beyond a tree. For each edge, we must decide whether it is colored red or blue. After fixing the coloring, we look at two induced subgraphs: one formed...

CF 1578M - The Mind

CF 1578M - The Mind Rating: 2700 Tags: constructive algorithms, interactive, probabilities Solve time: 6m 11s Verified: no Solution Problem Understanding Each test gives us a hand of five distinct numbers between 1 and 100. Two players independently receive such hands, and each player only sees their own five numbers. From those five numbers, only the smallest one matters for the actual game, because the rules force every player to...

CF 1578G - Game of Chance

CF 1578G - Game of Chance Rating: 3500 Tags: math, probabilities Solve time: 5m 52s Verified: no Solution Problem Understanding We are given a line of participants, each assigned a positive “luckiness” value. These participants enter a knockout tournament with a very rigid pairing structure. In any match between two players with luck values $x$ and $y$, the probability that the first player wins is $x/(x+y)$, and the second wins...

CF 1556H - DIY Tree

CF 1556H - DIY Tree Rating: 3300 Tags: graphs, greedy, math, probabilities Solve time: 4m 54s Verified: no Solution Problem Understanding We are given a complete weighted undirected graph on $n$ vertices, so every pair of vertices is connected and every edge has a known cost. The task is to select exactly $n-1$ edges that form a spanning tree of minimum total weight, but with an additional restriction that only...

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 1543C - Need for Pink Slips

CF 1543C - Need for Pink Slips Rating: 1900 Tags: bitmasks, brute force, dfs and similar, implementation, math, probabilities Solve time: 6m 31s Verified: no Solution Problem Understanding We are repeatedly running a stochastic process that evolves a small probability distribution over three outcomes. At any moment there are up to three “active” slips, one of which is a terminal success state (the pink slip) and the other two are...

CF 1305F - Kuroni and the Punishment Rating: 2500 Tags: math, number theory, probabilities Model: gpt-5-3-mini Solve time: 1m 51s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2dd87b-f5dc-83ec-a859-ab36a2e89043 Solution Problem Understanding We are given a list of large positive integers. In one move, we can pick any single element and shift it by exactly one unit up or down, as long as it stays positive. Each such shift costs one operation. The...

CF 1279D - Santa's Bot Rating: 1700 Tags: combinatorics, math, probabilities Model: gpt-5-5 Solve time: 7m 29s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2da1c9-21c8-83ec-814b-5dac8ec4dcde Solution Problem Understanding We are given a collection of children, where each child has written down a list of acceptable gifts. The bot does not directly assign gifts; instead, it performs a randomized three-step procedure that produces a triple consisting of a chosen “source child”, a chosen...

CF 1278F - Cards Rating: 2600 Tags: combinatorics, dp, math, number theory, probabilities Model: gpt-5-5 Solve time: 5m 35s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d9f62-60cc-83ec-9b1f-4ce602994ea3 Solution Problem Understanding We repeatedly perform a simple experiment on a deck that contains one special card and $m-1$ ordinary cards. Each trial consists of fully randomizing the deck, looking at the top card, and then putting it back without changing the deck composition. Because...

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

CF 1349D - Slime and Biscuits Rating: 3200 Tags: math, probabilities Model: gpt-5-3-mini Solve time: 3m 12s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e281b-5b68-83ec-9bc4-d38513abe39c Solution Problem Understanding We are given a collection of players, each initially holding some number of biscuits. At every second, the process performs two random choices. First, a biscuit is selected uniformly from all biscuits currently in the system, meaning a player is selected with probability proportional...

CF 1187F - Expected Square Beauty

CF 1187F - Expected Square Beauty Rating: 2500 Tags: dp, math, probabilities Solve time: 5m 41s Verified: yes Solution Problem Understanding We are given an array whose elements are not fixed numbers but independent random integers. Each position $i$ can take any integer in the interval $[l_i, r_i]$, all values equally likely and independent across indices. For any fully realized array $x$, we compress it into the minimum number of...

CF 1172C1 - Nauuo and Pictures (easy version)

CF 1172C1 - Nauuo and Pictures (easy version) Rating: 2300 Tags: dp, probabilities Solve time: 6m 32s Verified: yes Solution Problem Understanding We are working with a system of pictures where each picture has a weight that controls how likely it is to be shown when we visit a website. At any moment, the probability of seeing picture $i$ is its weight divided by the total weight of all pictures....

CF 1097D - Makoto and a Blackboard

CF 1097D - Makoto and a Blackboard Rating: 2200 Tags: dp, math, number theory, probabilities Solve time: 3m 58s Verified: yes Solution Problem Understanding We start with a single integer placed on a board. At each step, this number is replaced by one of its divisors, chosen uniformly at random. After repeating this operation exactly k times, the value on the board becomes a random variable over integers, and we...

CF 1096E - The Top Scorer

CF 1096E - The Top Scorer Rating: 2500 Tags: combinatorics, dp, math, probabilities Solve time: 6m 3s Verified: yes Solution Problem Understanding We are given a final score distribution across $p$ players whose scores are non-negative integers summing to $s$. Hasan is player 1, and his score is only partially constrained: it must be at least $r$, but otherwise unknown. Every valid score distribution satisfying these constraints is considered equally...

Codeforces Round 465 (Div. 2)

Codeforces Round 465 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 800-2600 | Time: 33m 56s Problem Name Rating Tags Solve Time Verified A Fafa and his Company 800 brute-force, implementation 9m 9s ✓ B Fafa and the Gates 900 implementation 2m 57s ✓ C Fifa and Fafa 1600 geometry 4m ✗ D Fafa and Ancient Alphabet 1900 math, probabilities 4m 24s ✓ E...

CF 935D - Fafa and Ancient Alphabet

CF 935D - Fafa and Ancient Alphabet Rating: 1900 Tags: math, probabilities Solve time: 4m 24s Verified: yes Solution Problem Understanding We are given two words of equal length over an alphabet consisting of symbols 1...m . Some positions are known, while others were erased and are represented by 0 . Every erased position is filled independently and uniformly with one of the m alphabet symbols. After all replacements are...

CF 913F - Strongly Connected Tournament

CF 913F - Strongly Connected Tournament Rating: 2800 Tags: dp, graphs, math, probabilities Solve time: 6m 14s Verified: no Solution Problem Understanding We are asked to compute the expected total number of games in a recursively defined chess tournament. There are n players, each with a known probability of beating any lower-numbered player. The tournament works by first having all players compete with each other once, then organizing players into...

CF 912D - Fishes

CF 912D - Fishes Rating: 2100 Tags: data structures, graphs, greedy, probabilities, shortest paths Solve time: 5m 22s Verified: yes Solution Problem Understanding We have a rectangular pond of size n by m where each cell can hold at most one fish. Sasha has a square scoop of size r by r that can catch all fishes inside the square if its bottom-left corner is placed within the pond. Sasha...

Good Bye 2017

Good Bye 2017 Type: Special | Problems: 8 | Verified: 6/8 | Rating range: 800-3100 | Time: 53m 34s Problem Name Rating Tags Solve Time Verified A New Year and Counting Cards 800 brute-force, implementation 1m 34s ✓ B New Year and Buggy Bot 1200 brute-force, implementation 8m 16s ✓ C New Year and Curling 1500 brute-force, geometry, implementation 3m 31s ✗ D New Year and Arbitrary Arrangement 2200 dp,...

CF 908D - New Year and Arbitrary Arrangement

CF 908D - New Year and Arbitrary Arrangement Rating: 2200 Tags: dp, math, probabilities Solve time: 6m 34s Verified: yes Solution Problem Understanding We build a string one character at a time. At each step we append 'a' with probability $$\frac{p_a}{p_a+p_b}$$ and append 'b' with probability $$\frac{p_b}{p_a+p_b}.$$ For a fixed string, the number of subsequences equal to "ab" is easy to describe. Every 'b' contributes as many "ab" subsequences as...

CF 1114E - Arithmetic Progression

CF 1114E - Arithmetic Progression Rating: 2200 Tags: binary search, interactive, number theory, probabilities Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a hidden array of size $n$, but the array is not directly accessible and is permuted arbitrarily. The only structural guarantee is that if we sort its elements, they form a perfect arithmetic progression with a strictly positive common difference. So the multiset of...

CF 1139D - Steps to One

CF 1139D - Steps to One Rating: 2300 Tags: dp, math, number theory, probabilities Solve time: 1m 39s Verified: yes Solution Problem Understanding We repeatedly choose a random integer from 1 to m , independently and uniformly. After each choice, we look at the gcd of all numbers chosen so far. The process stops as soon as this gcd becomes 1 . We must compute the expected number of chosen...

CF 1148G - Gold Experience

CF 1148G - Gold Experience Rating: 3300 Tags: constructive algorithms, graphs, math, number theory, probabilities Solve time: 1m 45s Verified: no Solution Problem Understanding We are given an array of integers placed on vertices of a complete set of labels. Between any two vertices we implicitly define an undirected edge if the two associated values share a nontrivial common divisor, meaning their gcd is greater than one. So the graph...

CF 1151F - Sonya and Informatics

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

CF 1153F - Serval and Bonus Problem

CF 1153F - Serval and Bonus Problem Rating: 2600 Tags: combinatorics, dp, math, probabilities Solve time: 2m 16s Verified: yes Solution Problem Understanding We are asked to consider a line segment of length $l$. We randomly choose $n$ subsegments on this line. Each subsegment is determined by picking two points uniformly at random on the segment, so their endpoints may be non-integer. After placing these $n$ random subsegments, we look...

CF 1156F - Card Bag

CF 1156F - Card Bag Rating: 2300 Tags: dp, math, probabilities Solve time: 1m 28s Verified: yes Solution Problem Understanding We are repeatedly drawing cards from a multiset of values, without replacement. The only thing that matters is the sequence of drawn values, and how each value compares to the previous drawn value. The game behaves like this: the first drawn card just sets a baseline value. From the second...

CF 1190F - Tokitsukaze and Powers

CF 1190F - Tokitsukaze and Powers Rating: 3400 Tags: number theory, probabilities Solve time: 1m 36s Verified: yes Solution Problem Understanding We are asked to generate a set of possible passwords under very specific rules. The lock accepts integers between 0 and m-1 . A candidate number is invalid if it shares any factor with m other than 1, or if it can be expressed as p^e mod m for...

CF 1194F - Crossword Expert

CF 1194F - Crossword Expert Rating: 2400 Tags: combinatorics, dp, number theory, probabilities, two pointers Solve time: 2m 31s Verified: yes Solution Problem Understanding We are asked to calculate the expected number of crosswords Adilbek can fully solve in a fixed amount of time, given that each crossword takes either t_i or t_i + 1 seconds independently with equal probability. He solves crosswords strictly in order and stops immediately when...

CF 1198F - GCD Groups 2

CF 1198F - GCD Groups 2 Rating: 2900 Tags: greedy, number theory, probabilities Solve time: 1m 57s Verified: yes Solution Problem Understanding We are given a list of integers and must split it into two non-empty groups. The requirement is not about sums or sizes, but about multiplicative structure: in each group, if you take the greatest common divisor of all its elements, the result must be exactly one. So...

CF 1265E - Beautiful Mirrors

CF 1265E - Beautiful Mirrors Rating: 2100 Tags: data structures, dp, math, probabilities Solve time: 2m 35s Verified: no Solution There is not enough information to diagnose the bug or provide a corrected solution. The sample 3 3 tab one bat with expected output 6 tabbat appears to belong to a string construction problem, but you have not provided: the problem statement, the original Python solution, or even the name...

Codeforces Round 604 (Div. 2)

Codeforces Round 604 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 1/2 | Rating range: 1000-2100 | Time: 4m Problem Name Rating Tags Solve Time Verified A Beautiful String 1000 constructive-algorithms, greedy 1m 25s ✓ E Beautiful Mirrors 2100 data-structures, dp, math 2m 35s ✗

CF 1295F - Good Contest

CF 1295F - Good Contest Rating: 2700 Tags: combinatorics, dp, probabilities Solve time: 1m 45s Verified: yes Solution Problem Understanding We are given a contest with n problems, where each problem i has a range [l_i, r_i] representing the possible number of accepted solutions. Each integer in this range is equally likely, and selections for different problems are independent. An inversion occurs when a problem that appears earlier in the...

2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2019-2020 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 12 problems | 3/12 verified | Difficulty 900-3500 | 22m 31s # Problem Rating Tags Accepted Time ✓ A Apprentice Learning Trajectory 2400 1,061 2m 35s B Balls of Buma 900 4,538 2m ✓ C Cactus Revenge 3500 constructive-algorithms 391 43s D DevOps Best Practices 2800 constructive-algorithms 261 2m 36s E Elections 1700 greedy 3,518...

CF 1361E - James and the Chase

CF 1361E - James and the Chase Rating: 3000 Tags: dfs and similar, graphs, probabilities, trees Solve time: 2m 53s Verified: no Solution Correct Solution for TAOCP 4.6.1.24 The exercise asks for a direct algebraic simplification of two displayed identities involving content and primitive part of polynomials over a unique factorization domain $S$. The goal is not to introduce new structural theorems, but to rewrite the given expressions until they...

CF 1392H - ZS Shuffles Cards

CF 1392H - ZS Shuffles Cards Rating: 3000 Tags: combinatorics, dp, math, probabilities Solve time: 2m 32s Verified: no Solution Solution Algorithm B is the binary gcd algorithm. A subtract-and-shift cycle consists of one subtraction, followed by the removal of all powers of $2$ from the resulting difference. Exercise 35 asks for the longest path in the corresponding graph; Exercise 36 asks for a construction that attains $m+1$ subtraction steps....

CF 1418E - Expected Damage

CF 1418E - Expected Damage Rating: 2400 Tags: binary search, combinatorics, probabilities Solve time: 1m 24s Verified: yes Solution Problem Understanding We have a fixed multiset of monster strengths. For each query, a shield starts with durability a and defence value b . Monsters are fought in a uniformly random order. A monster whose strength is at least b consumes one durability point but deals no damage. A weaker monster...

CF 1438F - Olha and Igor

CF 1438F - Olha and Igor Rating: 3000 Tags: interactive, probabilities, trees Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a perfect binary tree of height $h$, which contains $n = 2^h - 1$ nodes. Each node has a unique label from 1 to $n$, but the labeling is completely unknown. Our task is to determine the label of the root. We can interact with the...

Codeforces Round 688 (Div. 2)

Codeforces Round 688 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2700 | Time: 24m 16s Problem Name Rating Tags Solve Time Verified A Cancel the Trains 800 implementation 1m 25s ✓ B Suffix Operations 1400 constructive-algorithms, implementation 11m 6s ✓ C Triangles 1700 greedy, implementation 6m 32s ✓ D Checkpoints 1900 brute-force, constructive-algorithms, greedy 1m 49s ✗ E Dog Snacks 2300 binary-search, dfs-and-similar,...

CF 1453D - Checkpoints

CF 1453D - Checkpoints Rating: 1900 Tags: brute force, constructive algorithms, greedy, math, probabilities Solve time: 1m 49s Verified: no Solution Problem Understanding The problem asks us to design a sequence of game stages and checkpoints so that a player with a 50% chance of beating any stage has an exact expected number of tries over the whole game. Every stage may or may not have a checkpoint, and the...

Codeforces Round 686 (Div. 3)

Codeforces Round 686 (Div. 3) Type: Div. 3 | Problems: 6 | Verified: 2/6 | Rating range: 800-2100 | Time: 24m 40s Problem Name Rating Tags Solve Time Verified A Special Permutation 800 constructive-algorithms, probabilities 7m 42s ✗ B Unique Bid Auction 800 implementation 1m 23s ✓ C Sequence Transformation 1200 greedy, implementation 10m 13s ✓ D Number into Sequence 1300 constructive-algorithms, math, number-theory 1m 44s ✗ E Number of...

CF 1454A - Special Permutation

CF 1454A - Special Permutation Rating: 800 Tags: constructive algorithms, probabilities Solve time: 7m 42s Verified: no Solution Problem Understanding The task is to construct a permutation of length (n > 1) such that no element occupies its original position. In other words, for a permutation (p) of size (n), we require that (p_i \ne i) for every index (i). Each test case consists of a single integer (n), and...

Codeforces Round 691 (Div. 2)

Codeforces Round 691 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1300 | Time: 3m 2s Problem Name Rating Tags Solve Time Verified A Red-Blue Shuffle 800 math, probabilities 1m 23s ✓ B Move and Turn 1300 dp, math 1m 39s ✓

CF 1459A - Red-Blue Shuffle

CF 1459A - Red-Blue Shuffle Rating: 800 Tags: math, probabilities Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given a set of n cards, each with two digits: one red and one blue. After shuffling all the cards randomly, we read the red digits from left to right to form a number R and the blue digits similarly to form B . Two players, Red and Blue,...

CF 1461C - Random Events

CF 1461C - Random Events Rating: 1500 Tags: dp, math, probabilities Solve time: 7m 21s Verified: yes Solution Problem Understanding We are given an initial permutation and a sequence of probabilistic operations. Each operation focuses on a prefix of the permutation and, independently, sorts that prefix with a given probability. If the operation “fires”, the prefix becomes fully sorted; otherwise it remains unchanged. Operations are applied sequentially, and each decision...

CF 1477F - Nezzar and Chocolate Bars

CF 1477F - Nezzar and Chocolate Bars Rating: 3500 Tags: combinatorics, fft, math, probabilities Solve time: 2m 13s Verified: no Solution Problem Understanding Nezzar has a collection of chocolate bars with given lengths. His goal is to repeatedly split bars longer than a threshold $k$ until all bars are at most length $k$. Each split is probabilistic: a bar of length $x$ is chosen with probability proportional to $x$, and...

CF 1479E - School Clubs

CF 1479E - School Clubs Rating: 3500 Tags: dp, fft, math, number theory, probabilities Solve time: 3m 3s 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...

CF 1479D - Odd Mineral Resource

CF 1479D - Odd Mineral Resource Rating: 2900 Tags: binary search, bitmasks, brute force, data structures, probabilities, trees Solve time: 3m 13s Verified: no Solution Problem Understanding The input describes a tree where each node has a labeled value, and each query asks about a path in that tree. For any query, we look at all nodes on the unique path between two given cities and consider the multiset of...

CF 1510I - Is It Rated?

CF 1510I - Is It Rated? Rating: 2700 Tags: greedy, interactive, math, probabilities Solve time: 3m 29s Verified: no Solution Problem Understanding In this problem, you act as a participant, Izzy, in a series of wagers predicting whether improv contests will be rated or unrated. For each wager, you see the predictions of all other participants, then make your own prediction. After that, the real outcome is revealed. Your goal...

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 1525E - Assimilation IV

CF 1525E - Assimilation IV Rating: 2100 Tags: combinatorics, dp, math, probabilities, two pointers Solve time: 2m 33s Verified: no Solution Problem Understanding Monocarp has an empire of n cities and wants to control m points on a map. Each city can build one Monument. When a Monument is built, it controls all points within a distance that grows by 1 each turn. Specifically, if a Monument is built in...

CF 1526F - Median Queries

CF 1526F - Median Queries Rating: 3000 Tags: constructive algorithms, interactive, probabilities Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a hidden permutation of the numbers from 1 to n. The permutation is fixed, but we never see it directly. Instead, we can only interact with it through a query on three indices. A query picks three distinct positions a, b, c, and returns the median...

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 1540B - Tree Array

CF 1540B - Tree Array Rating: 2300 Tags: brute force, combinatorics, dp, graphs, math, probabilities, trees Solve time: 4m 3s Verified: no Solution Problem Understanding We are asked to calculate the expected number of inversions in a random process of marking nodes in a tree. The tree has n nodes, and the marking process begins with a uniformly random initial node. After that, nodes are added one by one, each...

CF 1562F - Tubular Bells

CF 1562F - Tubular Bells Rating: 2900 Tags: interactive, math, number theory, probabilities Solve time: 3m 24s Verified: no Solution Problem Understanding We are given a hidden permutation of integers that forms a contiguous interval, but the endpoints of that interval are unknown. Each position in the permutation stores a distinct integer, and together they cover every value in some range of length $n$. The only way to learn about...

CF 1571H - Laser Beams

CF 1571H - Laser Beams Rating: 2900 Tags: *special, geometry, probabilities Solve time: 4m 7s Verified: no Solution Problem Understanding We are given a rectangular game level defined by its width a and height b . Inside the level are n enemies, each at a unique position (x_i, y_i) . Every enemy is either basic or upgraded: basic enemies shoot four lasers along the axes, and upgraded enemies shoot lasers...

Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1)

Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1) Type: Div. 1 | Problems: 10 | Verified: 1/10 | Rating range: 2000-3200 | Time: 24m 39s Problem Name Rating Tags Solve Time Verified A Weights 2600 constructive-algorithms, greedy, two-pointers 8m 19s ✗ B Restaurant Game 3100 - 1m 38s ✗ C Bubble Strike 2000 combinatorics, math, probabilities 1m 44s ✗ D Bubble Popping 3200 -...

CF 1599C - Bubble Strike

CF 1599C - Bubble Strike Rating: 2000 Tags: combinatorics, math, probabilities, ternary search Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to determine how many maps Johnny must study to ensure that the probability he ends up playing on a studied map is at least $P$. The game process is as follows: from $N$ total maps, three are randomly presented, and each player discards one map....

CF 1612E - Messages

CF 1612E - Messages Rating: 2000 Tags: brute force, dp, greedy, probabilities, sortings Solve time: 1m 25s Verified: yes Solution Problem Understanding We have a group of students, each of whom Monocarp wants to read a specific message in a chat. Every student has a limit on how many messages they will read in a day. Monocarp can pin messages to make them more likely to be read, but students...

CF 1623D - Robot Cleaner Revisit

CF 1623D - Robot Cleaner Revisit Rating: 2300 Tags: implementation, math, probabilities Solve time: 1m 57s Verified: no Solution Problem Understanding A robot moves deterministically inside an $n \times m$ grid, bouncing off walls like a billiard ball. Its velocity starts as $(+1, +1)$, and whenever it would cross a boundary, the corresponding direction component flips before the move. This creates a fully periodic walk over the grid. At every...

CF 1626F - A Random Code Problem

CF 1626F - A Random Code Problem Rating: 2800 Tags: combinatorics, dp, math, number theory, probabilities Solve time: 1m 37s Verified: no Solution Problem Understanding We are working with a long array generated by a linear recurrence, and then a randomized process that repeatedly samples elements from this array and mutates the sampled value. At each of $k$ rounds, we pick a uniformly random index $idx$ from $0$ to $n-1$....

CF 1630E - Expected Components

CF 1630E - Expected Components Rating: 2900 Tags: combinatorics, math, number theory, probabilities Solve time: 2m 32s Verified: no Solution This problem is rated 3500 and its solution relies on a fairly deep structural characterization of graphs whose cycle space admits a consistent cyclic orientation. Producing a correct editorial requires reconstructing the full proof and construction, not merely explaining a known implementation trick. I do not currently have enough verified...

CF 1705F - Mark and the Online Exam

CF 1705F - Mark and the Online Exam Rating: 2900 Tags: bitmasks, constructive algorithms, interactive, probabilities Solve time: 2m 36s Verified: no Solution Problem Understanding We are asked to recover the answer key for an online true/false exam with $n$ questions. Each question has exactly one correct answer, either 'T' for true or 'F' for false. The only way to learn about the answer key is through a grading system:...

CF 1713D - Tournament Countdown

CF 1713D - Tournament Countdown Rating: 1800 Tags: constructive algorithms, greedy, interactive, number theory, probabilities Solve time: 1m 55s Verified: no Solution Problem Understanding We are dealing with a complete single-elimination tournament of size $2^n$. Players are indexed from 1 to $2^n$. Matches happened in a fixed bracket: adjacent pairs played first, then winners of neighboring matches played again, and so on until one champion remains. We do not see...

CF 1737E - Ela Goes Hiking

CF 1737E - Ela Goes Hiking Rating: 2500 Tags: combinatorics, dp, math, probabilities Solve time: 2m 34s Verified: no Solution Problem Understanding We are asked to simulate a line of identical ants on a stick, each moving randomly left or right. The ants "fight" when they collide: the heavier one eats the lighter, or if equal, the one moving left wins. After some time, only one ant survives. The input...

CF 1743D - Problem with Random Tests

CF 1743D - Problem with Random Tests Rating: 1700 Tags: brute force, dp, greedy, probabilities Solve time: 3m 58s Verified: no Solution Problem Understanding We are given a binary string. We may choose any two substrings of that string, convert each substring into the integer represented by its binary notation, and take the bitwise OR of those two integers. The goal is to maximize the resulting value and print that...

CF 1743F - Intersection and Union

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

CF 1746F - Kazaee

CF 1746F - Kazaee Rating: 2800 Tags: data structures, hashing, probabilities Solve time: 1m 19s Verified: no Solution Producing a correct editorial for Codeforces 1746F requires reconstructing the intended probabilistic proof, the exact hashing scheme, the error analysis, and the implementation details used to achieve acceptance at $n,q \le 3\cdot 10^5$. I can see the problem statement and several secondary references, and they confirm the high level idea: assign random...

Codeforces Round 829 (Div. 1)

Codeforces Round 829 (Div. 1) Type: Div. 1 | Problems: 7 | Verified: 2/7 | Rating range: 1300-3500 | Time: 19m 17s Problem Name Rating Tags Solve Time Verified A1 Make Nonzero Sum (easy version) 1300 constructive-algorithms, dp, greedy 2m 58s ✗ A2 Make Nonzero Sum (hard version) 1500 constructive-algorithms, dp, greedy 1m 14s ✗ B Factorial Divisibility 1600 math, number-theory 4m 40s ✓ C Wish I Knew How to...

CF 1753C - Wish I Knew How to Sort

CF 1753C - Wish I Knew How to Sort Rating: 2000 Tags: dp, math, probabilities Solve time: 2m 20s Verified: no Solution Problem Understanding We are given a binary array, meaning every element is either 0 or 1. The array evolves through repeated random operations: at each step we pick a uniformly random pair of indices $(i, j)$ with $i < j$. If the left value is 1 and the...

CF 1761G - Centroid Guess

CF 1761G - Centroid Guess Rating: 3500 Tags: interactive, probabilities, trees Solve time: 5m 43s Verified: no Solution Problem Understanding We are given a hidden tree with n nodes, and we do not know its structure. Our goal is to identify its centroid, which is the unique node such that removing it leaves all connected components with at most n/2 nodes each. The interaction allows us to query the distance...

CF 1765G - Guess the String

CF 1765G - Guess the String Rating: 2600 Tags: constructive algorithms, interactive, probabilities Solve time: 2m 3s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden binary string of length $n$, knowing that its first character is always '0'. We cannot read the string directly. Instead, we can query two special functions: the prefix function $p_i$, which measures the length of the longest prefix that matches the...

CF 1765F - Chemistry Lab

CF 1765F - Chemistry Lab Rating: 2200 Tags: dp, geometry, probabilities Solve time: 2m 17s Verified: no Solution Problem Understanding We have a chemistry lab scenario where Monocarp can buy contracts that give him unlimited access to specific solutions of an acid. Each contract specifies the concentration of the solution, the cost to sign the contract, and the price he can sell it for. Monocarp expects a number of customers,...

CF 1765C - Card Guessing

CF 1765C - Card Guessing Rating: 2600 Tags: combinatorics, dp, probabilities Solve time: 4m 5s Verified: yes Solution Problem Understanding We are dealing with a long sequence of independent random experiments: a deck contains exactly four suits, and each suit appears exactly (n) times, so the total length is (4n). The deck is shuffled uniformly at random, so every permutation is equally likely. A player scans the deck from top...

CF 1770E - Koxia and Tree

CF 1770E - Koxia and Tree Rating: 2400 Tags: combinatorics, dfs and similar, dp, dsu, math, probabilities, trees Solve time: 2m 4s Verified: no Solution Problem Understanding We are given a tree with $n$ vertices and $k$ butterflies initially located on distinct vertices. Each edge in the tree will be randomly directed, and butterflies can move along edges if the starting vertex has a butterfly and the target vertex is...

CF 1771F - Hossam and Range Minimum Query

CF 1771F - Hossam and Range Minimum Query Rating: 2500 Tags: binary search, bitmasks, data structures, hashing, probabilities, strings, trees Solve time: 2m 17s Verified: no Solution Problem-Type Check This is a Type B (prove inequality) problem, not Type C. The task is to prove that $$\frac1{a^3(b+c)}+\frac1{b^3(c+a)}+\frac1{c^3(a+b)}\ge \frac32$$ for all positive $a,b,c$ satisfying $abc=1$. A valid solution must establish the inequality for all admissible triples and correctly identify any equality...

CF 1773G - Game of Questions

CF 1773G - Game of Questions Rating: 2800 Tags: bitmasks, combinatorics, dp, fft, math, probabilities Solve time: 4m 17s Verified: yes Solution Problem Understanding Each test case gives a binary matrix with up to 17 columns and up to 2⋅10^5 rows. Each column represents a participant, and each row describes which participants would answer a particular question correctly. The questions are randomly permuted before being asked. As the sequence runs,...

CF 1777D - Score of a Tree

CF 1777D - Score of a Tree Rating: 1900 Tags: bitmasks, combinatorics, dfs and similar, dp, math, probabilities, trees Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a rooted tree with n nodes. Each node initially holds a value of either 0 or 1. The evolution of values in the tree is defined by a simple rule: at each integer time t > 0 , every...

CF 1778D - Flexible String Revisit

CF 1778D - Flexible String Revisit Rating: 2100 Tags: combinatorics, dp, math, probabilities Solve time: 1m 38s Verified: no Solution Problem Understanding Two binary strings of equal length evolve over time, but only one of them changes. At every move, we pick a position uniformly among all indices and flip the bit of the first string at that position. The second string is fixed. We are interested in how long...

CF 1784E - Infinite Game

CF 1784E - Infinite Game Rating: 3100 Tags: brute force, combinatorics, dp, games, probabilities Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a short string consisting of characters that can be interpreted as decisions in a repeated competitive process. Each character represents a round outcome between two players, and the string is repeated infinitely to generate an endless sequence of rounds. These rounds are grouped into...

Codeforces Round 851 (Div. 2)

Codeforces Round 851 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 800-2500 | Time: 10m 18s Problem Name Rating Tags Solve Time Verified A One and Two 800 brute-force, implementation, math 1m 51s ✓ B Sum of Two Numbers 1100 constructive-algorithms, greedy, implementation 2m 1s ✗ C Matching Numbers 1300 constructive-algorithms, greedy, math 1m 51s ✗ D Moving Dots 2000 binary-search, brute-force, combinatorics 1m...

CF 1819E - Roads in E City

CF 1819E - Roads in E City Rating: 3200 Tags: interactive, math, probabilities, trees Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a city represented as a graph with intersections as nodes and roads as edges. Some roads have been repaired and allow traffic, while others have not. Our task is to determine exactly which roads are repaired. The twist is that we do not know...

CF 1823F - Random Walk

CF 1823F - Random Walk Rating: 2600 Tags: dp, graphs, math, probabilities, trees Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a tree where a chip performs a random walk that stops only when it reaches a designated target vertex $t$. At each step, if the chip is at a vertex $v$, it chooses one of its neighbors uniformly at random, moves there, and increments a...

Codeforces Round 872 (Div. 1)

Codeforces Round 872 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1400-3500 | Time: 11m 28s Problem Name Rating Tags Solve Time Verified A LuoTianyi and the Show 1400 greedy, implementation 4m 6s ✗ B1 LuoTianyi and the Floating Islands (Easy Version) 1800 combinatorics, math, probabilities 1m 45s ✓ B2 LuoTianyi and the Floating Islands (Hard Version) 2300 combinatorics, dfs-and-similar, math 1m 19s ✓...

CF 1824B1 - LuoTianyi and the Floating Islands (Easy Version)

CF 1824B1 - LuoTianyi and the Floating Islands (Easy Version) Rating: 1800 Tags: combinatorics, math, probabilities, trees Solve time: 1m 45s Verified: yes Solution Problem Understanding We are given a tree with $n$ nodes representing islands. On this tree, $k$ distinct nodes are chosen uniformly at random to host people. For any fixed configuration of these $k$ nodes, every island can compute the total distance to all chosen nodes. An...

CF 1824B2 - LuoTianyi and the Floating Islands (Hard Version)

CF 1824B2 - LuoTianyi and the Floating Islands (Hard Version) Rating: 2300 Tags: combinatorics, dfs and similar, math, probabilities, trees Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a tree with $n$ nodes. Then we choose $k$ distinct nodes uniformly at random, and place one “person” on each of them. For every node in the tree, we compute its total distance to these $k$ chosen nodes,...

CF 1826F - Fading into Fog

CF 1826F - Fading into Fog Rating: 2800 Tags: geometry, interactive, math, probabilities Solve time: 1m 21s Verified: no Solution Problem Understanding We are asked to find a set of hidden points on a 2D plane using queries that return projections of all points onto a line of our choice. Each query gives us the locations of these projections along the line, with slight precision errors. The points themselves are...

CF 1835E - Old Mobile

CF 1835E - Old Mobile Rating: 3500 Tags: combinatorics, dp, probabilities Solve time: 1m 35s Verified: no Solution Problem Understanding We are asked to compute the expected number of button presses needed to type a number on an old mobile device with an unfamiliar keyboard. The keyboard has $m$ digit buttons and a backspace. Jan, the user, cannot distinguish which button is which until he presses it. If he presses...

CF 1835C - Twin Clusters

CF 1835C - Twin Clusters Rating: 2600 Tags: bitmasks, brute force, constructive algorithms, math, probabilities Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a sequence of galaxies, each with a certain number of stars. The total number of galaxies in a test case is always a power of two, specifically $2^{k+1}$. Each galaxy has a star count between 0 and $4^k - 1$. Our goal is...

CF 1836E - Twin Clusters

CF 1836E - Twin Clusters Rating: 2600 Tags: constructive algorithms, meet-in-the-middle, probabilities Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a sequence of integers for each test case, and we are allowed to look at any contiguous segment of this sequence. For any segment, we define its value as the bitwise XOR of all elements inside it. The task is to determine whether we can find...

CF 1840G1 - In Search of Truth (Easy Version)

CF 1840G1 - In Search of Truth (Easy Version) Rating: 2200 Tags: constructive algorithms, interactive, math, meet-in-the-middle, probabilities Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a circular arrangement of sectors numbered from 1 to some unknown integer $n$. The sectors are arranged in a fixed, but arbitrary order, and we initially see the number of the sector where the arrow points. Our task is to...

CF 1840G2 - In Search of Truth (Hard Version)

CF 1840G2 - In Search of Truth (Hard Version) Rating: 2500 Tags: constructive algorithms, interactive, math, meet-in-the-middle, probabilities Solve time: 1m 21s Verified: no Solution Problem Understanding We are placed in a circular arrangement of sectors numbered from 1 to $n$, but we do not know either the total number $n$ or the order of the numbers around the circle. Initially, the arrow points to a sector, and we are...

CF 1842H - Tenzing and Random Real Numbers

CF 1842H - Tenzing and Random Real Numbers Rating: 3000 Tags: bitmasks, dp, graphs, math, probabilities Solve time: 1m 55s Verified: no Solution Problem Understanding We have $n$ independent random variables, each chosen uniformly from the interval $[0,1]$. Between pairs of variables we are given constraints of the form $$x_i+x_j\le 1$$ or $$x_i+x_j\ge 1.$$ The task is to compute the probability that all constraints hold simultaneously. The most important observation...

CF 1842G - Tenzing and Random Operations

CF 1842G - Tenzing and Random Operations Rating: 2800 Tags: combinatorics, dp, math, probabilities Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given an array where each element starts as a fixed value, and then we repeatedly apply a random “suffix increment” operation. In one operation we pick an index uniformly from the array, and we add a constant value v to every element from that index...

CF 1847E - Triangle Platinum?

CF 1847E - Triangle Platinum? Rating: 2900 Tags: brute force, combinatorics, implementation, interactive, math, probabilities Solve time: 1m 20s Verified: no Solution Problem Understanding We are given an array of $n$ hidden integers, each between $1$ and $4$. We cannot see these numbers directly, but we can ask queries about triples of indices. Each query returns a number related to the area of a triangle formed by the three values...

CF 1854C - Expected Destruction

CF 1854C - Expected Destruction Rating: 2500 Tags: combinatorics, dp, math, probabilities Solve time: 1m 55s Verified: no Solution Problem Understanding We are given a set of distinct integers S drawn from the range 1 to m . Every second, we perform a stochastic operation: we select an element x from S uniformly at random, remove it, and if x+1 is within bounds and absent from S , we add...

CF 1855E - Expected Destruction

CF 1855E - Expected Destruction Rating: 2500 Tags: dp, math, probabilities Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a set of distinct integers between 1 and some maximum value m . At each second, we remove a random element x from the set. After removing it, if x+1 is within bounds and not already in the set, we add x+1 . The question asks for...

CF 2220E - Coloring a Red Black Tree

CF 2220E - Coloring a Red Black Tree Rating: 2300 Tags: dp, greedy, probabilities, sortings, trees Solve time: 2m 2s Verified: no Solution Problem Understanding We are given a tree with n nodes, where each node is either red or black. The goal is to make all nodes red using a stochastic operation: you select a node and recolor it with the color of one of its neighbors chosen uniformly...

CF 2175E2 - Beautiful Patterns (Hard Version)

CF 2175E2 - Beautiful Patterns (Hard Version) Rating: 2500 Tags: combinatorics, math, probabilities Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to compute the expected beauty of a one-dimensional mosaic of length $n$, where each position is independently colored using one of $m$ colors. The beauty is defined as the square of the number of palindromic subsegments of the mosaic. A subsegment is palindromic if it...

CF 2175E1 - Beautiful Patterns (Easy Version)

CF 2175E1 - Beautiful Patterns (Easy Version) Rating: 2400 Tags: combinatorics, math, probabilities Solve time: 1m 53s Verified: no Solution Problem Understanding We are looking at a random string of length $n$, where each position independently receives one of $m$ colors with equal probability. Every contiguous segment of the string contributes a value depending on whether it is a palindrome, and we count how many palindromic segments exist. That count...

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

CF 2090F2 - Key of Like (Hard Version)

CF 2090F2 - Key of Like (Hard Version) Rating: 3100 Tags: dp, math, probabilities Solve time: 1m 24s Verified: no Solution Problem Understanding We are asked to simulate a sequential key-and-lock game among n players. There are l locks, each with a unique corresponding key, and k counterfeit keys that do not open any lock. Each turn, a player picks a key and a lock to maximize the probability of...

CF 2090F1 - Key of Like (Easy Version)

CF 2090F1 - Key of Like (Easy Version) Rating: 2200 Tags: combinatorics, dp, math, probabilities Solve time: 1m 31s Verified: no Solution Problem Understanding We are asked to calculate the expected number of successful key-lock matches for each participant in a turn-based game. There are $n$ members taking turns sequentially, $l$ locks, and exactly $l$ keys (since $k = 0$ in this easy version). Each key opens exactly one lock....

CF 2082C - Math Division

CF 2082C - Math Division Rating: 1800 Tags: bitmasks, dp, math, probabilities Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a positive integer in binary representation, and the task is to compute the expected number of operations needed to reduce this number to 1. The operations allowed are halving the number, either by floor division or ceiling division, chosen independently with equal probability at each step....

CF 2078C - Breach of Faith

CF 2078C - Breach of Faith Rating: 1500 Tags: constructive algorithms, greedy, math, probabilities, sortings Solve time: 1m 27s Verified: no Solution Problem Understanding We are given a sequence of integers of length 2n+1 that satisfies a special alternating sum property: the first element equals the sum of the remaining elements taken with alternating signs, specifically a1 = a2 - a3 + a4 - a5 + ... + a2n -...

CF 1875F - Jellyfish and EVA

CF 1875F - Jellyfish and EVA Rating: 2300 Tags: dp, graphs, greedy, math, probabilities Solve time: 1m 10s Verified: no Solution Correctness The solution correctly restates the exercise in terms of the frequency test and the chi-square statistic for $b$ categories. It identifies the expected value $E(\chi^2)=b-1$ and explains why the observed value $1.06$ for the first 2000 decimal digits is unusually small. The solution addresses the exact question of...

CF 1864E - Guess Game

CF 1864E - Guess Game Rating: 2100 Tags: bitmasks, data structures, games, math, probabilities, sortings, strings, trees Solve time: 2m 9s Verified: no Solution Problem Understanding We are given a multiset of integers, and we repeatedly imagine picking two positions independently, forming an ordered pair of values $(a, b)$. Along with $a$ and $b$, both players also learn the bitwise OR $x = a \mid b$. Alice and Bob know...

CF 1866M - Mighty Rock Tower

CF 1866M - Mighty Rock Tower Rating: 2400 Tags: brute force, combinatorics, dp, math, probabilities Solve time: 2m 18s Verified: no Solution Problem Understanding We are asked to compute the expected number of moves to build a tower of height N using identical small rocks, where each placement may trigger a cascading fall of the top rocks. Every time a rock is placed at height x , the topmost rock...

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

CF 1874C - Jellyfish and EVA

CF 1874C - Jellyfish and EVA Rating: 2300 Tags: dp, graphs, greedy, math, probabilities Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a directed acyclic graph in a very specific form: every edge goes from a smaller numbered city to a larger numbered city. This means the graph is already topologically sorted by vertex index. We start at city 1 and want to reach city n....

CF 1912F - Fugitive Frenzy

CF 1912F - Fugitive Frenzy Rating: 3100 Tags: math, probabilities Solve time: 3m 5s Verified: no Solution Problem Understanding We are asked to compute the expected duration of a pursuit on a tree, where a police officer and a fugitive take turns moving. The city is represented as an undirected tree with $n$ vertices. The police officer starts at a fixed vertex, while the fugitive chooses any other vertex to...

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

CF 1924E - Paper Cutting Again

CF 1924E - Paper Cutting Again Rating: 3100 Tags: combinatorics, probabilities Solve time: 2m 13s Verified: no Solution Problem Understanding We are asked to model a stochastic process of repeatedly cutting a rectangular sheet of paper and discarding parts of it, and then compute the expected number of steps until its area falls below a threshold. The paper starts with dimensions $n \times m$, and at each step a cut...

CF 1925D - Good Trip

CF 1925D - Good Trip Rating: 1900 Tags: combinatorics, dp, math, probabilities Solve time: 2m 9s Verified: yes Solution Problem Understanding We have a graph on n children. Only m pairs are marked as friends, and each friendship edge has an initial weight f . The teacher performs exactly k excursions. During each excursion, one unordered pair of children is selected uniformly at random from all possible pairs. The same...

European Championship 2025 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

European Championship 2025 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ICPC/IOI | 11 problems | 4/11 verified | Difficulty 1900-3500 | 17m 46s # Problem Rating Tags Accepted Time ✓ A Condorcet Elections 2300 constructive-algorithms, graphs, greedy 997 1m 20s ✓ B Urban Planning 3100 constructive-algorithms 143 1m 30s ✓ C Ads 2100 binary-search, greedy, two-pointers 1,637 2m 40s D Morse Code 3100 dp, sortings, trees 265 1m 56s...

Codeforces Round 1010 (Div. 1, Unrated)

Codeforces Round 1010 (Div. 1, Unrated) Div. 1 | 8 problems | 2/8 verified | Difficulty 1800-3400 | 11m 13s # Problem Rating Tags Accepted Time ✓ A Math Division 1800 bitmasks, dp, math 4,078 1m 37s B Balancing 2500 greedy 997 1m 52s C Quaternary Matrix 2700 bitmasks, constructive-algorithms, greedy 353 1m 37s D MST in Modulo Graph 2600 constructive-algorithms, dsu, graphs 1,182 1m 39s E Quantifier 3300 combinatorics,...

CF 1970D2 - Arithmancy (Medium)

CF 1970D2 - Arithmancy (Medium) Rating: 2600 Tags: constructive algorithms, interactive, probabilities, strings Solve time: 1m 57s Verified: no Solution Problem Understanding We are asked to play the role of Professor Vector. We need to construct a set of distinct magic words made of 'X' and 'O' and then, given a number called the power of a spell, figure out which two words (and in which order) were concatenated to...

CF 1983E - I Love Balls

CF 1983E - I Love Balls Rating: 2300 Tags: combinatorics, math, probabilities Solve time: 3m 20s Verified: yes Solution Problem Understanding There are two kinds of balls. The first k balls are special, the remaining n-k are ordinary. Every ball has a value. The balls are removed one by one in a uniformly random order. The current player takes the chosen ball and adds its value to their score. The...

CF 2003F - Turtle and Three Sequences

CF 2003F - Turtle and Three Sequences Rating: 2800 Tags: brute force, data structures, dp, greedy, math, probabilities, two pointers Solve time: 2m 22s Verified: no Solution Problem-Type Check This is a counting problem, so it is closest to Type C in the supplied classification. The requirement is to determine the exact number of admissible fillings and justify the count rigorously. No optimization bound or equality case is involved, but...

CF 2020E - Expected Power

CF 2020E - Expected Power Rating: 2000 Tags: bitmasks, dp, math, probabilities Solve time: 2m 32s Verified: no Solution Problem Understanding We are given an array of integers, each with an independent probability of being included in a random multiset. The task is to compute the expected value of the square of the XOR of all selected elements. The input provides probabilities as integers out of 10,000 and the array...

CF 2023D - Many Games

CF 2023D - Many Games Rating: 2900 Tags: brute force, dp, greedy, math, probabilities Solve time: 1m 47s Verified: yes Solution Problem Understanding The problem presents a casino with multiple games, each offering a chance to win a certain amount. Each game has two parameters: a probability of winning, given as a percentage, and a payout if you win. You can choose any subset of games to play, but you...

CF 2028E - Alice's Adventures in the Rabbit Hole

CF 2028E - Alice's Adventures in the Rabbit Hole Rating: 2300 Tags: combinatorics, dfs and similar, dp, games, greedy, math, probabilities, trees Solve time: 1m 23s Verified: no Solution Problem Understanding We are given a tree with n vertices where vertex 1 is considered the exit of the rabbit hole, and Alice starts at some vertex v . Each turn a fair coin is flipped. On heads, Alice chooses an...

CF 2031F - Penchick and Even Medians

CF 2031F - Penchick and Even Medians Rating: 2800 Tags: binary search, constructive algorithms, interactive, probabilities Solve time: 2m 33s Verified: no Solution Problem Understanding The original problem is interactive: there is a hidden permutation, and we must locate the positions of the two middle values, namely $\frac n2$ and $\frac n2 + 1$, using median queries. For the hack version used in the archive, the interaction is removed. The...

CF 2127G2 - Inter Active (Hard Version)

CF 2127G2 - Inter Active (Hard Version) Rating: 3500 Tags: binary search, bitmasks, constructive algorithms, graphs, implementation, interactive, math, probabilities Solve time: 3m 19s Verified: no Solution Problem Understanding We are dealing with a hidden structure, a permutation of size $n$, where every position points to exactly one value and no value repeats. There is an additional restriction that no element stays in its original position, so the permutation contains...

CF 2127F - Hamed and AghaBalaSar

CF 2127F - Hamed and AghaBalaSar Rating: 2800 Tags: brute force, combinatorics, dp, math, probabilities Solve time: 3m 4s Verified: no Solution You’re not dealing with a “small bug anymore” - the issue is that the last solution implicitly solved a different problem (monotone feasibility) than the one your samples are testing. We can prove that directly from the third failing case. 1. Why the previous logic is wrong Take...

CF 2127G1 - Inter Active (Easy Version)

CF 2127G1 - Inter Active (Easy Version) Rating: 3400 Tags: binary search, constructive algorithms, interactive, probabilities Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a hidden permutation of size $n$, with the additional promise that no element stays in its own position. So every index points to a different value, and every value appears exactly once. We cannot see this permutation directly. Instead, we are allowed...

CF 2115C - Gellyfish and Eternal Violet

CF 2115C - Gellyfish and Eternal Violet Rating: 2700 Tags: combinatorics, dp, greedy, math, probabilities Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a group of monsters, each starting with some integer health value. Over a fixed number of rounds, we interact with a probabilistic weapon that sometimes performs a global action and sometimes allows a targeted action. Our goal is to reduce every monster’s health...

CF 2040E - Control of Randomness

CF 2040E - Control of Randomness Rating: 2100 Tags: combinatorics, dfs and similar, dp, graphs, greedy, math, probabilities, trees Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a tree, an undirected connected acyclic graph, with n vertices rooted at vertex 1 . A robot starts at some vertex v ≠ 1 and moves toward the root. Odd-numbered steps are deterministic: the robot always moves one step...

CF 2068A - Condorcet Elections

CF 2068A - Condorcet Elections Rating: 2300 Tags: constructive algorithms, graphs, greedy, probabilities Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given a directed relationship between candidates, where an input pair “a defeats b” is not a vote but a constraint on the final outcome we must simulate. The real output is not a ranking itself but a multiset of full rankings (permutations of all candidates), such...

CF 2071E - LeaFall

CF 2071E - LeaFall Rating: 2600 Tags: combinatorics, dp, probabilities, trees Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a tree with n vertices, where each vertex i has a probability p_i/q_i of "falling". When a vertex falls, it is removed along with all its incident edges, but its neighbors remain. After some subset of vertices have fallen, the remaining structure is a forest. A leaf...

CF 2074E - Empty Triangle

CF 2074E - Empty Triangle Rating: 1600 Tags: geometry, interactive, probabilities Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a hidden set of points on a plane, and we know there are no duplicates and no three points are collinear. The challenge is that we do not know their coordinates. We are allowed to query the interactor with any triangle formed by three points, and it...

CF 2074C - XOR and Triangle

CF 2074C - XOR and Triangle Rating: 1100 Tags: bitmasks, brute force, geometry, greedy, probabilities Solve time: 1m 33s Verified: no Solution Problem Understanding We are asked to find, for a given integer x ≥ 2 , another integer y such that three numbers x , y , and x XOR y can form a non-degenerate triangle, where a non-degenerate triangle is defined by the triangle inequality. The number y...

CF 2081A - Math Division

CF 2081A - Math Division Rating: 1800 Tags: bitmasks, dp, math, probabilities Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a number $x$, but instead of its decimal value we only receive its binary representation. The process we care about repeatedly transforms this number until it becomes $1$. At each step, one of two operations is applied with equal probability. One operation takes floor division by...

CF 2089C2 - Key of Like (Hard Version)

CF 2089C2 - Key of Like (Hard Version) Rating: 3100 Tags: dp, math, probabilities Solve time: 2m 2s Verified: no Solution Problem Understanding We are given a game where n members take turns trying to open l locks using a set of l + k keys. Among these keys, exactly l are genuine and each opens exactly one lock, while the remaining k keys are fake. Each member chooses one...

CF 2089C1 - Key of Like (Easy Version)

CF 2089C1 - Key of Like (Easy Version) Rating: 2200 Tags: dp, games, math, probabilities Solve time: 1m 50s Verified: no Solution Problem Understanding In this problem, we are asked to simulate a sequential game where a group of n participants try to unlock l locks using exactly l valid keys. Each participant takes one turn at a time in a fixed cyclic order. On each turn, a participant chooses...

Codeforces Round 1008 (Div. 2)

Codeforces Round 1008 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-2700 | Time: 11m 26s Problem Name Rating Tags Solve Time Verified A Final Verdict 800 math 1m 33s ✓ B Vicious Labyrinth 1100 constructive-algorithms, graphs, greedy 1m 16s ✓ C Breach of Faith 1500 constructive-algorithms, greedy, math 1m 27s ✗ D Scammy Game Ad 1800 dp, greedy, implementation 2m 33s ✓ E...

CF 2125D - Segments Covering

CF 2125D - Segments Covering Rating: 1600 Tags: dp, math, probabilities Solve time: 1m 40s Verified: yes Solution Problem Understanding We are working with a line of $m$ cells. Each cell must end up being covered by exactly one chosen interval. There are $n$ candidate segments. Each segment $i$ covers a contiguous range $[l_i, r_i]$, but it is not guaranteed to exist. Instead, it appears independently with probability $p_i /...

CF 2127H - 23 Rises Again

CF 2127H - 23 Rises Again Rating: 3100 Tags: brute force, dfs and similar, dp, flows, graph matchings, graphs, greedy, implementation, probabilities, trees Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given an undirected, connected graph with up to 30 vertices, where each vertex belongs to at most 5 simple cycles. A simple cycle here is a closed path where each vertex has exactly two neighbors. A...

CF 2140E2 - Prime Gaming (Hard Version)

CF 2140E2 - Prime Gaming (Hard Version) Rating: 2500 Tags: bitmasks, combinatorics, dp, probabilities Solve time: 1m 59s Verified: no Solution Problem Understanding We have a sequence of n piles. The number of stones in each pile can be any integer from 1 to m . The game itself does not depend on the stone values while moves are being made. Players only choose positions to delete. At every turn,...

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

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

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

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

CF 2162G - Beautiful Tree

CF 2162G - Beautiful Tree Rating: 2200 Tags: constructive algorithms, math, probabilities, trees Solve time: 1m 37s Verified: yes Solution Problem Understanding We are asked to construct a labeled tree with $n$ vertices such that the sum of the products of the labels of each edge is a perfect square. Formally, if the tree has edges $(u, v)$, we compute $S = \sum (u \cdot v)$, and $S$ must equal...

CF 2173E - Shiro's Mirror Duel

CF 2173E - Shiro's Mirror Duel Rating: 2200 Tags: constructive algorithms, greedy, interactive, probabilities, sortings Solve time: 2m 26s Verified: no Solution Problem Understanding We maintain a permutation of 1..n . A query chooses two indices x and y . The judge then flips a coin. Either positions (x,y) are swapped, or their mirrored positions (n-x+1, n-y+1) are swapped. After the swap, we are told which pair was actually exchanged,...

CF 2174C1 - Beautiful Patterns (Easy Version)

CF 2174C1 - Beautiful Patterns (Easy Version) Rating: 2400 Tags: combinatorics, math, probabilities Solve time: 4m 5s Verified: no Solution Problem Understanding We are asked to compute the expected beauty of a linear mosaic of pebbles, where each pebble is painted in one of $m$ colors chosen independently and uniformly. A mosaic of length $n$ has its correctness defined as the number of palindromic subsegments, and its beauty is the...

CF 2174C2 - Beautiful Patterns (Hard Version)

CF 2174C2 - Beautiful Patterns (Hard Version) Rating: 2500 Tags: combinatorics, math, probabilities Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to calculate the expected beauty of a 1×n mosaic, where each cell is painted independently with one of m colors. Beauty is defined as the square of the number of palindromic subsegments. A subsegment is palindromic if it reads the same forwards and backwards. Since...

CF 2178G - deCH OR Dations

CF 2178G - deCH OR Dations Rating: 2800 Tags: bitmasks, data structures, dp, hashing, probabilities Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a circle with $2n$ points labeled from $1$ to $2n$. Santa draws $n$ chords connecting distinct pairs of points. Chords may intersect. For each prefix of chords $1$ through $\ell$, we are asked whether the chords are tight-knit . A set of chords...

CF 2180F1 - Control Car (Easy Version)

CF 2180F1 - Control Car (Easy Version) Rating: 2800 Tags: combinatorics, dp, probabilities Solve time: 5m 10s Verified: no Solution Problem Understanding The grid in this problem is best thought of as a lattice of junction points, not cells. Every intersection point on the grid is assigned one of four directions. From each such point, we draw a unit segment in its chosen direction. These segments act as walls that...

CF 2180F2 - Control Car (Hard Version)

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

CF 2181J - Jinx or Jackpot

CF 2181J - Jinx or Jackpot Rating: 2300 Tags: brute force, dp, math, probabilities Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a casino machine whose behaviour is determined by one hidden probability value. There is an array of probabilities, and the casino owner secretly picks one index uniformly at random at the start and fixes it forever. That chosen entry defines a single-slot machine: whenever...

CF 2190D - Prufer Vertex

CF 2190D - Prufer Vertex Rating: 2500 Tags: combinatorics, dsu, number theory, probabilities, trees Solve time: 2m 45s Verified: no Solution Problem Understanding We start with a forest. We may add edges between its connected components until the whole graph becomes a single tree. For every resulting tree, run the standard Prüfer-code deletion process: repeatedly remove the smallest numbered leaf until only two vertices remain. One of those vertices is...

CF 2192F - Fish Fight

CF 2192F - Fish Fight Rating: 2900 Tags: dp, math, probabilities Solve time: 47s Verified: no Solution I can write a full editorial only if I first reconstruct the actual solution in detail. For this problem, the official editorial contains a fairly intricate two-phase DP with interval states, probability propagation, prefix/suffix aggregation, and a second DP once the two special fish become adjacent. The snippet I could verify explains the...

CF 2200G - Operation Permutation

CF 2200G - Operation Permutation Rating: 2200 Tags: combinatorics, dp, math, probabilities Solve time: 2m 17s Verified: no Solution Problem Understanding We are given a starting integer $x$ and a list of $n$ operations, each of which modifies $x$ by either addition, subtraction, multiplication, or division by a positive integer. The twist is that the operations are applied in a random order: all $n!$ permutations are equally likely. We are...

Codeforces Round 265 (Div. 1)

Codeforces Round 265 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-3000 | 8m 25s # Problem Rating Tags Accepted Time ✓ A No to Palindromes! 1700 greedy, strings 6,235 2m ✓ B Restore Cube 2000 brute-force, geometry 1,782 2m 45s C Substitutes in Number 2100 dp 1,952 1m 15s ✓ D World of Darkraft - 2 2700 dp, probabilities 757 1m 5s E The Classic...

Codeforces Round 282 (Div. 1)

Codeforces Round 282 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1500-3200 | 7m 13s # Problem Rating Tags Accepted Time ✓ A Treasure 1500 greedy 6,548 1m 33s ✓ B Obsessive String 2000 dp, strings 3,111 1m 52s ✓ C Helping People 2600 dp, probabilities 958 42s ✓ D Birthday 2700 data-structures, dfs-and-similar, dp 669 1m 47s E Sharti 3200 data-structures, games 374 1m 19s...

Codeforces Round 204 (Div. 1)

Codeforces Round 204 (Div. 1) Div. 1 | 5 problems | 5/5 verified | Difficulty 1800-2700 | 9m 11s # Problem Rating Tags Accepted Time ✓ A Jeff and Rounding 1800 dp, greedy, implementation 3,096 1m 31s ✓ B Jeff and Furik 1900 combinatorics, dp, probabilities 2,724 1m 56s ✓ C Jeff and Brackets 2500 dp, matrices 630 1m 29s ✓ D Jeff and Removing Periods 2700 data-structures 1,345 2m...

Codeforces Round 253 (Div. 1)

Codeforces Round 253 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-3100 | 9m 36s # Problem Rating Tags Accepted Time ✓ A Borya and Hanabi 1700 bitmasks, brute-force, implementation 2,352 1m 6s ✓ B Andrey and Problem 1800 greedy, math, probabilities 6,109 1m 14s ✓ C Artem and Array 2500 data-structures, greedy 1,950 1m 43s ✓ D Adam and Tree 2600 data-structures, trees 1,131 3m...

CF 2219C - Coloring a Red Black Tree

CF 2219C - Coloring a Red Black Tree Rating: - Tags: dfs and similar, dp, greedy, math, probabilities, trees Solve time: 3m 53s Verified: no Solution Problem Understanding We are given a tree with n nodes, where each node is initially colored either red or black according to a binary string. Red nodes are marked 1 and black nodes 0 . The task is to turn all nodes red by...

CF 2217F - Interval Game

CF 2217F - Interval Game Rating: 2300 Tags: bitmasks, combinatorics, constructive algorithms, dp, games, greedy, math, probabilities Solve time: 1m 56s Verified: no Solution Problem Understanding The problem describes a two-player turn-based game involving two intervals. Alice chooses the first interval within a fixed bound [1, x1] , and the second interval is picked uniformly at random from all valid intervals in [1, x2] . On a player’s turn, they...

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

CF 1957F2 - Frequency Mismatch (Hard Version)

CF 1957F2 - Frequency Mismatch (Hard Version) Rating: 2700 Tags: binary search, data structures, dfs and similar, hashing, probabilities, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a tree with $n$ nodes, each node labeled with an integer value. The tree is unrooted, but conceptually we can root it anywhere for processing. For each query, we are asked to compare the multiset of values along...

CF 1948F - Rare Coins

CF 1948F - Rare Coins Rating: 2500 Tags: combinatorics, math, probabilities Solve time: 2m 47s Verified: no Solution Problem Understanding Each bag contains two types of coins. Gold coins are simple: every gold coin always contributes exactly one unit of value. Silver coins are uncertain, each silver coin independently behaves like a fair coin flip and contributes either 0 or 1 with equal probability. The total value of a bag...

CF 482C - Game with Strings

CF 482C - Game with Strings Rating: 2600 Tags: bitmasks, dp, probabilities Solve time: 3m 42s Verified: yes Solution Problem Understanding We know all candidate strings in advance. One of them is chosen uniformly at random. We reveal information by asking about character positions. The order of questions is not chosen strategically. At every step we pick uniformly among positions that have not been asked yet. After some positions have...

CF 464D - World of Darkraft - 2

CF 464D - World of Darkraft - 2 Rating: 2700 Tags: dp, probabilities Solve time: 1m 5s Verified: no Solution Working

CF 444B - DZY Loves FFT

CF 444B - DZY Loves FFT Rating: 2300 Tags: probabilities Solve time: 1m 51s Verified: yes Solution Problem Understanding The task asks us to compute a sequence c based on two sequences a and b of length n . Sequence a is a permutation of the integers from 1 to n , and b is a binary sequence with exactly d ones, both shuffled in a pseudo-random but reproducible way....

CF 441E - Valera and Number

CF 441E - Valera and Number Rating: 2400 Tags: bitmasks, dp, math, probabilities Solve time: 1m 26s Verified: no Solution Problem Understanding Valera starts with a number $x$ and performs $k$ random operations on it. On each step, he flips a biased coin: with probability $p/100$, he doubles the current number, otherwise he increments it by one. After all $k$ steps, he counts how many times the final number can...

CF 351B - Jeff and Furik

CF 351B - Jeff and Furik Rating: 1900 Tags: combinatorics, dp, probabilities Solve time: 1m 56s Verified: yes Solution Problem Understanding We are asked to model a two-player game played on a permutation of integers from 1 to n . Jeff moves first and can swap any adjacent elements. Furik moves probabilistically: he flips a fair coin, and if heads, he chooses an adjacent inversion to swap; if tails, he...

Friday the 13th, Programmers Day

Friday the 13th, Programmers Day Special | 7 problems | 6/7 verified | Difficulty 1500-2700 | 13m 16s # Problem Rating Tags Accepted Time ✓ A Expecting Trouble 1500 *special, probabilities 532 1m 36s ✓ B Triskaidekaphobia 2100 *special 129 1m 47s ✓ C Counting Fridays 2000 *special 130 1m 43s ✓ D Chain Letter 2200 *special, dfs-and-similar, graphs 83 1m 27s ✓ E Black Cat Rush 2700 *special 55...

Codeforces Round 185 (Div. 2)

Codeforces Round 185 (Div. 2) Div. 2 | 2 problems | 1/2 verified | Difficulty 1100-1300 | 3m 14s # Problem Rating Tags Accepted Time ✓ A Whose sentence is it? 1100 implementation, strings 5,357 1m 30s B Archer 1300 math, probabilities 13,373 1m 44s ✓

CF 345A - Expecting Trouble

CF 345A - Expecting Trouble Rating: 1500 Tags: *special, probabilities Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a string representing Fridays the 13th across some period of time. Each character in the string can be "0" for a normal day, "1" for a particularly bad day, or "?" for a day the user cannot recall. Alongside this, we are given a probability p which represents...

CF 335E - Counting Skyscrapers

CF 335E - Counting Skyscrapers Rating: 2800 Tags: dp, math, probabilities Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to relate two counting schemes over a sequence of randomly sized skyscrapers. Imagine a row of skyscrapers with random heights, where the height of each building follows a geometric distribution with probability $2^{-i}$ for height $i$. Alice and Bob traverse these buildings differently. Alice moves sequentially from...

CF 312B - Archer

CF 312B - Archer Rating: 1300 Tags: math, probabilities Solve time: 1m 44s Verified: yes Solution Problem Understanding Two archers shoot at a target alternately. SmallR shoots first and hits with probability $a/b$ on each shot. Zanoes hits with probability $c/d$ on each shot. As soon as someone lands the first hit of the match, the game ends and that player wins. The input consists of four integers $a, b,...

CF 277D - Google Code Jam

CF 277D - Google Code Jam Rating: 2800 Tags: dp, probabilities Solve time: 1m 33s Verified: no Solution Problem Understanding Vasya is participating in a programming round with several problems, each split into a Small and a Large input. Completing the Small input of a problem gives him a guaranteed number of points in a certain amount of time. Completing the Large input takes additional time but is probabilistic: it...

Codeforces Round 172 (Div. 1)

Codeforces Round 172 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1800-3000 | 10m 1s # Problem Rating Tags Accepted Time ✓ A Rectangle Puzzle 2000 geometry 1,586 1m 57s ✓ B Maximum Xor Secondary 1800 data-structures, implementation, two-pointers 5,251 1m 39s ✓ C Game on Tree 2200 implementation, math, probabilities 5,126 2m 1s ✓ D k-Maximum Subsequence Sum 2800 data-structures, flows, graphs 1,653 2m 27s...

Codeforces Round 164 (Div. 2)

Codeforces Round 164 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2300 | 9m 9s # Problem Rating Tags Accepted Time ✓ A Games 800 brute-force 104,168 1m 34s ✓ B Buttons 1000 implementation, math 35,776 1m 34s ✓ C Beautiful Sets of Points 1500 constructive-algorithms, implementation 14,637 1m 58s D Wall Bars 2300 dp 576 1m 23s E Playlist 2100 math, probabilities, sortings 1,137 2m...

CF 293D - Ksusha and Square

CF 293D - Ksusha and Square Rating: 2700 Tags: geometry, math, probabilities, two pointers Solve time: 43s Verified: no Solution Problem Understanding We are given a convex polygon whose vertices have integer coordinates. Consider every lattice point, meaning every point with integer coordinates, that lies inside the polygon or on its boundary. Among all unordered pairs of distinct lattice points, we choose one pair uniformly at random. Those two points...

CF 280C - Game on Tree

CF 280C - Game on Tree Rating: 2200 Tags: implementation, math, probabilities, trees Solve time: 2m 1s Verified: yes Solution Problem Understanding We are given a tree with root at vertex 1 . A game is played on this rooted tree until every node disappears. At each move, one of the currently remaining vertices is chosen uniformly at random. When a vertex v is chosen, the entire subtree rooted at...

CF 268E - Playlist

CF 268E - Playlist Rating: 2100 Tags: math, probabilities, sortings Solve time: 2m 40s Verified: yes Solution Problem Understanding Each song has two attributes. Its length is l , and independently Manao likes it with probability p . When a song is played for the first time, one of two things happens. If he likes it, the song is added to a collection of remembered songs. If he dislikes it,...

Codeforces Round 146 (Div. 1)

Codeforces Round 146 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1600-3000 | 11m 29s # Problem Rating Tags Accepted Time ✓ A LCM Challenge 1600 number-theory 20,976 2m 32s ✓ B Let's Play Osu! 2000 dp, math, probabilities 4,306 1m 33s ✓ C Cyclical Quest 2700 data-structures, string-suffix-structures, strings 2,466 2m 36s ✓ D Graph Game 3000 graphs 573 2m 41s ✓ E Number Challenge...

CF 258D - Little Elephant and Broken Sorting

CF 258D - Little Elephant and Broken Sorting Rating: 2600 Tags: dp, math, probabilities Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given a permutation of integers from 1 to n and a sequence of m swap operations. Normally, these operations would sort the array into ascending order, but the swap program is broken: each move either swaps the indicated positions or does nothing, each with probability...

CF 235B - Let's Play Osu!

CF 235B - Let's Play Osu! Rating: 2000 Tags: dp, math, probabilities Solve time: 1m 33s Verified: yes Solution Problem Understanding Each click in the game independently becomes either a successful hit ( O ) or a miss ( X ). For a completed sequence, we split it into maximal consecutive blocks of O . If a block has length L , it contributes L² to the score. The total...

CF 175D - Plane of Tanks: Duel

CF 175D - Plane of Tanks: Duel Rating: 2400 Tags: brute force, dp, math, probabilities Solve time: 40s Verified: no Solution Problem Understanding Two tanks start fighting at time 0. Both fire immediately, then continue firing every dt seconds. Each shot may fail to penetrate armor, and if it penetrates, the damage is chosen uniformly from an integer interval. A tank is destroyed as soon as its hit points become...

Codeforces Beta Round 81

Codeforces Beta Round 81 Beta | 5 problems | 4/5 verified | Difficulty 1700-2700 | 13m 32s # Problem Rating Tags Accepted Time ✓ A Transmigration 1700 implementation 2,022 3m 6s ✓ B Dark Assembly 1800 brute-force, probabilities 906 2m 19s ✓ C Item World 2200 brute-force, implementation, sortings 390 3m 26s D Entertaining Geodetics 2700 brute-force, dsu, implementation 145 2m 8s ✓ E Lift and Throw 2500 brute-force 211...

CF 105B - Dark Assembly

CF 105B - Dark Assembly Rating: 1800 Tags: brute force, probabilities Solve time: 2m 19s Verified: yes Solution Problem Understanding We have a small assembly of n senators, each defined by a level and a loyalty score. Loyalty is a probability that a senator votes in favor of a proposal, given in 10% increments. If more than half of senators vote yes, the proposal passes. If the vote fails, the...

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) ICPC/IOI | 11 problems | 4/11 verified | Difficulty 1500-3300 | 26m 7s # Problem Rating Tags Accepted Time ✓ A Grove 3300 brute-force, dfs-and-similar, dp 203 2m 41s ✓ B Charming Meals 1500 binary-search, brute-force, greedy 4,896 1m 44s ✓ C Annual Ants' Gathering 1900 dfs-and-similar, dp, greedy 2,526 4m 48s ✓ D Funny or Scary? 2600 constructive-algorithms...

CF 1951G - Clacking Balls

CF 1951G - Clacking Balls Rating: 3100 Tags: combinatorics, math, probabilities Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a circle of baskets numbered from 1 to $m$, and $n$ balls initially placed in distinct baskets. Alice repeatedly chooses one of the balls uniformly at random and moves it clockwise to the next basket. If that basket already contains a ball, the existing ball is thrown...

CF 1949A - Grove

CF 1949A - Grove Rating: 3300 Tags: brute force, dfs and similar, dp, geometry, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding Every tree is planted at an integer lattice point. Around that point we place a disk of radius r , representing the root system. Two conditions must hold. The entire disk must stay inside the square lawn. Since the lawn is the square [0,n] × [0,n]...

CF 494C - Helping People

CF 494C - Helping People Rating: 2600 Tags: dp, probabilities Solve time: 42s Verified: yes Solution Problem Understanding We are tasked with calculating the expected maximum wealth of a group of people after a series of charitable recommendations. Each person starts with a known amount of money. There are several recommendations, each specifying a segment of people to receive one dollar, and each recommendation has a probability that it will...

MemSQL Start[c]UP 2.0 - Round 2

MemSQL Start[c]UP 2.0 - Round 2 Special | 6 problems | 4/6 verified | Difficulty 1700-3200 | 11m 5s # Problem Rating Tags Accepted Time ✓ A Golden System 1700 math, meet-in-the-middle 1,402 1m 15s ✓ B Distributed Join 1900 greedy 1,210 1m 7s ✓ C Elections 2100 brute-force 945 1m 25s ✓ D Bingo! 2700 combinatorics, math, probabilities 390 1m 42s ✓ E Flow Optimality 3000 constructive-algorithms, flows, math...

Codeforces Round 259 (Div. 1)

Codeforces Round 259 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1600-3100 | 8m 34s # Problem Rating Tags Accepted Time ✓ A Little Pony and Expected Maximum 1600 probabilities 12,433 1m 46s ✓ B Little Pony and Harmony Chest 2000 bitmasks, brute-force, dp 5,399 1m 19s ✓ C Little Pony and Summer Sun Celebration 2200 constructive-algorithms, dfs-and-similar, graphs 1,742 2m 13s D Little Pony and...

CF 476B - Dreamoon and WiFi

CF 476B - Dreamoon and WiFi Rating: 1300 Tags: bitmasks, brute force, combinatorics, dp, math, probabilities Solve time: 1m 35s Verified: yes Solution Problem Understanding Drazil sends a sequence of movement commands. Each '+' moves Dreamoon one step to the right and each '-' moves one step to the left. We know the original command string and also the string that Dreamoon receives. The received string may contain '?' characters,...

CF 453A - Little Pony and Expected Maximum

CF 453A - Little Pony and Expected Maximum Rating: 1600 Tags: probabilities Solve time: 1m 46s Verified: yes Solution Problem Understanding We roll a fair die with faces numbered from 1 to m , exactly n times. Every roll is independent, and each face appears with probability 1 / m . Among those n rolls, we look only at the largest value that appeared. The task is to compute the...

CF 457D - Bingo!

CF 457D - Bingo! Rating: 2700 Tags: combinatorics, math, probabilities Solve time: 1m 42s Verified: yes Solution Problem Understanding We have an $n \times n$ bingo board. Every cell contains a distinct number chosen from $1$ to $m$, and every valid board is equally likely. After the board is generated, exactly $k$ distinct numbers are called. Every set of $k$ numbers is equally likely. A cell becomes marked if its...

CF 452C - Magic Trick

CF 452C - Magic Trick Rating: 2100 Tags: combinatorics, math, probabilities Solve time: 1m 44s Verified: yes Solution Problem Understanding There are $m$ complete decks, each containing the same $n$ card values. After mixing all decks together, there are $mn$ physical cards in total, and every value appears exactly $m$ times. Alex randomly takes $n$ cards from this large pile and uses them as the working deck for the trick....

Codeforces Round 254 (Div. 1)

Codeforces Round 254 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1600-2700 | 15m 35s # Problem Rating Tags Accepted Time ✓ A DZY Loves Physics 1600 greedy, math 3,578 1m 32s ✓ B DZY Loves FFT 2300 probabilities 1,175 1m 51s ✓ C DZY Loves Colors 2400 data-structures 3,359 5m 19s D DZY Loves Strings 2500 binary-search, hashing, strings 862 1m 6s ✓ E DZY...

Codeforces Round 160 (Div. 1)

Codeforces Round 160 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1400-2800 | 10m 32s # Problem Rating Tags Accepted Time ✓ A Maxim and Discounts 1400 greedy, sortings 5,608 3m 10s ✓ B Maxim and Restaurant 1900 dp, math, probabilities 1,612 2m 19s C Maxim and Matrix 2000 constructive-algorithms, dp, math 836 1m 11s ✓ D Maxim and Increasing Subsequence 2600 dp 714 2m 12s...

Codeforces Round 129 (Div. 1)

Codeforces Round 129 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1500-2800 | 5m 54s # Problem Rating Tags Accepted Time ✓ A Little Elephant and Interval 1500 binary-search, combinatorics, dp 6,589 1m 39s ✓ B Little Elephant and Cards 1500 binary-search, data-structures 5,904 1m 8s ✓ C Little Elephant and Furik and Rubik 2000 math, probabilities 1,234 1m 23s D Little Elephant and Retro Strings...

Codeforces Round 114 (Div. 1)

Codeforces Round 114 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1600-3000 | 10m 57s # Problem Rating Tags Accepted Time ✓ A Wizards and Trolleybuses 1600 implementation, math 2,184 1m 40s ✓ B Wizards and Huge Prize 1800 dp, math, probabilities 2,450 1m 38s C Wizards and Numbers 2300 games, math 740 1m 39s D Wizards and Roads 3000 data-structures, divide-and-conquer, graph-matchings 217 2m 8s...

Codeforces Beta Round 99 (Div. 1)

Codeforces Beta Round 99 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1600-2900 | 9m 53s # Problem Rating Tags Accepted Time ✓ A Literature Lesson 1600 implementation 2,589 2m ✓ B Digits Permutations 1900 greedy 1,110 2m 29s C Mushroom Gnomes - 2 2200 binary-search, data-structures, probabilities 962 2m ✓ D World of Darkraft 2500 dp, games 592 2m 6s ✓ E Hellish Constraints 2900...

CF 229E - Gifts

CF 229E - Gifts Rating: 2600 Tags: combinatorics, dp, math, probabilities Solve time: 2m 48s Verified: yes Solution Problem Understanding We are given a collection of gifts, each with a name and a set of distinct prices. Some names may appear multiple times, each with different prices. The old man can request exactly n gifts, specifying only names. If he requests multiple gifts with the same name, the fish selects...

CF 261B - Maxim and Restaurant

CF 261B - Maxim and Restaurant Rating: 1900 Tags: dp, math, probabilities Solve time: 2m 19s Verified: no Solution

CF 138C - Mushroom Gnomes - 2

CF 138C - Mushroom Gnomes - 2 Rating: 2200 Tags: binary search, data structures, probabilities, sortings Solve time: 2m Verified: yes Solution Problem Understanding We have trees placed on a number line. Each tree may fall left, fall right, or remain standing. The probabilities for these three outcomes are given independently for every tree. A falling tree destroys mushrooms in a half-open interval determined by the tree position and height....

CF 442B - Andrey and Problem

CF 442B - Andrey and Problem Rating: 1800 Tags: greedy, math, probabilities Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a set of friends, where each friend independently succeeds in producing a contest problem with a known probability. Andrey will invite some subset of these friends. Once invited, each friend either contributes a problem or does not, independently of the others. The outcome we care about...

CF 303E - Random Ranking

CF 303E - Random Ranking Rating: 3000 Tags: dp, math, probabilities Solve time: 3m 7s Verified: no Solution Problem Understanding Each participant receives a real-valued score chosen uniformly from an interval $[l_i, r_i]$. Scores are independent. After all scores are generated, participants are sorted by score. Smaller score means better rank, so the participant with the largest score finishes last. For every participant $i$ and every rank $j$, we must...

CF 183D - T-shirt

CF 183D - T-shirt Rating: 2700 Tags: dp, greedy, probabilities Solve time: 1m 15s Verified: yes Solution Problem Understanding We are tasked with distributing T-shirts to a line of engineers where each engineer has a probability distribution over which T-shirt size fits them. We know how many engineers, n , there are, and the total number of T-shirt sizes, m . Each engineer has exactly one size that fits them,...

CF 167B - Wizards and Huge Prize

CF 167B - Wizards and Huge Prize Rating: 1800 Tags: dp, math, probabilities Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to calculate the probability of performing well in a sequence of wizard contests, given both your chances of winning each contest and the types of prizes you may receive. There are n contests, and for each contest, you know your probability of winning and whether...

CF 204C - Little Elephant and Furik and Rubik

CF 204C - Little Elephant and Furik and Rubik Rating: 2000 Tags: math, probabilities Solve time: 1m 23s Verified: no Solution Problem Understanding We are given two strings of equal length. From each string we independently pick a substring, and both substrings must have the same length. After choosing them, we compare them character by character and count how many positions match. The selection is uniform over all possible choices...

CF 446D - DZY Loves Games

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

CF 150C - Smart Cheater

CF 150C - Smart Cheater Rating: 2200 Tags: data structures, math, probabilities Solve time: 2m 11s Verified: yes Solution Problem Understanding We have a straight bus route with fixed stop coordinates. A passenger normally pays the full distance between their boarding and exit stops. The conductor is allowed to "hide" at most one continuous segment of that trip from the ticket. If a passenger travels from stop a to stop...

CF 424E - Colored Jenga

CF 424E - Colored Jenga Rating: 2500 Tags: dfs and similar, dp, probabilities Solve time: 6m 29s Verified: no Solution Problem Understanding We are given a vertical stack of levels, each level containing three colored blocks arranged left, middle, right. The tower has a physical constraint: it is only stable if every non-top level has at least one remaining block, and additionally a level is unstable if it is reduced...

CF 417E - Square Table

CF 417E - Square Table Rating: 2400 Tags: constructive algorithms, math, probabilities Solve time: 1m 48s Verified: yes Solution Problem Understanding We are asked to fill an $n \times m$ grid with positive integers not exceeding $10^8$. The constraint is not about individual cells but about structure: for every row and every column, if we square all numbers in that line and sum them, the result must itself be a...

CF 148D - Bag of mice

CF 148D - Bag of mice Rating: 1800 Tags: dp, games, math, probabilities Solve time: 1m 55s Verified: yes Solution Problem Understanding We have a bag containing white and black mice. The princess moves first, then the dragon, then the princess again, and so on. Whoever draws a white mouse immediately wins. If someone draws a black mouse, the game continues. There is one extra rule during the dragon’s turn....

CF 248E - Piglet's Birthday

CF 248E - Piglet's Birthday Rating: 2600 Tags: dp, math, probabilities Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to compute the expected number of shelves that have no untasted honey pots after a series of actions. Each shelf starts with some number of honey pots. Winnie moves a small number of pots from one shelf to another, tasting them in the process. Every pot on...

Codeforces Beta Round 83 (Div. 1 Only)

Codeforces Beta Round 83 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1400-2700 | 11m 41s # Problem Rating Tags Accepted Time ✓ A Dorm Water Supply 1400 dfs-and-similar, graphs 5,905 2m 19s ✓ B Basketball Team 1600 combinatorics, dp, math 4,272 2m 22s ✓ C Arrangement 2400 bitmasks, dp 460 2m 35s ✓ D Crime Management 2400 dp, graphs, matrices 487 2m 6s ✓...

Codeforces Beta Round 84 (Div. 1 Only)

Codeforces Beta Round 84 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1000-2700 | 11m 6s # Problem Rating Tags Accepted Time ✓ A Lucky Sum of Digits 1000 brute-force, implementation 19,819 2m 22s ✓ B Lucky Probability 1900 brute-force, probabilities 1,780 2m 23s ✓ C Lucky Tree 1900 dp, dsu, trees 4,117 2m 23s ✓ D Lucky Sorting 2000 constructive-algorithms, sortings 894 1m 47s...

Codeforces Beta Round 78 (Div. 1 Only)

Codeforces Beta Round 78 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1700-2700 | 10m 13s # Problem Rating Tags Accepted Time ✓ A Help Victoria the Wise 1700 brute-force, implementation 1,348 2m 12s ✓ B Help King 2200 implementation, probabilities, trees 152 1m 17s ✓ C Help Greg the Dwarf 2500 geometry, ternary-search 347 2m 29s ✓ D Help Monks 2500 constructive-algorithms 200 1m...

Codeforces Beta Round 69 (Div. 1 Only)

Codeforces Beta Round 69 (Div. 1 Only) Div. 1 | 5 problems | 2/5 verified | Difficulty 1400-2800 | 11m 16s # Problem Rating Tags Accepted Time ✓ A Heroes 1400 brute-force, implementation 1,953 1m 49s ✓ B Falling Anvils 1800 math, probabilities 2,866 2m 36s ✓ C Beavermuncher-0xFF 2100 dfs-and-similar, dp, dsu 1,172 2m 30s D Domino Carpet 2300 dp, implementation 363 1m 59s E Martian Food 2800 geometry...

Codeforces Beta Round 50

Codeforces Beta Round 50 Beta | 5 problems | 5/5 verified | Difficulty 1300-2700 | 8m 47s # Problem Rating Tags Accepted Time ✓ A Presents 1300 implementation 2,545 1m 19s ✓ B Cutting Jigsaw Puzzle 1800 hashing, implementation 909 1m 29s ✓ C First Digit Law 2000 dp, math, probabilities 1,639 1m 10s ✓ D Writing a Song 2100 brute-force, dp, strings 709 1m 3s ✓ E Vacuum \u0421leaner...

Codeforces Beta Round 30 (Codeforces format)

Codeforces Beta Round 30 (Codeforces format) Beta | 5 problems | 4/5 verified | Difficulty 1400-2800 | 7m 26s # Problem Rating Tags Accepted Time ✓ A Accounting 1400 brute-force, math 3,985 1m 23s ✓ B Codeforces World Finals 1700 implementation 1,387 1m 1s ✓ C Shooting Gallery 1800 dp, probabilities 2,392 1m ✓ D King's Problem? 2600 geometry, greedy 498 2m 12s E Tricky and Clever Password 2800 binary-search,...

Codeforces Beta Round 24

Codeforces Beta Round 24 Beta | 5 problems | 5/5 verified | Difficulty 1400-2400 | 11m 12s # Problem Rating Tags Accepted Time ✓ A Ring road 1400 graphs 6,848 3m 36s ✓ B F1 Champions 1500 implementation 2,033 2m 19s ✓ C Sequence of points 1800 geometry, implementation, math 1,444 2m 35s ✓ D Broken robot 2400 dp, math, probabilities 2,650 1m 34s ✓ E Berland collider 2300 binary-search...

Codeforces Beta Round 9 (Div. 2 Only)

Codeforces Beta Round 9 (Div. 2 Only) Div. 2 | 5 problems | 5/5 verified | Difficulty 800-2300 | 8m 20s # Problem Rating Tags Accepted Time ✓ A Die Roll 800 math, probabilities 69,646 2m 43s ✓ B Running Student 1200 brute-force, geometry, implementation 6,187 1m 26s ✓ C Hexadecimal's Numbers 1200 brute-force, implementation, math 14,345 1m 10s ✓ D How many trees? 1900 combinatorics, divide-and-conquer, dp 4,503 1m...

CF 50D - Bombing

CF 50D - Bombing Rating: 2100 Tags: binary search, dp, probabilities Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a set of enemy objects, each at a fixed 2D coordinate, and a fixed strike point. The objective is to determine the minimum impact radius of a nuclear warhead such that the probability of failing to deactivate at least K of these objects is at most ε...

CF 54C - First Digit Law

CF 54C - First Digit Law Rating: 2000 Tags: dp, math, probabilities Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a set of N random integers, where each integer i can take any value in a given inclusive range [L_i, R_i] , all values equally likely. The task is to compute the probability that at least K% of these N integers start with the digit 1...

CF 16E - Fish

CF 16E - Fish Rating: 1900 Tags: bitmasks, dp, probabilities Solve time: 1m 34s Verified: yes Solution Problem Understanding We have n fish in a lake. Every day, exactly one unordered pair of currently alive fish is chosen uniformly at random. When fish i meets fish j , fish i eats fish j with probability a[i][j] , and fish j eats fish i with probability a[j][i] = 1 - a[i][j]...

CF 85C - Petya and Tree

CF 85C - Petya and Tree Rating: 2200 Tags: binary search, dfs and similar, probabilities, sortings, trees Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a valid binary search tree where every internal node has exactly two children. Each node stores a unique key. We are also given several query keys that are guaranteed not to appear in the tree. A normal BST search starts at...

CF 26D - Tickets

CF 26D - Tickets Rating: 2400 Tags: combinatorics, math, probabilities Solve time: 1m 14s Verified: yes Solution Problem Understanding We have a ticket seller, Charlie, who sells race tickets costing 10 euros each. Customers arrive in some random order: some have only 10 euro banknotes, some have only 20 euro banknotes. Charlie initially has k 10 euro banknotes. Every customer with a 20 euro note requires Charlie to give one...

CF 123E - Maze

CF 123E - Maze Rating: 2500 Tags: dfs and similar, dp, probabilities, trees Solve time: 2m 39s Verified: no Solution Problem Understanding We are given a tree, and two independent probability distributions over its vertices. One distribution chooses the starting vertex of a DFS, the other chooses the target vertex where the search stops. The DFS behaves randomly: before exploring a node, it shuffles the adjacency list uniformly at random,...

CF 109B - Lucky Probability

CF 109B - Lucky Probability Rating: 1900 Tags: brute force, probabilities Solve time: 2m 23s Verified: yes Solution Problem Understanding We are asked to calculate the probability that if Petya and Vasya each pick an integer randomly from their respective intervals, the interval between the two chosen numbers contains exactly k lucky numbers. Lucky numbers are those containing only the digits 4 and 7. The input provides the bounds of...

CF 113D - Museum

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

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

CF 77B - Falling Anvils

CF 77B - Falling Anvils Rating: 1800 Tags: math, probabilities Solve time: 2m 36s Verified: yes Solution Problem Understanding We are given two real parameters chosen uniformly at random. The victim height p lies in the interval [0, a] , and the wind parameter q lies in [-b, b] . For every pair (p, q) , the anvil hits successfully if a certain quadratic equation has at least one real...

CF 9A - Die Roll

CF 9A - Die Roll Rating: 800 Tags: math, probabilities Solve time: 2m 43s Verified: yes Solution Problem Understanding We are asked to calculate the probability that Dot wins a simple dice game against Yakko and Wakko. Each character rolls a standard six-sided die. Dot wins if her roll is at least as large as the maximum of Yakko’s and Wakko’s rolls. Yakko and Wakko’s rolls are given as input,...

CF 30C - Shooting Gallery

CF 30C - Shooting Gallery Rating: 1800 Tags: dp, probabilities Solve time: 1m Verified: yes Solution Problem Understanding We are asked to help King Copa maximize his expected number of hits in a shooting gallery. The gallery is represented as a 2D plane, and each target appears at a specific point $(x_i, y_i)$ exactly at a specific time $t_i$ and disappears immediately afterward. If the king’s gun sight is aimed...

CF 101D - Castle

CF 101D - Castle Rating: 2300 Tags: dp, greedy, probabilities, sortings, trees Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a weighted tree rooted at hall 1, where Gerald starts. The treasure is hidden uniformly at random in one of the other halls. Gerald only discovers the treasure when he first enters the correct hall. The restriction that changes the problem completely is that every corridor...

CF 107B - Basketball Team

CF 107B - Basketball Team Rating: 1600 Tags: combinatorics, dp, math, probabilities Solve time: 2m 22s Verified: yes Solution Problem Understanding We have a university with several departments. Each department contributes some number of basketball players. Herr Wafa belongs to department h , and he is already guaranteed a place on the final team. The team must contain exactly n players including Wafa himself. Every valid team containing Wafa is...

CF 28C - Bath Queue

CF 28C - Bath Queue Rating: 2200 Tags: combinatorics, dp, probabilities Solve time: 1m 44s Verified: yes Solution Problem Understanding Every student independently chooses one of the bathroom rooms uniformly at random. A room may contain several wash basins, so students entering that room are split into several queues. The queues are balanced as evenly as possible, because the students arrange themselves to minimize the largest queue length in that...

CF 24D - Broken robot

CF 24D - Broken robot Rating: 2400 Tags: dp, math, probabilities Solve time: 1m 34s Verified: yes Solution Problem Understanding The board has N rows and M columns. A robot starts at cell (i, j) and repeatedly performs one random move. From an interior cell it has four equally likely choices: stay in place, move left, move right, or move down. On the left border, moving left is impossible, so...

CF 98B - Help King

CF 98B - Help King Rating: 2200 Tags: implementation, probabilities, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are asked to simulate a fair random selection of one knight out of n using a coin that can only produce two outcomes. Each coin flip has an equal probability of landing heads or tails. The goal is to find the expected number of flips required to select a...

CF 107E - Darts

CF 107E - Darts Rating: 2700 Tags: geometry, probabilities Solve time: 2m 19s Verified: yes Solution Problem Understanding We have several rectangles on the plane. Each rectangle represents a photo hanging on a wall. The rectangles may overlap, may share edges, may coincide completely, and may also be rotated arbitrarily. A dart is thrown uniformly at random over the entire wall, but we only care about throws that hit at...

CF 98E - Help Shrek and Donkey

CF 98E - Help Shrek and Donkey Rating: 2700 Tags: dp, games, math, probabilities Solve time: 2m 25s Verified: yes Solution Problem Understanding There are m + n + 1 distinct cards in total. Shrek initially knows his own m cards, Donkey knows his own n cards, and one card is hidden on the table. Nobody knows the hidden card directly. Players alternate turns, with Shrek moving first. On each...