graph-matchings

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 › Educational Codeforces Round 163 (Rated for Div. 2) ›

CF 1948G - MST with Matching

CF 1948G - MST with Matching Rating: 3100 Tags: bitmasks, brute force, dsu, graph matchings, trees Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a connected undirected weighted graph with at most 20 vertices. We must choose a spanning tree. The cost of that tree has two parts. The first part is standard, the sum of the chosen edge weights. The second part depends on the...

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 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 › Codeforces Round 268 (Div. 1) ›

CF 468E - Permanent

CF 468E - Permanent Rating: 3100 Tags: dp, graph matchings, math, meet-in-the-middle Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to compute the permanent of a large square matrix where almost every element is 1, and only a small number of entries are different. The permanent is similar to a determinant but without alternating signs: it is the sum over all permutations of the product of...

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

CF 468D - Tree

CF 468D - Tree Rating: 3100 Tags: graph matchings Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a tree with n nodes, where each edge has a positive length. A tree guarantees that there is exactly one simple path between any two nodes. The task is to assign the numbers 1 through n to the nodes, forming a permutation, in a way that maximizes the sum...

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

CF 468B - Two Sets

CF 468B - Two Sets Rating: 2000 Tags: 2-sat, dfs and similar, dsu, graph matchings, greedy Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a set of n distinct integers. Every number must be assigned to one of two groups. If a number x is placed into group A , then its complement with respect to a , namely a - x , must also be...

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 › April Fools Day Contest 2013 ›

CF 290C - WTF?

CF 290C - WTF? Rating: 1700 Tags: *special, graph matchings, implementation, trees Solve time: 1m 31s Verified: yes Solution Problem Understanding The statement is written as a LOLCODE program. The actual task is to understand what this program computes. The input is a sequence of digits between 0 and 9 , one per line. The program repeatedly reads numbers until it encounters 0 . During the process it maintains four...

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

CF 167D - Wizards and Roads

CF 167D - Wizards and Roads Rating: 3000 Tags: data structures, divide and conquer, graph matchings, graphs, greedy Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a set of cities on the plane. Every city has a unique x coordinate and a unique y coordinate. The first k cities are given explicitly, and the remaining cities are generated by two linear recurrences. For every query interval...

Practice › Codeforces Solutions › Codeforces Round 163 (Div. 2) ›

CF 266B - Queue at the School

CF 266B - Queue at the School Rating: 800 Tags: constructive algorithms, graph matchings, implementation, shortest paths Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a queue made of boys and girls, represented as a string containing only B and G . Every second, each adjacent pair "BG" swaps positions and becomes "GB" . The swaps happen simultaneously. That detail matters a lot. If a boy...

Practice › Codeforces Solutions › Codeforces Round 113 (Div. 2) ›

CF 166D - Shoe Store

CF 166D - Shoe Store Rating: 2500 Tags: dp, graph matchings, greedy, sortings, two pointers Solve time: 2m 34s Verified: yes Solution Problem Understanding We have a collection of shoes, where every shoe has a unique size and a price. We also have customers, where each customer has a budget and a foot size. A customer can buy a shoe only if two conditions hold. The first condition is financial:...

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 ›

April Fools Day Contest 2013

April Fools Day Contest 2013 Type: April Fools | Problems: 4 | Verified: 3/4 | Rating range: 1400-2800 | Time: 6m 44s Problem Name Rating Tags Solve Time Verified C WTF? 1700 *special, graph-matchings, implementation 1m 31s ✓ D Orange 1400 *special, implementation 2m 11s ✗ E HQ 2500 *special, constructive-algorithms 1m 43s ✓ F Greedy Petya 2800 *special, dfs-and-similar, graphs 1m 19s ✓

Practice › Codeforces Solutions ›

Codeforces Round 163 (Div. 2)

Codeforces Round 163 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 2/4 | Rating range: 800-2500 | Time: 8m 10s Problem Name Rating Tags Solve Time Verified B Queue at the School 800 constructive-algorithms, graph-matchings, implementation 1m 21s ✓ C Below the Diagonal 2100 constructive-algorithms, greedy, math 2m 17s ✗ D BerDonalds 2400 graphs, math, shortest-paths 2m 9s ✗ E More Queries to Array... 2500 data-structures, math 2m...

Practice › Codeforces Solutions › Codeforces Alpha Round 21 (Codeforces format) ›

CF 21D - Traveling Graph

CF 21D - Traveling Graph Rating: 2400 Tags: bitmasks, graph matchings, graphs Solve time: 42s Verified: yes Solution Problem Understanding We are given a weighted undirected graph with up to 15 vertices and up to 2000 edges. Each edge has a positive weight, and there may be multiple edges connecting the same pair of vertices or edges that loop back to the same vertex. The task is to find the...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86B - Tetris revisited

CF 86B - Tetris revisited Rating: 2200 Tags: constructive algorithms, graph matchings, greedy, math Solve time: 2m 5s Verified: yes Solution Problem Understanding We have a rectangular board where some cells are already blocked by # and the remaining cells . must be covered by polyominoes. The allowed pieces are extremely flexible: any connected shape consisting of 2, 3, 4, or 5 cells may be used, with arbitrary rotations and...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Round 2

Yandex.Algorithm 2011: Round 2 Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1600-2700 | Time: 11m 50s Problem Name Rating Tags Solve Time Verified A Reflection 1600 math 2m 9s ✓ B Tetris revisited 2200 constructive-algorithms, graph-matchings, greedy 2m 5s ✓ C Genetic engineering 2500 dp, string-suffix-structures, trees 2m 12s ✓ D Powerful array 2200 data-structures, implementation, math 3m 46s ✓ E Long sequence 2700 brute-force, math,...

Practice › Codeforces Solutions › School Regional Team Contest, Saratov, 2011 ›

CF 120H - Brevity is Soul of Wit

CF 120H - Brevity is Soul of Wit Rating: 1800 Tags: graph matchings Solve time: 2m 33s Verified: no Solution Problem Understanding We are given up to 200 distinct lowercase words. For every word, we must choose a short abbreviation whose length is between 1 and 4 characters, and whose characters appear in the original word in the same order. The characters do not need to be adjacent, so every...

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

#graph-matchings

Testing Round 11

CF 1948G - MST with Matching

CF 491C - Deciphering

CF 1955H - The Most Reckless Defense

CF 468E - Permanent

CF 468D - Tree

CF 468B - Two Sets

ABBYY Cup 3.0

CF 290C - WTF?

CF 167D - Wizards and Roads

CF 266B - Queue at the School

CF 166D - Shoe Store

CF 316C2 - Tidying Up

April Fools Day Contest 2013

Codeforces Round 163 (Div. 2)

CF 21D - Traveling Graph

CF 86B - Tetris revisited

Yandex.Algorithm 2011: Round 2

CF 120H - Brevity is Soul of Wit

CF 103E - Buying Sets