flows | brain

Practice › Codeforces Solutions › Testing Round 11 ›

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

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

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

Practice › Codeforces Solutions ›

Testing Round 11

Testing Round 11 Type: Special | Problems: 3 | Verified: 1/3 | Rating range: 1000-2300 | Time: 17m 39s Problem Name Rating Tags Solve Time Verified A Up the hill 1000 constructive-algorithms, implementation 5m 18s ✗ B New York Hotel 2100 greedy, math 11m 40s ✗ C Deciphering 2300 flows, graph-matchings 41s ✓

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

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

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

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

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

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

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

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316C2 - Tidying Up

CF 316C2 - Tidying Up Rating: 2300 Tags: flows, graph matchings Solve time: 3m 19s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid where each cell contains an integer representing a “shoe pair ID”. Every ID appears exactly twice in the grid, so each number defines exactly two positions. The goal is to rearrange the grid conceptually by moving shoes between cells so that for...

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

CF 269C - Flawed Flow

CF 269C - Flawed Flow Rating: 2100 Tags: constructive algorithms, flows, graphs, greedy Solve time: 2m Verified: yes Solution Problem Understanding We are given an undirected graph where every edge already has a flow amount attached to it. The graph is supposed to represent a valid maximum flow from vertex 1 to vertex n , but the directions of the edges were lost. Our task is to recover directions for...

Practice › Codeforces Solutions ›

Codeforces Round 165 (Div. 1)

Codeforces Round 165 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 2/4 | Rating range: 1700-3100 | Time: 7m 2s Problem Name Rating Tags Solve Time Verified B Greenhouse Effect 1700 dp 1m 21s ✓ C Flawed Flow 2100 constructive-algorithms, flows, graphs 2m ✓ D Maximum Waterfall 2600 data-structures, dp, graphs 1m 43s ✗ E String Theory 3100 geometry, math, strings 1m 58s ✗

Practice › Codeforces Solutions ›

VK Cup 2012 Round 3

VK Cup 2012 Round 3 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1700-3100 | Time: 9m 50s Problem Name Rating Tags Solve Time Verified A Variable, or There and Back Again 1700 dfs-and-similar, graphs 1m 51s ✓ B Ancient Berland Hieroglyphs 2000 two-pointers 1m 30s ✓ C Machine Programming 2400 flows, graphs 2m 16s ✓ D Minimum Diameter 3100 binary-search, brute-force 2m 18s ✗ E Polycarpus...

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

CF 311E - Biologist

CF 311E - Biologist Rating: 2300 Tags: flows Solve time: 2m 20s Verified: no Solution Problem Understanding We are tasked with optimizing the gain of a biologist, SmallR, who can change the sex of each of her n dogs at a cost. Each dog has an initial sex, either female (0) or male (1), and a cost to change sex. Multiple rich folk are making bets: each has a set...

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

CF 277E - Binary Tree on Plane

CF 277E - Binary Tree on Plane Rating: 2400 Tags: flows, trees Solve time: 2m 5s Verified: no Solution Problem Understanding We are given a set of points in the plane, each with distinct coordinates, and we need to construct a rooted binary tree such that each node has at most two children. The arcs, which connect parents to children, must be directed strictly downward in terms of y-coordinates. The...

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316C1 - Tidying Up

CF 316C1 - Tidying Up Rating: 2200 Tags: flows Solve time: 1m 56s Verified: yes Solution Problem Understanding We are given a rectangular dressing room divided into n × m squares, where each square contains a single shoe. Every shoe belongs to exactly one pair, and each pair is represented by a unique integer appearing exactly twice in the grid. Smart Beaver considers the room neat only if each pair...

Practice › Codeforces Solutions ›

VK Cup 2012 Finals (unofficial online-version)

VK Cup 2012 Finals (unofficial online-version) Type: Special | Problems: 5 | Verified: 1/5 | Rating range: 1500-3000 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Privatization 3000 flows, graphs 2m 20s ✗ B Polycarpus is Looking for Good Substrings 2300 bitmasks, hashing, implementation 1m 54s ✓ C Cowboys 2100 combinatorics, dp, math 1m 28s ✗ D Cutting a Fence 2500 binary-search, data-structures, dsu 1m 8s...

Practice › Codeforces Solutions ›

ABBYY Cup 3.0

ABBYY Cup 3.0 Type: Special | Problems: 12 | Verified: 6/12 | Rating range: 1100-2400 | Time: 30m 35s Problem Name Rating Tags Solve Time Verified A1 Special Task 1100 greedy 1m 30s ✗ B1 EKG 1500 brute-force, dfs-and-similar 3m 27s ✗ B2 EKG 1600 dfs-and-similar, dp 3m 21s ✗ C1 Tidying Up 2200 flows 1m 56s ✓ C2 Tidying Up 2300 flows, graph-matchings 3m 19s ✓ D2 PE Lesson...

Practice › Codeforces Solutions ›

Codeforces Round 170 (Div. 1)

Codeforces Round 170 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1400-2800 | Time: 6m 6s Problem Name Rating Tags Solve Time Verified A Learning Languages 1400 dfs-and-similar, dsu 1m 44s ✓ D Google Code Jam 2800 dp, probabilities 2m 17s ✗ E Binary Tree on Plane 2400 flows, trees 2m 5s ✗

Practice › Codeforces Solutions › VK Cup 2012 Round 3 ›

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 96 (Div. 1)

Codeforces Beta Round 96 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-2700 | Time: 9m 16s Problem Name Rating Tags Solve Time Verified A Turing Tape 1300 implementation 1m 39s ✓ B Piet 2100 implementation 1m 56s ✓ C Logo Turtle 1800 dp 1m 52s ✓ D Constants in the language of Shakespeare 2100 constructive-algorithms, dp, greedy 2m 2s ✗ E Bits of...

Practice › Codeforces Solutions › Codeforces Beta Round 96 (Div. 1) ›

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

Practice › Codeforces Solutions › Codeforces Beta Round 70 (Div. 2) ›

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

Practice › Codeforces Solutions › Codeforces Beta Round 58 ›

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

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

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

#flows

CF 491C - Deciphering

CF 1951I - Growing Trees

Testing Round 11

CF 1965F - Conference

CF 1942H - Farmer John's Favorite Intern

CF 1955H - The Most Reckless Defense

CF 457E - Flow Optimality

CF 316C2 - Tidying Up

CF 269C - Flawed Flow

Codeforces Round 165 (Div. 1)

VK Cup 2012 Round 3

CF 311E - Biologist

CF 277E - Binary Tree on Plane

CF 212A - Privatization

CF 316C1 - Tidying Up

VK Cup 2012 Finals (unofficial online-version)

ABBYY Cup 3.0

Codeforces Round 170 (Div. 1)

CF 164C - Machine Programming

Codeforces Beta Round 96 (Div. 1)

CF 132E - Bits of merry old England

CF 78E - Evacuation

CF 62E - World Evil

CF 103E - Buying Sets