#meet-in-the-middle

CF 1558E - Down Below

CF 1558E - Down Below Rating: 3000 Tags: binary search, dfs and similar, graphs, greedy, meet-in-the-middle, shortest paths Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a graph of caves connected by tunnels, and a hero who starts at cave 1 with some initial power. Every other cave initially contains a monster. The hero’s task is to visit and defeat the monster in every cave at...

CF 1263C - Everyone is a Winner!

CF 1263C - Everyone is a Winner! Rating: 1400 Tags: binary search, math, meet-in-the-middle, number theory Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a fixed amount of rating points, call it $n$. A draw splits these points equally among $k$ participants, but only whole units are distributed, so each participant receives $\lfloor n / k \rfloor$ points. Any leftover points are discarded. The task is...

CF 1105E - Helping Hiasat

CF 1105E - Helping Hiasat Rating: 2200 Tags: bitmasks, brute force, dp, meet-in-the-middle Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given a timeline of events. At any moment, Hiasat’s profile has a single visible handle, and he is allowed to change this handle only at specific moments marked in the input. Between changes, the handle stays fixed. Alongside this timeline, several friends exist, each identified by...

CF 995E - Number Clicker Rating: 2700 Tags: divide and conquer, graphs, meet-in-the-middle, number theory Model: gpt-5-3-mini Solve time: 1m 18s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a3295a7-dfbc-83ec-94b8-8dde43a79130 Solution Problem Understanding We are working in a system where the state is a single number on a circular modulo ring of size $p$, where $p$ is prime. The screen always shows a value between $0$ and $p-1$. We start from an initial...

CF 1006F - Xor-Paths

CF 1006F - Xor-Paths Rating: 2100 Tags: bitmasks, brute force, dp, meet-in-the-middle Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a rectangular grid where each cell contains a non-negative integer. A path starts at the top-left cell and moves only right or down until it reaches the bottom-right cell. Every path produces a value obtained by taking the bitwise XOR of all numbers along the visited...

CF 1043D - Mysterious Crime

CF 1043D - Mysterious Crime Rating: 1700 Tags: brute force, combinatorics, math, meet-in-the-middle, two pointers Solve time: 4m 37s Verified: yes Solution Problem Understanding We are given several different observations of the same set of people, each observation being a full ordering of the same $n$ elements. Each observer saw a complete permutation, but their viewpoints are inconsistent, so the relative positions of the same element differ across permutations. The...

CF 1249C2 - Good Numbers (hard version)

CF 1249C2 - Good Numbers (hard version) Rating: 1500 Tags: binary search, greedy, math, meet-in-the-middle Solve time: 1m 37s Verified: no Solution Problem Understanding We are given several independent queries. Each query provides a large integer $n$, and we must output the smallest integer $m \ge n$ such that $m$ can be expressed as a sum of distinct powers of 3. In other words, every valid number corresponds to choosing...

CF 912E - Prime Gift

CF 912E - Prime Gift Rating: 2400 Tags: binary search, dfs and similar, math, meet-in-the-middle, number theory, two pointers Solve time: 7m 30s Verified: yes Solution Problem Understanding We are asked to enumerate a very specific set of integers and then pick a particular element from that ordered list. The allowed numbers are those whose prime factors all come from a fixed small set of given primes. In other words,...

CF 1326F1 - Wise Men (Easy Version) Rating: 2600 Tags: bitmasks, brute force, dp, meet-in-the-middle Model: gpt-5-3-mini Solve time: 1m 52s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2df639-6d24-83ec-bae5-fc7883223013 Solution Problem Understanding We are given a small undirected graph with up to 14 vertices, representing which pairs of people know each other. Each input row is a bitmask row of the adjacency matrix, so we can quickly check whether two people are...

CF 1257F - Make Them Similar

CF 1257F - Make Them Similar Rating: 2400 Tags: bitmasks, brute force, hashing, meet-in-the-middle Solve time: 7m 36s Verified: no Solution Problem Understanding We are given a fixed array of integers. We are allowed to choose a single integer x and apply it to every element using XOR. After this transformation, each original value a_i becomes b_i = a_i XOR x . The goal is not to make the resulting...

CF 1192C - Cubeword

CF 1192C - Cubeword Rating: - Tags: *special, brute force, dp, meet-in-the-middle Solve time: 7m 17s Verified: yes Solution Problem Understanding We are given a collection of strings that can be placed on the edges of a cube. Each string has length between 3 and 10, and we are allowed to use any of them repeatedly. A valid construction consists of taking a cube and assigning one string to each...

