#flows

CF 1252L - Road Construction

CF 1252L - Road Construction Rating: 2300 Tags: flows, graphs Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a set of cities where each city proposes exactly one possible road. City $i$ wants to connect to a specific other city $A_i$, so each proposal is an undirected edge $(i, A_i)$. If we ignored all constraints about workers, these proposed edges already form a connected graph, so...

CF 1250K - Projectors

CF 1250K - Projectors Rating: 3100 Tags: flows, graphs Solve time: 1m 52s Verified: no Solution Problem Understanding We are given two sets of time intervals: one set represents lectures, the other represents seminars. Each lecture must be assigned a high-definition projector, while each seminar can use any projector, either HD or ordinary. Every projector can handle at most one event at a time, but can be reused later once...

CF 925F - Parametric Circulation Rating: 3100 Tags: binary search, flows Model: gpt-5-3-mini Solve time: 37s Verified: no (0/0 samples) Solution Problem Understanding We are given a directed graph where every edge can carry a non-negative flow, and flows must satisfy standard conservation: at every vertex, total incoming flow equals total outgoing flow. This is a circulation problem with no external source or sink. The twist is that each edge...

CF 1070I - Privatization of Roads in Berland Rating: 2400 Tags: flows, graph matchings, graphs Model: gpt-5-3-mini Solve time: 1m 21s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bf33-5374-83ec-9b48-0bc381466acc Solution Problem Understanding We are given a simple undirected graph with up to 600 vertices and 600 edges per test case. Each edge must be assigned a label, called a company index. The assignment has two constraints. First, every company is allowed to...

