#bitmasks

CF 1552D - Array Differentiation

CF 1552D - Array Differentiation Rating: 1800 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dp, graphs, math Solve time: 5m 22s Verified: no Solution Problem Understanding We are given a list of integers, and we want to decide whether it is possible to assign another list of the same length, say $b_1, b_2, \dots, b_n$, such that every given number $a_i$ can be expressed as a difference between...

CF 1360F - Spy-string

CF 1360F - Spy-string Rating: 1700 Tags: bitmasks, brute force, constructive algorithms, dp, hashing, strings Solve time: 1m 13s Verified: no Solution Problem Understanding We are given several strings of equal length, and we want to construct a new string of the same length. The requirement is that this constructed string must be extremely close to every given string: for each input string, it is allowed to differ from our...

CF 1305G - Kuroni and Antihype

CF 1305G - Kuroni and Antihype Rating: 3500 Tags: bitmasks, brute force, dp, dsu, graphs Solve time: 3m 16s Verified: no Solution Problem Understanding We are given a group of people, each with an associated integer value that can be interpreted as a bitmask. These people can form a network by joining a system where actions produce profit: once someone has joined, they can “invite” a person who has not...

CF 1242C - Sum Balance

CF 1242C - Sum Balance Rating: 2400 Tags: bitmasks, dfs and similar, dp, graphs Solve time: 1m 43s Verified: no Solution Problem Understanding We are given several containers, each holding a multiset of distinct integers. A single operation is performed exactly once: from every container, we must pick exactly one value, and then redistribute those chosen values back into the containers so that each container still ends up with the...

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 1103D - Professional layer

CF 1103D - Professional layer Rating: 3100 Tags: bitmasks, dp Solve time: 1m 56s Verified: yes Solution Problem Understanding We are given a collection of judges. Each judge contributes two values: a number $a_i$, which controls how “resistant” their opinion is, and a cost parameter $e_i$, which is the time cost if we decide to interact with that judge. We may choose to play with a judge at most once....

CF 960C - Subsequence Counting Rating: 1700 Tags: bitmasks, constructive algorithms, greedy, implementation Model: gpt-5-3-mini Solve time: 4m 22s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a069-6ac8-83ec-b946-bc1675dc98b7 Solution Problem Understanding We are given two numbers: a target count of subsequences and a threshold value. We must construct an integer array such that when we look at all its non-empty subsequences and keep only those subsequences whose maximum minus minimum is strictly less...

CF 1234F - Yet Another Substring Reverse Rating: 2200 Tags: bitmasks, dp Model: gpt-5-3-mini Solve time: 1m 11s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a338620-5650-83ec-b987-01e3ce728cd8 Solution Problem Understanding We are given a string built from a very small alphabet, only the first twenty lowercase letters. The task is to locate a contiguous segment inside the string such that all characters inside that segment are distinct. We are interested in the maximum...

CF 959F - Mahmoud and Ehab and yet another xor task Rating: 2400 Tags: bitmasks, dp, math, matrices Model: gpt-5-3-mini Solve time: 1m 11s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a339f5b-7da0-83ec-9af1-078177c4b240 Solution Problem Understanding We are given an array of integers where each value is treated as a 20-bit number. For every query, we look only at a prefix of the array, specifically the first $l$ elements, and we must count...

CF 981D - Bookshelves Rating: 1900 Tags: bitmasks, dp, greedy Model: gpt-5-3-mini Solve time: 1m 10s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a5e2-81c8-83ec-803d-4377b87d6ef6 Solution Problem Understanding We are given a sequence of positive integers representing books arranged in a fixed order. Each book has a value, and we must split this sequence into exactly k contiguous segments. Each segment corresponds to one bookshelf, and the value of a bookshelf is the...

CF 1042B - Vitamins Rating: 1200 Tags: bitmasks, brute force, dp, implementation Model: gpt-5-5 Solve time: 5m 6s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bcc3-88bc-83ec-9157-fb55c8978ed7 Solution Problem Understanding We are given a collection of juice options, where each option has a cost and a set of vitamins it provides. There are only three vitamins in total, labeled A, B, and C. When Petya buys a set of juices, he effectively takes...

CF 986C - AND Graph Rating: 2500 Tags: bitmasks, dfs and similar, dsu, graphs Model: gpt-5-5 Solve time: 1m 5s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33779d-a8a4-83ec-af71-7ea6e697c632 Solution Problem Understanding We are given a collection of distinct integers, each of which can be viewed as an n-bit mask. We build a graph whose vertices are these numbers, and we connect two vertices whenever their bitwise AND is zero. In other words,...

CF 900D - Unusual Sequences Rating: 2000 Tags: bitmasks, combinatorics, dp, math, number theory Model: gpt-5-3-mini Solve time: 1m 11s Verified: yes (1/1 samples) Solution Problem Understanding We are asked to count how many sequences of positive integers of a fixed length produce a specific greatest common divisor while also satisfying an additional constraint involving their sum. A cleaner way to view the problem is to think in terms of...

CF 938G - Shortest Path Queries Rating: 2900 Tags: bitmasks, data structures, dsu, graphs Model: gpt-5-3-mini Solve time: 2m 21s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32799a-0180-83ec-8ea1-490a97920b8d Solution Problem Understanding We are maintaining a graph whose edges carry integer weights, but distance is not defined in the usual additive sense. Instead, when you walk along a path, the cost of that path is the bitwise XOR of all edge weights along...

CF 938F - Erasing Substrings

CF 938F - Erasing Substrings Rating: 2700 Tags: bitmasks, dp, greedy Solve time: 2m 34s Verified: no Solution Problem Understanding We start with a single string of lowercase letters and repeatedly perform a sequence of destructive operations. In the i-th operation, we are forced to delete a contiguous block whose length is fixed to be $2i - 1$, but we are free to choose where that block lies in the...

Educational Codeforces Round 38 (Rated for Div. 2)

Educational Codeforces Round 38 (Rated for Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 800-2700 | 6m 30s # Problem Rating Tags Accepted Time ✓ A Word Correction 800 implementation 12,042 1m 21s B Run For Your Prize 1100 brute-force, greedy 9,303 1m 10s ✓ E Max History 2300 combinatorics, math 1,555 1m 25s F Erasing Substrings 2700 bitmasks, dp, greedy 613 2m 34s

CF 959E - Mahmoud and Ehab and the xor-MST

CF 959E - Mahmoud and Ehab and the xor-MST Rating: 1900 Tags: bitmasks, dp, graphs, implementation, math Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given a complete graph on vertices labeled from 0 to n − 1. Every pair of distinct vertices is connected, and the weight of the edge between u and v is the bitwise XOR of their labels. The task is to compute...

Codeforces Round 473 (Div. 2)

Codeforces Round 473 (Div. 2) Div. 2 | 3 problems | 3/3 verified | Difficulty 800-1900 | 4m 23s # Problem Rating Tags Accepted Time ✓ A Mahmoud and Ehab and the even-odd game 800 games, math 55,647 58s ✓ C Mahmoud and Ehab and the wrong algorithm 1500 constructive-algorithms, trees 6,207 1m 13s ✓ E Mahmoud and Ehab and the xor-MST 1900 bitmasks, dp, graphs 3,765 2m 12s ✓

Educational Codeforces Round 41 (Rated for Div. 2)

Educational Codeforces Round 41 (Rated for Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 900-2700 | 4m 42s # Problem Rating Tags Accepted Time ✓ A Tetris 900 implementation 10,850 1m 9s ✓ C Chessboard 1400 bitmasks, brute-force, implementation 5,636 1m 22s ✓ F k-substrings 2700 binary-search, hashing, string-suffix-structures 946 1m 46s G Partitions 2700 combinatorics, math, number-theory 1,611 25s

CF 961C - Chessboard

CF 961C - Chessboard Rating: 1400 Tags: bitmasks, brute force, implementation Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given four separate square fragments of a chessboard, each fragment being an $n \times n$ grid where every cell is already colored either black or white. The value $n$ is odd, and the goal is to assemble these four pieces into a larger $2n \times 2n$ chessboard. We...

Codeforces Round 482 (Div. 2)

Codeforces Round 482 (Div. 2) Div. 2 | 5 problems | 2/5 verified | Difficulty 1000-2400 | 8m 57s # Problem Rating Tags Accepted Time ✓ A Pizza, Pizza, Pizza!!! 1000 math 14,574 1m 6s ✓ B Treasure Hunt 1800 greedy 4,779 1m 14s ✓ C Kuro and Walking Route 1600 dfs-and-similar, trees 7,333 2m 52s D Kuro and GCD and XOR and SUM 2200 binary-search, bitmasks, brute-force 2,176 1m...

CF 979D - Kuro and GCD and XOR and SUM

CF 979D - Kuro and GCD and XOR and SUM Rating: 2200 Tags: binary search, bitmasks, brute force, data structures, dp, dsu, greedy, math, number theory, strings, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are maintaining a dynamic multiset of positive integers. The structure supports insertions, and after each insertion phase we may receive queries asking us to pick one previously inserted value that satisfies three...

Avito Code Challenge 2018

Avito Code Challenge 2018 Special | 4 problems | 3/4 verified | Difficulty 900-3100 | 7m 46s # Problem Rating Tags Accepted Time ✓ A Antipalindrome 900 brute-force, implementation, strings 10,327 1m 8s ✓ C Useful Decomposition 1400 implementation, trees 6,856 2m 15s ✓ E Addition on Segments 2200 bitmasks, data-structures, divide-and-conquer 2,535 2m 22s ✓ H K Paths 3100 combinatorics, data-structures, dp 288 2m 1s

CF 981E - Addition on Segments

CF 981E - Addition on Segments Rating: 2200 Tags: bitmasks, data structures, divide and conquer, dp Solve time: 2m 22s Verified: yes Solution Problem Understanding We start with an array of length $n$ filled with zeros. There are $q$ operations, each operation adds a positive value $x_i$ to every position in a contiguous segment $[l_i, r_i]$. We are not forced to apply all operations. Instead, we may choose any subset...

Codeforces Round 488 by NEAR (Div. 1)

Codeforces Round 488 by NEAR (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1900-3200 | 15m 27s # Problem Rating Tags Accepted Time ✓ B Open Communication 1900 bitmasks, brute-force 2,052 4m 46s ✓ C Careful Maneuvering 2100 bitmasks, brute-force, geometry 1,808 2m 3s ✓ D Compute Power 2500 binary-search, dp, greedy 835 1m 45s E Nikita and Order Statistics 2300 chinese-remainder-theorem, fft, math 1,785 1m...

CF 993B - Open Communication

CF 993B - Open Communication Rating: 1900 Tags: bitmasks, brute force Solve time: 4m 46s Verified: yes Solution Problem Understanding Two people each receive a secret pair of distinct digits from 1 to 9. The two hidden pairs are linked by a single property: they share exactly one common number. You are not given the hidden pairs directly. Instead, each person sends a small list of candidate pairs that includes...

CF 993C - Careful Maneuvering

CF 993C - Careful Maneuvering Rating: 2100 Tags: bitmasks, brute force, geometry Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given two sets of enemy ships, all lying on two vertical lines: one group is fixed at $x=-100$, the other at $x=100$. Each ship has an integer $y$-coordinate, and multiple ships may share the same $y$. We are allowed to place two friendly ships anywhere on the...

CF 1004F - Sonya and Bitwise OR

CF 1004F - Sonya and Bitwise OR Rating: 2600 Tags: bitmasks, data structures, divide and conquer Solve time: 2m 39s Verified: no Solution Problem Understanding We are given an array that changes over time and we must repeatedly answer queries about subarrays inside a given segment. For any segment $[l, r]$, we consider every contiguous subarray $[L, R]$ fully contained inside it. For each such subarray, we compute the bitwise...

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

Codeforces Round 497 (Div. 1)

Codeforces Round 497 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1300-3400 | 11m 58s # Problem Rating Tags Accepted Time ✓ A Reorder the Array 1300 combinatorics, data-structures, math 13,066 3m 11s ✓ B Pave the Parallelepiped 2400 bitmasks, brute-force, combinatorics 1,037 2m 4s ✓ C Guess two numbers 3000 binary-search, interactive 527 2m 36s D Ants 3200 2-sat, data-structures, trees 322 2m 5s ✓...

CF 1007B - Pave the Parallelepiped

CF 1007B - Pave the Parallelepiped Rating: 2400 Tags: bitmasks, brute force, combinatorics, math, number theory Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a fixed rectangular box with side lengths $A, B, C$. We want to count how many different triples $(a,b,c)$, ordered so that $a \le b \le c$, can serve as a building block such that copies of this smaller box can exactly...

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 1016G - Appropriate Team

CF 1016G - Appropriate Team Rating: 2700 Tags: bitmasks, math, number theory Solve time: 3m 12s Verified: no Solution Problem Understanding We are given a list of candidate values, and we want to count how many ordered pairs of candidates can simultaneously support a hidden integer value $v$ under two arithmetic constraints involving gcd and lcm with fixed constants $X$ and $Y$. For a chosen pair of indices $(i, j)$,...

Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)

Codeforces Round 502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) Div. 1+2 | 8 problems | 6/8 verified | Difficulty 800-3300 | 18m 34s # Problem Rating Tags Accepted Time ✓ A The Rank 800 implementation 21,583 1m 30s ✓ B The Bits 1200 implementation, math 9,623 1m 47s ✓ C The Phone Number 1600 constructive-algorithms, greedy 6,470 1m 29s ✓ D The Wu 1900 bitmasks, brute-force,...

CF 1017D - The Wu

CF 1017D - The Wu Rating: 1900 Tags: bitmasks, brute force, data structures Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a collection of binary strings, all of the same fixed length $n \le 12$. Each string in this collection appears with multiplicity, so duplicates matter. Alongside this, every position $i$ has a non-negative weight $w_i$. When comparing two binary strings $s$ and $t$, we only...

CF 1027G - X-mouse in the Campus

CF 1027G - X-mouse in the Campus Rating: 2600 Tags: bitmasks, math, number theory Solve time: 5m 3s Verified: yes Solution Problem Understanding We are given a system of rooms labeled from 0 to $m-1$. A token, called the x-mouse, starts in an unknown room and evolves deterministically: if it is in room $i$, after one second it moves to $i \cdot x \bmod m$. We are allowed to place...

Technocup 2019 - Elimination Round 1

Technocup 2019 - Elimination Round 1 Special | 7 problems | 4/7 verified | Difficulty 800-2900 | 30m 17s # Problem Rating Tags Accepted Time ✓ A In Search of an Easy Problem 800 implementation 171,367 3m 6s ✓ B Vasya and Cornfield 1100 geometry 13,225 5m 15s ✓ C Vasya and Golden Ticket 1300 implementation 9,923 3m 44s ✓ D Vasya and Triangle 1800 geometry, number-theory 6,253 4m 52s...

CF 1030E - Vasya and Good Sequences

CF 1030E - Vasya and Good Sequences Rating: 2000 Tags: bitmasks, dp Solve time: 4m 57s Verified: no Solution Problem Understanding We are given an array of integers, and we need to count how many contiguous subarrays have a special property. A subarray is considered valid if we can “rearrange bits inside each number independently” by swapping any two bits in its binary representation any number of times, and after...

CF 1033F - Boolean Computer

CF 1033F - Boolean Computer Rating: 2800 Tags: bitmasks, brute force, fft, math Solve time: 15m 35s Verified: no Solution Problem Understanding We are given a collection of up to 30,000 integers, each representable in at most 12 bits. Alongside this, we are given many “bitwise machines”, where each machine defines a transformation from two input numbers into one output number. The transformation works bit by bit: for every bit...

CF 1034E - Little C Loves 3 III

CF 1034E - Little C Loves 3 III Rating: 3200 Tags: bitmasks, dp, math Solve time: 6m 38s Verified: yes Solution Problem Understanding We are given two arrays indexed by bitmasks of length n , so each index represents a subset of an n -element universe encoded as a binary number from 0 to 2^n - 1 . For each mask i , we need to compute a value c[i]...

CF 1036G - Sources and Sinks

CF 1036G - Sources and Sinks Rating: 2700 Tags: bitmasks, brute force, dfs and similar Solve time: 5m 32s Verified: yes Solution Problem Understanding We start with a directed acyclic graph. Some vertices have no incoming edges, these are called sources, and some have no outgoing edges, these are sinks. The graph is guaranteed to have the same number of sources and sinks, and this number is at most 20....

Codeforces Round 737 (Div. 2)

Codeforces Round 737 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2800 | 19m 9s # Problem Rating Tags Accepted Time ✓ A Ezzat and Two Subsequences 800 brute-force, math, sortings 29,144 3m 16s ✓ B Moamen and k-subarrays 1100 greedy, sortings 24,608 3m 16s ✓ C Moamen and XOR 1700 bitmasks, combinatorics, dp 10,496 5m 29s ✓ D Ezzat and Grid 2200 data-structures, dp, greedy...

Codeforces Round 730 (Div. 2)

Codeforces Round 730 (Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 900-2700 | 32m 37s # Problem Rating Tags Accepted Time ✓ A Exciting Bets 900 greedy, math, number-theory 40,917 8m 6s ✓ B Customising the Track 900 combinatorics, greedy, math 24,475 4m 35s ✓ C Need for Pink Slips 1900 bitmasks, brute-force, dfs-and-similar 5,625 6m 31s D1 RPD and Rap Sheet (Easy Version) 1700 bitmasks,...

CF 1038E - Maximum Matching

CF 1038E - Maximum Matching Rating: 2400 Tags: bitmasks, brute force, dfs and similar, dp, graphs Solve time: 4m 42s Verified: yes Solution Problem Understanding Each block can be viewed as a weighted undirected edge between two colors, where each endpoint is one of two possible colors depending on orientation. Choosing an orientation is equivalent to deciding a direction for that edge in a path, because once we fix an...

CF 1043F - Make It One

CF 1043F - Make It One Rating: 2500 Tags: bitmasks, combinatorics, dp, math, number theory, shortest paths Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a multiset of positive integers, and we are allowed to choose any subset of these numbers. For a chosen subset, we compute the greatest common divisor of all selected elements. The goal is not to maximize this gcd, but instead to...

CF 1725F - Field Photography

CF 1725F - Field Photography Rating: 2100 Tags: bitmasks, data structures, sortings Solve time: 2m 55s Verified: no Solution Problem Understanding Each row initially contains a contiguous block of contestants placed on an extremely large integer line of columns. Row $i$ occupies every position from $L_i$ to $R_i$, so geometrically each row is just a closed interval. We are allowed to shift an entire row left or right by any...

CF 1560F2 - Nearest Beautiful Number (hard version)

CF 1560F2 - Nearest Beautiful Number (hard version) Rating: 2100 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dp, greedy Solve time: 1m 43s Verified: no Solution Problem Understanding We are asked to construct, for each query, the smallest integer that is at least a given number n , under a digit-restriction constraint. The constraint is that the resulting number may use at most k distinct decimal digits in...

CF 1554C - Mikasa

CF 1554C - Mikasa Rating: 1800 Tags: binary search, bitmasks, greedy, implementation Solve time: 3m 44s Verified: no Solution Problem Understanding We are given a fixed integer n and a range of integers 0, 1, 2, ..., m . Each number in this range is XORed with n , producing a set of values. From this resulting set, we want the smallest non-negative integer that does not appear. A useful...

CF 1543D1 - RPD and Rap Sheet (Easy Version)

CF 1543D1 - RPD and Rap Sheet (Easy Version) Rating: 1700 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 6m 17s Verified: no Solution Problem Understanding We are playing an interactive game with a hidden number that always stays in the range from 0 to n − 1. We repeatedly submit guesses. If a guess is correct, the interaction ends immediately. If the guess is incorrect, the system does not...

CF 1391D - 505

CF 1391D - 505 Rating: 2000 Tags: bitmasks, brute force, constructive algorithms, dp, greedy, implementation Solve time: 7m 33s Verified: yes Solution Problem Understanding We are given a binary grid and we are allowed to flip cells from 0 to 1 or 1 to 0. The goal is to transform the grid so that every square submatrix whose side length is even contains an odd number of ones. The condition...

CF 1385D - a-Good String

CF 1385D - a-Good String Rating: 1500 Tags: bitmasks, brute force, divide and conquer, dp, implementation Solve time: 8m 44s Verified: no Solution Problem Understanding The task is to transform a given string into a very specific recursively defined structure centered around the letter 'a' . The structure is not arbitrary: every string is evaluated as being “good” for a given character c , where either the string is a...

CF 1383C - String Transformation 2

CF 1383C - String Transformation 2 Rating: 3100 Tags: bitmasks, dp, graphs, trees Solve time: 4m 49s Verified: no Solution Problem Understanding We are given two strings of equal length, built from a small alphabet of 20 letters. We start with string A and want to transform it into string B using a specific operation. One operation works like this: pick a letter x. Look at all positions in A...

CF 1365G - Secure Password

CF 1365G - Secure Password Rating: 2800 Tags: bitmasks, combinatorics, constructive algorithms, interactive, math Solve time: 2m 3s Verified: no Solution Problem Understanding We are given an unknown array of non-negative integers, each up to 64-bit range. We cannot see the array directly. Instead, we can query any subset of indices, and the judge returns the bitwise OR of the elements at those positions. From this hidden array, a second...

CF 1364E - X-OR

CF 1364E - X-OR Rating: 2700 Tags: bitmasks, constructive algorithms, divide and conquer, interactive, probabilities Solve time: 3m 40s Verified: no Solution Problem Understanding We are given a hidden arrangement of the numbers from 0 to n−1 placed at indices 1 through n. The only way to gain information is to choose two different positions and receive the bitwise OR of the values stored at those positions. The task is...

Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!

Codeforces Round 647 (Div. 2) - Thanks, Algo Muse! Div. 2 | 3 problems | 2/3 verified | Difficulty 1000-1400 | 13m 41s # Problem Rating Tags Accepted Time ✓ A Johnny and Ancient Computer 1000 implementation 34,050 3m 46s ✓ B Johnny and His Hobbies 1200 bitmasks, brute-force 21,033 2m 2s ✓ C Johnny and Another Rating Drop 1400 bitmasks, greedy, math 23,690 7m 53s

CF 1362C - Johnny and Another Rating Drop

CF 1362C - Johnny and Another Rating Drop Rating: 1400 Tags: bitmasks, greedy, math Solve time: 7m 53s Verified: no Solution Problem Understanding We are given a sequence that always contains consecutive integers starting from 0 up to some number n. Each number is viewed in binary, and all numbers are conceptually padded with leading zeros so they share the same bit length. For every adjacent pair in this sequence,...

CF 1361C - Johnny and Megan's Necklace

CF 1361C - Johnny and Megan's Necklace Rating: 2500 Tags: binary search, bitmasks, constructive algorithms, dfs and similar, dsu, graphs Solve time: 6m 34s Verified: no Solution Problem Understanding Each input item is a small “edge gadget” consisting of two pearls, and each pearl has an integer color in the range $[0, 2^{20})$. The goal is to take all these $n$ gadgets and connect their endpoints into one single cycle...

Codeforces Round 637 (Div. 1) - Thanks, Ivan Belonogov!

Codeforces Round 637 (Div. 1) - Thanks, Ivan Belonogov! Div. 1 | 3 problems | 0/3 verified | Difficulty 1500-2400 | 17m 38s # Problem Rating Tags Accepted Time ✓ A Nastya and Strange Generator 1500 brute-force, data-structures, greedy 13,691 6m 43s B Nastya and Scoreboard 1700 bitmasks, dp, graphs 8,310 5m 26s C Nastya and Unexpected Guest 2400 dfs-and-similar, dp, graphs 2,416 5m 29s

CF 1338C - Perfect Triples

CF 1338C - Perfect Triples Rating: 2200 Tags: bitmasks, brute force, constructive algorithms, divide and conquer, math Solve time: 6m 54s Verified: no Solution Problem Understanding We are building an infinite sequence by repeatedly selecting groups of three unused positive integers. Each group must satisfy a strict bitwise condition: the XOR of the three numbers is zero. Among all valid unused triples, we always pick the lexicographically smallest one, append...

Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!

Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov! Div. 1 | 5 problems | 2/5 verified | Difficulty 1700-3300 | 23m 52s # Problem Rating Tags Accepted Time ✓ A Dreamoon Likes Coloring 1800 constructive-algorithms, greedy, implementation 9,669 5m 5s B Dreamoon Likes Sequences 1700 bitmasks, combinatorics, math 7,056 6m 56s ✓ C Drazil Likes Heap 2400 constructive-algorithms, data-structures, greedy 1,804 5m 42s D Dreamoon Likes Strings 3100...

CF 1329B - Dreamoon Likes Sequences

CF 1329B - Dreamoon Likes Sequences Rating: 1700 Tags: bitmasks, combinatorics, math Solve time: 6m 56s Verified: yes Solution Problem Understanding We are asked to count how many strictly increasing sequences of integers we can choose from the range $[1, d]$, with an extra constraint that depends on cumulative XORs of the chosen values. Concretely, we pick a non-empty increasing sequence $a_1 < a_2 < \dots < a_n$, all within...

CF 1327F - AND Segments

CF 1327F - AND Segments Rating: 2500 Tags: bitmasks, combinatorics, data structures, dp, two pointers Solve time: 3m 17s Verified: no Solution Problem Understanding We are building an array of length $n$, where each position stores an integer with at most $k$ bits. On top of that, we are given several constraints, each describing a segment $[l, r]$ and a required value for the bitwise AND of all elements in...

Educational Codeforces Round 83 (Rated for Div. 2)

Educational Codeforces Round 83 (Rated for Div. 2) Div. 2 | 4 problems | 0/4 verified | Difficulty 1000-2600 | 9m 40s # Problem Rating Tags Accepted Time ✓ B Bogosort 1000 constructive-algorithms, sortings 39,027 4m 47s C Adding Powers 1400 bitmasks, greedy, implementation 18,342 1m 8s D Count the Arrays 1700 combinatorics, math 10,525 2m 54s G Autocompletion 2600 data-structures, dfs-and-similar, dp 1,081 51s

CF 1303D - Fill The Bag

CF 1303D - Fill The Bag Rating: 1900 Tags: bitmasks, greedy Solve time: 6m 48s Verified: yes Solution Problem Understanding We are given a target amount of space, and a collection of available blocks whose sizes are powers of two. The task is to decide whether we can exactly compose the target size using these blocks, and if not, report impossibility. If it is possible, we want to minimize how...

AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred) Div. 1 | 8 problems | 2/8 verified | Difficulty - | 41m 23s # Problem Rating Tags Accepted Time ✓ A Nash equilibrium 299 6m 35s B DAG constructive-algorithms 156 2m 50s C Segment tree or Fenwick? data-structures 388 1m 46s ✓ E Amazing bitset 51 9m 19s F Keep talking and nobody explodes -- easy bitmasks, brute-force, expression-parsing...

CF 1302F - Keep talking and nobody explodes -- easy

CF 1302F - Keep talking and nobody explodes -- easy Rating: - Tags: bitmasks, brute force, expression parsing Solve time: 6m 46s Verified: no Solution Problem Understanding We are given a 5-digit lock state. Each digit behaves like a circular counter from 0 to 9, so increasing a digit by 1 means moving to the next digit and wrapping 9 back to 0. The process consists of a fixed sequence...

CF 1285D - Dr. Evil Underscores

CF 1285D - Dr. Evil Underscores Rating: 1900 Tags: bitmasks, brute force, dfs and similar, divide and conquer, dp, greedy, strings, trees Solve time: 8m 56s Verified: yes Solution Problem Understanding We are given a list of integers, and we are allowed to choose a single integer $X$. Once $X$ is fixed, every array value is transformed by XOR with $X$, and we care about the largest transformed value. The...

CF 1270C - Make Good

CF 1270C - Make Good Rating: 1400 Tags: bitmasks, constructive algorithms, math Solve time: 5m 12s Verified: no Solution Problem Understanding We are given an array of nonnegative integers, and we are allowed to append at most three additional numbers. The goal is to make the final multiset of numbers satisfy a very specific algebraic condition: the sum of all elements must equal twice their bitwise XOR. This condition couples...

CF 1238E - Keyboard Purchase

CF 1238E - Keyboard Purchase Rating: 2200 Tags: bitmasks, dp Solve time: 8m 18s Verified: no Solution Problem Understanding We are given a fixed string that we type repeatedly using a one-finger keyboard. The keyboard is defined by choosing a permutation of the first $m$ lowercase letters, and this permutation places each letter at a unique position on a line. When typing the string, every consecutive pair of characters incurs...

CF 1225C - p-binary

CF 1225C - p-binary Rating: 1600 Tags: bitmasks, brute force, math Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a positive target number $n$. We also fix an integer $p$, which shifts a family of numbers of the form $2^x + p$, where $x \ge 0$. Each such value is a single “building block”, and we are allowed to reuse the same block any number of...

CF 1220D - Alex and Julian

CF 1220D - Alex and Julian Rating: 1900 Tags: bitmasks, math, number theory Solve time: 5m 37s Verified: no Solution Problem Understanding We are given a finite set of positive integers, but the structure we build from it is infinite. Every integer is a vertex, and each number in the set is interpreted as a “distance type”. For every value d in the set, we connect every pair of integers...

Educational Codeforces Round 72 (Rated for Div. 2)

Educational Codeforces Round 72 (Rated for Div. 2) Div. 2 | 6 problems | 5/6 verified | Difficulty 1300-2600 | 25m 8s # Problem Rating Tags Accepted Time ✓ A Creating a Character 1300 binary-search, math 15,823 5m 30s ✓ B Zmei Gorynich 1600 greedy, math 11,856 5m 17s ✓ C The Number Of Good Substrings 1700 binary-search, bitmasks, brute-force 7,856 1m 48s ✓ D Coloring Edges 2100 constructive-algorithms, dfs-and-similar,...

CF 1209E2 - Rotate Columns (hard version)

CF 1209E2 - Rotate Columns (hard version) Rating: 2500 Tags: bitmasks, dp, greedy, sortings Solve time: 4m 14s Verified: no Solution Problem Understanding We are given a grid with a small number of rows and a potentially large number of columns. The only operation allowed is to take any single column and rotate it cyclically any number of times. After performing these rotations independently for each column, we look at...

CF 1208F - Bits And Pieces

CF 1208F - Bits And Pieces Rating: 2600 Tags: bitmasks, dfs and similar, dp, greedy Solve time: 2m 39s Verified: yes Solution Problem Understanding We are given a sequence of integers and asked to choose three indices $i < j < k$. For each such triple, we take the value of the first element OR the bitwise AND of the other two elements. The goal is to maximize this expression...

CF 1207E - XOR Guessing

CF 1207E - XOR Guessing Rating: 1900 Tags: bitmasks, interactive, math Solve time: 3m 8s Verified: no Solution Problem Understanding We are playing an interactive guessing game where a hidden number $x$ is fixed in advance, and it lies in the range from $0$ to $2^{14}-1$. We are allowed to ask up to two questions. Each question consists of a list of 100 distinct numbers within the same range, and...

CF 1168C - And Reachability

CF 1168C - And Reachability Rating: 2200 Tags: bitmasks, dp Solve time: 4m 57s Verified: yes Solution Problem Understanding We are given a sequence of integers arranged on a line, and we want to answer connectivity queries between pairs of positions, but connectivity is not based on adjacency. Instead, we are allowed to jump from an index to a later index if the bitwise AND of their values shares at...

CF 1163E - Magical Permutation

CF 1163E - Magical Permutation Rating: 2400 Tags: bitmasks, brute force, constructive algorithms, data structures, graphs, math Solve time: 4m 34s Verified: yes Solution Problem Understanding We are given a set of integers that represent allowed XOR “moves”. We are asked to build a permutation of all integers from 0 up to some power of two minus one, such that every adjacent pair in the permutation differs by a value...

CF 1097H - Mateusz and an Infinite Sequence

CF 1097H - Mateusz and an Infinite Sequence Rating: 3400 Tags: bitmasks, brute force, dp, strings Solve time: 7m 51s Verified: no Solution Problem Understanding We are working with an infinite sequence that is not written explicitly, but generated recursively. The construction starts from a single value zero. Each time we expand the sequence, we replace every element with multiple copies of the previous sequence, one copy per value in...

CF 1093G - Multidimensional Queries

CF 1093G - Multidimensional Queries Rating: 2300 Tags: bitmasks, data structures Solve time: 3m 41s Verified: yes Solution Problem Understanding We are working with a collection of points in a very low-dimensional space, where each point has up to five coordinates. The distance between two points is defined as the sum of absolute differences across each coordinate, which is the Manhattan metric. The system evolves over time. At any moment,...

CF 914G - Sum the Fibonacci

CF 914G - Sum the Fibonacci Rating: 2600 Tags: bitmasks, divide and conquer, dp, fft, math Solve time: 5m 10s Verified: no Solution Problem Understanding We are given a sequence of integers, each of which can be thought of as a 17-bit mask. From this array we must form ordered selections of five positions. Each selection contributes a value computed from bitwise combinations of the chosen elements, followed by evaluating...

CF 914E - Palindromes in a Tree

CF 914E - Palindromes in a Tree Rating: 2400 Tags: bitmasks, data structures, divide and conquer, trees Solve time: 4m 42s Verified: no Solution Problem Understanding We are given a tree where each node carries a lowercase character from a limited alphabet of size 20. The task is to examine every simple path in the tree and determine whether the multiset of characters along that path can be rearranged into...

CF 1051D - Bicolorings

CF 1051D - Bicolorings Rating: 1700 Tags: bitmasks, dp Solve time: 8m 54s Verified: no Solution Problem Understanding We are working with a very small geometric object: a grid with exactly two rows and $n$ columns. Each cell can independently be painted in one of two colors, which we can think of as black or white. Once a coloring is fixed, we interpret it as a graph where every cell...

CF 1073E - Segment Sum

CF 1073E - Segment Sum Rating: 2300 Tags: bitmasks, combinatorics, dp, math Solve time: 3m 54s Verified: yes Solution Problem Understanding We are asked to consider every integer inside a range $[l, r]$ and filter it by a digit constraint: we only keep numbers that use at most $k$ distinct decimal digits in their usual base-10 representation. Among all such valid numbers, we must compute their total sum modulo $998244353$....

CF 1088D - Ehab and another another xor problem

CF 1088D - Ehab and another another xor problem Rating: 2000 Tags: bitmasks, constructive algorithms, implementation, interactive Solve time: 6m 30s Verified: no Solution Problem Understanding We are trying to determine two hidden integers, a and b , each less than $2^{30}$. We cannot see them directly. Instead, we are allowed to query pairs $(c, d)$, and the judge compares the values $a \oplus c$ and $b \oplus d$, returning...

Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3)

