meet-in-the-middle

Practice › Codeforces Solutions › Kotlin Heroes: Episode 10 ›

CF 1958I - Equal Trees

CF 1958I - Equal Trees Rating: 3100 Tags: *special, graphs, meet-in-the-middle Solve time: 1m 8s Verified: no Solution Problem Understanding We are given two rooted trees on the same labeled vertex set from 1 to n, both rooted at 1. Each tree is described by its parent array, so every node knows its immediate parent except the root. We are allowed to perform a single kind of structural operation: pick...

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

CF 490D - Chocolate

CF 490D - Chocolate Rating: 1900 Tags: brute force, dfs and similar, math, meet-in-the-middle, number theory Solve time: 5m 18s Verified: no Solution

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 273 (Div. 2) ›

CF 478E - Wavy numbers

CF 478E - Wavy numbers Rating: 2900 Tags: brute force, dfs and similar, meet-in-the-middle, sortings Solve time: 1m 37s Verified: no Solution Problem Understanding We are asked to work with a special class of integers defined purely by their digit structure. A number is called “wavy” if, whenever you look at any digit that is not at the boundary, that digit must sit either strictly above both its neighbors or...

Practice › Codeforces Solutions ›

MemSQL Start[c]UP 2.0 - Round 2

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

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

CF 457A - Golden System

CF 457A - Golden System Rating: 1700 Tags: math, meet-in-the-middle Solve time: 1m 15s Verified: yes Solution Problem Understanding In this problem, we are asked to compare two numbers written in an unusual numeral system called the golden system. Each number is represented as a string of 0s and 1s, and the value of a number is computed by interpreting it as a sum of powers of the golden ratio...

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

CF 327E - Axis Walking

CF 327E - Axis Walking Rating: 2300 Tags: bitmasks, combinatorics, constructive algorithms, dp, meet-in-the-middle Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a multiset of positive segment lengths. Any permutation of these lengths defines a walk along the number line starting from 0, where we cumulatively add each chosen segment. After each segment, we “pause” at the current position, and these pause positions are exactly the...

Practice › Codeforces Solutions › School Team Contest 3 (Winter Computer School 2010/11) ›

CF 45D - Event Dates

CF 45D - Event Dates Rating: 1900 Tags: greedy, meet-in-the-middle, sortings Solve time: 1m 35s Verified: yes Solution Problem Understanding Each event has a range of possible days when it could have happened. For the $i$-th event, any integer day between $l_i$ and $r_i$ is acceptable. We must assign exactly one day to every event, and no two events may share the same day. The task is not to count...