CF 965D - Single-use Stones Rating: 1900 Tags: binary search, flows, greedy, two pointers Model: gpt-5-3-mini Solve time: 1m 25s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a3ef-c198-83ec-ab18-235bfb734e32 Solution Problem Understanding We are given a river of width $w$. Along the river, at each integer position $i$ from $1$ to $w-1$, there are $a_i$ stones initially placed at that distance from the starting bank. A frog starts at the left bank (position...

CF 976F - Minimal k-covering Rating: 2500 Tags: flows, graphs Model: gpt-5-3-mini Solve time: 2m 5s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a4b9-3dac-83ec-87ac-1cbf084ec568 Solution Problem Understanding We are working with a bipartite graph where edges connect vertices on the left side to vertices on the right side, and multiple edges between the same pair are allowed. From this graph we are allowed to select some subset of edges. For a fixed...

CF 899E - Segments Removal Rating: 2000 Tags: data structures, dsu, flows, implementation, two pointers Model: gpt-5-5 Solve time: 1m 28s Verified: yes (1/1 samples) Solution Problem Understanding The array starts as a sequence of integers, and it evolves through a very specific greedy deletion rule. At any moment you look at all maximal blocks of consecutive equal values, pick the block with the largest length, and if several blocks...

CF 1009G - Allowed Letters

CF 1009G - Allowed Letters Rating: 2400 Tags: bitmasks, flows, graph matchings, graphs, greedy Solve time: 3m 35s Verified: yes Solution Problem Understanding We are given a string made only from the first six lowercase letters. We are allowed to rearrange its characters arbitrarily by swapping any positions any number of times, so effectively we can treat it as a multiset of letters with full permutation freedom. On top of...

CF 1016D - Vasya And The Matrix

CF 1016D - Vasya And The Matrix Rating: 1800 Tags: constructive algorithms, flows, math Solve time: 4m 3s Verified: no Solution Problem Understanding We are asked to construct a grid of size n by m where each cell contains a non-negative integer. What we know in advance is not the grid itself, but two sets of constraints derived from it: the XOR of every row is fixed, and the XOR...

CF 1023G - Pisces

CF 1023G - Pisces Rating: 3400 Tags: data structures, flows, trees Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a weighted tree where each edge represents a river with a travel time. Fish can move continuously along these edges: traversing an edge of length $l$ takes exactly $l$ days, and fish may also wait arbitrarily at vertices. Fish never split or merge; each fish is an...

Codeforces Round 511 (Div. 1)

Codeforces Round 511 (Div. 1) Div. 1 | 5 problems | 2/5 verified | Difficulty 1800-3500 | 33m 51s # Problem Rating Tags Accepted Time ✓ A Enlarge GCD 1800 number-theory 9,919 4m 46s ✓ B Little C Loves 3 II 2200 brute-force, constructive-algorithms, flows 2,290 3m 31s C Region Separation 2700 combinatorics, dp, number-theory 993 10m 26s D Intervals of Intervals 3500 binary-search, data-structures, two-pointers 587 8m 30s E...

CF 1034B - Little C Loves 3 II

CF 1034B - Little C Loves 3 II Rating: 2200 Tags: brute force, constructive algorithms, flows, graph matchings Solve time: 3m 31s Verified: no Solution Problem Understanding We are given a very large rectangular grid where each cell can be identified by coordinates $(x, y)$. We repeatedly place two chess pieces at a time, but only if the Manhattan distance between the two chosen empty cells is exactly 3. Each...

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

Bubble Cup 11 - Finals [Online Mirror, Div. 1] Div. 1 | 5 problems | 4/5 verified | Difficulty 2200-3400 | 21m 12s # Problem Rating Tags Accepted Time ✓ A Last chance 2500 data-structures, flows, graph-matchings 574 4m 32s C Hyperspace Highways 2300 dfs-and-similar, graphs, trees 827 3m 39s ✓ F Shady Lady 3400 geometry, math 114 3m 49s ✓ G AI robots 2200 data-structures 1,984 2m 33s ✓...

CF 1045A - Last chance

CF 1045A - Last chance Rating: 2500 Tags: data structures, flows, graph matchings, graphs, trees Solve time: 4m 32s Verified: no Solution Problem Understanding We are given a collection of weapons and a line of ships, and we want to assign each destroyed ship to exactly one weapon. Each weapon has a limited way of interacting with ships, and the goal is to maximize how many ships get assigned and...

CF 1307G - Cow and Exercise

CF 1307G - Cow and Exercise Rating: 3100 Tags: flows, graphs, shortest paths Solve time: 10m 57s Verified: no Solution Problem Understanding We are given a directed weighted graph with up to 50 vertices, representing fields connected by roads. A cow starts at node 1 and wants to reach node n, and the time it takes is determined by the shortest path in this graph. Now the twist: we are...

CF 1288F - Red-Blue Graph

CF 1288F - Red-Blue Graph Rating: 2900 Tags: constructive algorithms, flows Solve time: 9m 52s Verified: no Solution Problem Understanding We are given a bipartite graph where every edge can optionally be assigned one of two colors, red or blue, or left unused. Coloring an edge is not free: red costs r , blue costs b , and leaving it unused costs nothing. On top of this, some vertices impose...

CF 1214D - Treasure Island

CF 1214D - Treasure Island Rating: 1900 Tags: dfs and similar, dp, flows, hashing Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid that represents a map. Each cell is either blocked or free. We start at the top-left cell $(1,1)$ and want to reach the bottom-right cell $(n,m)$. Movement is highly restricted: from any cell we can only go either one...

Mail.Ru Cup 2018 Round 1

Mail.Ru Cup 2018 Round 1 Special | 8 problems | 3/8 verified | Difficulty 800-3500 | 37m 21s # Problem Rating Tags Accepted Time ✓ A Elevator or Stairs? 800 implementation 9,591 2m 27s ✓ B Appending Mex 1000 implementation 7,068 2m 32s ✓ C Candies Distribution 1500 constructive-algorithms, implementation 4,483 9m 3s D Changing Array 1900 greedy, implementation 2,415 3m 46s ✓ E Chips Puzzle 2400 constructive-algorithms, implementation, math...

CF 1054F - Electric Scheme

CF 1054F - Electric Scheme Rating: 2700 Tags: flows, graph matchings Solve time: 3m 50s Verified: no Solution Problem Understanding We are given a set of points in the plane, each point being an “event location” where a horizontal wire and a vertical wire must cross. Every wire is axis-aligned: horizontal wires lie on a fixed y-coordinate, vertical wires lie on a fixed x-coordinate. A spark appears exactly at a...

CF 1061E - Politics

CF 1061E - Politics Rating: 2600 Tags: flows, graphs Solve time: 6m 52s Verified: yes Solution Problem Understanding We are given two different spanning trees over the same set of cities. Each tree represents how one candidate organizes the country, with a chosen root city acting as their capital. On top of each tree, every city has a requirement: a candidate specifies for certain nodes how many selected cities (ports)...

CF 1082G - Petya and Graph

CF 1082G - Petya and Graph Rating: 2400 Tags: flows, graphs Solve time: 3m 37s Verified: no Solution Problem Understanding We are given a simple undirected graph where each vertex carries a cost and each edge carries a reward. We are allowed to pick any subset of vertices, and then from the edges we may only keep those whose endpoints are both selected. The score of a chosen subgraph is...

CF 1721F - Matching Reduction

CF 1721F - Matching Reduction Rating: 2800 Tags: brute force, constructive algorithms, dfs and similar, flows, graph matchings, graphs, interactive Solve time: 4m 58s Verified: no Solution Problem Understanding We are working with a bipartite graph where the left side has $n_1$ vertices and the right side has $n_2$ vertices. Edges are fixed and each edge connects one left vertex to one right vertex. At any moment, we consider a...

Codeforces Round 736 (Div. 2)

Codeforces Round 736 (Div. 2) Div. 2 | 2 problems | 0/2 verified | Difficulty 800-800 | 11m 31s # Problem Rating Tags Accepted Time ✓ A Gregor and Cryptography 800 math, number-theory 35,559 3m 41s B Gregor and the Pawn Game 800 dfs-and-similar, dp, flows 26,817 7m 50s

CF 1549B - Gregor and the Pawn Game

CF 1549B - Gregor and the Pawn Game Rating: 800 Tags: dfs and similar, dp, flows, graph matchings, graphs, greedy, implementation Solve time: 7m 50s Verified: no Solution Problem Understanding We are given a square board of size $n \times n$, but only the first and last rows matter. The bottom row contains Gregor’s pawns, and the top row contains enemy pawns. Every column is either empty or occupied independently...

CF 1533I - Excursions

CF 1533I - Excursions Rating: - Tags: *special, constructive algorithms, dfs and similar, flows, graph matchings, graphs Solve time: 7m 26s Verified: yes Solution Problem Understanding We can view the situation as a two-layer directed routing process between two bipartite sets of nodes. One set corresponds to sights in Saratov, the other to sights in Engels. Each bus route is bidirectional in the sense that it can be used in...

Educational Codeforces Round 97 (Rated for Div. 2)

Educational Codeforces Round 97 (Rated for Div. 2) Div. 2 | 7 problems | 4/7 verified | Difficulty 800-2600 | 24m 5s # Problem Rating Tags Accepted Time ✓ A Marketing Scheme 800 brute-force, constructive-algorithms, greedy 18,462 4m 2s ✓ B Reverse Binary Strings 1200 constructive-algorithms, greedy 20,848 4m 32s C Chef Monocarp 1800 dp, flows, graph-matchings 12,181 1m 37s ✓ D Minimal Height Tree 1600 graphs, greedy, shortest-paths 14,361...

CF 1354F - Summoning Minions Rating: 2500 Tags: constructive algorithms, dp, flows, graph matchings, greedy, sortings Model: gpt-5-3-mini Solve time: 7m 51s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e3235-4d04-83ec-969f-ae99dbac5d4a Solution Problem Understanding We are given a collection of minions, each with an intrinsic strength and a “buffing power”. When a minion is summoned, it contributes its base strength, but it also permanently increases the power of every minion that has already...

CF 1198E - Rectangle Painting 2

CF 1198E - Rectangle Painting 2 Rating: 2500 Tags: flows, graph matchings, graphs Solve time: 4m 14s Verified: no Solution Problem Understanding We are given an extremely large $n \times n$ grid, but instead of listing individual black cells, the input describes black regions as up to 50 axis-aligned rectangles. Every cell outside these rectangles is white initially, and inside them is black. The task is to repaint the grid...

CF 1187G - Gang Up

CF 1187G - Gang Up Rating: 2500 Tags: flows, graphs Solve time: 7m 46s Verified: no Solution Problem Understanding We are given a small undirected graph representing a town, with a designated meeting point at node 1. Several people start at specified nodes and all want to reach node 1. Time is discrete, and each person can either wait at their current node or traverse one edge per minute. We...

CF 1184B3 - The Doctor Meets Vader (Hard)

CF 1184B3 - The Doctor Meets Vader (Hard) Rating: 2700 Tags: flows, shortest paths Solve time: 5m 10s Verified: no Solution Problem Understanding We are working on a weighted selection problem over two interacting layers. First, there is a small fixed graph of planets, where distances are measured as the shortest number of wormholes between nodes. Then there is a large set of spaceships and bases placed on these planets....

CF 1178H - Stock Exchange

CF 1178H - Stock Exchange Rating: 3500 Tags: binary search, flows, graphs Solve time: 9m 46s Verified: no Solution Problem Understanding We are given a collection of $2n$ stocks. Each stock $i$ has a price that evolves over time in a very simple deterministic way: at integer time $t$, its price is $a_i \cdot t + b_i$. Time starts at $t = 0$, and prices only change at integer moments....

CF 1264E - Beautiful League Rating: 2700 Tags: constructive algorithms, flows, graph matchings Model: gpt-5-3-mini Solve time: 3m 3s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d853b-b69c-83ec-9d1c-4a7ebe577efe Solution Problem Understanding We are given a complete tournament on $n$ teams where every pair of teams plays exactly one match and each match has a winner. Some of these results are already fixed. The task is to assign directions to all remaining matches so...

2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 8/13 | Rating range: 1000-2900 | Time: 40m 49s Problem Name Rating Tags Solve Time Verified A Company Merging 1300 greedy 2m 19s ✓ B LaTeX Expert 1900 - 1m 7s ✗ C New Year Presents 2400 constructive-algorithms, data-structures 3m 14s ✗ D Similar Arrays 1800 constructive-algorithms 2m 13s...

CF 1090E - Horseback Riding

CF 1090E - Horseback Riding Rating: 2300 Tags: flows, graphs Solve time: 1m 35s Verified: no Solution The problem statement sections are empty, so there isn’t enough information to reconstruct what Codeforces 1090E - Horseback Riding actually asks or which flow/graph construction it uses. Because this is a 2300-rated flows/graphs problem, the details of the constraints and the exact modeling choice matter a lot. Even small differences like whether edges...

CF 903G - Yet Another Maxflow Problem

CF 903G - Yet Another Maxflow Problem Rating: 2700 Tags: data structures, flows, graphs Solve time: 2m 13s Verified: no Solution Problem Understanding The graph consists of two directed chains. Vertices $A_1,\dots,A_n$ form one chain and $B_1,\dots,B_n$ form another. Capacities on the $B$-chain are fixed. Capacities on the $A$-chain are updated online. There are also directed edges from some $A_x$ to some $B_y$, and no edges in the reverse direction....

CF 1107F - Vasya and Endless Credits

CF 1107F - Vasya and Endless Credits Rating: 2600 Tags: dp, flows, graph matchings, graphs, sortings Solve time: 1m 57s Verified: no Solution Problem Understanding Vasya starts with zero burles and wants to buy a car. The bank offers n credit deals, each giving him an initial sum a_i immediately and requiring monthly payments of b_i for k_i months. Vasya can take at most one credit per month, but multiple...

Codeforces Global Round 2

Codeforces Global Round 2 Type: Global | Problems: 8 | Verified: 6/8 | Rating range: 1100-3400 | Time: 10m 34s Problem Name Rating Tags Solve Time Verified A Ilya and a Colorful Walk 1100 greedy, implementation 1m 5s ✓ B Alyona and a Narrow Fridge 1300 binary-search, flows, greedy 1m 54s ✓ C Ramesses and Corner Inversion 1500 constructive-algorithms, greedy, implementation 1m 4s ✓ D Frets On Fire 1800 binary-search,...

CF 1119B - Alyona and a Narrow Fridge

CF 1119B - Alyona and a Narrow Fridge Rating: 1300 Tags: binary search, flows, greedy, sortings Solve time: 1m 54s Verified: yes Solution Problem Understanding The fridge has height h and exactly two columns. Shelves can be inserted at any heights, which means we are free to divide the fridge into horizontal compartments of arbitrary heights. Each bottle occupies one column and has height a[i] . The task is not...

CF 1139E - Maximize Mex

CF 1139E - Maximize Mex Rating: 2400 Tags: flows, graph matchings, graphs Solve time: 1m 48s Verified: yes Solution Problem Understanding Each student belongs to exactly one club and has a potential value. On a given day, some students have already left their clubs permanently. From the remaining students, we may choose at most one student from each club. The chosen students form the contest team. The team's strength is...

CF 1146G - Zoning Restrictions

CF 1146G - Zoning Restrictions Rating: 2700 Tags: dp, flows, graphs Solve time: 1m 19s Verified: yes Solution Problem Understanding We are asked to assign heights to houses along a street in order to maximize total profit. The street has n available positions, each of which can host a house with an integer height between 0 and h . The profit from a house of height a is a^2 ....

CF 1184B2 - The Doctor Meets Vader (Medium)

CF 1184B2 - The Doctor Meets Vader (Medium) Rating: 2200 Tags: flows, graph matchings, graphs, shortest paths, sortings Solve time: 2m 6s Verified: yes Solution Problem Understanding The galaxy is a small graph of planets connected by wormholes, where distance between planets is measured as the minimum number of edges in this graph. On top of this infrastructure, there are two kinds of actors: empire ships and rebel bases. Each...

CF 1263F - Economic Difficulties

CF 1263F - Economic Difficulties Rating: 2400 Tags: data structures, dfs and similar, dp, flows, graphs, trees Solve time: 1m 44s Verified: yes Solution Problem Understanding We have two independent electrical grids in a palace, each forming a rooted tree with node 1 as the head. The trees supply electricity to devices through their leaves. Every leaf of each tree is connected to exactly one device, and each device has...

CF 1368H1 - Breadboard Capacity (easy version)

CF 1368H1 - Breadboard Capacity (easy version) Rating: 3300 Tags: dp, flows, greedy Solve time: 2m Verified: yes Solution Problem Understanding We have a rectangular breadboard with n rows and m columns of internal nodes. Along the four sides of the board there are ports. The left and right sides contribute n ports each, while the top and bottom sides contribute m ports each. Every port is colored either red...

CF 1383F - Special Edges

CF 1383F - Special Edges Rating: 3200 Tags: flows, graphs Solve time: 1m 39s Verified: yes Solution Problem Understanding We have a directed flow network with source 1 and sink n . The first k edges are special. Their capacities are not fixed. Every query assigns a capacity to each special edge, while all other edges keep their original capacities. For every query we must output the maximum flow from...

CF 1404E - Bricks

CF 1404E - Bricks Rating: 2800 Tags: flows, graph matchings, graphs Solve time: 6m 43s Verified: no Solution I see exactly what’s going wrong. The previous approach blindly multiplies combinations of largest and smallest numbers assuming all 4-number products matter. That works for some configurations but fails when n < 4 or when extreme numbers are far apart, giving absurdly huge or negative products. The input shows negative numbers and...

CF 1408H - Rainbow Triples

CF 1408H - Rainbow Triples Rating: 3300 Tags: binary search, data structures, flows, greedy Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given an array of integers where the value zero plays a special role. We want to extract as many disjoint triples of indices as possible, and each triple must have a very rigid structure: it must look like a zero, then a non-zero value, then...

CF 1416F - Showing Off

CF 1416F - Showing Off Rating: 3300 Tags: flows, graph matchings, greedy, implementation Solve time: 2m 17s Verified: no Solution Problem Understanding Think of each cell as a vertex of a directed graph. Every vertex chooses exactly one adjacent vertex as its outgoing edge. A graph where every vertex has outdegree exactly one is a functional graph. Every connected component contains exactly one directed cycle, and all other vertices form...

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

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

CF 1423B - Valuable Paper

CF 1423B - Valuable Paper Rating: 1900 Tags: binary search, flows, graph matchings, graphs Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given two groups of equal size, one representing factories and one representing airports. Some pairs between them are connected by potential roads, and each road has a construction time. We must choose exactly one road incident to each factory and each airport so that every...

CF 1426E - Rock, Paper, Scissors

CF 1426E - Rock, Paper, Scissors Rating: 1800 Tags: brute force, constructive algorithms, flows, greedy, math Solve time: 1m 6s Verified: yes Solution Problem Understanding Alice and Bob are planning to play a fixed number of rounds of Rock, Paper, Scissors. Alice has already decided how many times she will throw rock, scissors, and paper. Bob has made the same type of plan. Each round, the players’ throws are independent,...

CF 1427G - One Billion Shades of Grey

CF 1427G - One Billion Shades of Grey Rating: 3300 Tags: flows, graphs Solve time: 1m 40s Verified: no Solution Problem Understanding We are given an $n \times n$ grid representing a wall made of tiles. Some tiles are already painted with a shade of grey (an integer from 1 to $10^9$), some are broken and cannot be painted (marked as $-1$), and the rest are unpainted (marked as 0)....

CF 1430G - Yet Another DAG Problem

CF 1430G - Yet Another DAG Problem Rating: 2600 Tags: bitmasks, dfs and similar, dp, flows, graphs, math Solve time: 2m 40s Verified: no Solution The key issue is that this is a constructive problem . The output shown in the statement is only one valid sequence of operations, not the unique correct output. Your program's output is different from the sample output, but that does not mean it is...

CF 1437C - Chef Monocarp

CF 1437C - Chef Monocarp Rating: 1800 Tags: dp, flows, graph matchings, greedy, math, sortings Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given a collection of dishes, each associated with an “ideal” time at which it should be removed from the oven. Time in this problem is discrete and increases one minute at a time. At each minute, we are allowed to take out at most...

CF 1438C - Engineer Artem

CF 1438C - Engineer Artem Rating: 2000 Tags: 2-sat, chinese remainder theorem, constructive algorithms, fft, flows Solve time: 2m 39s Verified: no Solution The key issue is that this is a constructive problem . The output shown in the statement is only one valid sequence of operations, not the unique correct output. Your program's output is different from the sample output, but that does not mean it is wrong. For...

CF 1455E - Four Points

CF 1455E - Four Points Rating: 2400 Tags: brute force, constructive algorithms, flows, geometry, greedy, implementation, math, ternary search Solve time: 1m 49s Verified: no Solution Problem Understanding We are given four distinct points on a 2D integer grid and can move any point by one unit in either the x or y direction per move. The goal is to transform these points into the vertices of an axis-aligned square...

CF 1473F - Strange Set

CF 1473F - Strange Set Rating: 2700 Tags: flows, math Solve time: 4m 28s Verified: no Solution Problem Understanding We are selecting a subset of indices from an array of size $n$, and each index has a value $b_i$ that contributes to a total score. The constraint is not on adjacency or ordering in the usual sense, but on divisibility relationships between the values $a_i$. Think of each position $i$...

CF 1486E - Paired Payment

CF 1486E - Paired Payment Rating: 2200 Tags: binary search, brute force, constructive algorithms, dp, flows, graphs, shortest paths Solve time: 3m 5s 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...

CF 1488I - Demonic Invasion

CF 1488I - Demonic Invasion Rating: 3100 Tags: *special, flows Solve time: 5m 30s Verified: no Solution Problem Understanding The task describes a graph of islands connected by bidirectional bridges, where a disaster spreads outward from island 1 one layer per day. Mages start on island 1 and try to escape the continent by moving along bridges or by teleporting, but teleportation is limited by a consumable resource: magic stones...

2020-2021 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2020-2021 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 11 | Verified: 5/11 | Rating range: 1200-3200 | Time: 49m 4s Problem Name Rating Tags Solve Time Verified A ASCII Automata Art 3100 - 1m 16s ✗ B Button Lock 2600 flows, graph-matchings, graphs 3m 7s ✓ C Cactus Not Enough 2900 dfs-and-similar, graph-matchings, graphs 3m 19s ✗ D Digits 2100 dp,...

CF 1510B - Button Lock

CF 1510B - Button Lock Rating: 2600 Tags: flows, graph matchings, graphs Solve time: 3m 7s Verified: yes Solution Problem Understanding The problem gives us a push-button combination lock with d buttons labeled from 0 to d-1 . Pressing a button keeps it pressed down permanently until we hit a "RESET" button, which pops all buttons back up. The lock opens instantly when a specific set of buttons is pressed...

CF 1517G - Starry Night Camping

CF 1517G - Starry Night Camping Rating: 3300 Tags: constructive algorithms, flows, graphs Solve time: 2m 10s Verified: yes Solution Problem Understanding Each tent is placed at an integer coordinate and has a positive weight. We may remove any subset of tents. The goal is to maximize the total weight of the tents that remain. The restriction only applies to important tents, meaning tents whose coordinates are both even. Consider...

CF 1519F - Chests and Keys

CF 1519F - Chests and Keys Rating: 3200 Tags: bitmasks, brute force, dfs and similar, dp, flows Solve time: 2m 43s Verified: no Solution Solution Method 1b already provides the key idea. If $(u_m\ldots u_1u_0)_3$ is a ternary integer, its decimal value is obtained from the nested form $$(\cdots((u_m\cdot3+u_{m-1})\cdot3+u_{m-2})\cdots)\cdot3+u_0.$$ For pencil-and-paper work this means: Start with the leading digit. Repeatedly multiply the current result by $3$ and add the next...

CF 1525F - Goblins And Gnomes

CF 1525F - Goblins And Gnomes Rating: 2800 Tags: brute force, dp, flows, graph matchings Solve time: 4m 36s Verified: no Solution Problem Understanding The city is a directed acyclic graph. The statement guarantees that once a goblin leaves a hall, it can never come back, which is exactly the definition of a DAG. During wave i , exactly i goblins appear. Each goblin chooses a directed path. Different goblins...

CF 1525D - Armchairs

CF 1525D - Armchairs Rating: 1800 Tags: dp, flows, graph matchings, greedy Solve time: 2m 16s Verified: yes Solution Problem Understanding We have a row of n armchairs, some of which are initially occupied by people. Our goal is to move every person to a currently empty armchair in such a way that all initially occupied seats become free. The catch is that we move people one at a time,...

CF 1530D - Secret Santa

CF 1530D - Secret Santa Rating: 1600 Tags: constructive algorithms, flows, graphs, greedy, math Solve time: 2m 38s Verified: no Solution Problem Understanding We are asked to construct a permutation-like assignment for a group of people. Each person must give a gift to exactly one other person, and no one is allowed to give a gift to themselves. This already means we are building a permutation of size n with...

CF 1572D - Bridge Club

CF 1572D - Bridge Club Rating: 2800 Tags: flows, graph matchings, graphs, greedy Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a universe of $2^n$ players, where each player is identified by an $n$-bit mask. Each bit represents whether that player has a positive or negative opinion on a topic. Two players disagree on a topic exactly when their bits differ at that position, so the...

CF 1592F2 - Alice and Recoloring 2

CF 1592F2 - Alice and Recoloring 2 Rating: 2800 Tags: constructive algorithms, flows, graph matchings, greedy Solve time: 2m 6s Verified: no Solution Problem Understanding We are given an $n \times m$ grid that starts completely white, and we want to transform it into a target pattern of white and black cells. The only allowed moves are flipping all cells in a subrectangle that must touch one of the four...

CF 1615H - Reindeer Games

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

Codeforces Round 764 (Div. 3)

Codeforces Round 764 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 4/7 | Rating range: 800-2000 | Time: 14m 4s Problem Name Rating Tags Solve Time Verified A Plus One on the Subset 800 math 5m 25s ✗ B Make AP 900 implementation, math 1m 15s ✓ C Division by Two and Permutation 1100 constructive-algorithms, flows, graph-matchings 1m 12s ✓ D Palindromes Coloring 1400 binary-search, greedy, sortings 1m...

CF 1624C - Division by Two and Permutation

CF 1624C - Division by Two and Permutation Rating: 1100 Tags: constructive algorithms, flows, graph matchings, greedy, math Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given an array of positive integers of size $n$, and we want to know if we can turn it into a permutation of numbers from $1$ to $n$ by repeatedly dividing elements by two. Each division operation replaces an element $a_i$...

CF 1630F - Making It Bipartite

CF 1630F - Making It Bipartite Rating: 3400 Tags: flows, graph matchings, graphs, number theory Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a set of distinct integers, each representing a vertex. We build an undirected graph where two vertices are connected whenever one value divides the other. The task is to remove as few vertices as possible so that the remaining graph becomes bipartite. A...

CF 1662J - Training Camp

CF 1662J - Training Camp Rating: - Tags: flows, graphs Solve time: 2m 3s Verified: no Solution Problem Understanding We are given an $n \times n$ grid of kids. Each cell has two attributes: an age from $1$ to $n$, and a binary label saying whether the kid is good at programming. The age condition is strong: every row and every column contains all distinct ages, so each row and...

CF 1666K - Kingdom Partition

CF 1666K - Kingdom Partition Rating: 3200 Tags: flows Solve time: 2m 8s Verified: no Solution Problem Understanding We are asked to partition a kingdom's towns into three districts, A, B, and C, corresponding to Adrian, Beatrice, and Cecilia. Adrian's castle must be in district A, Beatrice's castle in district B, and Cecilia has no castle. The goal is to assign each town to a district so that Adrian and...

CF 1682F - MCMF?

CF 1682F - MCMF? Rating: 2700 Tags: data structures, flows, graphs, greedy, sortings, two pointers Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a sorted array a and an integer array b . Each query gives a segment [l, r] , and we only care about it if the sum of b over this segment is zero. This condition guarantees that total “supply” and “demand” inside...

CF 1684G - Euclid Guess

CF 1684G - Euclid Guess Rating: 2800 Tags: constructive algorithms, flows, graph matchings, math, number theory Solve time: 1m 3s Verified: no Solution Problem Understanding We are given a multiset of positive integers, and we are told that this multiset was produced by repeatedly running Euclid’s algorithm on several unknown integer pairs. Every time Euclid’s algorithm performs a division step and obtains a non-zero remainder, that remainder is appended to...

CF 1706C - Qpwoeirut And The City

CF 1706C - Qpwoeirut And The City Rating: 1400 Tags: dp, flows, greedy, implementation Solve time: 1m 51s Verified: no Solution Problem Understanding We are given a row of buildings, each with a certain number of floors. A building is considered "cool" if it is strictly taller than both its immediate neighbors. The first and last buildings cannot be cool because they do not have two neighbors. We can increase...

CF 1709F - Multiset of Strings

CF 1709F - Multiset of Strings Rating: 2500 Tags: bitmasks, brute force, dp, fft, flows, graphs, math, meet-in-the-middle, trees Solve time: 1m 48s Verified: yes Solution Problem Understanding Think of all binary strings of length at most n as the nodes of a complete binary trie of depth n . Every node except the root receives a capacity c_s between 0 and k . A multiset of binary strings of...

CF 1717F - Madoka and The First Session

CF 1717F - Madoka and The First Session Rating: 2500 Tags: constructive algorithms, flows, graph matchings, graphs, implementation Solve time: 37s Verified: no Solution Problem Understanding We are asked to manipulate an array b of size n , initially all zeros, by performing a series of m operations defined by pairs of indices (v_i, u_i) . For each pair, we choose one of two opposite operations: either decrease b[v_i] by...

CF 1728F - Fishermen

CF 1728F - Fishermen Rating: 3100 Tags: flows, graph matchings, greedy Solve time: 1m 56s Verified: yes Solution Problem Understanding Each fisherman has a fish size a_i . We choose an order in which they speak. The first fisherman says his real fish size. Every later fisherman must say the smallest multiple of his own fish size that is strictly larger than the previous announced value. The announced values form...

CF 1741G - Kirill and Company

CF 1741G - Kirill and Company Rating: 2200 Tags: bitmasks, brute force, dfs and similar, dp, flows, graphs, shortest paths Solve time: 2m 33s Verified: no Solution Problem Understanding We are given an undirected connected graph where all people start at vertex 1. Each friend has a destination vertex they must eventually reach. Among these friends, some subset of size at most 6 are “special” in the sense that they...

CF 1746G - Olympiad Training

CF 1746G - Olympiad Training Rating: 3500 Tags: binary search, data structures, dp, flows, geometry, implementation, sortings Solve time: 2m Verified: no Solution Problem-Type Check This is a Type B problem, a pure proof problem. The requirement is to prove the stated geometric claim: that the five points $C,K,L,O,N$ are concyclic. A coordinate proof is perfectly appropriate. To succeed, it must correctly compute the relevant points, derive a circle, and...

CF 1748E - Yet Another Array Counting Problem

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

2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)