CF 1266H - Red-Blue Graph Rating: 3400 Tags: dp, graphs, math, matrices, meet-in-the-middle Model: gpt-5-3-mini Solve time: 4m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d882b-4204-83ec-8de7-91488c63d3c1 Solution Problem Understanding We are given a directed graph where every vertex except the last one has exactly two outgoing edges, one red and one blue. At any moment, each vertex is in one of two internal states, which decides which of its two edges...

CF 1221G - Graph And Numbers

CF 1221G - Graph And Numbers Rating: 2900 Tags: bitmasks, brute force, combinatorics, dp, meet-in-the-middle Solve time: 2m 26s Verified: no Solution Problem Understanding We have an undirected graph. Every vertex must be assigned either 0 or 1 . For each edge, we write the sum of the values on its two endpoints. Since endpoints are binary, every edge receives one of three possible values: 0 if both endpoints are...

Codeforces Round 603 (Div. 2)

Codeforces Round 603 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 1100-2400 | 11m 5s # Problem Rating Tags Accepted Time ✓ A Sweet Problem 1100 math 17,223 2m 33s ✓ B PIN Codes 1400 greedy, implementation 11,810 1m 40s C Everyone is a Winner! 1400 binary-search, math, meet-in-the-middle 14,661 1m 40s E Editor 2100 data-structures, implementation 2,974 3m 28s ✓ F Economic Difficulties 2400 data-structures,...

CF 1423L - Light switches

CF 1423L - Light switches Rating: 2600 Tags: meet-in-the-middle Solve time: 1m 12s Verified: yes Solution Problem Understanding We are asked to determine the minimal set of switches Nikola must flip to turn all warehouse lights off, given the state of the lights at the end of several days. Each switch flips a predefined subset of lights. Conceptually, the problem reduces to transforming a starting bitmask (lights on or off)...

CF 1536F - Omkar and Akmar

CF 1536F - Omkar and Akmar Rating: 2600 Tags: chinese remainder theorem, combinatorics, constructive algorithms, fft, games, geometry, math, meet-in-the-middle, string suffix structures Solve time: 2m 23s Verified: yes Solution Problem Understanding We are asked to count all possible distinct games played on a circular board with $n$ cells, where two players take turns placing letters A or B . Akmar moves first. A letter cannot be placed adjacent to...

CF 1569E - Playoff Restoration

CF 1569E - Playoff Restoration Rating: 2600 Tags: bitmasks, brute force, hashing, implementation, meet-in-the-middle Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a single-elimination tournament with $2^k$ teams, where $k$ ranges from 1 to 5. The matches are structured in a fixed bracket: in the first round, consecutive teams play each other, and winners advance to the next round, pairing up according to the same rule...

CF 1593F - Red-Black Number

CF 1593F - Red-Black Number Rating: 2100 Tags: dfs and similar, dp, implementation, math, meet-in-the-middle Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a number as a string of digits and two divisors, A and B. The task is to color each digit either red or black such that the number formed by the red digits is divisible by A, the number formed by the black...

CF 1601F - Two Sorts

CF 1601F - Two Sorts Rating: 3400 Tags: binary search, dfs and similar, math, meet-in-the-middle Solve time: 1m 30s Verified: yes Solution Problem Understanding We take all integers from $1$ to $n$ and sort them not by numeric value but by their string representation in lexicographic order, as if they were words. This produces a permutation $a_1, a_2, \dots, a_n$, where $a_i$ is the number that appears in the $i$-th...

CF 1609F - Interesting Sections

CF 1609F - Interesting Sections Rating: 2800 Tags: data structures, divide and conquer, meet-in-the-middle, two pointers Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a long array of non-negative integers. The task is to count how many contiguous subarrays have a specific property that depends on two extreme values inside the subarray: its minimum and its maximum. For any segment, we compute the smallest value and...

CF 1698G - Long Binary String

CF 1698G - Long Binary String Rating: 2900 Tags: bitmasks, math, matrices, meet-in-the-middle, number theory Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a small binary string s of length up to 35, and we need to manipulate a conceptual binary string t of length $10^{100}$, which is initially all zeros. The operation allowed is selecting a contiguous substring of t of the same length as...

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 1767E - Algebra Flash

CF 1767E - Algebra Flash Rating: 2500 Tags: bitmasks, brute force, dp, graphs, math, meet-in-the-middle, trees Solve time: 1m 45s Verified: yes Solution Problem Understanding We are given a linear sequence of platforms, each with a fixed color, and a cost associated with activating all platforms of each color. Initially, all platforms are deactivated. You can only jump from a platform to the next one or skip one to the...

CF 1779H - Olympic Team Building

CF 1779H - Olympic Team Building Rating: 3500 Tags: brute force, meet-in-the-middle Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a set of $n$ players, where $n$ is a power of two, and each player has a fixed positive strength. A sequence of elimination rounds is played. In each round, the current set of players is split into two equal groups. The total strength of a...