Codeforces Round 602 (Div. 1, based on Technocup 2020 Elimination Round 3) Div. 1 | 1 problems | 0/1 verified | Difficulty 3100-3100 | 6m 41s # Problem Rating Tags Accepted Time ✓ F Xor-Set 3100 bitmasks, divide-and-conquer, math 442 6m 41s

CF 1261F - Xor-Set

CF 1261F - Xor-Set Rating: 3100 Tags: bitmasks, divide and conquer, math Solve time: 6m 41s Verified: no Solution Problem Understanding We are given two very large sets of integers, but they are not listed explicitly. Instead, each set is described as a union of intervals. Every integer inside an interval belongs to the set, and different intervals may overlap, so the same number can appear multiple times in the...

CF 1600J - Robot Factory

CF 1600J - Robot Factory Rating: 1400 Tags: bitmasks, dfs and similar Solve time: 1m 44s Verified: yes Solution Problem Understanding The grid describes a rectangular factory floor where each cell is a tile that may have walls on some of its four sides. Each tile contains a number from 0 to 15, and this number encodes its walls using four bits. Interpreting the binary representation from most significant to...

CF 1804H - Code Lock

CF 1804H - Code Lock Rating: 3300 Tags: bitmasks, dp Solve time: 9m 31s Verified: no Solution Problem Understanding We are given a circular dial with $k$ positions. Each position is labeled with a distinct letter from the first $k$ letters of the alphabet. We are allowed to permute which letter sits at which position before starting. After fixing this permutation, we begin at position 1 and want to type...

CF 1804E - Routing

CF 1804E - Routing Rating: 2400 Tags: bitmasks, brute force, dfs and similar, dp, graphs Solve time: 2m 51s Verified: no Solution Problem Understanding We are given an undirected, connected graph with up to 20 vertices. Each vertex represents a server, and edges represent direct bidirectional communication links. For every server $u$, we must choose exactly one adjacent vertex $a(u)$. Think of this as assigning each node a single outgoing...

CF 1734F - Zeros and Ones

CF 1734F - Zeros and Ones Rating: 2500 Tags: bitmasks, divide and conquer, dp, math Solve time: 4m 13s Verified: no Solution Problem Understanding The construction defines an infinite binary string where each stage doubles the previous string and flips the bits in the second half. This produces the well-known Thue-Morse sequence, but the important perspective here is not its recursive construction, rather the arithmetic structure behind each position. Each...

CF 1732C2 - Sheikh (Hard Version)

CF 1732C2 - Sheikh (Hard Version) Rating: 2100 Tags: binary search, bitmasks, brute force, greedy, implementation, two pointers Solve time: 4m Verified: no Solution Problem Understanding We are given an array and multiple range queries. For each query interval, we must choose a contiguous subarray fully inside that interval and maximize a score defined on that subarray. The score of a segment depends on two quantities computed over the same...

CF 1732C1 - Sheikh (Easy version)

CF 1732C1 - Sheikh (Easy version) Rating: 1800 Tags: binary search, bitmasks, greedy, two pointers Solve time: 2m 46s Verified: yes Solution Problem Understanding We are given an array and we are allowed to choose any contiguous segment inside it. For each segment, we compute a score defined as the difference between its sum and its bitwise XOR. The task is to answer a single query per test case, which...

CF 1731C - Even Subarrays

CF 1731C - Even Subarrays Rating: 1700 Tags: bitmasks, brute force, hashing, math, number theory Solve time: 3m 54s Verified: yes Solution Problem Understanding We are given an array of integers, and we look at every contiguous segment of it. For each segment we compute the bitwise XOR of its elements, producing a single number. The task is to count how many of these segments produce a XOR value whose...

CF 1730F - Almost Sorted

CF 1730F - Almost Sorted Rating: 2700 Tags: bitmasks, data structures, dp Solve time: 10m 6s Verified: no Solution Problem Understanding We are given a permutation p of size n , and we must construct another permutation q of indices 1..n . The constraint on q is unusual: if we look at the values of p along q , they cannot drop by more than k as we move forward....

CF 1728G - Illumination

CF 1728G - Illumination Rating: 2700 Tags: binary search, bitmasks, brute force, combinatorics, dp, math, two pointers Solve time: 10m 9s Verified: no Solution Problem Understanding We are working on a one-dimensional segment from 0 to d. Some positions on this line are special points that must be “covered”. We also have a collection of lantern positions, and each lantern can be assigned a nonnegative power up to d. A...

Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022

Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 Div. 1+2 | 7 problems | 1/7 verified | Difficulty 900-3500 | 38m 29s # Problem Rating Tags Accepted Time ✓ A Mainak and Array 900 greedy, math 36,505 4m 32s ✓ B Mainak and Interesting Sequence 1100 bitmasks, constructive-algorithms, math 16,838 4m 46s C Jatayu's Balanced Bracket Sequence 1300 data-structures, dsu, graphs 13,398 7m...

CF 1726B - Mainak and Interesting Sequence

CF 1726B - Mainak and Interesting Sequence Rating: 1100 Tags: bitmasks, constructive algorithms, math Solve time: 4m 46s Verified: no Solution Problem Understanding We are asked to construct a sequence of positive integers of length $n$ whose sum is fixed to $m$, but with an additional constraint that comes from a peculiar XOR condition applied to value ordering rather than positions. For every value $x$ appearing in the sequence, if...

CF 1725D - Deducing Sortability

CF 1725D - Deducing Sortability Rating: 2900 Tags: binary search, bitmasks, math Solve time: 4m 6s Verified: no Solution Problem Understanding We are asked to construct a very large hidden array indexed from 1 to N, where N can be up to one billion, without explicitly building it. This array is special because it is chosen so that it can be transformed, through a particular operation applied independently on elements,...

CF 1722G - Even-Odd XOR

CF 1722G - Even-Odd XOR Rating: 1500 Tags: bitmasks, constructive algorithms, greedy Solve time: 3m 7s Verified: no Solution Problem Understanding We are asked to construct, for each test case, a sequence of distinct nonnegative integers, all strictly below $2^{31}$, with a very specific balancing condition. If we split the array into two groups based on position parity, the XOR of elements in one group must match the XOR of...

Educational Codeforces Round 134 (Rated for Div. 2)