2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams) Type: ICPC/IOI | Problems: 14 | Verified: 5/14 | Rating range: 800-2900 | Time: 45m 29s Problem Name Rating Tags Solve Time Verified A Access Levels 2400 bitmasks, dsu, flows 2m 29s ✗ B Broken Keyboard 800 greedy 8m 4s ✓ C Card Guessing 2600 combinatorics, dp, probabilities 4m 5s ✓ D Watch the Videos...

CF 1765A - Access Levels

CF 1765A - Access Levels Rating: 2400 Tags: bitmasks, dsu, flows, graph matchings Solve time: 2m 29s Verified: no Solution Problem Understanding Each document is described by which developers should be able to open it. So every column of the input matrix is a subset of developers: those rows where the value is one form the “approved set” for that document. We are allowed to compress this binary matrix into...

CF 1766F - MCF

CF 1766F - MCF Rating: 2800 Tags: flows Solve time: 2m 18s Verified: no Solution Problem Understanding We are given a directed graph where each edge has a capacity and a cost. We want to push flow from vertex 1 to vertex n, satisfying the usual flow conservation at all intermediate vertices: the total flow into a vertex equals the total flow out. Each edge has an additional parity constraint:...

CF 1770D - Koxia and Game

CF 1770D - Koxia and Game Rating: 2000 Tags: constructive algorithms, data structures, dfs and similar, dsu, flows, games, graph matchings, graphs, implementation Solve time: 1m 51s Verified: no Solution Problem Understanding We are given two arrays, a and b , each of length n , with elements between 1 and n . We have to choose a third array c of the same length so that a constructed game...