CF 1800F - Dasha and Nightmares

CF 1800F - Dasha and Nightmares Rating: 1900 Tags: bitmasks, hashing, meet-in-the-middle, strings Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given a list of words and asked to count pairs of words whose concatenation satisfies several strict properties. Specifically, a "nightmare" is formed by concatenating two words, resulting in a string of odd length, containing exactly 25 distinct letters, and having each letter occur an odd...

CF 1801F - Another n-dimensional chocolate bar

CF 1801F - Another n-dimensional chocolate bar Rating: 2700 Tags: dp, math, meet-in-the-middle, number theory Solve time: 2m 8s Verified: no Solution Problem Understanding We are given a chocolate bar in n dimensions. Along each dimension, the bar is already divided into discrete units: for dimension i, there are a_i units. Vasya wants to cut the chocolate further along these pre-existing divisions to produce at least k pieces. He can...

CF 1836E - Twin Clusters

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

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

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

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

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

CF 1982E - Number of k-good subarrays

CF 1982E - Number of k-good subarrays Rating: 2300 Tags: bitmasks, brute force, combinatorics, divide and conquer, dp, math, meet-in-the-middle Solve time: 3m 13s Verified: no Solution Problem Understanding In this problem, we are given an array consisting of consecutive integers starting from zero. A subarray is considered k-good if every element within it has no more than k ones in its binary representation. Our task is to count all...

CF 2002G - Lattice Optimizing

CF 2002G - Lattice Optimizing Rating: 3400 Tags: bitmasks, brute force, hashing, meet-in-the-middle Solve time: 39s Verified: no Solution Exploration The problem asks only for existence or nonexistence in three classes. For part (1), it suffices to exhibit a tetrahedron that tiles space by congruent copies. For part (2), we must decide whether a congruent tiling by equifacial tetrahedra exists. An equifacial tetrahedron is a disphenoid, that is, a tetrahedron...

CF 2155F - Juan's Colorful Tree

CF 2155F - Juan's Colorful Tree Rating: 2800 Tags: data structures, dfs and similar, dsu, graphs, meet-in-the-middle, trees Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a tree with n nodes, where each node contains a set of colors drawn from a palette of size k . Each node's set may be different, and the total number of color assignments across all nodes is s ....

CF 2159E - Super-Short-Polynomial-San

CF 2159E - Super-Short-Polynomial-San Rating: 3500 Tags: math, meet-in-the-middle Solve time: 2m 18s Verified: no Solution Problem Understanding We are given a quadratic polynomial in one variable, and we repeatedly raise it to a power that changes per query. From the expanded form of this power, we are not asked for a single coefficient, but for a cumulative quantity: the total contribution of all coefficients from degree 0 up to...

CF 490D - Chocolate

CF 490D - Chocolate Rating: 1900 Tags: brute force, dfs and similar, math, meet-in-the-middle, number theory Solve time: 1m 25s Verified: yes Solution Problem Understanding Each chocolate bar is a rectangle made of unit squares, so its “value” is just its area. We start with two rectangles and we are allowed to modify them minute by minute. In one minute we pick exactly one bar and reduce its area by...

CF 327E - Axis Walking

CF 327E - Axis Walking Rating: 2300 Tags: bitmasks, combinatorics, constructive algorithms, dp, meet-in-the-middle Solve time: 2m 25s Verified: yes Solution Problem Understanding We have n positive segment lengths. Their total sum is d , which is also the destination point on the number line. A route is simply an ordering of these lengths. While following a route, we keep a running prefix sum. After taking the first segment we...

CF 285D - Permutation Sum

CF 285D - Permutation Sum Rating: 1900 Tags: bitmasks, combinatorics, dp, implementation, meet-in-the-middle Solve time: 2m 10s Verified: no Solution Problem Understanding We are asked to count pairs of permutations (a, b) of length n such that their modular sum produces another valid permutation c . For each index i , c[i] = ((a[i]-1 + b[i]-1) mod n) + 1 . This is a bijective operation, meaning every element of...

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

MemSQL Start[c]UP 2.0 - Round 2

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

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

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

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

School Team Contest 3 (Winter Computer School 2010/11)

School Team Contest 3 (Winter Computer School 2010/11) Special | 10 problems | 7/10 verified | Difficulty 900-2500 | 19m 28s # Problem Rating Tags Accepted Time ✓ A Codecraft III 900 implementation 8,108 1m 14s ✓ B School 2200 dp, dsu 319 2m 6s ✓ C Dancing Lessons 1900 data-structures 1,147 1m 24s ✓ D Event Dates 1900 greedy, meet-in-the-middle, sortings 1,973 1m 35s ✓ E Director 2000 constructive-algorithms,...

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