Educational Codeforces Round 134 (Rated for Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2800 | 21m 34s # Problem Rating Tags Accepted Time ✓ A Image 800 greedy, implementation 28,308 3m 11s ✓ B Deadly Laser 1000 implementation 23,878 4m 23s C Min-Max Array Transformation 1400 binary-search, greedy, two-pointers 14,557 2m 13s ✓ D Maximum AND 1800 bitmasks, dfs-and-similar, divide-and-conquer 7,679 3m 45s E Prefix...

CF 1721D - Maximum AND

CF 1721D - Maximum AND Rating: 1800 Tags: bitmasks, dfs and similar, divide and conquer, greedy, sortings Solve time: 3m 45s Verified: no Solution Problem Understanding We are given two arrays of equal length. One array, call it a , is fixed in place. The second array b can be permuted arbitrarily. After choosing a permutation of b , we pair elements by index and form a new array where...

CF 1720D2 - Xor-Subsequence (hard version)

CF 1720D2 - Xor-Subsequence (hard version) Rating: 2400 Tags: bitmasks, data structures, dp, strings, trees Solve time: 2m 51s Verified: no Solution Problem Understanding We are given an array of integers, and we want to choose a subsequence of indices. The chosen indices must be strictly increasing in position, but the values we compare are not just the array values themselves. Each step in the subsequence introduces a constraint that...

CF 1720D1 - Xor-Subsequence (easy version)

CF 1720D1 - Xor-Subsequence (easy version) Rating: 1800 Tags: bitmasks, brute force, dp, strings, trees, two pointers Solve time: 2m 1s Verified: no Solution Problem Understanding We are given an array of integers where each value is small, but the index range can be large. From this array we want to pick a subsequence of positions, keeping the indices strictly increasing. The goal is to make this subsequence as long...

CF 1658D1 - 388535 (Easy Version)

CF 1658D1 - 388535 (Easy Version) Rating: 1600 Tags: bitmasks, math Solve time: 3m 18s Verified: no Solution Problem Understanding We are given a final array that was produced by taking a consecutive integer segment, permuting it, and then applying a fixed XOR mask to every element. The original segment is known to be all integers from l to r inclusive, but their order is scrambled. After scrambling, every value...

CF 1658D2 - 388535 (Hard Version)

CF 1658D2 - 388535 (Hard Version) Rating: 2300 Tags: bitmasks, brute force, data structures, math Solve time: 2m 48s Verified: no Solution Problem Understanding We are given a hidden construction process that starts with a clean consecutive integer segment from some interval $[l, r]$. Gojou first takes all integers in that interval, then shuffles them arbitrarily. After that, he applies the same unknown XOR mask $x$ to every element, producing...

CF 1654F - Minimal String Xoration

CF 1654F - Minimal String Xoration Rating: 2800 Tags: bitmasks, data structures, divide and conquer, greedy, hashing, sortings, strings Solve time: 2m 42s Verified: yes Solution Problem Understanding We are given a string whose length is a power of two, indexed from 0 to $2^n - 1$. The key operation allowed is a global reindexing of the string using bitwise XOR with a fixed mask $j$. In other words, we...

CF 1583F - Defender of Childhood Dreams

CF 1583F - Defender of Childhood Dreams Rating: 2500 Tags: bitmasks, constructive algorithms, divide and conquer Solve time: 4m 38s Verified: no Solution Problem Understanding We are given a complete directed acyclic graph on the vertices from 1 to n, where every pair (i, j) with i < j has a directed edge from i to j. Every path is simply a strictly increasing sequence of vertices, and its length...

CF 1560F1 - Nearest Beautiful Number (easy version)

CF 1560F1 - Nearest Beautiful Number (easy version) Rating: 1900 Tags: binary search, bitmasks, brute force, constructive algorithms, dfs and similar, greedy Solve time: 7m 52s Verified: no Solution Problem Understanding We are given a starting number and a restriction on how many distinct digits we are allowed to use. For each query, we must find the smallest integer that is not smaller than the given number and whose decimal...

CF 1557C - Moamen and XOR

CF 1557C - Moamen and XOR Rating: 1700 Tags: bitmasks, combinatorics, dp, math, matrices Solve time: 5m 29s Verified: yes Solution Problem Understanding We are counting how many arrays of length n can be formed when each element is an integer in the range [0, 2^k - 1] , with the additional constraint that a certain bitwise inequality holds. For any such array, we compute two aggregate values over all...

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)

Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) Div. 1+2 | 8 problems | 3/8 verified | Difficulty 800-3300 | 41m 34s # Problem Rating Tags Accepted Time ✓ A A Variety of Operations 800 math 18,543 3m 43s ✓ B Take Your Places! 1300 implementation 13,275 2m 51s ✓ C Compressed Bracket Sequence 1800 brute-force, implementation 6,215 4m 31s D Take a Guess 1800...

CF 1556G - Gates to Another World

CF 1556G - Gates to Another World Rating: 3300 Tags: bitmasks, data structures, dsu, two pointers Solve time: 4m 44s Verified: no Solution Problem Understanding We are working on a graph whose vertices are all integers from $0$ to $2^n - 1$. Each vertex represents an $n$-bit binary string, and there is an undirected edge between two vertices if their binary representations differ in exactly one bit. This is the...

CF 1556D - Take a Guess

CF 1556D - Take a Guess Rating: 1800 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 9m 7s Verified: no Solution Problem Understanding We are given a hidden array of integers, and we cannot access its elements directly. The only way to learn anything about the array is by asking queries on pairs of indices. Each query returns either the bitwise AND or bitwise OR of two elements. Using only...

CF 1556F - Sports Betting

CF 1556F - Sports Betting Rating: 2500 Tags: bitmasks, combinatorics, dp, graphs, math, probabilities Solve time: 5m 15s Verified: yes Solution Problem Understanding We are given a complete tournament where every pair of teams plays exactly one match. The result of each match is random, but biased: team $i$ beats team $j$ with probability proportional to its strength, specifically $\frac{a_i}{a_i + a_j}$. Each match outcome is independent. From all match...

CF 1554B - Cobb

CF 1554B - Cobb Rating: 1700 Tags: bitmasks, brute force, greedy, math Solve time: 4m 33s Verified: yes Solution Problem Understanding We are given an array of values indexed from one, and we want to choose two different positions in this array. For any chosen pair of indices, we compute a score made of two competing parts: a positive term that grows with the product of the indices, and a...

CF 1550E - Stringforces

CF 1550E - Stringforces Rating: 2500 Tags: binary search, bitmasks, brute force, dp, strings, two pointers Solve time: 5m 43s Verified: yes Solution Problem Understanding We are given a string made of lowercase letters from a small alphabet of size $k$, plus wildcard characters that can be replaced freely. After replacing every wildcard with a letter from this alphabet, each letter induces a value: the longest contiguous block consisting only...

CF 1548D1 - Gregor and the Odd Cows (Easy)

CF 1548D1 - Gregor and the Odd Cows (Easy) Rating: 2300 Tags: bitmasks, geometry, math, number theory Solve time: 6m 39s Verified: yes Solution Problem Understanding We are given a set of points on a plane that serve as possible vertices of a triangle. Every point has even integer coordinates, and no three points are collinear. From these points we choose any triple and form a triangle. Every integer lattice...

Codeforces Round 731 (Div. 3)

Codeforces Round 731 (Div. 3) Div. 3 | 7 problems | 2/7 verified | Difficulty 800-2100 | 52m 52s # Problem Rating Tags Accepted Time ✓ A Shortest Path with Obstacle 800 implementation, math 32,287 7m 40s ✓ B Alphabetical Strings 800 greedy, implementation, strings 27,889 8m 37s C Pair Programming 1100 greedy, two-pointers 24,412 9m 7s D Co-growing Sequence 1300 bitmasks, constructive-algorithms, greedy 18,586 8m 23s E Air Conditioners...

CF 1547D - Co-growing Sequence

CF 1547D - Co-growing Sequence Rating: 1300 Tags: bitmasks, constructive algorithms, greedy Solve time: 8m 23s Verified: no Solution Problem Understanding We are given a sequence $x_1, x_2, \dots, x_n$. Our task is to construct another sequence $y_1, y_2, \dots, y_n$ such that when we XOR them elementwise, the resulting sequence $$a_i = x_i \oplus y_i$$ has a monotone bit-structure: every bit that is set in $a_i$ must also be...

CF 1543E - The Final Pursuit

CF 1543E - The Final Pursuit Rating: 2700 Tags: bitmasks, constructive algorithms, divide and conquer, graphs, greedy, math Solve time: 6m Verified: no Solution Problem Understanding The input describes a graph that is guaranteed to be a permuted hypercube. This means the graph has exactly $2^n$ vertices, every vertex has degree exactly $n$, and the structure is isomorphic to the standard $n$-dimensional hypercube, but the vertex labels have been arbitrarily...

CF 1543C - Need for Pink Slips

CF 1543C - Need for Pink Slips Rating: 1900 Tags: bitmasks, brute force, dfs and similar, implementation, math, probabilities Solve time: 6m 31s Verified: no Solution Problem Understanding We are repeatedly running a stochastic process that evolves a small probability distribution over three outcomes. At any moment there are up to three “active” slips, one of which is a terminal success state (the pink slip) and the other two are...

CF 1533H - Submatrices

CF 1533H - Submatrices Rating: - Tags: *special, bitmasks, data structures, dp Solve time: 4m 23s Verified: yes Solution Problem Understanding We are working with a grid of uppercase letters, but the alphabet is extremely small: only the first five letters appear. The task is not to inspect individual cells, but to count how many rectangular subregions of this grid contain exactly a given number of distinct letters, from one...

CF 1316E - Team Building Rating: 2300 Tags: bitmasks, dp, greedy, sortings Model: gpt-5-3-mini Solve time: 2m 52s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2de5ba-74c8-83ec-b78e-8c873f6a8ba6 Solution Problem Understanding We are asked to build a club structure from a pool of $n$ people. Each person can either become a player assigned to exactly one of $p$ distinct positions, or become part of an audience group of size exactly $k$. Nobody can be...

CF 1338B - Edge Weight Assignment Rating: 1800 Tags: bitmasks, constructive algorithms, dfs and similar, greedy, math, trees Model: gpt-5-3-mini Solve time: 1m 50s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e145b-5f7c-83ec-9103-1a6faf811420 Solution Problem Understanding We are given a tree where each edge must be assigned a positive integer weight. The restriction is not local to edges, it applies to paths: whenever we pick two leaves and walk along the unique path...

CF 1336E2 - Chiori and Doll Picking (hard version) Rating: 3500 Tags: bitmasks, brute force, combinatorics, math Model: gpt-5-3-mini Solve time: 2m 40s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e11d2-8d80-83ec-bdeb-135701da8ea4 Solution Problem Understanding We are given a collection of integers, each representing a “doll”, where each value is already encoded in binary and fits within m bits. From these dolls, we consider every possible subset. For each subset, we compute the...

CF 1331C - ...And after happily lived ever they Rating: ? Tags: *special, bitmasks Model: gpt-5-5 Solve time: 5m 18s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e0474-2e44-83ec-841e-f2d641d79b62 Solution Problem Understanding The task is extremely minimal on the surface: we are given a single integer a , guaranteed to lie in the range from 0 to 63, and we must output exactly one integer. The constraint immediately suggests that the input is...

CF 1332D - Walk on Matrix Rating: 1700 Tags: bitmasks, constructive algorithms, math Model: gpt-5-5 Solve time: 2m 47s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e0632-eed0-83ec-99e5-e8c87ad6dd8f Solution Problem Understanding We are asked to construct a matrix where movement is restricted to right and down from the top-left corner to the bottom-right corner. Every cell contains a non-negative integer, and as we move, we maintain a running value that is updated by...

CF 1322B - Present Rating: 2100 Tags: binary search, bitmasks, constructive algorithms, data structures, math, sortings Model: gpt-5-3-mini Solve time: 1m 28s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2deae4-fc9c-83ec-aeba-66f8cbbf4563 Solution Problem Understanding We are given an array of integers, and we consider every unordered pair of distinct elements. For each pair, we compute their sum. After collecting all these pairwise sums, instead of summing or minimizing them, we combine them using...

CF 1336E1 - Chiori and Doll Picking (easy version) Rating: 2700 Tags: bitmasks, brute force, combinatorics, math Model: gpt-5-3-mini Solve time: 5m 27s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e11cf-8ffc-83ec-899d-666c2225f7ac Solution Problem Understanding We are given a collection of integers, each encoded as an m-bit mask. From these numbers we may choose any subset of them, including the empty subset, and for each subset we compute the XOR of all chosen...

CF 1299D - Around the World Rating: 3000 Tags: bitmasks, combinatorics, dfs and similar, dp, graphs, math, trees Model: gpt-5-5 Solve time: 1m 17s Verified: yes (1/1 samples) Solution Problem Understanding We are given an undirected connected graph with weighted edges. The graph has a special structural restriction: any simple cycle that includes vertex 1 can only have length at most 3, meaning vertex 1 is not part of any...

CF 1322D - Reality Show Rating: 2800 Tags: bitmasks, dp Model: gpt-5-3-mini Solve time: 3m 5s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2deb92-56ac-83ec-ba70-95f7be671fa1 Solution Problem Understanding We are given a sequence of candidates that arrive in a fixed order. Each candidate has an initial aggressiveness level and a cost to recruit them. We may choose some of them, but with a constraint tied to the maximum aggressiveness we have already accepted:...

CF 1288D - Minimax Problem Rating: 2000 Tags: binary search, bitmasks, dp Model: gpt-5-3-mini Solve time: 2m 41s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2db7e1-74b8-83ec-b93f-88d597a14c54 Solution Problem Understanding We are given a collection of n vectors, each of length m. Think of each vector as describing m attributes of an object. We are allowed to pick two objects, possibly the same one twice. Once we pick them, we build a new...

CF 1325D - Ehab the Xorcist Rating: 1700 Tags: bitmasks, constructive algorithms, greedy, number theory Model: gpt-5-3-mini Solve time: 7m 3s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2df36e-7d1c-83ec-8eb8-d0b7521b6e99 Solution Problem Understanding We are asked to construct a shortest possible sequence of positive integers such that two aggregate properties are satisfied simultaneously: the bitwise XOR of all elements equals a given value u , and the sum of all elements equals another...

CF 1368D - AND, OR and square sum Rating: 1700 Tags: bitmasks, greedy, math Model: gpt-5-3-mini Solve time: 3m 16s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e4e27-f0e4-83ec-a61e-619a59836cd4 Solution Problem Understanding We are given a list of integers, each up to 20 bits. We can repeatedly pick two positions and apply a bitwise transformation that pushes bits from one number into another: one number becomes the bitwise AND of the pair, the...

CF 1327G - Letters and Question Marks Rating: 2800 Tags: bitmasks, dp, string suffix structures Model: gpt-5-3-mini Solve time: 6m 41s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2dfb41-0418-83ec-b67c-5f5a96738144 Solution Problem Understanding We are given a long base string and a collection of weighted pattern strings. Each pattern contributes a score every time it appears as a substring in the final string. The total value of the final string is the sum...

CF 1360H - Binary Median Rating: 2100 Tags: binary search, bitmasks, brute force, constructive algorithms Model: gpt-5-3-mini Solve time: 4m 37s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e3ffc-019c-83ec-9f2e-0b9dbb143a88 Solution Problem Understanding We start with the full space of all binary strings of length m , ordered in standard lexicographic order, which is equivalent to sorting them as fixed-length binary numbers from 0...0 up to 1...1 . From this complete ordered set,...

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 1245F - Daniel and Spring Cleaning

CF 1245F - Daniel and Spring Cleaning Rating: 2300 Tags: bitmasks, brute force, combinatorics, dp Solve time: 6m 2s Verified: yes Solution Problem Understanding We are given a range of integers from l to r , and we need to count ordered pairs (a, b) inside this range such that adding them behaves exactly like XOR. In other words, the usual addition of a and b produces the same result...

Technocup 2020 - Elimination Round 2

Technocup 2020 - Elimination Round 2 Special | 8 problems | 6/8 verified | Difficulty 900-3100 | 31m 49s # Problem Rating Tags Accepted Time ✓ A Forgetting Things 900 math 16,621 8m 53s B1 TV Subscriptions (Easy Version) 1000 implementation 12,518 2m 41s ✓ B2 TV Subscriptions (Hard Version) 1300 implementation, two-pointers 12,194 1m 46s ✓ C p-binary 1600 bitmasks, brute-force, math 9,787 2m 54s ✓ D Power Products...

Educational Codeforces Round 70 (Rated for Div. 2)

Educational Codeforces Round 70 (Rated for Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 1100-2700 | 20m 35s # Problem Rating Tags Accepted Time ✓ A You Are Given Two Binary Strings... 1100 bitmasks, greedy 10,718 7m 35s ✓ B You Are Given a Decimal String... 1700 brute-force, dp, shortest-paths 4,840 5m 33s C You Are Given a WASD-string... 2100 brute-force, data-structures, dp 2,768 1m 37s...

Codeforces Round 562 (Div. 1)

Codeforces Round 562 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-3100 | 23m 43s # Problem Rating Tags Accepted Time ✓ A Increasing by Modulo 1700 binary-search, greedy 7,595 2m 19s ✓ B Good Triple 1900 brute-force, two-pointers 3,811 3m 3s ✓ C And Reachability 2200 bitmasks, dp 2,728 4m 57s ✓ D Anagram Paths 3000 dp, implementation, trees 435 8m 7s E Xor Permutations...

Codeforces Round 580 (Div. 1)

Codeforces Round 580 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1200-3400 | Time: 28m 3s Problem Name Rating Tags Solve Time Verified A Almost Equal 1200 constructive-algorithms, greedy, math 5m 8s ✗ B Shortest Cycle 1900 bitmasks, brute-force, graphs 1m 41s ✓ C Palindromic Paths 2400 implementation, interactive 5m 3s ✗ D Almost All 2700 constructive-algorithms, trees 4m 42s ✗ E Expected Value...

CF 1202A - You Are Given Two Binary Strings...

CF 1202A - You Are Given Two Binary Strings... Rating: 1100 Tags: bitmasks, greedy Solve time: 7m 35s Verified: yes Solution Problem Understanding We are given two binary strings, which represent two integers. One of them, call it $x$, is fixed. The other, $y$, is effectively shifted left by some number of positions $k$, then added to $x$. After computing this sum, we take its binary representation and reverse it....

Educational Codeforces Round 68 (Rated for Div. 2)

Educational Codeforces Round 68 (Rated for Div. 2) Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 800-2700 | Time: 29m 26s Problem Name Rating Tags Solve Time Verified A Remove a Progression 800 math 4m 23s ✗ B Yet Another Crosses Problem 1300 implementation 3m 1s ✓ C From S To T 1300 implementation, strings 1m 41s ✓ D 1-2-K Game 1700 games, math 6m 6s...

CF 1194E - Count The Rectangles

CF 1194E - Count The Rectangles Rating: 2200 Tags: bitmasks, brute force, data structures, geometry, sortings Solve time: 4m 34s Verified: yes Solution Problem Understanding We are given a collection of axis-aligned line segments in the plane. Each segment is either perfectly horizontal or perfectly vertical. Horizontal segments never overlap with other horizontal segments, and the same is true for vertical segments. Intersections only happen between a horizontal and a...

Codeforces Round 456 (Div. 2)

Codeforces Round 456 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 800-2500 | 33m 2s # Problem Rating Tags Accepted Time ✓ A Tricky Alchemy 800 implementation 14,383 4m 12s ✓ B New Year's Eve 1300 bitmasks, constructive-algorithms, number-theory 13,833 10m 57s ✓ C Perun, Ult! 2500 brute-force, greedy, sortings 540 5m 1s ✓ D Fishes 2100 data-structures, graphs, greedy 2,148 5m 22s ✓ E Prime...

CF 1185G1 - Playlist for Polycarp (easy version)

CF 1185G1 - Playlist for Polycarp (easy version) Rating: 2100 Tags: bitmasks, combinatorics, dp Solve time: 5m 13s Verified: yes Solution Problem Understanding We are given a small collection of songs. Each song has a duration and a genre, and we want to form an ordered playlist by selecting some of these songs without repetition. The playlist must satisfy three constraints at the same time. The total listening time must...

Codeforces Round 563 (Div. 2)

Codeforces Round 563 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 1000-2500 | Time: 24m 56s Problem Name Rating Tags Solve Time Verified A Ehab Fails to Be Thanos 1000 constructive-algorithms, greedy, sortings 2m 41s ✗ B Ehab Is an Odd Person 1200 sortings 1m 33s ✓ C Ehab and a Special Coloring Problem 1300 constructive-algorithms, number-theory 2m 22s ✓ D Ehab and the...

CF 1174D - Ehab and the Expected XOR Problem

CF 1174D - Ehab and the Expected XOR Problem Rating: 1900 Tags: bitmasks, constructive algorithms Solve time: 5m 12s Verified: no Solution Problem Understanding We are asked to build a sequence of integers, each lying in the range from 1 up to $2^n - 1$, with a very specific restriction on its contiguous segments. For every contiguous subarray, we compute the bitwise XOR of its elements, and none of these...

CF 1097B - Petr and a Combination Lock

CF 1097B - Petr and a Combination Lock Rating: 1200 Tags: bitmasks, brute force, dp Solve time: 3m 57s Verified: yes Solution Problem Understanding We are given a circular lock that behaves like a 360-degree dial. Starting from zero, we perform a sequence of rotations, each rotation having a fixed magnitude, but we are free to choose its direction: clockwise or counterclockwise. Clockwise can be thought of as adding the...

Codeforces Round 529 (Div. 3)

Codeforces Round 529 (Div. 3) Type: Div. 3 | Problems: 6 | Verified: 3/6 | Rating range: 800-1900 | Time: 56m 48s Problem Name Rating Tags Solve Time Verified A Repeating Cipher 800 implementation 22m 53s ✗ B Array Stabilization 900 implementation 1m 24s ✓ C Powers Of Two 1400 bitmasks, greedy 12m 24s ✗ D Circular Dance 1600 implementation 11m 57s ✗ E Almost Regular Bracket Sequence 1900 implementation...

CF 1095C - Powers Of Two

CF 1095C - Powers Of Two Rating: 1400 Tags: bitmasks, greedy Solve time: 12m 24s Verified: no Solution Problem Understanding We are asked to express a given integer n as a sum of exactly k numbers, where every summand must be a power of two. Each chosen number is therefore of the form 1, 2, 4, 8, ... , and repetitions are allowed because we can use the same power...

CF 920G - List Of Integers

CF 920G - List Of Integers Rating: 2200 Tags: binary search, bitmasks, brute force, combinatorics, math, number theory Solve time: 4m 34s Verified: yes Solution Problem Understanding The problem asks us to generate a special list of integers for multiple queries. For a given query with integers x , p , and k , we need to find the k -th integer greater than x that is coprime with p...

Codeforces Round 457 (Div. 2)

Codeforces Round 457 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 900-2400 | Time: 21m 30s Problem Name Rating Tags Solve Time Verified A Jamie and Alarm Snooze 900 brute-force, implementation, math 3m 14s ✓ B Jamie and Binary Sequence (changed after round) 2000 bitmasks, greedy, math 2m 14s ✓ C Jamie and Interesting Graph 1600 constructive-algorithms, graphs, shortest-paths 5m 35s ✗ D Jamie...

Hello 2018

Hello 2018 Type: Special | Problems: 8 | Verified: 4/8 | Rating range: 900-3400 | Time: 47m 3s Problem Name Rating Tags Solve Time Verified A Modular Exponentiation 900 implementation, math 6m 16s ✓ B Christmas Spruce 1200 implementation, trees 2m 58s ✓ C Party Lemonade 1600 bitmasks, dp, greedy 6m 30s ✓ D Too Easy Problems 1800 binary-search, brute-force, data-structures 6m 50s ✗ E Logical Expression 2400 bitmasks, dp,...

CF 913E - Logical Expression

CF 913E - Logical Expression Rating: 2400 Tags: bitmasks, dp, shortest paths Solve time: 3m 25s Verified: no Solution Problem Understanding We are working with Boolean functions of exactly three variables, x , y , and z . A Boolean function on three variables has only eight possible input assignments. The input gives the value of the function on each of those eight assignments as a binary string of length...

CF 913C - Party Lemonade

CF 913C - Party Lemonade Rating: 1600 Tags: bitmasks, dp, greedy Solve time: 6m 30s Verified: yes Solution Problem Understanding We are asked to buy at least L liters of lemonade at minimum cost. The store offers n types of bottles , where the i-th type has a volume of 2^(i-1) liters and a cost of c[i] roubles , and we can buy an unlimited number of each type. The...

CF 912B - New Year's Eve

CF 912B - New Year's Eve Rating: 1300 Tags: bitmasks, constructive algorithms, number theory Solve time: 10m 57s Verified: yes Solution Problem Understanding We are asked to help Grisha maximize his happiness by choosing up to k candies from a bag of n candies, each with a unique tastiness from 1 to n . The happiness is not the usual sum of tastinesses but the xor-sum, which is the result...

CF 908E - New Year and Entity Enumeration

CF 908E - New Year and Entity Enumeration Rating: 2500 Tags: bitmasks, combinatorics, dp, math Solve time: 9m 9s Verified: no Solution Problem Understanding We work with binary vectors of length m , which can be viewed as integers from 0 to 2^m - 1 . A valid set S must satisfy three structural properties. First, it contains every vector from the given set T . Second, it is closed...

Codeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4)

Codeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1600-3300 | Time: 38m 39s Problem Name Rating Tags Solve Time Verified A Shockers 1600 implementation, strings 5m 30s ✓ B Seating of Students 2200 brute-force, constructive-algorithms, math 6m 9s ✗ C Party 2400 bitmasks, brute-force, dp 7m 24s ✓ D Power Tower 2700 chinese-remainder-theorem, math,...

CF 906C - Party

CF 906C - Party Rating: 2400 Tags: bitmasks, brute force, dp, graphs Solve time: 7m 24s Verified: yes Solution Problem Understanding We have a connected friendship graph. Choosing a vertex means that all of its neighbors become pairwise adjacent. In graph theory language, we are allowed to pick a vertex and turn its open neighborhood into a clique. The process continues until the whole graph becomes a complete graph. We...

CF 903F - Clear The Matrix

CF 903F - Clear The Matrix Rating: 2200 Tags: bitmasks, dp Solve time: 2m 8s Verified: yes Solution Problem Understanding We are given a 4-row by n -column matrix filled with either asterisks or dots. The asterisks represent tiles that must be cleared. The allowed operation is selecting a square submatrix of size 1×1 up to 4×4 and replacing every asterisk inside it with dots. Each submatrix has a fixed...

Hello 2019

Hello 2019 Special | 8 problems | 5/8 verified | Difficulty 800-3400 | 33m 15s # Problem Rating Tags Accepted Time ✓ A Gennady and a Card Game 800 brute-force, implementation 43,794 1m 17s ✓ B Petr and a Combination Lock 1200 bitmasks, brute-force, dp 35,929 3m 57s ✓ C Yuhao and a Parenthesis 1400 greedy, implementation 8,783 4m 37s ✓ D Makoto and a Blackboard 2200 dp, math, number-theory...

CF 914F - Substrings in a String

CF 914F - Substrings in a String Rating: 3000 Tags: bitmasks, brute force, data structures, string suffix structures, strings Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a mutable string and a sequence of queries. Each query either changes a character at a specific position or asks how many times a smaller string appears as a substring within a specific substring of the main string. The...

CF 916B - Jamie and Binary Sequence (changed after round)

CF 916B - Jamie and Binary Sequence (changed after round) Rating: 2000 Tags: bitmasks, greedy, math Solve time: 2m 14s Verified: yes Solution Problem Understanding We want to represent a positive integer n as a sum of exactly k powers of two: $$n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}$$ The exponents may be positive, zero, or even negative. Among all valid sequences of length k , we first...

CF 1097F - Alex and a TV Show

CF 1097F - Alex and a TV Show Rating: 2500 Tags: bitmasks, combinatorics, number theory Solve time: 1m 21s Verified: yes Solution Problem Understanding We are asked to simulate operations on a set of multisets, each initially empty. The operations are either assigning a single value to a multiset, combining two multisets via union, combining two multisets via a multiset product using greatest common divisors, or querying the parity of...

CF 1102F - Elongated Matrix

CF 1102F - Elongated Matrix Rating: 2000 Tags: binary search, bitmasks, brute force, dp, graphs Solve time: 1m 6s Verified: yes Solution Problem Understanding We have a rectangular grid of numbers with $n$ rows and $m$ columns. We are allowed to reorder the rows however we like, but the order of numbers within each row is fixed. After picking an order, we traverse the grid column by column from top...

CF 1114F - Please, another Queries on Array?

CF 1114F - Please, another Queries on Array? Rating: 2400 Tags: bitmasks, data structures, divide and conquer, math, number theory Solve time: 1m 7s Verified: yes Solution Problem Understanding We have an array of integers, each between 1 and 300, and we need to process two types of queries. The first query multiplies a contiguous segment of the array by a given number. The second query asks for the Euler...

CF 1117F - Crisp String

CF 1117F - Crisp String Rating: 2500 Tags: bitmasks, dp Solve time: 2m 1s Verified: yes Solution Problem Understanding We are given a string consisting of the first p letters of the lowercase English alphabet, and a symmetric adjacency matrix A that specifies which letters can appear next to each other. A string is crisp if every consecutive pair of letters in it is allowed by this matrix. We are...

CF 1117E - Decypher the String

CF 1117E - Decypher the String Rating: 2200 Tags: bitmasks, chinese remainder theorem, constructive algorithms, interactive, math Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a string t of length n which is the result of applying an unknown sequence of swaps to an original string s . Each swap exchanges two characters at positions a_i and b_i in s . The sequence of swaps could...

Codeforces Round 550 (Div. 3)

Codeforces Round 550 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 3/7 | Rating range: 800-2400 | Time: 12m 3s Problem Name Rating Tags Solve Time Verified A Diverse Strings 800 implementation, strings 1m 18s ✓ B Parity Alternated Deletions 900 greedy, implementation, sortings 1m 18s ✓ C Two Shuffled Sequences 1000 constructive-algorithms, sortings 1m 48s ✗ D Equalize Them All 1400 constructive-algorithms, greedy 3m 16s ✗ E...

CF 1144E - Median String

CF 1144E - Median String Rating: 1900 Tags: bitmasks, math, number theory, strings Solve time: 1m 18s Verified: yes Solution Problem Understanding We are asked to find the median string between two given strings of the same length, s and t , using lexicographical ordering. Both strings consist only of lowercase Latin letters, and s is guaranteed to be strictly smaller than t . The "median" here is defined as...

April Fools Day Contest 2019

April Fools Day Contest 2019 Type: April Fools | Problems: 7 | Verified: 7/7 | Rating range: - | Time: 11m 54s Problem Name Rating Tags Solve Time Verified A Thanos Sort - *special, implementation 1m 23s ✓ B Kanban Numbers - *special, brute-force 1m 36s ✓ C Mystery Circuit - bitmasks, brute-force 1m 52s ✓ D Pigeon d'Or - *special, implementation 1m 39s ✓ E Fourier Doodles - -...

CF 1145C - Mystery Circuit

CF 1145C - Mystery Circuit Rating: - Tags: bitmasks, brute force Solve time: 1m 52s Verified: yes Solution Problem Understanding We are given a single integer a between 0 and 15. This integer represents a configuration of a simple 4-bit circuit, where each bit can be either 0 or 1. The task is to compute an output integer based on a mysterious internal rule of the circuit. From the sample,...

Forethought Future Cup - Elimination Round