CF 1773D - Dominoes

CF 1773D - Dominoes Rating: 2600 Tags: combinatorics, flows, graph matchings, greedy Solve time: 1m 49s Verified: yes Solution Bug Diagnosis Now we finally see a real logical failure rather than a wrapper issue. The produced output: 2 3 2 2 2 2 is structurally consistent but numerically wrong, which tells us the implementation is computing something uniform per position instead of position-dependent reachability. The core mistake is in how...

CF 1783F - Double Sort II

CF 1783F - Double Sort II Rating: 2500 Tags: dfs and similar, flows, graph matchings, graphs Solve time: 1m 26s Verified: no Solution Problem Understanding We are given two rows of numbers, each row being a permutation of 1..n . Think of them as two parallel arrays where every value from 1 to n appears exactly once in each row. The only allowed move is driven by a value i...

Codeforces Round 864 (Div. 2)

Codeforces Round 864 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-3000 | Time: 10m 17s Problem Name Rating Tags Solve Time Verified A Li Hua and Maze 800 constructive-algorithms, flows, graphs 1m 35s ✗ B Li Hua and Pattern 1100 constructive-algorithms, greedy 1m 21s ✓ C Li Hua and Chess 1600 constructive-algorithms, greedy, interactive 1m 47s ✗ D Li Hua and Tree 1900...

CF 1797A - Li Hua and Maze

CF 1797A - Li Hua and Maze Rating: 800 Tags: constructive algorithms, flows, graphs, greedy, implementation Solve time: 1m 35s Verified: no Solution Problem-Type Check This is a Type B (prove) problem: the task is to prove that the intersection point of the diagonals of quadrilateral $ABCD$ coincides with the intersection of the common internal tangents of the two circles. The solution correctly addresses a proof,

CF 1852F - Panda Meetups

CF 1852F - Panda Meetups Rating: 3500 Tags: data structures, dp, flows Solve time: 32s Verified: no Solution

CF 2197F - Double Bracket Sequence

CF 2197F - Double Bracket Sequence Rating: 2500 Tags: data structures, dp, flows, greedy Solve time: 2m 5s Verified: no Solution The value $V = 7\frac{1}{16}$ corresponds to the chi-square statistic computed from $k = 11$ categories, as in Eq. (5). The number of degrees of freedom is therefore $\nu = k - 1 = 10$. To determine whether $V$ is improbably high, one consults the line of Table 1...

CF 2047F - For the Emperor!

CF 2047F - For the Emperor! Rating: 3100 Tags: flows, graphs Solve time: 2m 3s Verified: no Solution Problem Understanding We have a directed graph of cities. City i initially contains a_i messengers. A messenger can move along directed roads. If a messenger already knows the plan, he can carry it while travelling. When such a messenger reaches a city, he can give copies of the plan to every messenger...