Forethought Future Cup - Elimination Round Type: Special | Problems: 8 | Verified: 3/8 | Rating range: 800-2900 | Time: 15m 34s Problem Name Rating Tags Solve Time Verified A [Love ](https://codeforces.com/problemset/problem/1146/A) 800 implementation, strings 1m 27s ✓ B [Hate ](https://codeforces.com/problemset/problem/1146/B) 1100 implementation, strings 1m 23s ✓ C Tree Diameter 1700 bitmasks, graphs, interactive 2m 14s ✗ D Frog Jumping 2100 dfs-and-similar, math, number-theory 3m 25s ✗ E Hot is...

CF 1146E - Hot is Cold

CF 1146E - Hot is Cold Rating: 2400 Tags: bitmasks, data structures, divide and conquer, implementation Solve time: 2m 5s Verified: no Solution Problem Understanding We are given an array of integers and a series of queries. Each query instructs us to flip the sign of numbers in the array that satisfy a comparison: either all numbers greater than a threshold or all numbers less than a threshold. After performing...

CF 1146C - Tree Diameter

CF 1146C - Tree Diameter Rating: 1700 Tags: bitmasks, graphs, interactive Solve time: 2m 14s Verified: no Solution Problem Understanding We are asked to determine the diameter of an unknown weighted tree. The tree has n nodes connected by n-1 edges, each with a positive integer weight at most 100. We do not have direct access to the edges. Instead, we can query the system: for any two disjoint nonempty...

CF 1148F - Foo Fighters

CF 1148F - Foo Fighters Rating: 2700 Tags: bitmasks, constructive algorithms Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a collection of objects, each contributing a signed value and a binary mask. We must choose a positive integer s . Once s is fixed, each object is either kept as-is or flipped in sign depending on a parity condition computed from s and its mask. Concretely,...

Codeforces Round 553 (Div. 2)

Codeforces Round 553 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 5/6 | Rating range: 1000-2300 | Time: 12m 3s Problem Name Rating Tags Solve Time Verified A Maxim and Biology 1000 brute-force, strings 1m 38s ✓ B Dima and a Bad XOR 1600 bitmasks, brute-force, constructive-algorithms 1m 41s ✓ C Problem for Nazar 1800 constructive-algorithms, math 1m 41s ✓ D Stas and the Queue at the Buffet...

CF 1151B - Dima and a Bad XOR

CF 1151B - Dima and a Bad XOR Rating: 1600 Tags: bitmasks, brute force, constructive algorithms, dp Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a grid of integers where each row represents a set of choices, and from every row we must pick exactly one number. After picking one number per row, we compute the bitwise XOR of all chosen numbers. The task is to...

Codeforces Round 554 (Div. 2)

Codeforces Round 554 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 800-3000 | Time: 12m 11s Problem Name Rating Tags Solve Time Verified A Neko Finds Grapes 800 greedy, implementation, math 1m 24s ✓ B Neko Performs Cat Furrier Transform 1300 bitmasks, constructive-algorithms, dfs-and-similar 1m 43s ✗ C Neko does Maths 1800 brute-force, math, number-theory 3m 35s ✓ D Neko and Aki's Prank 2100...

CF 1152F2 - Neko Rules the Catniverse (Large Version)

CF 1152F2 - Neko Rules the Catniverse (Large Version) Rating: 3000 Tags: bitmasks, dp, matrices Solve time: 2m 1s Verified: no Solution Problem Understanding We are asked to count sequences of planet visits with strong structural constraints. A path starts at any planet from 1 to n, and then performs exactly k − 1 moves. Each move goes from the current planet x to a new planet y that has...

CF 1152F1 - Neko Rules the Catniverse (Small Version)

CF 1152F1 - Neko Rules the Catniverse (Small Version) Rating: 2800 Tags: bitmasks, dp, matrices Solve time: 58s Verified: yes Solution Problem Understanding We are asked to count ordered sequences of distinct planets visited by a character who starts on any planet and then makes exactly $k-1$ moves. Each move goes from the current planet $x$ to a new planet $y$, with two restrictions: $y$ must not have been visited...

CF 1152B - Neko Performs Cat Furrier Transform

CF 1152B - Neko Performs Cat Furrier Transform Rating: 1300 Tags: bitmasks, constructive algorithms, dfs and similar, math Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a positive integer x representing the "number" of a cat. Our goal is to transform x into a number of the form 2^m - 1 for some non-negative integer m . These numbers in binary consist entirely of 1s, such...

CF 1166E - The LCMs Must be Large

CF 1166E - The LCMs Must be Large Rating: 2100 Tags: bitmasks, brute force, constructive algorithms, math, number theory Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a set of stores, each selling an unknown positive integer, and a record of Dora's purchases over several days. On each day, she bought integers from some stores, while her rival, Swiper, bought from the remaining stores. Dora wants...

CF 1185F - Two Pizzas

CF 1185F - Two Pizzas Rating: 2100 Tags: bitmasks, brute force Solve time: 1m 6s Verified: yes Solution Problem Understanding We are asked to help a group of friends pick exactly two pizzas so that the maximum number of friends are satisfied with the choice. Each friend has a set of favorite ingredients, and a friend is satisfied if every one of their favorite ingredients appears on at least one...

CF 1205B - Shortest Cycle

CF 1205B - Shortest Cycle Rating: 1900 Tags: bitmasks, brute force, graphs, shortest paths Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a collection of integers, and we interpret each integer as a node in a graph. Two nodes are connected when their bitwise AND is non-zero, meaning they share at least one common bit set to 1. The task is to determine the length of...

CF 1209E1 - Rotate Columns (easy version)

CF 1209E1 - Rotate Columns (easy version) Rating: 2000 Tags: bitmasks, brute force, dp, greedy, sortings Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given a matrix with n rows and m columns, where each entry is a positive integer. We can pick any column and rotate it cyclically any number of times. After performing such rotations, we consider each row and take the maximum value in...

CF 1214G - Feeling Good

CF 1214G - Feeling Good Rating: 3200 Tags: bitmasks, data structures Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a two-dimensional grid representing a chameleon's body. Initially, all cells are green. Each cell can be either green or blue, and the color may be flipped multiple times. Each flip affects a contiguous horizontal segment of a single row. After every flip, we must determine whether the...

CF 1215E - Marbles

CF 1215E - Marbles Rating: 2200 Tags: bitmasks, dp Solve time: 2m 26s Verified: yes Solution Problem Understanding We are given a long row of marbles, each painted with one of at most 20 colors. The only allowed move is swapping two adjacent marbles, and we want to use as few swaps as possible. The goal is not to sort the marbles in the usual sense. Instead, we want to...

CF 1217C - The Number Of Good Substrings

CF 1217C - The Number Of Good Substrings Rating: 1700 Tags: binary search, bitmasks, brute force Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given a binary string and asked to count its "good" substrings. A substring is good if its length equals the decimal value of its binary representation, allowing leading zeros. That means for a substring like 011 , which is 3 in decimal, it...

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

CF 1225G - To Make 1

CF 1225G - To Make 1 Rating: 3100 Tags: bitmasks, constructive algorithms, dp, greedy, number theory Solve time: 1m 8s Verified: yes Solution Problem Understanding We have a set of $n$ positive integers on a blackboard and a number $k \ge 2$. None of the integers is divisible by $k$. We are allowed to repeatedly pick any two numbers $x$ and $y$, erase them, and write $f(x+y)$ instead. The function...

CF 1292F - Nora's Toy Boxes

CF 1292F - Nora's Toy Boxes Rating: 3500 Tags: bitmasks, combinatorics, dp Solve time: 1m 56s Verified: yes Solution Problem Understanding We are given a collection of n distinct toy boxes, each labeled with a positive integer a_i . ROBO can perform a very specific action multiple times: pick three distinct boxes where one box's label divides the other two, and then remove the third box to place it on...

Codeforces Round 656 (Div. 3)

Codeforces Round 656 (Div. 3) Div. 3 | 7 problems | 0/7 verified | Difficulty 800-2300 | 34m 47s # Problem Rating Tags Accepted Time ✓ A A 800 math 43,323 4m 30s B Restore the Permutation by Merger 800 greedy 39,577 2m 55s C Make It Good 1200 greedy 28,910 4m 8s D a-Good String 1500 bitmasks, brute-force, divide-and-conquer 21,953 8m 44s E Directing Edges 2000 constructive-algorithms, dfs-and-similar, graphs...

CF 1312C - Adding Powers

CF 1312C - Adding Powers Rating: 1400 Tags: bitmasks, greedy, implementation, math, number theory, ternary search Solve time: 1m 8s Verified: no Solution Problem Understanding We are given an array of non-negative integers, and a base $k \ge 2$. Starting from an array of zeroes of the same length, we can repeatedly pick a step $i$ and add $k^i$ to any single element of the array, or skip the step....

CF 1313D - Happy New Year

CF 1313D - Happy New Year Rating: 2500 Tags: bitmasks, dp, implementation Solve time: 2m 33s Verified: no Solution Problem Understanding We are given a large line of positions from 1 to $m$, and a collection of $n$ intervals. Each interval represents a “spell” that, when used, adds one candy to every position inside its range. Each spell can be used at most once. After choosing a subset of spells,...

CF 1326F2 - Wise Men (Hard Version)

CF 1326F2 - Wise Men (Hard Version) Rating: 3200 Tags: bitmasks, dp, math Solve time: 2m 36s Verified: yes Solution Problem Understanding We are asked to analyze permutations of a group of $n$ wise men, where some pairs of them know each other. For each permutation of these wise men, we can create a binary string of length $n-1$ indicating adjacency of acquaintances: a '1' if two consecutive wise men...

CF 1334G - Substring Search

CF 1334G - Substring Search Rating: 2900 Tags: bitmasks, brute force, fft Solve time: 2m 26s Verified: yes Solution Problem Understanding We are asked to find all substrings of a string t that "match" another string s according to a flexible definition of equality. Normally, a substring matches s if each character is exactly equal, but here we have a permutation p of the numbers 1 through 26 that allows...

CF 1340B - Nastya and Scoreboard

CF 1340B - Nastya and Scoreboard Rating: 1700 Tags: bitmasks, dp, graphs, greedy Solve time: 5m 26s Verified: no Solution The previous solution is based on a misunderstanding of the problem. The goal is not to match the sample output exactly. The sample output shows one valid answer among many. The real requirement is: t must be a subsequence of s . |s| ≤ 2|t| . s must have the...

CF 1342F - Make It Ascending

CF 1342F - Make It Ascending Rating: 3000 Tags: bitmasks, brute force, dp Solve time: 3m 2s Verified: no Solution Problem Understanding We are given an array of integers, and we are allowed to repeatedly perform an operation where we pick two distinct indices, add the value from the first index to the second, and remove the first element from the array. The goal is to end up with an...

CF 1362B - Johnny and His Hobbies

CF 1362B - Johnny and His Hobbies Rating: 1200 Tags: bitmasks, brute force Solve time: 2m 2s Verified: yes Solution Problem Understanding We are given a set of distinct integers. Johnny chooses a positive integer k and replaces every value s in the set with s XOR k . The transformation is applied to every element simultaneously. After the transformation, we want the resulting set to be exactly the same...

CF 1383B - GameGame

CF 1383B - GameGame Rating: 1900 Tags: bitmasks, constructive algorithms, dp, games, greedy, math Solve time: 1m 32s Verified: yes Solution Problem Understanding The problem describes a two-player game played on an array of non-negative integers. The players take turns removing an element from the array and XOR-ing it with their current score. The game ends when all elements are removed, and the player with the larger score wins, while...

CF 1386C - Joker

CF 1386C - Joker Rating: 2800 Tags: *special, bitmasks, data structures, divide and conquer, dsu Solve time: 2m 24s Verified: no Solution Solution Let $N = pq$ where $p \equiv 3 \pmod 8$ and $q \equiv 7 \pmod 8$. We first prove the claimed identity involving the Jacobi symbol. Recall that the Jacobi symbol is multiplicative and satisfies $$\left(\frac{a}{N}\right) = \left(\frac{a}{p}\right) \left(\frac{a}{q}\right)$$ for any integer $a$. We compute $\left(\frac{-1}{N}\right)$ and...

Codeforces Global Round 10

Codeforces Global Round 10 Type: Global | Problems: 9 | Verified: 2/9 | Rating range: 800-3300 | Time: 31m 49s Problem Name Rating Tags Solve Time Verified A Omkar and Password 800 greedy, math 1m 10s ✗ B Omkar and Infinity Clock 800 implementation, math 11m 32s ✗ C Omkar and Waterslide 1200 greedy, implementation 1m 35s ✓ D Omkar and Bed Wars 1700 dp, greedy 5m 37s ✗ E...

CF 1392G - Omkar and Pies

CF 1392G - Omkar and Pies Rating: 2900 Tags: bitmasks, dfs and similar, dp, math, shortest paths Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a very small binary “target state” of size $k \le 20$, representing pies placed in fixed positions. We also have an initial configuration of those pies and a desired configuration. There is a long sequence of operations, each operation being a...

CF 1392E - Omkar and Duck

CF 1392E - Omkar and Duck Rating: 2100 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 2m Verified: no Solution Problem Understanding We are working with a small grid, at most 25 by 25, where a path is formed from the top-left cell to the bottom-right cell using only moves to the right or downward. Each path therefore always has exactly $2n-1$ visited cells, because every step increases either the...

Codeforces Round 664 (Div. 2)

Codeforces Round 664 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 1000-1600 | Time: 18m 47s Problem Name Rating Tags Solve Time Verified A Boboniu Likes to Color Balls 1000 brute-force, math 8m 29s ✗ B Boboniu Plays Chess 1100 constructive-algorithms 9m 1s ✗ C Boboniu and Bit Operations 1600 bitmasks, brute-force, dp 1m 17s ✓

CF 1395C - Boboniu and Bit Operations

CF 1395C - Boboniu and Bit Operations Rating: 1600 Tags: bitmasks, brute force, dp, greedy Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given two small arrays of integers. For every element in the first array, we must pick one element from the second array and combine them using bitwise AND. This produces a new value for each position in the first array. After choosing all these...

Educational Codeforces Round 86 (Rated for Div. 2)

Educational Codeforces Round 86 (Rated for Div. 2) Div. 2 | 4 problems | 1/4 verified | Difficulty 1000-3000 | 13m 44s # Problem Rating Tags Accepted Time ✓ A Road To Zero 1000 greedy, math 46,404 2m 20s ✓ B Binary Period 1100 constructive-algorithms, strings 24,582 3m 32s C Yet Another Counting Problem 1600 math, number-theory 14,996 4m 50s F Make It Ascending 3000 bitmasks, brute-force, dp 989 3m...

CF 1398G - Running Competition

CF 1398G - Running Competition Rating: 2600 Tags: bitmasks, fft, math, number theory Solve time: 2m Verified: no Solution Problem Understanding We are asked to model a running stadium as a rectangle subdivided by vertical lines. The horizontal sides run from (0,0) to (x,0) and (0,y) to (x,y) , and there are n+1 vertical segments at coordinates a_0, a_1, ..., a_n , which connect the top and bottom edges. Each...

Codeforces Round 633 (Div. 1)

Codeforces Round 633 (Div. 1) Div. 1 | 3 problems | 2/3 verified | Difficulty 1500-2700 | 15m 48s # Problem Rating Tags Accepted Time ✓ A Powered Addition 1500 greedy, math 30,333 2m 29s ✓ C Perfect Triples 2200 bitmasks, brute-force, constructive-algorithms 3,440 6m 54s D Nested Rubber Bands 2700 constructive-algorithms, dfs-and-similar, dp 1,127 6m 25s ✓

CF 1400G - Mercenaries

CF 1400G - Mercenaries Rating: 2600 Tags: bitmasks, brute force, combinatorics, dp, dsu, math, two pointers Solve time: 1m 20s Verified: yes Solution Problem Understanding Polycarp wants to select a subset of mercenaries from a pool of n individuals. Each mercenary has two constraints: the minimum and maximum size of the team they are willing to join, given by l_i and r_i . In addition, some pairs of mercenaries dislike...

CF 1401F - Reverse and Swap

CF 1401F - Reverse and Swap Rating: 2400 Tags: binary search, bitmasks, data structures Solve time: 2m 1s Verified: no Solution Problem Understanding We are working with an array of length $2^n$, where $n$ can be up to 18, so the array can have up to $262{,}144$ elements. Queries modify the array or request the sum of subarrays. There are four types of modifications. The first directly replaces an element....

Educational Codeforces Round 84 (Rated for Div. 2)

Educational Codeforces Round 84 (Rated for Div. 2) Div. 2 | 3 problems | 1/3 verified | Difficulty 1100-2500 | 10m 27s # Problem Rating Tags Accepted Time ✓ A Sum of Odd Integers 1100 math 45,721 4m 16s C Game with Chips 1600 constructive-algorithms, implementation 14,086 2m 54s ✓ F AND Segments 2500 bitmasks, combinatorics, data-structures 2,028 3m 17s

CF 1411G - No Game No Life

CF 1411G - No Game No Life Rating: 2700 Tags: bitmasks, games, math, matrices Solve time: 1m 22s Verified: yes Solution Problem Understanding We are asked to calculate the probability that Alice wins a two-player chip-moving game on a directed acyclic graph. Each vertex can hold any number of chips, and players take turns moving a single chip along an outgoing edge. Alice starts first, and the player who cannot...

CF 1411E - Poman Numbers

CF 1411E - Poman Numbers Rating: 2300 Tags: bitmasks, greedy, math, strings Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a string of lowercase letters, which we interpret as a number in a strange “poman” numeral system. Each single letter corresponds to a power of two, where a is 2^0 = 1, b is 2^1 = 2, c is 2^2 = 4, and so on up...

Technocup 2021 - Elimination Round 2

Technocup 2021 - Elimination Round 2 Type: Special | Problems: 6 | Verified: 6/6 | Rating range: 800-2900 | Time: 15m 13s Problem Name Rating Tags Solve Time Verified A Prison Break 800 brute-force, math 1m 23s ✓ B Repainting Street 1100 brute-force, greedy 1m 53s ✓ C Bouncing Ball 1400 brute-force, dp, implementation 1m 45s ✓ D XOR-gun 2000 bitmasks, brute-force, constructive-algorithms 1m 25s ✓ E New Game Plus!...

CF 1415D - XOR-gun

CF 1415D - XOR-gun Rating: 2000 Tags: bitmasks, brute force, constructive algorithms Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a sorted array, and we are allowed to repeatedly compress any adjacent pair into a single value equal to their bitwise XOR. Each compression reduces the length of the array by one, and we are never allowed to reduce below length one. The goal is not...

CF 1416C - XOR Inverse

CF 1416C - XOR Inverse Rating: 2000 Tags: bitmasks, data structures, divide and conquer, dp, greedy, math, sortings, strings, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given an array of non-negative integers, and we need to pick a number $x$ so that when we XOR every element in the array with $x$, the resulting array has as few inversions as possible. An inversion is a...

Codeforces Round 672 (Div. 2)

Codeforces Round 672 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 900-2500 | Time: 11m 56s Problem Name Rating Tags Solve Time Verified A Cubes Sorting 900 math, sortings 1m 10s ✓ B Rock and Lever 1200 bitmasks, math 1m 33s ✓ C1 Pok\u00e9mon Army (easy version) 1300 constructive-algorithms, dp, greedy 5m 17s ✗ C2 Pok\u00e9mon Army (hard version) 2100 data-structures, divide-and-conquer, dp 1m...

CF 1420B - Rock and Lever

CF 1420B - Rock and Lever Rating: 1200 Tags: bitmasks, math Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given several independent arrays of integers. For each array, we must count how many pairs of positions form a “good interaction” under a bitwise condition. A pair of indices contributes to the answer when the bitwise AND of the two values is at least as large as their...

CF 1421A - XORwice

CF 1421A - XORwice Rating: 800 Tags: bitmasks, greedy, math Solve time: 10m 16s Verified: yes Solution Problem Understanding The problem asks for the minimum sum of two XOR operations for a pair of integers a and b when XORed with the same number x . Concretely, given a and b , we must choose x such that the expression (a XOR x) + (b XOR x) is as small...

Codeforces Round 676 (Div. 2)

Codeforces Round 676 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2700 | Time: 23m 51s Problem Name Rating Tags Solve Time Verified A XORwice 800 bitmasks, greedy, math 10m 16s ✓ B Putting Bricks in the Wall 1100 constructive-algorithms, implementation 1m 41s ✓ C Palindromifier 1400 constructive-algorithms, strings 8m 21s ✓ D Hexagons 1900 brute-force, constructive-algorithms, greedy 2m 5s ✗ E Swedish Heroes...

CF 1423J - Bubble Cup hypothesis

CF 1423J - Bubble Cup hypothesis Rating: 2400 Tags: bitmasks, constructive algorithms, dp, math Solve time: 1m 25s Verified: yes Solution Problem Understanding We are counting representations of a number using base-2 evaluation of a polynomial whose coefficients are restricted to small digits from 0 to 7. Concretely, each polynomial corresponds to choosing coefficients $a_0, a_1, a_2, \dots$, each between 0 and 7, and evaluating it at $x = 2$....

CF 1423I - Lookup Tables

CF 1423I - Lookup Tables Rating: 3000 Tags: bitmasks Solve time: 2m 20s Verified: yes Solution Problem Understanding We have a function over 2K bits. Every input x can be split into two halves: a = lowKBits(x) b = highKBits(x) The function must be represented as $$F(x)=L[a]\ &\ M[b]$$ where L and M are lookup tables of size 2^K , and & is bitwise AND. Instead of specifying the value...

Educational Codeforces Round 82 (Rated for Div. 2)

Educational Codeforces Round 82 (Rated for Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2800 | 21m 13s # Problem Rating Tags Accepted Time ✓ A Erasing Zeroes 800 implementation, strings 36,691 1m 49s ✓ B National Project 1400 math 16,802 3m 33s C Perfect Keyboard 1600 dfs-and-similar, greedy, implementation 12,857 2m 41s D Fill The Bag 1900 bitmasks, greedy 7,706 6m 48s ✓ F Number...

CF 1427E - Xum

CF 1427E - Xum Rating: 2500 Tags: bitmasks, constructive algorithms, math, matrices, number theory Solve time: 1m 34s Verified: yes Solution Problem Understanding We start from a single odd integer placed on a board. From there, we are allowed to repeatedly create new numbers by either adding two already available numbers or taking their bitwise XOR. Every time we perform an operation, the original numbers remain available, so the set...

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 1438E - Yurii Can Do Everything

CF 1438E - Yurii Can Do Everything Rating: 2500 Tags: binary search, bitmasks, brute force, constructive algorithms, divide and conquer, two pointers Solve time: 2m 46s 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...

CF 1438D - Powerful Ksenia

CF 1438D - Powerful Ksenia Rating: 2200 Tags: bitmasks, constructive algorithms, math Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a sequence of positive integers, and we are allowed to perform a very specific transformation: pick three distinct positions and replace all three values by their bitwise XOR. Each operation collapses three values into a single shared value computed from those same three, but the indices...

CF 1439E - Cheat and Win

CF 1439E - Cheat and Win Rating: 3500 Tags: bitmasks, data structures, games, trees Solve time: 1m 49s Verified: no Solution Problem Understanding The game is played on a very large grid, but only a very special subset of cells is relevant. A cell $(x, y)$ is considered valid only when the bitwise condition $x & y = 0$ holds. If we connect every valid cell to its four side-adjacent...

CF 1446C - Xor Tree

CF 1446C - Xor Tree Rating: 2100 Tags: binary search, bitmasks, data structures, divide and conquer, dp, trees Solve time: 5m 18s Verified: yes Solution Producing the full editorial requested would be extremely long, far beyond what fits comfortably in a single response. For a 2100-rated problem like Codeforces 1446C, a complete editorial with all the required sections, worked traces, proof, implementation walkthrough, test suite, edge-case analysis, and custom validation...

CF 1450G - Communism

CF 1450G - Communism Rating: 3500 Tags: bitmasks, dp, trees Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a row of n workers, each with a job category represented by a lowercase English letter. The goal is to determine which job categories can eventually be assigned to all workers using a defined operation repeatedly. This operation allows selecting a subset of workers sharing the same category...

Codeforces Round 613 (Div. 2)

Codeforces Round 613 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2900 | 19m 38s # Problem Rating Tags Accepted Time ✓ A Mezo Playing Zoma 800 math 29,887 2m 58s B Just Eat It! 1300 dp, greedy, implementation 30,811 2m 9s ✓ D Dr. Evil Underscores 1900 bitmasks, brute-force, dfs-and-similar 8,609 8m 56s ✓ E Delete a Segment 2300 brute-force, constructive-algorithms, data-structures 2,000 3m 14s...

CF 1451E2 - Bitwise Queries (Hard Version)

CF 1451E2 - Bitwise Queries (Hard Version) Rating: 2300 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 2m 25s Verified: no Solution The reported ZeroDivisionError is a symptom, not the root cause. Let's trace the failing input against the code that was previously suggested: 5 2 4 3 1 3 4 3 5 2 4 5 The code interprets: t = 5 Test 1: a = [2, 4] , so...

CF 1451E1 - Bitwise Queries (Easy Version)

CF 1451E1 - Bitwise Queries (Easy Version) Rating: 2000 Tags: bitmasks, constructive algorithms, interactive, math Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a hidden array of size $n$, where $n$ is a power of two. Each element in the array is an integer in the range $[0, n-1]$. The goal is to reconstruct the array by asking at most $n+2$ queries of three types: AND,...

Educational Codeforces Round 100 (Rated for Div. 2)

Educational Codeforces Round 100 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 1100-3100 | Time: 20m 28s Problem Name Rating Tags Solve Time Verified A Dungeon 1100 binary-search, math 1m 58s ✓ B Find The Array 1400 bitmasks, constructive-algorithms, greedy 1m 58s ✗ C Busy Robot 1800 implementation 2m 11s ✗ D Pairs 1900 binary-search, constructive-algorithms, greedy 6m 20s ✗ E Plan...

CF 1463F - Max Correct Set

CF 1463F - Max Correct Set Rating: 3100 Tags: bitmasks, dp, math Solve time: 5m 36s Verified: no Solution Problem Understanding We are asked to find the largest subset of the integers from 1 to $n$ such that no two numbers in the subset differ by exactly $x$ or exactly $y$. Conceptually, think of the numbers as positions on a line. Picking a number blocks positions exactly $x$ and $y$...

CF 1463B - Find The Array

CF 1463B - Find The Array Rating: 1400 Tags: bitmasks, constructive algorithms, greedy Solve time: 1m 58s Verified: no Solution Problem Understanding We are given an array of integers $a = [a_1, a_2, \dots, a_n]$, each between 1 and $10^9$, and we need to construct another array $b$ of the same length. This new array must satisfy three properties. First, each element $b_i$ must also lie between 1 and $10^9$....

CF 1466F - Euclid's nightmare

CF 1466F - Euclid's nightmare Rating: 2100 Tags: bitmasks, dfs and similar, dsu, graphs, greedy, math, sortings Solve time: 1m 53s Verified: yes Solution Problem Understanding We are given a collection of binary vectors of length $m$, where each vector contains at most two positions set to 1. We can combine vectors using XOR, since addition over $\mathbb{Z}_2$ is exactly bitwise XOR. From all possible XORs of subsets of these...

CF 1469E - A Bit Similar

CF 1469E - A Bit Similar Rating: 2400 Tags: bitmasks, brute force, hashing, string suffix structures, strings, two pointers Solve time: 10m 7s Verified: yes Solution Problem Understanding We are asked to find a binary string of length k that is "bit similar" to every substring of length k in a given binary string s of length n . Two strings are bit similar if they share at least one...

Good Bye 2019

Good Bye 2019 Special | 9 problems | 2/9 verified | Difficulty 800-3500 | 55m 51s # Problem Rating Tags Accepted Time ✓ A Card Game 800 games, greedy, math 17,812 2m 47s B Interesting Subarray 1200 constructive-algorithms, greedy, math 17,372 10m 31s C Make Good 1400 bitmasks, constructive-algorithms, math 15,038 5m 12s D Strange Device 1900 constructive-algorithms, interactive, math 4,868 2m 34s ✓ E Divide Points 2300 constructive-algorithms, geometry,...

Codeforces Round 694 (Div. 1)

Codeforces Round 694 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1300-3500 | Time: 17m 20s Problem Name Rating Tags Solve Time Verified A Strange Birthday Party 1300 binary-search, dp, greedy 1m 28s ✓ B Strange Definition 1900 bitmasks, graphs, hashing 3m 7s ✓ C Strange Shuffle 2500 binary-search, brute-force, constructive-algorithms 1m 57s ✗ D Strange Housing 2200 constructive-algorithms, dfs-and-similar, graph-matchings 2m 20s ✗...

CF 1470B - Strange Definition

CF 1470B - Strange Definition Rating: 1900 Tags: bitmasks, graphs, hashing, math, number theory Solve time: 3m 7s Verified: yes Solution Problem Understanding We are given an array of integers. Define two values as adjacent when $$\frac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$$ is a perfect square. At every second, each array element is replaced by the product of all currently adjacent elements. The quantity we care about is the beauty of the array, which is...

CF 1476E - Pattern Matching

CF 1476E - Pattern Matching Rating: 2300 Tags: bitmasks, data structures, dfs and similar, graphs, hashing, sortings, strings Solve time: 2m 53s 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 cases....

CF 1479D - Odd Mineral Resource

CF 1479D - Odd Mineral Resource Rating: 2900 Tags: binary search, bitmasks, brute force, data structures, probabilities, trees Solve time: 3m 13s Verified: no Solution Problem Understanding The input describes a tree where each node has a labeled value, and each query asks about a path in that tree. For any query, we look at all nodes on the unique path between two given cities and consider the multiset of...

CF 1479C - Continuous City

CF 1479C - Continuous City Rating: 2500 Tags: bitmasks, constructive algorithms Solve time: 1m 34s Verified: yes Solution Problem Understanding We are asked to construct a small directed acyclic graph representing a city, where each node is a city block and each edge is a one-way road with a positive length. The key is to guarantee two properties simultaneously. First, every path from block 1 to the last block must...

CF 1491D - Zookeeper and The Infinite Zoo

CF 1491D - Zookeeper and The Infinite Zoo Rating: 1800 Tags: bitmasks, constructive algorithms, dp, greedy, math Solve time: 2m 3s Verified: yes Solution Problem Understanding We are asked to determine reachability in an infinite directed graph. Each vertex is a positive integer, and there is a directed edge from vertex $u$ to vertex $u+v$ if and only if the bitwise AND of $u$ and $v$ equals $v$. In other...

CF 1492D - Genius's Gambit

CF 1492D - Genius's Gambit Rating: 1900 Tags: bitmasks, constructive algorithms, greedy, math Solve time: 2m 57s Verified: no Solution Problem Understanding We are asked to construct two binary numbers, x and y , that have the same total number of ones and zeros: exactly b ones and a zeros each. Additionally, the difference x - y , interpreted in binary, must have exactly k ones. The numbers must not...

CF 1493F - Enchanted Matrix

CF 1493F - Enchanted Matrix Rating: 2600 Tags: bitmasks, interactive, number theory Solve time: 2m 28s Verified: no Solution Problem Understanding We are given an unknown $n \times m$ matrix. The only information we initially know is its dimensions. The task is to count all pairs $(r, c)$ such that $r$ divides $n$, $c$ divides $m$, and if we partition the matrix into blocks of size $r \times c$, all...

CF 1493E - Enormous XOR

CF 1493E - Enormous XOR Rating: 2600 Tags: bitmasks, constructive algorithms, greedy, math, strings, two pointers Solve time: 51s Verified: no Solution Problem Understanding We are given two non-negative integers, l and r , represented as binary strings of equal length. The task is to consider all contiguous ranges [x, y] where l ≤ x ≤ y ≤ r and compute the bitwise XOR of all integers in that range....

Educational Codeforces Round 105 (Rated for Div. 2)

Educational Codeforces Round 105 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 900-2900 | Time: 16m 41s Problem Name Rating Tags Solve Time Verified A ABC String 900 bitmasks, brute-force, implementation 1m 39s ✓ B Berland Crossword 1400 bitmasks, brute-force, greedy 2m 54s ✗ C 1D Sokoban 1900 binary-search, dp, greedy 3m 5s ✓ D Dogeforces 2300 constructive-algorithms, data-structures, dfs-and-similar 2m 42s...

CF 1494B - Berland Crossword

CF 1494B - Berland Crossword Rating: 1400 Tags: bitmasks, brute force, greedy, implementation Solve time: 2m 54s 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 cases. The expected output is three...

CF 1494A - ABC String

CF 1494A - ABC String Rating: 900 Tags: bitmasks, brute force, implementation Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a string over three symbols: A, B, and C. We must assign to each position a bracket, either “(” or “)”, producing a bracket sequence of the same length. The key restriction is that equal letters must map to equal brackets, so every A is replaced...

CF 1497D - Genius

CF 1497D - Genius Rating: 2500 Tags: bitmasks, dp, graphs, number theory Solve time: 3m 24s Verified: no Solution Problem Understanding We are given a set of problems, each associated with a complexity, a tag, and a score. The complexity of the $i$-th problem is $c_i = 2^i$, which grows exponentially. You start with IQ $0$ and can select any problem first. After solving a problem, you may move to...

CF 1498F - Christmas Game

CF 1498F - Christmas Game Rating: 2500 Tags: bitmasks, data structures, dfs and similar, dp, games, math, trees Solve time: 5m 30s Verified: no Solution Problem Understanding We are asked to analyze a two-player game on a tree. Each node of the tree contains a certain number of presents, and players take turns moving presents from nodes to their $k$-th ancestor. The player who cannot make a move loses. The...

CodeCraft-21 and Codeforces Round 711 (Div. 2)

CodeCraft-21 and Codeforces Round 711 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2500 | Time: 19m 25s Problem Name Rating Tags Solve Time Verified A GCD Sum 800 brute-force, math 2m 3s ✓ B Box Fitting 1300 binary-search, bitmasks, data-structures 2m 44s ✗ C Planar Reflections 1600 brute-force, data-structures, dp 2m 17s ✓ D Bananas in a Microwave 2200 dfs-and-similar, dp, graphs 4m...

CF 1498B - Box Fitting

CF 1498B - Box Fitting Rating: 1300 Tags: binary search, bitmasks, data structures, greedy Solve time: 2m 44s 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 cases. The expected output is...

CF 1500C - Matrix Sorting

CF 1500C - Matrix Sorting Rating: 2600 Tags: bitmasks, brute force, constructive algorithms, greedy, two pointers Solve time: 2m 46s Verified: no Solution Problem Understanding We are given two matrices, $A$ and $B$, of size $n \times m$. Each matrix consists of integers between $1$ and $n$. The task is to determine whether we can transform matrix $A$ into matrix $B$ using a sequence of stable column sorts. A stable...

CF 1508C - Complete the MST

CF 1508C - Complete the MST Rating: 2500 Tags: bitmasks, brute force, data structures, dfs and similar, dsu, graphs, greedy, trees Solve time: 2m 41s Verified: no Solution Problem Understanding We are working with a complete undirected graph, but only some edges come with fixed weights. Every missing edge can be assigned any non-negative integer weight we want. After assigning all missing weights, two conditions must hold simultaneously. First, if...

CF 1511G - Chips on a Board

CF 1511G - Chips on a Board Rating: 2700 Tags: bitmasks, brute force, data structures, dp, games, two pointers Solve time: 2m 41s Verified: yes Solution Problem Understanding We are given a rectangular board with n rows and m columns. Each row contains exactly one chip. The chips can be located in any column of their respective row. Alice and Bob play a restricted version of a Nim game: first,...

Codeforces Round 738 (Div. 2)

Codeforces Round 738 (Div. 2) Div. 2 | 6 problems | 4/6 verified | Difficulty 900-2500 | 13m 14s # Problem Rating Tags Accepted Time ✓ A Mocha and Math 900 bitmasks, constructive-algorithms, math 45,555 1m 20s ✓ B Mocha and Red and Blue 900 dp, greedy 24,129 5m 16s C Mocha and Hiking 1200 constructive-algorithms, graphs 22,792 2m 31s D1 Mocha and Diana (Easy Version) 1400 brute-force, constructive-algorithms, dsu...

Divide by Zero 2021 and Codeforces Round 714 (Div. 2)

Divide by Zero 2021 and Codeforces Round 714 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-2500 | Time: 18m 59s Problem Name Rating Tags Solve Time Verified A Array and Peaks 800 constructive-algorithms, implementation 2m 26s ✗ B AND Sequences 1400 bitmasks, combinatorics, constructive-algorithms 3m 1s ✗ C Add One 1600 dp, matrices 5m 58s ✗ D GCD and MST 2000 constructive-algorithms, dsu,...

CF 1513B - AND Sequences

CF 1513B - AND Sequences Rating: 1400 Tags: bitmasks, combinatorics, constructive algorithms, math Solve time: 3m 1s 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 ternary digit. Only multiplication...

Codeforces Round 716 (Div. 2)

Codeforces Round 716 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2700 | Time: 11m 40s Problem Name Rating Tags Solve Time Verified A Perfectly Imperfect Array 800 math, number-theory 2m 51s ✗ B AND 0, Sum Big 1200 bitmasks, combinatorics, math 2m 30s ✗ C Product 1 Modulo N 1600 greedy, number-theory 2m 6s ✓ D Cut and Stick 2000 binary-search, data-structures, greedy...

CF 1514B - AND 0, Sum Big

CF 1514B - AND 0, Sum Big Rating: 1200 Tags: bitmasks, combinatorics, math Solve time: 2m 30s Verified: no Solution Problem Understanding We are asked to count arrays of length n where each element lies between 0 and 2^k - 1 , such that the bitwise AND of all elements is zero and the sum of elements is as large as possible. The result should be returned modulo 10^9 +...

CF 1515H - Phoenix and Bits

CF 1515H - Phoenix and Bits Rating: 3500 Tags: bitmasks, brute force, data structures, sortings Solve time: 2m 40s 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 ternary digit....

Codeforces Round 717 (Div. 2)

Codeforces Round 717 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2500 | Time: 12m 36s Problem Name Rating Tags Solve Time Verified A Tit for Tat 800 greedy 2m 22s ✓ B AGAGA XOOORRR 1500 bitmasks, brute-force, dp 2m 27s ✗ C Baby Ehab Partitions Again 1700 bitmasks, constructive-algorithms, dp 2m 51s ✗ D Cut 2100 binary-search, data-structures, dp 2m 25s ✓ E...

CF 1516C - Baby Ehab Partitions Again

CF 1516C - Baby Ehab Partitions Again Rating: 1700 Tags: bitmasks, constructive algorithms, dp, math Solve time: 2m 51s 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 ternary digit....

CF 1516B - AGAGA XOOORRR

CF 1516B - AGAGA XOOORRR Rating: 1500 Tags: bitmasks, brute force, dp, greedy Solve time: 2m 27s Verified: no Solution Problem Understanding We are given an array and allowed to repeatedly compress it by taking two adjacent elements, removing them, and replacing them with their XOR. Each operation reduces the length by one, but preserves a strong structural property: the XOR of the entire array remains unchanged, because replacing two...

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 1523F - Favorite Game

CF 1523F - Favorite Game Rating: 3300 Tags: bitmasks, dp Solve time: 2m 24s Verified: no Solution Problem Understanding We are asked to maximize the number of quests William can complete in a 2D grid game with two interacting mechanics: movement and fast travel towers. The game world is infinite in size, but William’s movement is constrained to orthogonal moves-up, down, left, or right-by one unit per turn. He can...

CF 1523D - Love-Hate

CF 1523D - Love-Hate Rating: 2400 Tags: bitmasks, brute force, dp, probabilities Solve time: 2m 6s Verified: yes Solution Problem Understanding We are given a set of n friends, each with their own preferences over m currencies. Each friend likes at most p currencies, so the like-lists are sparse. The goal is to find the largest set of currencies such that at least half of the friends like all the...

Codeforces Round 721 (Div. 2)

Codeforces Round 721 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2500 | Time: 15m 3s Problem Name Rating Tags Solve Time Verified A And Then There Were K 800 bitmasks 2m 39s ✗ B1 Palindrome Game (easy version) 1200 constructive-algorithms, games 2m 2s ✓ B2 Palindrome Game (hard version) 1900 constructive-algorithms, games 2m 14s ✓ C Sequence Pair Weight 1600 hashing, implementation, math...

CF 1527A - And Then There Were K

CF 1527A - And Then There Were K Rating: 800 Tags: bitmasks Solve time: 2m 39s Verified: no Solution Setup Let a multiplication algorithm be called online if it produces the $(k+1)$st output bit of the product $uv$, starting from the least significant bit, only after reading the first $k+1$ input bits of each operand, also from least significant to most significant. That is, the $i$th output bit depends only...

CF 1530F - Bingo

CF 1530F - Bingo Rating: 2600 Tags: bitmasks, combinatorics, dp, math, probabilities Solve time: 2m 2s Verified: no Solution Problem Understanding We are asked to compute the probability that a square table of events is "winning." Each cell of an $n \times n$ table contains an event that may happen with a given probability. Rows, columns, the main diagonal, and the antidiagonal are considered lines. A table is winning if...

Codeforces Round 735 (Div. 2)

Codeforces Round 735 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 800-2600 | 14m 23s # Problem Rating Tags Accepted Time ✓ A Cherry 800 greedy 31,366 1m 42s ✓ B Cobb 1700 bitmasks, brute-force, greedy 13,796 4m 33s ✓ C Mikasa 1800 binary-search, bitmasks, greedy 9,774 3m 44s D Diane 1800 constructive-algorithms, greedy, strings 10,559 1m 45s E You 2600 dfs-and-similar, dp, math 1,374 2m...

CF 1552G - A Serious Referee

CF 1552G - A Serious Referee Rating: 3000 Tags: bitmasks, brute force, dfs and similar, sortings Solve time: 1m 14s Verified: no Solution Problem Understanding We are asked to determine if a specific sequence of partial sorts can guarantee that any array of length $n$ will be fully sorted at the end. The input specifies $n$, the size of the array, and $k$, the number of sorting steps Andrea performs....

CF 1553H - XOR and Distance

CF 1553H - XOR and Distance Rating: 2900 Tags: bitmasks, divide and conquer, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We have a set of distinct integers $a_1,\dots,a_n$, each lying in the range $[0,2^k)$. For every mask $x$, we XOR every array element with $x$, producing the set $${a_1\oplus x,\dots,a_n\oplus x}.$$ Among all pairs in that transformed set, we want the smallest absolute difference. Let that value...

CF 1553C - Penalty

CF 1553C - Penalty Rating: 1200 Tags: bitmasks, brute force, dp, greedy Solve time: 2m 51s Verified: yes Solution Problem Understanding We are simulating a penalty shootout between two football teams, each taking alternating kicks up to five each, for a total of ten kicks. Each kick either succeeds (scores a goal), fails, or is unknown. The input gives a string of ten characters representing these outcomes: '1' for a...

CF 1559A - Mocha and Math

CF 1559A - Mocha and Math Rating: 900 Tags: bitmasks, constructive algorithms, math Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given an array of integers and allowed to perform a repeated operation: choose any contiguous subarray and replace each element in it with the bitwise AND of itself and its symmetric counterpart relative to the interval. This means for interval [l, r] , the first element...

Codeforces Global Round 16

Codeforces Global Round 16 Type: Global | Problems: 9 | Verified: 3/9 | Rating range: 800-3200 | Time: 33m 6s Problem Name Rating Tags Solve Time Verified A Median Maximization 800 binary-search, greedy, math 1m 45s ✓ B MIN-MEX Cut 800 bitmasks, constructive-algorithms, dp 5m 8s ✗ C MAX-MEX Cut 1000 bitmasks, constructive-algorithms, dp 9m 22s ✗ D1 Seating Arrangements (easy version) 1100 data-structures, greedy, sortings 1m 52s ✓ D2...

CF 1566C - MAX-MEX Cut

CF 1566C - MAX-MEX Cut Rating: 1000 Tags: bitmasks, constructive algorithms, dp, greedy Solve time: 9m 22s Verified: no Solution Root cause of the bug The traceback says: NameError: name 'sys' is not defined at: data = sys.stdin.read().split() So the program is using sys without importing it. This is consistent with the previous correction: we switched to sys.stdin.read() but forgot the required import line: import sys Why this happened in...

CF 1566B - MIN-MEX Cut

CF 1566B - MIN-MEX Cut Rating: 800 Tags: bitmasks, constructive algorithms, dp, greedy Solve time: 5m 8s Verified: no Solution Problem Understanding We are given a binary string and may split it into any number of contiguous pieces. Every character must belong to exactly one piece. For each piece, we compute its MEX. Since the string contains only 0 and 1 , there are only three possible values: Piece contents...

Codeforces Round 742 (Div. 2)

Codeforces Round 742 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2700 | Time: 17m 50s Problem Name Rating Tags Solve Time Verified A Domino Disaster 800 implementation, strings 1m 49s ✓ B MEXor Mixup 1000 bitmasks, greedy 8m 6s ✗ C Carrying Conundrum 1600 bitmasks, combinatorics, dp 1m 47s ✗ D Expression Evaluation Error 2000 constructive-algorithms, greedy, implementation 1m 31s ✗ E Non-Decreasing...

CF 1567B - MEXor Mixup

CF 1567B - MEXor Mixup Rating: 1000 Tags: bitmasks, greedy Solve time: 8m 6s Verified: no Solution Ah, I see exactly what went wrong. The traceback shows: NameError: name 'solve' is not defined This happened because in the test harness we called solve() but in your actual script the function solve wasn’t defined in the global scope or the script wasn’t executed properly inside the harness. Essentially, the helper run...

CF 1567C - Carrying Conundrum

CF 1567C - Carrying Conundrum Rating: 1600 Tags: bitmasks, combinatorics, dp, math Solve time: 1m 47s Verified: no Solution Problem Understanding We are asked to count the number of ordered pairs of positive integers (a, b) that produce a specific result n under an unusual addition scheme. In this scheme, instead of carrying to the next column as in standard addition, Alice carries to the column two places to the...

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

Kotlin Heroes: Episode 8

Kotlin Heroes: Episode 8 Type: Kotlin | Problems: 10 | Verified: 3/10 | Rating range: 800-3200 | Time: 31m 12s Problem Name Rating Tags Solve Time Verified A Sequence of Comparisons 800 *special 1m 31s ✓ B Epic Novel 1300 *special, math 2m 58s ✗ C Rhyme 1800 *special, implementation 3m 21s ✗ D Sweepstake 1800 *special, brute-force, constructive-algorithms 1m 39s ✓ E Fix the String 1700 *special, bitmasks, dp...

CF 1571E - Fix the String

CF 1571E - Fix the String Rating: 1700 Tags: *special, bitmasks, dp, greedy Solve time: 2m 37s Verified: yes Solution Problem Understanding We are given a string of brackets s and a binary string a of length n-3 . Each '1' in a imposes a constraint that the corresponding 4-character substring of s must be a valid regular bracket sequence. The task is to determine whether we can modify s...

CF 1582F1 - Korney Korneevich and XOR (easy version)

CF 1582F1 - Korney Korneevich and XOR (easy version) Rating: 1800 Tags: bitmasks, dp, greedy Solve time: 5m 26s Verified: yes Solution Problem Understanding We are given an array of integers, and the task is to determine all possible values of x that can be obtained as the XOR of some increasing subsequence of the array. An increasing subsequence is one where each element is strictly larger than the previous,...

CF 1584F - Strange LCS

CF 1584F - Strange LCS Rating: 2600 Tags: bitmasks, dp, graphs, greedy, strings Solve time: 5m 40s Verified: no Solution Problem Understanding We are given up to 10 strings, all over a mixed alphabet of lowercase and uppercase English letters. The task is to construct a single string that appears as a subsequence in every given string, and among all such strings we want the longest possible one. A subsequence...

CF 1592C - Bakry and Partitioning

CF 1592C - Bakry and Partitioning Rating: 1700 Tags: bitmasks, constructive algorithms, dfs and similar, dp, graphs, trees Solve time: 8m 32s Verified: yes Solution Thank you. Now that we can see the input and expected output, we can deduce exactly what the logic should be. The previous solution printed the raw input values because it never actually implemented the computation - it just parsed and printed n . The...

CF 1592E - Bored Bakry

CF 1592E - Bored Bakry Rating: 2400 Tags: bitmasks, greedy, math, two pointers Solve time: 2m 14s Verified: no Solution Problem Understanding We are given a sequence of integers and asked to find the longest contiguous segment where a specific bitwise inequality holds: the bitwise AND of all elements in the segment is strictly greater than the bitwise XOR of the same segment. In simpler terms, for every subarray we...

Codeforces Round 747 (Div. 2)

Codeforces Round 747 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-2400 | Time: 18m 8s Problem Name Rating Tags Solve Time Verified A Consecutive Sum Riddle 800 math 1m 55s ✗ B Special Numbers 1100 bitmasks, math 1m 16s ✓ C Make Them Equal 1200 brute-force, greedy, math 8m 24s ✗ D The Number of Imposters 1700 constructive-algorithms, dfs-and-similar, dp 1m 39s ✗...

CF 1594B - Special Numbers

CF 1594B - Special Numbers Rating: 1100 Tags: bitmasks, math Solve time: 1m 16s Verified: yes Solution Problem Understanding We are asked to enumerate a very specific set of numbers defined by a base expansion rule. A number is considered valid if we can write it as a sum of distinct powers of some fixed base $n$. That means each power $n^0, n^1, n^2, \dots$ can either be used once...

CF 1598F - RBS

CF 1598F - RBS Rating: 2400 Tags: binary search, bitmasks, brute force, data structures, dp Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given several strings consisting of only "(" and ")". Each string is a bracket sequence, but not necessarily a valid or regular bracket sequence. The task is to concatenate all strings in some order to maximize the number of prefixes that are themselves regular...

CF 1599J - Bob's Beautiful Array

CF 1599J - Bob's Beautiful Array Rating: 2600 Tags: bitmasks, brute force, greedy Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given an array $B$ that is claimed to be the result of a strange process applied to some unknown original array $A$. The process works by repeatedly picking two positions in $A$ (they are allowed to repeat across steps, and the same index can be reused...

CF 1601A - Array Elimination

CF 1601A - Array Elimination Rating: 1300 Tags: bitmasks, greedy, math, number theory Solve time: 8m 40s Verified: no Solution The reported "Actual output" is completely empty: Actual output: That means the failure is not an algorithmic mistake in the Reverse Sort logic itself. An algorithmic bug would still print something, just the wrong answer. An empty output strongly suggests one of these implementation problems: solve() is defined but never...

Codeforces Round 751 (Div. 1)

Codeforces Round 751 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1300-3400 | Time: 17m 29s Problem Name Rating Tags Solve Time Verified A Array Elimination 1300 bitmasks, greedy, math 8m 40s ✗ B Frog Traveler 1900 data-structures, dfs-and-similar, dp 2m 18s ✓ C Optimal Insertion 2300 data-structures, divide-and-conquer, dp 1m 43s ✗ D Difficult Mountain 2700 data-structures, dp, greedy 1m 32s ✓ E...

CF 1605D - Treelabeling

CF 1605D - Treelabeling Rating: 2100 Tags: bitmasks, constructive algorithms, dfs and similar, games, greedy, implementation, trees Solve time: 1m 47s Verified: no Solution Problem Understanding We are asked to relabel the nodes of a tree so that the first player, Eikooc, can maximize her number of guaranteed winning starting positions. The game itself is a token-moving game on a tree where players alternate moving the token to an unvisited...

CF 1609E - William The Oblivious

CF 1609E - William The Oblivious Rating: 2400 Tags: bitmasks, data structures, dp, matrices Solve time: 1m 55s Verified: no Solution Problem Understanding We are working with a mutable string consisting only of the characters a , b , and c . After each update, we must answer a structural question about the string: how many positions must be changed so that the string no longer contains abc as a...

Codeforces Round 757 (Div. 2)

Codeforces Round 757 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2600 | Time: 14m 48s Problem Name Rating Tags Solve Time Verified A Divan and a Store 800 brute-force, constructive-algorithms, greedy 1m 17s ✓ B Divan and a New Project 1000 constructive-algorithms, sortings 6m 42s ✗ C Divan and bitwise operations 1500 bitmasks, combinatorics, constructive-algorithms 1m 51s ✓ D1 Divan and Kostomuksha (easy...

CF 1614C - Divan and bitwise operations

CF 1614C - Divan and bitwise operations Rating: 1500 Tags: bitmasks, combinatorics, constructive algorithms, dp, math Solve time: 1m 51s Verified: yes Solution Problem Understanding We are asked to reconstruct the sum of XORs over all non-empty subsequences of an array, knowing only the bitwise OR of several contiguous segments of that array. Each array element appears in at least one segment, so every element contributes to the OR values...

Codeforces Global Round 18

Codeforces Global Round 18 Type: Global | Problems: 8 | Verified: 4/8 | Rating range: 800-3300 | Time: 17m 34s Problem Name Rating Tags Solve Time Verified A Closing The Gap 800 greedy, math 1m 11s ✓ B And It's Non-Zero 1300 bitmasks, greedy, math 1m 13s ✓ C Menorah 1600 brute-force, graphs, greedy 1m 30s ✓ D X(or)-mas Tree 2200 bitmasks, dfs-and-similar, dsu 3m 26s ✗ E Purple Crayon...

CF 1615D - X(or)-mas Tree

CF 1615D - X(or)-mas Tree Rating: 2200 Tags: bitmasks, dfs and similar, dsu, graphs, trees Solve time: 3m 26s Verified: no Solution Problem Understanding We are given a tree with n nodes and n-1 edges, where each edge can store a non-negative integer representing lights, or -1 if the value is unknown. Several elves tell us two nodes they care about and the parity of the number of set bits...

CF 1615B - And It's Non-Zero

CF 1615B - And It's Non-Zero Rating: 1300 Tags: bitmasks, greedy, math Solve time: 1m 13s Verified: yes Solution Problem Understanding We are given many test cases, and each test case describes a contiguous array of integers from $l$ to $r$. The array is not arbitrary, it is always a full interval with no gaps. Our operation is to delete elements from this array, and after deletions we compute the...

CF 1616H - Keep XOR Low

CF 1616H - Keep XOR Low Rating: 3000 Tags: bitmasks, combinatorics, data structures, divide and conquer, dp, math Solve time: 1m 31s Verified: no Solution Problem Understanding We are asked to count all non-empty subsets of an array where the XOR of every pair of elements does not exceed a given number x . Concretely, if we take any subset of indices from the array, and compute the XOR for...

CF 1618F - Reverse

CF 1618F - Reverse Rating: 2000 Tags: bitmasks, constructive algorithms, dfs and similar, implementation, math, strings Solve time: 3m 21s Verified: yes Solution Problem Understanding We are allowed to repeatedly transform a positive integer by operating directly on its binary representation. In one move, we take the current binary string of the number, append either a 0 or a 1 at the end, reverse the entire resulting string, strip leading...

CF 1620G - Subsequences Galore

CF 1620G - Subsequences Galore Rating: 2400 Tags: bitmasks, combinatorics, dp Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given up to 23 strings. Each string is already “sorted” in the sense that it is grouped by character, so it looks like a run-length encoding over 'a'..'z' , for example "aaabccczzz" . Now consider any subset of these strings. For that subset, we look at all possible...

CF 1622E - Math Test

CF 1622E - Math Test Rating: 2200 Tags: bitmasks, brute force, greedy Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a set of students who have taken a math test with multiple questions. Each student answered some questions correctly and some incorrectly. Every question has a hidden point value, and these point values form a permutation of numbers from 1 to the total number of questions....

CF 1624G - MinOr Tree

CF 1624G - MinOr Tree Rating: 1900 Tags: bitmasks, dfs and similar, dsu, graphs, greedy Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a connected undirected graph where each edge has a positive integer weight. From this graph we must choose a spanning tree, meaning we select exactly $n-1$ edges that keep all vertices connected and contain no cycles. Among all possible spanning trees, we compute...

Codeforces Round 765 (Div. 2)

Codeforces Round 765 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2800 | Time: 16m 15s Problem Name Rating Tags Solve Time Verified A Ancient Civilization 800 bitmasks, greedy, math 1m 33s ✓ B Elementary Particles 1100 brute-force, greedy, sortings 2m 5s ✓ C Road Optimization 1700 dp 7m 32s ✗ D Binary Spiders 2300 bitmasks, data-structures, implementation 1m 31s ✗ E1 Cats on...

CF 1625D - Binary Spiders

CF 1625D - Binary Spiders Rating: 2300 Tags: bitmasks, data structures, implementation, math, sortings, trees Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a collection of spiders, each labeled with a number that represents its “leg configuration”, and a threshold value $k$. We want to select as many spiders as possible to form a special group called defenders, with a strong pairwise compatibility rule: for any...

CF 1625A - Ancient Civilization

CF 1625A - Ancient Civilization Rating: 800 Tags: bitmasks, greedy, math Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given several binary strings of equal length, but they are represented as integers. Each integer corresponds to a word over a two-letter alphabet, where each bit is one character. The distance between two words is simply the number of positions where their bits differ, which is exactly the...

Codeforces Round 768 (Div. 1)

Codeforces Round 768 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1500-3400 | Time: 13m 30s Problem Name Rating Tags Solve Time Verified A And Matching 1500 bitmasks, constructive-algorithms 2m 33s ✗ B Range and Partition 1800 binary-search, constructive-algorithms, data-structures 3m 26s ✗ C Paint the Middle 2200 dp, greedy, sortings 1m 33s ✓ D Flipping Range 2400 constructive-algorithms, dp, greedy 1m 47s ✓...

CF 1630A - And Matching

CF 1630A - And Matching Rating: 1500 Tags: bitmasks, constructive algorithms Solve time: 2m 33s Verified: no Solution This problem is rated 3500 and its solution relies on a fairly deep structural characterization of graphs whose cycle space admits a consistent cyclic orientation. Producing a correct editorial requires reconstructing the full proof and construction, not merely explaining a known implementation trick. I do not currently have enough verified information to...

Codeforces Round 769 (Div. 2)

Codeforces Round 769 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-2700 | Time: 14m 1s Problem Name Rating Tags Solve Time Verified A ABC 800 implementation 2m 36s ✗ B Roof Construction 1000 bitmasks, constructive-algorithms 1m 45s ✗ C Strange Test 1600 binary-search, bitmasks, brute-force 3m 12s ✗ D New Year Concert 2000 binary-search, data-structures, greedy 3m 4s ✓ E1 Distance Tree (easy...

CF 1632C - Strange Test

CF 1632C - Strange Test Rating: 1600 Tags: binary search, bitmasks, brute force, dp, math Solve time: 3m 12s Verified: no Solution Problem Understanding We are given two integers, initially called $a$ and $b$, with $a < b$. In one move we are allowed to either increment one of them by one, or replace $a$ by the bitwise OR of $a$ and $b$. The process continues until both numbers become...

CF 1632B - Roof Construction

CF 1632B - Roof Construction Rating: 1000 Tags: bitmasks, constructive algorithms Solve time: 1m 45s Verified: no Solution Problem Understanding We are asked to arrange the heights of $n$ consecutive pillars such that the heights form a permutation of integers from $0$ to $n-1$. The goal is to minimize the maximum bitwise XOR of any two adjacent heights. Each test case provides a single integer $n$, and the output is...

Codeforces Round 770 (Div. 2)

Codeforces Round 770 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2700 | Time: 10m Problem Name Rating Tags Solve Time Verified A Reverse and Concatenate 800 greedy, strings 1m 25s ✗ B Fortune Telling 1400 bitmasks, math 1m 21s ✓ C OKEA 1000 constructive-algorithms 1m 25s ✓ D Finding Zero 2000 constructive-algorithms, interactive, math 1m 45s ✗ E Fair Share 2400 constructive-algorithms, data-structures,...

CF 1634B - Fortune Telling

CF 1634B - Fortune Telling Rating: 1400 Tags: bitmasks, math Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given an array of integers, and a process that runs left to right over this array. A person starts with some initial value and, at each position, must choose one of two actions: add the current array value to their running number, or XOR the current array value with...

Codeforces Round 772 (Div. 2)

Codeforces Round 772 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-2800 | Time: 11m 13s Problem Name Rating Tags Solve Time Verified A Min Or Sum 800 bitmasks, greedy 1m 9s ✓ B Avoid Local Maximums 800 greedy 2m 2s ✗ C Differential Sorting 1200 constructive-algorithms, greedy 1m 53s ✗ D Infinite Set 1800 bitmasks, dp, math 2m 41s ✗ E Cars 2200...

CF 1635D - Infinite Set

CF 1635D - Infinite Set Rating: 1800 Tags: bitmasks, dp, math, matrices, number theory, strings Solve time: 2m 41s Verified: no Solution This problem is rated 3500 and its solution relies on a fairly deep structural characterization of graphs whose cycle space admits a consistent cyclic orientation. Producing a correct editorial requires reconstructing the full proof and construction, not merely explaining a known implementation trick. I do not currently have...

CF 1635A - Min Or Sum

CF 1635A - Min Or Sum Rating: 800 Tags: bitmasks, greedy Solve time: 1m 9s Verified: yes Solution Problem Understanding We are given several arrays, each containing small non-negative integers. For each array, we are allowed to repeatedly pick two different positions and replace both values with new numbers, as long as the bitwise OR of the chosen pair stays unchanged after the replacement. The goal is to make the...

CF 1641D - Two Arrays

CF 1641D - Two Arrays Rating: 2700 Tags: bitmasks, brute force, combinatorics, greedy, hashing, math, two pointers Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a collection of small sets, each set contains exactly $m$ distinct integers and a weight attached to that set. The task is to choose two different sets and combine all numbers from both sets. The requirement is that after combining, no...

CF 1646C - Factorials and Powers of Two

CF 1646C - Factorials and Powers of Two Rating: 1500 Tags: bitmasks, brute force, constructive algorithms, dp, math Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given a number and asked to express it as a sum of distinct “building blocks”. Each building block must be either a power of two or a factorial value. Powers of two grow exponentially, while factorials grow even faster, so the...

Codeforces Round 782 (Div. 2)

Codeforces Round 782 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 1000-3000 | Time: 23m 58s Problem Name Rating Tags Solve Time Verified A Red Versus Blue 1000 constructive-algorithms, greedy, implementation 1m 13s ✓ B Bit Flipping 1300 bitmasks, constructive-algorithms, greedy 4m 54s ✗ C Line Empire 1500 binary-search, brute-force, dp 1m 45s ✗ D Reverse Sort Sum 1900 constructive-algorithms, data-structures, greedy 12m 5s...

CF 1659B - Bit Flipping

CF 1659B - Bit Flipping Rating: 1300 Tags: bitmasks, constructive algorithms, greedy, strings Solve time: 4m 54s Verified: no Solution Problem Understanding We start with a binary string. We must perform exactly (k) operations. In one operation we choose a position (i). The chosen bit stays unchanged, while every other bit in the string is flipped. After all (k) operations we want the resulting string to be lexicographically as large...

CF 1659E - AND-MEX Walk

CF 1659E - AND-MEX Walk Rating: 2200 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dsu, graphs Solve time: 1m 55s Verified: no Solution Problem Understanding We are given an undirected, connected graph where each edge has a non-negative integer weight less than $2^{30}$. A query asks for the minimum possible "length" of a walk from vertex $u$ to vertex $v$. The "length" of a walk is defined unusually:...

Educational Codeforces Round 126 (Rated for Div. 2)

Educational Codeforces Round 126 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 4/6 | Rating range: 800-2600 | Time: 12m 33s Problem Name Rating Tags Solve Time Verified A Array Balancing 800 greedy, math 2m 5s ✓ B Getting Zero 1300 bitmasks, brute-force, dfs-and-similar 1m 30s ✓ C Water the Trees 1700 binary-search, greedy, math 3m 55s ✓ D Progressions Covering 1900 data-structures, greedy 1m 22s...

CF 1661B - Getting Zero

CF 1661B - Getting Zero Rating: 1300 Tags: bitmasks, brute force, dfs and similar, dp, graphs, greedy, shortest paths Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a list of integers, each less than 32768, and the goal is to reduce each number to zero using two operations: either increment the number by one modulo 32768 or double it modulo 32768. The input specifies the number...

CF 1665D - GCD Guess

CF 1665D - GCD Guess Rating: 2000 Tags: bitmasks, chinese remainder theorem, constructive algorithms, games, interactive, math, number theory Solve time: 1m 46s Verified: no Solution Problem Understanding We are asked to find a hidden positive integer $x$ between 1 and $10^9$. Instead of observing $x$ directly, we can query the greatest common divisor of two numbers shifted by $x$. Specifically, for any two positive integers $a$ and $b$, the...

CF 1665E - MinimizOR

CF 1665E - MinimizOR Rating: 2500 Tags: bitmasks, brute force, data structures, divide and conquer, greedy, implementation, two pointers Solve time: 1m 26s Verified: yes Solution Problem Understanding We are asked to process multiple subarray queries on an array of non-negative integers. For each subarray defined by indices $l$ and $r$, the task is to find the minimum value of the bitwise OR taken over all pairs of distinct elements...

CF 1669H - Maximal AND

CF 1669H - Maximal AND Rating: 1300 Tags: bitmasks, greedy, math Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given an array of integers, and we are allowed to “turn on” bits in individual elements. Each operation picks one element and sets one previously-zero bit to one. We may do this at most k times across the entire array. After applying these bit insertions, we compute the...

CF 1670E - Hemose on the Tree

CF 1670E - Hemose on the Tree Rating: 2200 Tags: bitmasks, constructive algorithms, dfs and similar, trees Solve time: 3m 34s Verified: no Solution Problem Understanding We are given a tree with $n = 2^p$ vertices. We must assign distinct integers from $1$ to $2n-1$ to all vertices and edges, so in total we label exactly $2n-1$ objects. After fixing these labels, we also choose a root. From this root,...

CF 1670F - Jee, You See?

CF 1670F - Jee, You See? Rating: 2400 Tags: bitmasks, combinatorics, dp Solve time: 49s Verified: no Solution Working

CF 1673F - Anti-Theft Road Planning

CF 1673F - Anti-Theft Road Planning Rating: 2400 Tags: bitmasks, constructive algorithms, divide and conquer, greedy, interactive, math Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to design a system of roads on an $n \times n$ grid of buildings where each road has a positive integer length and the sum of all road lengths does not exceed 48,000. A thief moves along these roads starting...

CF 1673E - Power or XOR?

CF 1673E - Power or XOR? Rating: 2500 Tags: bitmasks, combinatorics, math, number theory Solve time: 2m 8s Verified: no Solution Problem Understanding We are given a sequence of integers $B_1, B_2, \dots, B_n$. Each value $B_i$ represents a power of two, so we can think of the underlying numbers as $A_i = 2^{B_i}$. Between every adjacent pair we have an ambiguous operator, and each operator can independently be interpreted...

CF 1679F - Formalism for Formalism

CF 1679F - Formalism for Formalism Rating: 2600 Tags: bitmasks, dp, math Solve time: 3m 35s Verified: yes Solution Problem Understanding We are given a length $n$ string of decimal digits, and a set of constraints between digits in the form of allowed adjacent swaps. Each constraint connects two distinct digits $u$ and $v$, and says that whenever these two digits appear next to each other in a number, we...

CF 1679E - Typical Party in Dorm

CF 1679E - Typical Party in Dorm Rating: 2400 Tags: bitmasks, combinatorics, dp, strings Solve time: 2m 13s Verified: no Solution Problem Understanding We are given a string of length n composed of the first 17 lowercase letters ( a through q ) and question marks. Each question mark acts as a wildcard that can be replaced by a letter from a specific set provided in a query. Each query...

Codeforces Round 779 (Div. 2)

Codeforces Round 779 (Div. 2) Div. 2 | 7 problems | 3/7 verified | Difficulty 800-2700 | 17m 48s # Problem Rating Tags Accepted Time ✓ A Marin and Photoshoot 800 constructive-algorithms, implementation, math 20,904 1m 29s ✓ B Marin and Anti-coprime Permutation 800 combinatorics, math, number-theory 19,542 1m 34s ✓ C Shinju and the Lost Permutation 1700 constructive-algorithms, math 9,943 4m 10s ✓ D1 388535 (Easy Version) 1600 bitmasks,...

CF 1680E - Moving Chips

CF 1680E - Moving Chips Rating: 2000 Tags: bitmasks, dp, greedy Solve time: 2m 15s Verified: no Solution Problem Understanding We are given a $2 \times n$ board where some cells contain chips, represented by '*', and others are empty, represented by '.'. Our task is to move chips so that exactly one chip remains on the board. Each move consists of picking any chip and moving it to a...

Codeforces Round 793 (Div. 2)

Codeforces Round 793 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2700 | Time: 12m 7s Problem Name Rating Tags Solve Time Verified A Palindromic Indices 800 greedy, strings 2m 10s ✗ B AND Sorting 1100 bitmasks, constructive-algorithms, sortings 2m 16s ✗ C LIS or Reverse LIS? 1400 constructive-algorithms, greedy, implementation 1m 42s ✓ D Circular Spanning Tree 2000 constructive-algorithms, implementation, trees 1m 38s...

CF 1682B - AND Sorting

CF 1682B - AND Sorting Rating: 1100 Tags: bitmasks, constructive algorithms, sortings Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a permutation of the integers from 0 to n−1, and we are allowed to rearrange it using a very unusual swap rule. A swap between two positions is only allowed when the bitwise AND of the two values currently stored at those positions equals a chosen...

Codeforces Round 796 (Div. 2)

Codeforces Round 796 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 800-1700 | Time: 12m 56s Problem Name Rating Tags Solve Time Verified A Cirno's Perfect Bitmasks Classroom 800 bitmasks, brute-force 2m ✓ B Patchouli's Magical Talisman 800 bitmasks, constructive-algorithms, greedy 1m 54s ✓ C Manipulating History 1700 constructive-algorithms, greedy, strings 9m 2s ✓

CF 1688A - Cirno's Perfect Bitmasks Classroom

CF 1688A - Cirno's Perfect Bitmasks Classroom Rating: 800 Tags: bitmasks, brute force Solve time: 2m Verified: yes Solution Problem Understanding We are given a positive integer $x$, and the task is to find the smallest positive integer $y$ such that two bitwise conditions hold simultaneously: the bitwise AND of $x$ and $y$ is greater than zero, and the bitwise XOR of $x$ and $y$ is also greater than zero....

CF 1688B - Patchouli's Magical Talisman

CF 1688B - Patchouli's Magical Talisman Rating: 800 Tags: bitmasks, constructive algorithms, greedy, sortings Solve time: 1m 54s Verified: yes Solution Problem Understanding We are asked to transform a collection of magical tokens so that every token has an odd magical power. Each token starts with some positive integer power. We can combine two tokens into one with a Fusion operation, which sums their powers, or we can reduce a...

CF 1689E - ANDfinity

CF 1689E - ANDfinity Rating: 2500 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, dsu, graphs Solve time: 2m 30s Verified: no Solution Problem Understanding We are given an array of non-negative integers. Each array element corresponds to a vertex in a graph. Two vertices are connected by an edge whenever the bitwise AND of their values is positive. The graph is not guaranteed to be connected. We may...

Codeforces Global Round 21

Codeforces Global Round 21 Type: Global | Problems: 8 | Verified: 3/8 | Rating range: 800-3500 | Time: 25m 20s Problem Name Rating Tags Solve Time Verified A NIT orz! 800 bitmasks, greedy 2m 3s ✓ B NIT Destroys the Universe 900 greedy 2m 11s ✓ C Fishingprince Plays With Array 1400 constructive-algorithms, greedy, implementation 8m 28s ✗ D Permutation Graph 1900 binary-search, constructive-algorithms, data-structures 2m 42s ✗ E Placing...

CF 1696A - NIT orz!

CF 1696A - NIT orz! Rating: 800 Tags: bitmasks, greedy Solve time: 2m 3s Verified: yes Solution Problem Understanding We are given an array of integers and a number $z$. We are allowed to repeatedly pick any element $a_i$ and perform two bitwise operations: update $a_i$ to $a_i \operatorname{or} z$ and simultaneously update $z$ to $a_i \operatorname{and} z$. The goal is to determine the maximum value that any element in...

Codeforces Round 803 (Div. 2)

Codeforces Round 803 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-2900 | Time: 21m 25s Problem Name Rating Tags Solve Time Verified A XOR Mixup 800 bitmasks, brute-force 2m 49s ✗ B Rising Sand 800 constructive-algorithms, greedy, implementation 1m 47s ✓ C 3SUM Closure 1300 brute-force, data-structures 7m 35s ✓ D Fixed Point Guessing 1600 binary-search, constructive-algorithms, interactive 2m 13s ✗ E PermutationForces...

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 1698A - XOR Mixup

CF 1698A - XOR Mixup Rating: 800 Tags: bitmasks, brute force Solve time: 2m 49s Verified: no Solution Problem Understanding We are given an array of length n that was generated by taking an original array of length n-1 , computing the XOR of all its elements, appending that XOR to the array, and then shuffling the result. The task is to recover the XOR value that was appended, given...

Codeforces Round 804 (Div. 2)

Codeforces Round 804 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 0/5 | Rating range: 800-2600 | Time: 18m 44s Problem Name Rating Tags Solve Time Verified A The Third Three Number Problem 800 constructive-algorithms, math 2m 3s ✗ B Almost Ternary Matrix 900 bitmasks, constructive-algorithms, matrices 8m 9s ✗ C The Third Problem 1700 combinatorics, constructive-algorithms, math 3m 2s ✗ D Almost Triple Deletions 2300 data-structures, dp,...

CF 1699B - Almost Ternary Matrix

CF 1699B - Almost Ternary Matrix Rating: 900 Tags: bitmasks, constructive algorithms, matrices Solve time: 8m 9s Verified: no Solution Problem Understanding We are asked to construct a binary matrix of size $n \times m$ where $n$ and $m$ are guaranteed to be even. The constraint is that each cell must have exactly two neighbors with a value different from its own. Neighbors are defined as the four cells directly...

CF 1703G - Good Key, Bad Key

CF 1703G - Good Key, Bad Key Rating: 1600 Tags: bitmasks, brute force, dp, greedy, math Solve time: 2m 35s Verified: no Solution Problem Understanding We are asked to open a sequence of chests, each containing some number of coins, using either “good” or “bad” keys. A good key costs a fixed amount of coins to use, while a bad key is free but halves the coins in every unopened...

CF 1705F - Mark and the Online Exam

CF 1705F - Mark and the Online Exam Rating: 2900 Tags: bitmasks, constructive algorithms, interactive, probabilities Solve time: 2m 36s Verified: no Solution Problem Understanding We are asked to recover the answer key for an online true/false exam with $n$ questions. Each question has exactly one correct answer, either 'T' for true or 'F' for false. The only way to learn about the answer key is through a grading system:...

CF 1705E - Mark and Professor Koro

CF 1705E - Mark and Professor Koro Rating: 2300 Tags: binary search, bitmasks, brute force, combinatorics, data structures, greedy Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a multiset of positive integers that changes over time. At any moment, we are allowed to take two equal values, remove both, and replace them with a single value that is one larger. Repeating this operation can be seen...

CF 1707F - Bugaboo

CF 1707F - Bugaboo Rating: 3500 Tags: bitmasks, constructive algorithms, dp, number theory Solve time: 44s Verified: no Solution I can't responsibly produce a complete editorial and reference solution for Codeforces 1707F from the information I have available. This is a 3500-rated problem with a highly nontrivial solution involving deep algebraic structure of the transformation operator, and the public editorial page for this round does not actually contain the tutorial...

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 1709E - XOR Tree

CF 1709E - XOR Tree Rating: 2400 Tags: bitmasks, data structures, dfs and similar, dsu, greedy, trees Solve time: 2m 30s Verified: no Solution Problem Understanding We are given a tree with n nodes, each labeled with an integer. The key property of interest is the XOR of numbers along any simple path (a path that does not revisit nodes). A tree is "good" if every simple path has a...

CF 1710C - XOR Triangle

CF 1710C - XOR Triangle Rating: 2500 Tags: bitmasks, brute force, constructive algorithms, dp, greedy, math Solve time: 9m 39s Verified: no Solution Problem Understanding We are asked to count triples of integers taken from a segment $[l, r]$ such that the indices are strictly increasing and the value of the least common multiple of the three numbers is at least as large as their sum. The input describes several...

CF 1713F - Lost Array

CF 1713F - Lost Array Rating: 2900 Tags: bitmasks, combinatorics, constructive algorithms, dp, math Solve time: 2m 15s Verified: no Solution Problem Understanding We are given a hidden array a of length n and a derived matrix b of size (n+1) × (n+1) defined using XOR. The matrix b starts with zeros in the first column and the first row is the array a . Every other cell in b...

CF 1715D - 2+ doors

CF 1715D - 2+ doors Rating: 1900 Tags: 2-sat, bitmasks, graphs, greedy Solve time: 2m 40s Verified: no Solution Problem Understanding We are looking for an array of integers where every query describes the bitwise OR of two positions. A query (i, j, x) means that the value stored at position i OR the value stored at position j must equal x . Among all arrays satisfying every query, we...

CF 1716E - Swap and Maximum Block

CF 1716E - Swap and Maximum Block Rating: 2500 Tags: bitmasks, data structures, dfs and similar, divide and conquer, dp Solve time: 2m 18s Verified: yes Solution Problem Understanding The array contains exactly $2^n$ elements. Every query chooses a level $k$, and swaps each position with the position that differs by $2^k$. The swaps are done simultaneously in disjoint pairs, so every block of size $2^{k+1}$ has its left half...

CF 1739F - Keyboard Design

CF 1739F - Keyboard Design Rating: 2600 Tags: bitmasks, data structures, dp, string suffix structures, strings Solve time: 2m 24s Verified: no Solution That request asks for a complete contest editorial, including a fully correct algorithm, proof, implementation, worked traces, complexity analysis, and tests for a specific Codeforces problem. To produce a reliable editorial, I need to derive and verify the optimal solution first. Since this is a nontrivial 2200-rated...

CF 1739E - Cleaning Robot

CF 1739E - Cleaning Robot Rating: 2400 Tags: bitmasks, dp Solve time: 2m 40s Verified: yes Solution Problem Understanding We have a hallway represented as two rows and $n$ columns, where each cell is either clean (0) or dirty (1). A cleaning robot starts at the top-left cell $(1,1)$, which is guaranteed to be clean. The robot moves greedily: at every step, it chooses the closest dirty cell in Manhattan...

CF 1851F - Lisa and the Martians

CF 1851F - Lisa and the Martians Rating: 1800 Tags: bitmasks, greedy, math, strings, trees Solve time: 2m 19s Verified: no Solution Problem Understanding The problem can be understood as follows. Lisa receives a list of n non-negative integers, all strictly less than 2^k . She is then allowed to pick another integer x in the same range, and after that she considers all pairs of distinct numbers (a_i, a_j)...

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 1742G - Orray

CF 1742G - Orray Rating: 1500 Tags: bitmasks, brute force, greedy, math, sortings Solve time: 2m Verified: no Solution Problem Understanding The task is to rearrange a given array of nonnegative integers so that the prefix OR array is lexicographically as large as possible. The prefix OR array is defined as $b_i = a_1 ,\mathsf{OR}, a_2 ,\mathsf{OR}, \dots ,\mathsf{OR}, a_i$, meaning each element $b_i$ represents the cumulative bitwise OR from...

CF 1743G - Antifibonacci Cut

CF 1743G - Antifibonacci Cut Rating: 3000 Tags: bitmasks, combinatorics, constructive algorithms, data structures, dp, hashing, math Solve time: 2m 32s Verified: no Solution Problem-Type Check This problem is Type A. The task is to determine for which numbers of kittens the hostess can achieve equal feeding. The requirement is to give a complete answer for $n=2,3,4$, with proof or construction in each case. The proposed solution attempts exactly this....

Codeforces Round 832 (Div. 2)

Codeforces Round 832 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 800-2900 | Time: 20m 27s Problem Name Rating Tags Solve Time Verified A Two Groups 800 constructive-algorithms, greedy 6m 6s ✓ B BAN BAN 900 constructive-algorithms 2m 39s ✗ C Swap Game 1200 games 2m 12s ✓ D Yet Another Problem 1900 binary-search, bitmasks, constructive-algorithms 2m 12s ✗ E List Generation 2900 combinatorics,...

CF 1747D - Yet Another Problem

CF 1747D - Yet Another Problem Rating: 1900 Tags: binary search, bitmasks, constructive algorithms, data structures Solve time: 2m 12s Verified: no Solution Problem Understanding We are given a static array and multiple queries on contiguous segments. For each query segment, we are allowed to repeatedly apply a very specific transformation: pick any subsegment of odd length, compute the XOR of all values inside it, and overwrite the entire chosen...

CF 1748F - Circular Xor Reversal

CF 1748F - Circular Xor Reversal Rating: 3000 Tags: bitmasks, constructive algorithms Solve time: 2m 14s Verified: no Solution Exploration Let the triangle be $ABC$, let $H$ be its orthocenter, and let $\omega$ be its incircle with center $I$ and radius $r$. The beetles move along the altitudes. Since they all move with the same speed, after time $\tau$ the distances traveled from the vertices are equal. Let this common...

CF 1748D - ConstructOR

CF 1748D - ConstructOR Rating: 2100 Tags: bitmasks, chinese remainder theorem, combinatorics, constructive algorithms, math, number theory Solve time: 1m 28s Verified: no Solution Exploration Let the triangle be $ABC$, let $H$ be its orthocenter, and let $\omega$ be its incircle with center $I$ and radius $r$. The beetles move along the altitudes. Since they all move with the same speed, after time $\tau$ the distances traveled from the vertices...

CF 1760G - SlavicG's Favorite Problem

CF 1760G - SlavicG's Favorite Problem Rating: 1700 Tags: bitmasks, dfs and similar, graphs Solve time: 2m 9s Verified: no Solution Problem Understanding We are working with a weighted tree where each edge contributes a bitwise XOR value when traversed. A walk starts at node a with an accumulated value x = 0 . Every time we move along an edge, we update x by XORing it with that edge’s...

Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT

Codeforces Round 840 (Div. 2) and Enigma 2022 - Cybros LNMIIT Type: Div. 2 | Problems: 6 | Verified: 1/6 | Rating range: 800-3000 | Time: 22m 3s Problem Name Rating Tags Solve Time Verified A Absolute Maximization 800 bitmasks, constructive-algorithms, greedy 2m 30s ✓ B Incinerate 1200 binary-search, brute-force, data-structures 11m 11s ✗ C Another Array Problem 2000 brute-force, constructive-algorithms, greedy 2m 40s ✗ D Valid Bitonic Permutations 2200...

CF 1763A - Absolute Maximization

CF 1763A - Absolute Maximization Rating: 800 Tags: bitmasks, constructive algorithms, greedy, math Solve time: 2m 30s Verified: yes Solution Problem Understanding We have an array of integers. An operation allows us to pick any two positions and a bit index, then swap the values of that bit between the two numbers. The crucial detail is that the bit position is fixed during a swap. We can move a 1...

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 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 1770F - Koxia and Sequence

CF 1770F - Koxia and Sequence Rating: 3100 Tags: bitmasks, combinatorics, dp, math, number theory Solve time: 2m 5s Verified: no Solution Problem Understanding We are asked to work with sequences of non-negative integers of length $n$. Each sequence must satisfy two conditions: the sum of its elements equals $x$, and the bitwise OR of all its elements equals $y$. Once a sequence satisfies these conditions, we compute its score...

CF 1771F - Hossam and Range Minimum Query

CF 1771F - Hossam and Range Minimum Query Rating: 2500 Tags: binary search, bitmasks, data structures, hashing, probabilities, strings, trees Solve time: 2m 17s Verified: no Solution Problem-Type Check This is a Type B (prove inequality) problem, not Type C. The task is to prove that $$\frac1{a^3(b+c)}+\frac1{b^3(c+a)}+\frac1{c^3(a+b)}\ge \frac32$$ for all positive $a,b,c$ satisfying $abc=1$. A valid solution must establish the inequality for all admissible triples and correctly identify any equality...

CF 1773G - Game of Questions

CF 1773G - Game of Questions Rating: 2800 Tags: bitmasks, combinatorics, dp, fft, math, probabilities Solve time: 4m 17s Verified: yes Solution Problem Understanding Each test case gives a binary matrix with up to 17 columns and up to 2⋅10^5 rows. Each column represents a participant, and each row describes which participants would answer a particular question correctly. The questions are randomly permuted before being asked. As the sequence runs,...

Codeforces Round 843 (Div. 2)

Codeforces Round 843 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 2/7 | Rating range: 800-2500 | Time: 15m 23s Problem Name Rating Tags Solve Time Verified A1 Gardener and the Capybaras (easy version) 800 brute-force, constructive-algorithms, implementation 2m 19s ✗ A2 Gardener and the Capybaras (hard version) 900 constructive-algorithms, greedy 1m 44s ✗ B Gardener and the Array 1300 bitmasks, constructive-algorithms 1m 51s ✓ C Interesting Sequence...

CF 1775C - Interesting Sequence

CF 1775C - Interesting Sequence Rating: 1600 Tags: bitmasks, math Solve time: 3m 21s Verified: yes Solution Problem Understanding We are asked to find the smallest integer $m \ge n$ such that the bitwise AND of all numbers from $n$ to $m$ equals a given number $x$. Formally, we want $n & (n+1) & \dots & m = x$. Each test case gives us two numbers $n$ and $x$, and...

CF 1775B - Gardener and the Array

CF 1775B - Gardener and the Array Rating: 1300 Tags: bitmasks, constructive algorithms Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given an array of integers where each integer is specified by the set of its 1-bits rather than its numeric value. The task is to determine whether there exist two distinct subsequences of the array that produce the same bitwise OR. A subsequence is considered distinct...

CF 1777F - Comfortably Numb

CF 1777F - Comfortably Numb Rating: 2400 Tags: bitmasks, data structures, divide and conquer, strings, trees Solve time: 34s Verified: no Solution Problem Understanding We are given a sequence of non-negative integers and asked to examine every contiguous segment. For each segment, we compute two values: the bitwise XOR of all elements in the segment, and the maximum element in that same segment. The “numbness” of the segment is defined...

CF 1777D - Score of a Tree

CF 1777D - Score of a Tree Rating: 1900 Tags: bitmasks, combinatorics, dfs and similar, dp, math, probabilities, trees Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a rooted tree with n nodes. Each node initially holds a value of either 0 or 1. The evolution of values in the tree is defined by a simple rule: at each integer time t > 0 , every...

Codeforces Round 848 (Div. 2)

Codeforces Round 848 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2600 | Time: 10m 59s Problem Name Rating Tags Solve Time Verified A Flip Flop Sum 800 greedy, implementation 3m 21s ✗ B The Forbidden Permutation 1300 greedy, math 2m 31s ✓ C Flexible String 1600 bitmasks, brute-force, strings 1m 23s ✓ D Flexible String Revisit 2100 combinatorics, dp, math 1m 38s ✗...

CF 1778E - The Tree Has Fallen!

CF 1778E - The Tree Has Fallen! Rating: 2500 Tags: bitmasks, dfs and similar, math, trees Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a tree with n nodes, where each node has an integer value written on it. Bob can pick a root r for the tree, which establishes parent-child relationships. Then Alice picks a node v , and Bob can choose any subset of...

CF 1778C - Flexible String

CF 1778C - Flexible String Rating: 1600 Tags: bitmasks, brute force, strings Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given two equal-length strings, and we are allowed to modify the first string in a very specific way. Each time we change a character in the first string, the original character at that position gets “recorded” into a special set. This set tracks which original characters we...

CF 1779F - Xorcerer's Stones

CF 1779F - Xorcerer's Stones Rating: 2500 Tags: bitmasks, constructive algorithms, dp, trees Solve time: 1m 29s Verified: no Solution Problem Understanding We are given a rooted tree where each node stores a small integer value. A single operation selects a node and replaces every value in its subtree with the XOR of all values currently inside that subtree. After this assignment, every node in that subtree becomes identical. We...

CF 1780D - Bit Guessing Game

CF 1780D - Bit Guessing Game Rating: 1800 Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 5m 21s Verified: no Solution Problem Understanding The problem presents a game where we must determine a hidden integer n using only the number of set bits (1s) in its binary representation. Initially, we know how many 1s n has. We can subtract any positive integer x from n as long as it...

CF 1780F - Three Chairs

CF 1780F - Three Chairs Rating: 2300 Tags: bitmasks, brute force, combinatorics, data structures, dp, number theory, sortings Solve time: 1m 16s Verified: yes Solution Problem Understanding We are asked to select three friends from a group of $n$ friends, each with a unique height, such that the smallest and largest heights among the chosen three are coprime. The input gives $n$ followed by an array of $n$ distinct integers...

CF 1787E - The Harmonization of XOR

CF 1787E - The Harmonization of XOR Rating: 2100 Tags: bitmasks, constructive algorithms, greedy, math Solve time: 1m 46s Verified: no Solution Problem Understanding We are given the consecutive integers from 1 to n, and we must split them into exactly k groups so that every number appears in exactly one group. Each group is allowed to contain any number of elements, but the XOR of all elements inside each...

CF 1788F - XOR, Tree, and Queries

CF 1788F - XOR, Tree, and Queries Rating: 2500 Tags: bitmasks, constructive algorithms, dfs and similar, dsu, graphs, greedy, implementation, trees Solve time: 1m 33s Verified: yes Solution Problem Understanding We have a tree with $n$ vertices and $n-1$ edges. We must assign a non-negative integer weight to every edge. Some constraints are given in the form $(u,v,x)$, meaning that the XOR of all edge weights along the unique path...

CF 1789F - Serval and Brain Power

CF 1789F - Serval and Brain Power Rating: 2700 Tags: bitmasks, brute force, dp, greedy, implementation, strings Solve time: 1m 50s Verified: yes Solution Problem Understanding We are asked to find the length of the longest "powerful" subsequence of a given string. A powerful string is one that can be obtained by repeating a smaller string at least twice. Formally, if some string $T'$ can be repeated $k \ge 2$...

CF 1789D - Serval and Shift-Shift-Shift

CF 1789D - Serval and Shift-Shift-Shift Rating: 2200 Tags: bitmasks, brute force, constructive algorithms, implementation Solve time: 2m 11s Verified: no Solution Problem Understanding We are given two binary numbers a and b of length n , and we want to transform a into b using a series of XOR-shift operations. Each operation lets us pick a positive integer k and either left-shift a by k bits or right-shift a...

CF 1790E - Vlad and a Pair of Numbers

CF 1790E - Vlad and a Pair of Numbers Rating: 1400 Tags: bitmasks, constructive algorithms Solve time: 2m 41s Verified: no Solution Problem Understanding The problem asks us to find two positive integers, a and b , given a number x , such that two conditions hold simultaneously: a XOR b = x and (a + b)/2 = x . In other words, Vlad remembers the XOR of two numbers...

CF 1792D - Fixed Prefix Permutations

CF 1792D - Fixed Prefix Permutations Rating: 1700 Tags: binary search, bitmasks, data structures, hashing, math, sortings Solve time: 2m 6s Verified: no Solution Problem Understanding We are given multiple permutations of length $m$. Each permutation contains all integers from 1 to $m$ exactly once. The "beauty" of a permutation is the length of its initial prefix that forms the identity sequence $1, 2, 3, \dots, k$. For example, the...

CF 1795G - Removal Sequences

CF 1795G - Removal Sequences Rating: 2700 Tags: bitmasks, dfs and similar, graphs Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a graph with $n$ vertices and $m$ edges. Each vertex $i$ has an associated number $a_i$. A vertex can only be removed if its current degree equals $a_i$, and when a vertex is removed, its incident edges disappear, reducing the degrees of its neighbors. We...

CF 1799H - Tree Cutting

CF 1799H - Tree Cutting Rating: 3200 Tags: bitmasks, dfs and similar, dp Solve time: 57s Verified: no Solution I can't reliably write a correct, complete editorial for Codeforces 1799H from the problem statement alone. This is a 3200-rated problem with a highly nontrivial tree DP over subsets, and the solution involves delicate state design and transition conditions. Producing an editorial that includes a correctness proof, complexity analysis, worked examples,...

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

Codeforces Round 857 (Div. 1)

Codeforces Round 857 (Div. 1) Type: Div. 1 | Problems: 7 | Verified: 2/7 | Rating range: 1600-3400 | Time: 16m 53s Problem Name Rating Tags Solve Time Verified A The Very Beautiful Blanket 1600 bitmasks, constructive-algorithms 2m 17s ✗ B Buying gifts 1800 data-structures, greedy, sortings 1m 44s ✗ C Music Festival 1900 binary-search, data-structures, dp 4m 24s ✗ D The way home 2100 binary-search, data-structures, dp 3m 31s...

CF 1801A - The Very Beautiful Blanket

CF 1801A - The Very Beautiful Blanket Rating: 1600 Tags: bitmasks, constructive algorithms Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to construct an $n \times m$ grid filled with integers such that a specific XOR condition holds for every $4 \times 4$ subgrid. For any contiguous block of four rows and four columns, two opposite $2 \times 2$ corners must have equal XOR sums: the...

Codeforces Round 862 (Div. 2)

Codeforces Round 862 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-3100 | Time: 15m 37s Problem Name Rating Tags Solve Time Verified A We Need the Zero 800 bitmasks, brute-force 3m 13s ✗ B The String Has a Target 800 greedy, strings 1m 34s ✓ C Place for a Selfie 1400 binary-search, data-structures, geometry 1m 50s ✗ D A Wide, Wide Graph 1800...

CF 1807G2 - Subsequence Addition (Hard Version)

CF 1807G2 - Subsequence Addition (Hard Version) Rating: 1100 Tags: bitmasks, dp, greedy, implementation, sortings Solve time: 1m 31s Verified: no Solution Problem Understanding We are asked whether a given array c can be generated starting from an initial array [1] by repeatedly adding a new element equal to the sum of any subsequence of the current array. The subsequence can have any length from 1 to the size of...

CF 1815D - XOR Counting

CF 1815D - XOR Counting Rating: 2600 Tags: bitmasks, combinatorics, dp, math Solve time: 1m 42s Verified: no Solution Problem Understanding We are asked to distribute a fixed total amount n into m non-negative parts. Every way of splitting the number creates an array (a1, a2, ..., am) whose sum is exactly n . For each such valid split, we compute the bitwise XOR of all parts. Many different splits...

CF 1826E - Walk the Runway

CF 1826E - Walk the Runway Rating: 2400 Tags: bitmasks, brute force, data structures, dp, graphs, implementation, sortings Solve time: 1m 3s Verified: yes Solution Problem Understanding We are given a sequence of runway shows across multiple cities, each with its own ranking of models. There are n models and m cities. Each model has a profit value, and each city gives a rating to each model. We want to...

Codeforces Round 871 (Div. 4)

Codeforces Round 871 (Div. 4) Type: Div. 4 | Problems: 8 | Verified: 6/8 | Rating range: 800-1700 | Time: 10m 54s Problem Name Rating Tags Solve Time Verified A Love Story 800 implementation, strings 1m ✓ B Blank Space 800 implementation 2m 10s ✗ C Mr. Perfectly Fine 800 bitmasks, greedy, implementation 1m 8s ✓ D Gold Rush 1000 brute-force, dfs-and-similar, dp 1m 23s ✓ E The Lakes 1100...

CF 1829H - Don't Blame Me

CF 1829H - Don't Blame Me Rating: 1700 Tags: bitmasks, combinatorics, dp, math Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given an array where every element is a small integer, specifically a 6-bit value. From this array, we can choose any non-empty subsequence, meaning we pick any subset of indices while preserving order, although order does not actually matter for the bitwise operation. For each chosen...

CF 1829C - Mr. Perfectly Fine

CF 1829C - Mr. Perfectly Fine Rating: 800 Tags: bitmasks, greedy, implementation Solve time: 1m 8s Verified: yes Solution Problem Understanding Victor has two independent skills he wants to acquire, and each book he can read either teaches him skill 1, skill 2, both, or none. Every book also has a time cost. The task is to choose a set of books whose combined skills cover both required skills while...

CF 1835F - Good Graph

CF 1835F - Good Graph Rating: 3500 Tags: bitmasks, dfs and similar, graph matchings, graphs, implementation Solve time: 1m 4s Verified: no Solution Exercise 3.3.1.22 [ HM46 ] Investigate the "improved" KS test suggested in the answer to exercise 6. Setup Let $X_1, X_2, \ldots, X_n$ be independent observations drawn from a continuous distribution function $F(x)$. Denote by $F_n(x)$ the empirical distribution function: $F_n(x) = \frac{1}{n}\sum_{i=1}^{n} \mathbf{1}_{{X_i \le x}}.$ The...

CF 1835C - Twin Clusters

CF 1835C - Twin Clusters Rating: 2600 Tags: bitmasks, brute force, constructive algorithms, math, probabilities Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a sequence of galaxies, each with a certain number of stars. The total number of galaxies in a test case is always a power of two, specifically $2^{k+1}$. Each galaxy has a star count between 0 and $4^k - 1$. Our goal is...

Codeforces Round 878 (Div. 3)

Codeforces Round 878 (Div. 3) Type: Div. 3 | Problems: 8 | Verified: 4/8 | Rating range: 800-2500 | Time: 13m 11s Problem Name Rating Tags Solve Time Verified A Cipher Shifer 800 implementation, strings, two-pointers 1m 10s ✗ B Binary Cafe 1100 bitmasks, combinatorics, math 1m 8s ✓ C Ski Resort 1000 combinatorics, math, two-pointers 1m 11s ✓ D Wooden Toy Festival 1400 binary-search, greedy, sortings 1m 41s ✓...

CF 1840B - Binary Cafe

CF 1840B - Binary Cafe Rating: 1100 Tags: bitmasks, combinatorics, math Solve time: 1m 8s Verified: yes Solution Problem Understanding We are asked to count the number of ways Toma can select desserts in a binary-themed cafe. Each dessert has a cost that is a power of two: the first dessert costs 1 coin, the second 2 coins, the third 4 coins, and so on, following the sequence $2^0, 2^1,...

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) Type: Div. 1+2 | Problems: 9 | Verified: 3/9 | Rating range: 800-3500 | Time: 16m 2s Problem Name Rating Tags Solve Time Verified A Tenzing and Tsondu 800 games, math 58s ✗ B Tenzing and Books 1100 bitmasks, greedy, math 1m 45s ✓ C Tenzing and Balls 1500 dp 3m 10s ✗ D Tenzing and His Animal Friends 1900...