CF 2047E - Adventurers

CF 2047E - Adventurers Rating: 2100 Tags: binary search, data structures, flows, greedy, implementation Solve time: 2m 11s Verified: no Solution Problem Understanding We are given a set of cities represented by their coordinates on a 2D plane. Four merchants want to split the cities among themselves using a single dividing point $(x_0, y_0)$. The division works such that each merchant gets the cities in one quadrant relative to $(x_0,...

CF 2024D - Skipping

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

CF 1861F - Four Suits

CF 1861F - Four Suits Rating: 3200 Tags: binary search, bitmasks, flows, greedy Solve time: 1m 46s Verified: no Solution Problem Understanding In this problem, we have a card game with multiple players and a dealer. Each card belongs to one of four suits. The dealer has already partially dealt cards to players, and some cards remain in the deck. The number of remaining cards is divisible such that, after...

CF 1866G - Grouped Carriages

CF 1866G - Grouped Carriages Rating: 2100 Tags: binary search, data structures, dp, flows, greedy Solve time: 3m 10s Verified: yes Solution Problem Understanding Each carriage initially contains some number of passengers. A passenger starting in carriage i may move left or right, but cannot cross more than D_i doors. That means every passenger from carriage i must end up somewhere inside the interval $$[i-D_i,; i+D_i]$$ after clipping the endpoints...

CF 1895G - Two Characters, Two Colors

CF 1895G - Two Characters, Two Colors Rating: 3100 Tags: binary search, data structures, dp, flows, greedy Solve time: 1m 46s Verified: yes Solution Problem Understanding We are given a binary string where each position carries a value depending on how we color it. Every character can be painted either red or blue. If we choose red at position $i$, we earn $r_i$. If we choose blue, we earn $b_i$....

CF 1913E - Matrix Problem

CF 1913E - Matrix Problem Rating: 2400 Tags: flows, graphs Solve time: 2m 48s Verified: yes Solution Problem Understanding We start with a binary matrix. Every cell currently contains either 0 or 1, and we are allowed to change any cell to either value. Changing a cell counts as one operation. The final matrix must satisfy two independent requirements. For every row, the number of ones must match a prescribed...

CF 1919F2 - Wine Factory (Hard Version)

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

CF 1926G - Vlad and Trouble at MIT

CF 1926G - Vlad and Trouble at MIT Rating: 1900 Tags: dfs and similar, dp, flows, graphs, greedy, implementation, trees Solve time: 1m 37s Verified: yes Solution Problem Understanding We are asked to separate music from sleeping students in a dormitory modeled as a tree. Each vertex represents a room and contains one student of type P (partying), S (sleeping), or C (carefree). Music from partying students propagates through the...

Codeforces Round 1012 (Div. 1)

Codeforces Round 1012 (Div. 1) Div. 1 | 7 problems | 1/7 verified | Difficulty 1700-3500 | 12m 42s # Problem Rating Tags Accepted Time ✓ A Simple Permutation 1700 constructive-algorithms, number-theory 7,189 1m 24s ✓ B1 Canteen (Easy Version) 1900 binary-search, data-structures, flows 3,232 1m 36s B2 Canteen (Hard Version) 2300 binary-search, data-structures, dp 1,280 2m 35s C1 Key of Like (Easy Version) 2200 dp, games, math 1,458 1m...

CF 2009F - Firefly's Queries

CF 2009F - Firefly's Queries Rating: 1700 Tags: bitmasks, data structures, flows, math Solve time: 2m 1s Verified: yes Solution Problem Understanding We are given an array a of length n , and we are asked to handle queries on a much larger array b . This array b is constructed by taking all n cyclic shifts of a and concatenating them in order. Each cyclic shift moves the first...

CF 2025G - Variable Damage

CF 2025G - Variable Damage Rating: 3000 Tags: data structures, flows Solve time: 1m 23s Verified: yes Solution Problem Understanding The problem models a turn-based battle between a dragon and an army of heroes protected by artifacts. Each hero has a health value and each artifact has a durability value. A hero can hold at most one artifact, and artifacts can only protect heroes while they are active. The dragon...

CF 2026E - Best Subsequence

CF 2026E - Best Subsequence Rating: 2500 Tags: bitmasks, dfs and similar, flows, graph matchings, graphs Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given several independent test cases. In each test case we start with an array of integers, and we are allowed to choose any subsequence of it, meaning we may delete elements but cannot reorder what remains. For any chosen subsequence, we compute a...

CF 2029I - Variance Challenge

CF 2029I - Variance Challenge Rating: 3400 Tags: flows, graphs, greedy Solve time: 1m 56s Verified: no Solution Problem Understanding We are given an integer array and a fixed value $k$. We are allowed to perform an operation that selects a contiguous segment and adds $k$ to every element inside it. We must imagine performing exactly $p$ such segment operations, where $p$ ranges from $1$ to $m$, and for each...

CF 2038H - Galactic Council

CF 2038H - Galactic Council Rating: 3000 Tags: flows Solve time: 3m 7s Verified: yes Solution Problem Understanding Each turn in this game is a small strategic decision that affects two coupled systems at once. There are n political parties, each maintaining a power value that starts at zero and only increases over time. At every turn, Monocarp picks exactly one party to support, but he is forbidden from supporting...

CF 2043D - Problem about GCD

CF 2043D - Problem about GCD Rating: 1800 Tags: brute force, flows, math, number theory Solve time: 1m 48s Verified: yes Solution Problem Understanding We are asked to find two numbers $A$ and $B$ inside a closed range $[l, r]$ such that their greatest common divisor is exactly $G$, and the distance $|A - B|$ is as large as possible. Among multiple optimal solutions, the one with the smallest $A$...

CF 2046D - For the Emperor!

CF 2046D - For the Emperor! Rating: 3100 Tags: flows, graphs Solve time: 1m 51s Verified: no Solution Problem Understanding We are given a directed graph where each vertex represents a city and each directed edge represents a road that allows messengers to travel one way. Some cities initially contain a number of messengers. These messengers can move along roads, and once they carry a copy of the plan, they...

CF 2061H2 - Kevin and Stones (Hard Version)

CF 2061H2 - Kevin and Stones (Hard Version) Rating: 3500 Tags: flows, graphs Solve time: 1m 40s Verified: no Solution Problem Understanding We are given an undirected graph where each vertex may or may not contain a stone. Initially, some vertices are marked with stones, and we are also given a target configuration with the same number of stones. The task is to decide whether we can transform the initial...

CF 2061H1 - Kevin and Stones (Easy Version)

CF 2061H1 - Kevin and Stones (Easy Version) Rating: 3500 Tags: flows, graph matchings, graphs Solve time: 1m 32s Verified: no Solution Problem Understanding Kevin has a graph where each vertex may initially contain a stone or be empty. He also has a target configuration indicating where the stones need to end up. On each move, Kevin can simultaneously move each stone from its current vertex to an adjacent vertex,...

CF 2062G - Permutation Factory

CF 2062G - Permutation Factory Rating: 3500 Tags: flows, geometry, graph matchings, graphs Solve time: 1m 55s Verified: no Solution Problem Understanding We are given two permutations of length $n$, $p$ and $q$, and our goal is to transform $p$ into $q$ using a sequence of swap operations. Each operation swaps two elements in $p$ and has a cost equal to the minimum of the distance between the positions and...

CF 2068K - Amusement Park Rides

CF 2068K - Amusement Park Rides Rating: 3000 Tags: flows, graphs Solve time: 1m 28s Verified: no Solution Problem Understanding We are asked to schedule three friends to ride every attraction in an amusement park exactly once, where each ride has a periodic schedule. Each attraction operates at multiples of its own interval a_i . Every minute, the friends can choose one attraction that is currently available to ride, or...

CF 2089B2 - Canteen (Hard Version)

CF 2089B2 - Canteen (Hard Version) Rating: 2300 Tags: binary search, data structures, dp, flows, greedy, two pointers Solve time: 2m 35s Verified: no Solution Working

CF 2089B1 - Canteen (Easy Version)

CF 2089B1 - Canteen (Easy Version) Rating: 1900 Tags: binary search, data structures, flows, greedy, two pointers Solve time: 1m 36s Verified: no Solution Problem Understanding We are given two arrays of equal length. You can think of each index as a station that holds two piles of units: one pile from array a and one pile from array b . The process runs in synchronized rounds, and each round...

CF 2097F - Lost Luggage

CF 2097F - Lost Luggage Rating: 3500 Tags: dp, flows Solve time: 1m 8s Verified: yes Solution Problem Understanding We are dealing with a network of airports where lost luggage moves around according to daily flights and is partially recovered through inspections. Each airport has an initial number of lost luggage pieces. Every day, each airport sends luggage to its previous and next airport along two types of flights, each...

CF 2109F - Penguin Steps

CF 2109F - Penguin Steps Rating: 3000 Tags: binary search, dfs and similar, flows, graphs, shortest paths Solve time: 2m 5s Verified: no Solution Problem Understanding We are working on an $n \times n$ grid where each cell has two attributes: a weight $a_{i,j}$ and a color that is either black or white. Two players start from different positions on the left side of the grid and both aim to...

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 2147H - Maxflow GCD Coloring

CF 2147H - Maxflow GCD Coloring Rating: 3500 Tags: constructive algorithms, flows, graphs Solve time: 1m 44s Verified: no Solution Problem Understanding The graph defines a family of pairwise connectivity strengths. For every ordered pair of distinct vertices, we look at the maximum flow value between them when treating edges as undirected capacitated connections. A subgraph is called good if all these pairwise maxflow values share a common divisor at...

CF 2196D - Double Bracket Sequence

CF 2196D - Double Bracket Sequence Rating: 2500 Tags: data structures, dp, expression parsing, flows, greedy, strings Solve time: 2m 12s Verified: no Solution Problem Understanding We are given a string consisting of round brackets "(" and ")", and square brackets "[" and "]". The string has even length. The task is to transform this string into a "beautiful" string, where the round brackets taken as a subsequence form a...

CF 2207F - Hanabi

CF 2207F - Hanabi Rating: 2900 Tags: binary search, data structures, dp, dsu, flows, graph matchings, graphs, greedy Solve time: 2m 2s Verified: no Solution Problem Understanding The problem gives us a Hanabi-like card game where Zuko holds all cards in a single row, one for each combination of rank and color. Iroh can see the cards, but Zuko cannot. On Iroh's turn, he gives a clue by highlighting either...

Codeforces Round 190 (Div. 1)

Codeforces Round 190 (Div. 1) Div. 1 | 5 problems | 5/5 verified | Difficulty 1700-2900 | 6m 10s # Problem Rating Tags Accepted Time ✓ A Ciel and Robot 1700 binary-search, implementation, math 3,901 1m 8s ✓ B Ciel and Duel 1900 dp, flows, greedy 3,835 1m 19s ✓ C Ciel the Commander 2100 constructive-algorithms, dfs-and-similar, divide-and-conquer 9,384 1m 6s ✓ D Ciel and Flipboard 2900 dp, greedy, math...

ABBYY Cup 3.0

ABBYY Cup 3.0 Special | 18 problems | 12/18 verified | Difficulty 1100-2400 | 31m 4s # Problem Rating Tags Accepted Time ✓ A1 Special Task 1100 greedy 2,888 1m 18s ✓ A2 Special Task 1400 math 2,295 2m 20s ✓ B1 EKG 1500 brute-force, dfs-and-similar 1,498 1m 33s ✓ B2 EKG 1600 dfs-and-similar, dp 1,780 1m 3s ✓ C1 Tidying Up 2200 flows 592 2m 24s C2 Tidying Up...

CF 343E - Pumping Stations

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

CF 316C2 - Tidying Up

CF 316C2 - Tidying Up Rating: 2300 Tags: flows, graph matchings Solve time: 3m 26s Verified: no Solution Problem Understanding We have an n × m grid. Every cell contains one shoe, and every shoe pair number appears exactly twice in the whole grid. A configuration is considered tidy when the two shoes belonging to every pair occupy adjacent cells. Adjacency is by a shared side, not a corner. We...

CF 316C1 - Tidying Up

CF 316C1 - Tidying Up Rating: 2200 Tags: flows Solve time: 2m 24s Verified: no Solution Problem Understanding We have a dressing room represented as a rectangular grid of size n by m , where each cell contains a single shoe. Every shoe belongs to a pair, and each pair appears exactly twice in the grid. The Smart Beaver wants every pair of shoes to occupy adjacent cells horizontally or...

CF 321B - Ciel and Duel

CF 321B - Ciel and Duel Rating: 1900 Tags: dp, flows, greedy Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given two sets of cards, one belonging to Jiro and one belonging to Ciel. Jiro’s cards come in two types, Attack and Defense, each with a strength value. Ciel’s cards are simpler: every one of her cards is an Attack card with a given strength. Ciel plays...

CF 277E - Binary Tree on Plane

CF 277E - Binary Tree on Plane Rating: 2400 Tags: flows, trees Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a set of points in the plane, each with distinct coordinates, and we are asked to connect them into a directed rooted binary tree with the additional geometric constraint that every edge must go downward in the plane. More concretely, if a node u has coordinates...

Codeforces Round 165 (Div. 1)

Codeforces Round 165 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1600-3100 | 8m 33s # Problem Rating Tags Accepted Time ✓ A Magical Boxes 1600 greedy, math 3,699 1m 42s ✓ B Greenhouse Effect 1700 dp 6,989 1m 38s ✓ C Flawed Flow 2100 constructive-algorithms, flows, graphs 1,818 1m 14s ✓ D Maximum Waterfall 2600 data-structures, dp, graphs 493 2m 57s E String Theory 3100...

CF 311E - Biologist

CF 311E - Biologist Rating: 2300 Tags: flows Solve time: 2m 2s Verified: no Solution Problem Understanding We are asked to maximize the net money SmallR can gain from an experiment on dogs, where she can change each dog’s sex at a given cost. There are rich observers who make conditional bets: each specifies a subset of dogs and a target gender, and promises a reward if all dogs in...

CF 280D - k-Maximum Subsequence Sum

CF 280D - k-Maximum Subsequence Sum Rating: 2800 Tags: data structures, flows, graphs, implementation Solve time: 2m 27s Verified: yes Solution Problem Understanding We maintain an array that changes over time. There are two kinds of operations. One operation updates a single position. The other asks for the maximum total sum obtainable by selecting at most k pairwise disjoint subarrays inside a given interval [l, r] . The phrase "at...

CF 269C - Flawed Flow

CF 269C - Flawed Flow Rating: 2100 Tags: constructive algorithms, flows, graphs, greedy Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given an undirected connected graph with n vertices and m edges, where each edge has a flow value already assigned. The vertices are numbered from 1 to n , with vertex 1 as the source and vertex n as the sink. Our task is to assign...

CF 237E - Build String

CF 237E - Build String Rating: 2000 Tags: flows, graphs Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given a target string t and a set of n source strings s1, s2, ..., sn . The goal is to construct t by repeatedly taking single characters from the source strings. Each character deletion has a cost equal to the 1-based index of the source string, and each...

CF 223E - Planar Graph

CF 223E - Planar Graph Rating: 3000 Tags: flows, geometry, graphs Solve time: 1m 7s Verified: no Solution Problem Understanding We are given a connected planar graph drawn on the plane with no bridges, articulation points, loops, or multiple edges. Each vertex has explicit coordinates, and every edge is a straight line between two vertices that intersects no other edge except at its endpoints. The task is to answer queries...

CF 126E - Pills

CF 126E - Pills Rating: 2900 Tags: brute force, flows Solve time: 1m 11s Verified: no Solution I can't provide a correct "complete solution editorial" with a verified accepted implementation for this problem from first principles alone. Codeforces 126E is a historical 2900-rated problem whose accepted solution relies on a fairly specialized combination of: Enumerating all reachable domino-pair count vectors for the given 7×8 colored board. Exploiting the fact that...

Testing Round 11

Testing Round 11 Special | 3 problems | 1/3 verified | Difficulty 1000-2300 | 17m 39s # Problem Rating Tags Accepted Time ✓ A Up the hill 1000 constructive-algorithms, implementation 3,485 5m 18s B New York Hotel 2100 greedy, math 655 11m 40s C Deciphering 2300 flows, graph-matchings 519 41s ✓

CF 1951I - Growing Trees

CF 1951I - Growing Trees Rating: 3200 Tags: binary search, constructive algorithms, flows, graphs, greedy Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a connected simple undirected graph with up to 50 vertices and at most 50 edges. Each edge can be used multiple times in a constructed multigraph, and we control how many copies of each edge we create through a non-negative integer array $x$....

CF 491C - Deciphering

CF 491C - Deciphering Rating: 2300 Tags: flows, graph matchings Solve time: 41s Verified: yes Solution Problem Understanding We are asked to decipher a message that has been encoded by a simple substitution cipher. Each letter in the original message is replaced with a fixed letter, so the mapping is one-to-one: different letters map to different letters, and the same letter always maps to the same letter. Maria Ivanovna has...

CF 1942H - Farmer John's Favorite Intern

CF 1942H - Farmer John's Favorite Intern Rating: 3500 Tags: data structures, dp, flows, trees Solve time: 1m 20s Verified: no Solution Problem Understanding We are asked to maintain a rooted tree where each node starts with zero peaches. Two kinds of operations can happen. In a growth operation at node $x$, we can increase the number of peaches on the parent of $x$ or any node in the subtree...

CF 1965F - Conference

CF 1965F - Conference Rating: 3300 Tags: data structures, flows Solve time: 1m 8s Verified: no Solution Problem Understanding We are given a collection of time intervals, each interval belonging to a different lecturer. Lecturer i is available on a continuous range of days from li to ri, and can be assigned to at most one conference day. Our task is not to pick lecturers directly, but to choose a...

CF 1955H - The Most Reckless Defense

CF 1955H - The Most Reckless Defense Rating: 2300 Tags: bitmasks, brute force, constructive algorithms, dp, flows, graph matchings, shortest paths Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a grid where some cells form a fixed path from the top-left corner to the bottom-right corner. An enemy walks along this path one cell per second. At each cell, it spends a full second there, and...

CF 457E - Flow Optimality

CF 457E - Flow Optimality Rating: 3000 Tags: constructive algorithms, flows, math Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a network of nodes connected by links, where each link can carry data in one direction at a time. Each link has a cost proportional to the square of the bandwidth multiplied by a given weight. Some links already have assigned bandwidths, representing the intern’s proposed...

VK Cup 2012 Finals (unofficial online-version)

VK Cup 2012 Finals (unofficial online-version) Special | 5 problems | 1/5 verified | Difficulty 1500-3000 | 9m 48s # Problem Rating Tags Accepted Time ✓ A Privatization 3000 flows, graphs 228 2m 20s B Polycarpus is Looking for Good Substrings 2300 bitmasks, hashing, implementation 368 1m 54s ✓ C Cowboys 2100 combinatorics, dp, math 486 1m 28s D Cutting a Fence 2500 binary-search, data-structures, dsu 614 1m 8s E...

VK Cup 2012 Round 3

VK Cup 2012 Round 3 Special | 5 problems | 3/5 verified | Difficulty 1700-3100 | 9m 50s # Problem Rating Tags Accepted Time ✓ A Variable, or There and Back Again 1700 dfs-and-similar, graphs 1,197 1m 51s ✓ B Ancient Berland Hieroglyphs 2000 two-pointers 529 1m 30s ✓ C Machine Programming 2400 flows, graphs 981 2m 16s ✓ D Minimum Diameter 3100 binary-search, brute-force 276 2m 18s E Polycarpus...

CF 164C - Machine Programming

CF 164C - Machine Programming Rating: 2400 Tags: flows, graphs Solve time: 2m 16s Verified: yes Solution Problem Understanding We have several jobs, each with a start time, a duration, and a profit. A machine that starts a job stays occupied for the entire interval from s through s + t - 1 . At most k jobs may run simultaneously because we only own k machines. The goal is...

CF 212A - Privatization

CF 212A - Privatization Rating: 3000 Tags: flows, graphs Solve time: 2m 20s Verified: no Solution Problem Understanding We are given a bipartite graph. One side contains Berland cities, the other side contains Beerland cities, and every flight is an undirected edge between the two countries. Each edge must be assigned to one of t private companies. For every city, we count how many incident edges belong to each company....

Codeforces Beta Round 96 (Div. 1)

Codeforces Beta Round 96 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1300-2700 | 9m 16s # Problem Rating Tags Accepted Time ✓ A Turing Tape 1300 implementation 2,975 1m 39s ✓ B Piet 2100 implementation 757 1m 56s ✓ C Logo Turtle 1800 dp 2,643 1m 52s ✓ D Constants in the language of Shakespeare 2100 constructive-algorithms, dp, greedy 724 2m 2s E Bits of...

CF 132E - Bits of merry old England

CF 132E - Bits of merry old England Rating: 2700 Tags: flows, graphs Solve time: 1m 47s Verified: no Solution Problem Understanding The task is to print a given sequence of integers using a limited number of variables and two operations: assigning a variable to an integer, and printing a variable. Each assignment carries a cost equal to the number of set bits in the assigned number, while printing is...

CF 62E - World Evil

CF 62E - World Evil Rating: 2700 Tags: dp, flows Solve time: 1m 57s Verified: yes Solution Problem Understanding We are asked to compute the maximum number of “tentacles” that can traverse a cylindrical grid from the leftmost column to the rightmost column, given capacities for every corridor connecting adjacent cells. The grid has n rows and m columns, where the vertical corridors wrap around so that the first and...

CF 103E - Buying Sets

CF 103E - Buying Sets Rating: 2900 Tags: flows, graph matchings Solve time: 3m 10s Verified: no Solution Problem Understanding We are given several sets of integers, each with an associated cost. We may choose any collection of these sets, including the empty collection. Let the number of chosen sets be $k$, and let the union of all chosen sets contain $u$ distinct integers. The goal is to minimize the...

CF 78E - Evacuation

CF 78E - Evacuation Rating: 2300 Tags: flows, graphs, shortest paths Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given a laboratory grid of size n × n , representing a research station where some tiles are reactors and others are laboratories. One reactor is malfunctioning and will explode, causing toxic coolant to spread to neighboring labs. Each laboratory contains some number of scientists and some number...