#interactive

CF 1557E - Assiut Chess

CF 1557E - Assiut Chess Rating: 2800 Tags: brute force, constructive algorithms, interactive Solve time: 2m Verified: no Solution Problem Understanding We are playing an interactive game on an 8 by 8 chessboard. There is a queen that we control and a king controlled by the judge. The king starts at an unknown cell different from our queen’s starting cell. We choose the initial queen position, then the game begins...

CF 1543D2 - RPD and Rap Sheet (Hard Version)

CF 1543D2 - RPD and Rap Sheet (Hard Version) Rating: 2200 Tags: brute force, constructive algorithms, interactive, math Solve time: 1m 8s Verified: no Solution Problem Understanding We are interacting with a hidden number that changes whenever we make a wrong guess. We know the number always stays within the range from 0 to n − 1, and we are allowed to ask up to n queries to discover it....

CF 1267I - Intriguing Selection

CF 1267I - Intriguing Selection Rating: 2600 Tags: brute force, constructive algorithms, implementation, interactive, sortings Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a hidden set of $2n$ distinct values, one per player, and we can only compare two players at a time and learn which one is stronger. The goal is not to fully reconstruct the ranking, but to identify exactly which $n$ players belong...

CF 1254C - Point Ordering

CF 1254C - Point Ordering Rating: 2300 Tags: constructive algorithms, geometry, interactive, math Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a hidden set of points in the plane, each point identified only by an index from 1 to n. We cannot see coordinates, but we can ask geometric queries involving any three distinct indices. From these queries we can either obtain twice the signed area...

CF 1167B - Lost Numbers

CF 1167B - Lost Numbers Rating: 1400 Tags: brute force, divide and conquer, interactive, math Solve time: 1m 25s Verified: no Solution Problem Understanding We are given an unknown ordering of six fixed numbers: 4, 8, 15, 16, 23, and 42. Each number appears exactly once in an array of length six, but their positions are hidden. Our only way to learn about the array is by asking queries of...

CF 1103B - Game with modulo

CF 1103B - Game with modulo Rating: 2000 Tags: binary search, constructive algorithms, interactive Solve time: 1m 38s Verified: no Solution Problem Understanding We are interacting with a hidden number $a$, which is fixed for each game and lies between 1 and $10^9$. We cannot query it directly. Instead, we can ask questions consisting of two non-negative integers $x$ and $y$, and the judge compares $x \bmod a$ and $y...

CF 1033E - Hidden Bipartite Graph Rating: 2800 Tags: binary search, constructive algorithms, dfs and similar, graphs, interactive Model: gpt-5-3-mini Solve time: 2m 27s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33b4bd-0d58-83ec-9581-09aa8217a4ba Solution Problem Understanding We are given an unknown connected simple graph with up to 600 vertices. We cannot see its edges directly. Instead, we can only ask questions of the form: choose a subset of vertices, and receive the number...

CF 896B - Ithea Plays With Chtholly Rating: 2000 Tags: binary search, constructive algorithms, games, greedy, interactive Model: gpt-5-3-mini Solve time: 3m 12s Verified: yes (1/1 samples) Solution Problem Understanding We are maintaining a row of n positions, each initially empty. Over time, we receive a sequence of m numbers. After each number arrives, we must immediately assign it to one of the n positions, possibly overwriting what was there...

VK Cup 2018 - Wild-card Round 2

VK Cup 2018 - Wild-card Round 2 Special | 1 problems | 1/1 verified | Difficulty 2900-2900 | 1m 8s # Problem Rating Tags Accepted Time ✓ A BuberPool Taxi Optimization 2900 *special, interactive 1 1m 8s ✓

CF 927A - BuberPool Taxi Optimization

CF 927A - BuberPool Taxi Optimization Rating: 2900 Tags: *special, interactive Solve time: 1m 8s Verified: yes Solution Problem Understanding The system simulates a fleet of taxis moving on a large rectangular grid where distance is measured in Manhattan terms, but movement has an additional constraint: whenever a car is instructed to go to a point, it first adjusts its x-coordinate fully and only then adjusts its y-coordinate. This makes...

April Fools Contest 2018

April Fools Contest 2018 April Fools | 4 problems | 3/4 verified | Difficulty 800-2400 | 7m 7s # Problem Rating Tags Accepted Time ✓ A Quirky Quantifiers 800 *special, math 11,974 1m 11s ✓ B A Map of the Cat 1900 *special, brute-force, interactive 2,116 1m 2s ✓ E Cheese Board 2000 *special 679 3m 39s F 2 + 2 != 4 2400 *special 424 1m 15s ✓

CF 952B - A Map of the Cat

CF 952B - A Map of the Cat Rating: 1900 Tags: *special, brute force, interactive Solve time: 1m 2s Verified: yes Solution Problem Understanding We are interacting with a single unknown “cat”, but we are not told directly whether it behaves like a normal cat or a grumpy one. Instead, the cat is split into 10 labeled regions from 0 to 9, and we can probe the cat by choosing...

CF 1007C - Guess two numbers

CF 1007C - Guess two numbers Rating: 3000 Tags: binary search, interactive Solve time: 2m 36s Verified: no Solution Problem Understanding We are dealing with a hidden pair of integers, both lying in a very large range up to $10^{18}$. The only way to learn about this pair is by repeatedly asking queries of the form $(x, y)$. Each query compares your guess against the hidden pair $(a, b)$, but...

Codeforces Round 499 (Div. 1)

Codeforces Round 499 (Div. 1) Div. 1 | 6 problems | 4/6 verified | Difficulty 1500-3400 | 15m 26s # Problem Rating Tags Accepted Time ✓ A Fly 1500 binary-search, math 9,003 1m 41s ✓ B Rocket 1800 binary-search, interactive 6,386 2m 23s C Border 1800 number-theory 5,930 4m 4s ✓ D Mars rover 2000 dfs-and-similar, graphs, implementation 2,563 1m 48s ✓ E Store 2700 data-structures 386 2m 29s ✓...

CF 1010B - Rocket

CF 1010B - Rocket Rating: 1800 Tags: binary search, interactive Solve time: 2m 23s Verified: no Solution Problem Understanding We are trying to determine an unknown integer $x$ in the range from 1 to $m$, but we are not allowed to see it directly. Instead, we can probe it by asking queries with a chosen number $y$. Each query behaves like a comparison against $x$, but the answer is unreliable...

Codeforces Round 503 (by SIS, Div. 1)

Codeforces Round 503 (by SIS, Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1700-3200 | 12m 46s # Problem Rating Tags Accepted Time ✓ A Elections 1700 brute-force, greedy 4,852 2m 7s ✓ B The hat 2000 binary-search, interactive 2,112 2m 40s C Sergey's problem 3000 constructive-algorithms, graphs 1,454 2m 39s D Large Triangle 2700 binary-search, geometry, sortings 742 2m 44s ✓ E Raining season 3200...

CF 1019B - The hat

CF 1019B - The hat Rating: 2000 Tags: binary search, interactive Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a circle of $n$ students, where $n$ is even. Each student holds an unknown integer, and the only structural guarantee about these values is local: any two neighbors on the circle differ by exactly one in value. This forces the entire configuration to behave like a “walk”...

CF 1023E - Down or Right

CF 1023E - Down or Right Rating: 2100 Tags: constructive algorithms, interactive, matrices Solve time: 2m 14s Verified: no Solution Problem Understanding We are given an unknown $n \times n$ grid where each cell is either open or blocked. Movement is only allowed from a cell to its right neighbor or its bottom neighbor, and only if the destination cell is open. The goal is to determine any valid path...

CF 1028G - Guess the number

CF 1028G - Guess the number Rating: 3000 Tags: dp, interactive Solve time: 3m 33s Verified: no Solution Problem Understanding We are trying to identify an unknown integer $x$ in a very large range from $1$ to $M = 10004205361450474$. Instead of asking direct yes or no questions, we are allowed to submit up to five queries, where each query is an increasing list of integers. After each query, we...

CF 1033D - Divisors

CF 1033D - Divisors Rating: 2000 Tags: interactive, math, number theory Solve time: 8m 46s Verified: no Solution Problem Understanding We are given a collection of integers, each of which is known to be “almost prime structured” in the sense that its number of divisors is very small, between 3 and 5. We multiply all these numbers together into one huge number and are asked to compute how many divisors...

Codeforces Round 507 (Div. 1, based on Olympiad of Metropolises)

Codeforces Round 507 (Div. 1, based on Olympiad of Metropolises) Div. 1 | 5 problems | 3/5 verified | Difficulty 2100-3400 | 34m 14s # Problem Rating Tags Accepted Time ✓ A Timetable 2300 constructive-algorithms, data-structures, greedy 861 6m 10s B Subway Pursuit 2100 binary-search, interactive, probabilities 2,589 11m 23s C Network Safety 2200 dfs-and-similar, dsu, graphs 1,490 8m 24s ✓ D You Are Given a Tree 2800 data-structures, dp,...

CF 1039B - Subway Pursuit

CF 1039B - Subway Pursuit Rating: 2100 Tags: binary search, interactive, probabilities Solve time: 11m 23s Verified: no Solution Problem Understanding We are dealing with a single moving target on a very large numbered line of stations from 1 to n. At any moment there is exactly one station where the train is located, but after every query the train is allowed to move up to k stations left or...

Lyft Level 5 Challenge 2018 - Final Round

Lyft Level 5 Challenge 2018 - Final Round Special | 6 problems | 1/6 verified | Difficulty 1700-3100 | 30m 21s # Problem Rating Tags Accepted Time ✓ A The Tower is Going Home 1700 binary-search, two-pointers 3,076 10m 12s B Intersecting Subtrees 1900 dfs-and-similar, interactive, trees 1,708 1m 59s ✓ C Optimal Polygon Perimeter 2100 dp, geometry 1,409 5m 59s D Deduction Queries 2400 data-structures, dsu 1,186 7m E...

CF 1044B - Intersecting Subtrees

CF 1044B - Intersecting Subtrees Rating: 1900 Tags: dfs and similar, interactive, trees Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given a tree with n vertices, but there is a twist: there are two different labelings of the same underlying tree. In your view, the vertices are numbered from 1 to n and the edges are given in this numbering. Li Chen has independently assigned his...

CF 2013C - Password Cracking

CF 2013C - Password Cracking Rating: 1400 Tags: constructive algorithms, interactive, strings Solve time: 2m 33s Verified: no Solution Problem Under

CF 1552H - Guess the Perimeter

CF 1552H - Guess the Perimeter Rating: 3300 Tags: binary search, interactive, number theory Solve time: 3m 43s Verified: yes Solution Problem Understanding We are dealing with a hidden axis-aligned rectangle whose corners lie on integer grid points inside a fixed 200 by 200 grid. The only way to learn anything about this rectangle is by querying a set of grid points and receiving the count of how many of...

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

Baltic Olympiad in Informatics 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)

Baltic Olympiad in Informatics 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated) ICPC/IOI | 3 problems | 0/3 verified | Difficulty 2700-2900 | 16m 58s # Problem Rating Tags Accepted Time ✓ A Colors 2700 *special, binary-search, constructive-algorithms 350 7m 19s B Mixture 2900 *special, data-structures, geometry 141 7m 15s C Joker 2800 *special, bitmasks, data-structures 656 2m 24s

CF 1386A - Colors

CF 1386A - Colors Rating: 2700 Tags: *special, binary search, constructive algorithms, interactive Solve time: 7m 19s Verified: no Solution Problem Understanding We are interacting with a hidden system that has chosen an integer threshold $C$ between 1 and $N$. We can think of the numbers from 1 to $N$ as positions on a line, and every time we pick a position, we are effectively “dyeing” hair with that color....

CF 1375F - Integer Game

CF 1375F - Integer Game Rating: 2600 Tags: constructive algorithms, games, interactive, math Solve time: 6m 23s Verified: no Solution Problem Understanding Three numbers represent the sizes of three piles of stones. The interaction alternates between us and the opponent. On our turn we output a positive integer y , and on the opponent’s turn they must add exactly y stones to one of the three piles, with the restriction...

CF 1372F - Omkar and Modes

CF 1372F - Omkar and Modes Rating: 2700 Tags: binary search, divide and conquer, interactive Solve time: 4m 31s Verified: no Solution Problem Understanding We are given a hidden array of length $n$, already sorted in nondecreasing order, and containing at most $k \le 25000$ distinct values. Our only way to inspect it is by querying a segment $[l,r]$. Each query returns the mode of that segment and how many...

CF 1370F2 - The Hidden Pair (Hard Version)

CF 1370F2 - The Hidden Pair (Hard Version) Rating: 2700 Tags: binary search, dfs and similar, graphs, interactive, shortest paths, trees Solve time: 8m 8s Verified: no Solution Problem Understanding We are given a tree and two hidden distinct nodes inside it. We do not know which nodes they are, but we can interactively probe the tree by choosing any subset of nodes. For each subset, the system returns one...

CF 1368F - Lamps on a Circle

CF 1368F - Lamps on a Circle Rating: 2600 Tags: games, implementation, interactive, math Solve time: 2m 16s Verified: yes Solution Problem Understanding We are playing an interactive game on a circular array of n positions. All positions start empty. On each turn, the player is allowed to pick a number k and activate any k positions. Immediately after that, an adversary removes a block of exactly k consecutive positions...

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

CF 1363D - Guess The Maximums

CF 1363D - Guess The Maximums Rating: 2100 Tags: binary search, implementation, interactive, math Solve time: 6m 18s Verified: no Solution Problem Understanding We are given an array $A$ of length $n$, but we cannot see it directly. Instead, we can ask queries: pick any subset of indices and the judge returns the maximum value of $A$ over those indices. Along with this hidden array, we are given $k$ special...

CF 1355F - Guess Divisors Count

CF 1355F - Guess Divisors Count Rating: 2600 Tags: constructive algorithms, interactive, number theory Solve time: 4m 21s Verified: no Solution Problem Understanding We are given a hidden integer $X$ in each game, but we are never allowed to see it directly. Instead, we can query any integer $Q$, and the judge returns $\gcd(X, Q)$. Our goal is not to reconstruct $X$, but to estimate how many divisors $X$ has,...

CF 1354G - Find a Gift

CF 1354G - Find a Gift Rating: 2600 Tags: binary search, interactive, probabilities Solve time: 5m 29s Verified: no Solution Problem Understanding We are given a row of boxes, each box hiding either a valuable gift or a stone. Exactly k boxes contain gifts, and every other box contains stones. The key structural property is about weights. Every stone box has the same weight, and that weight is strictly larger...

CF 1336D - Yui and Mahjong Set

CF 1336D - Yui and Mahjong Set Rating: 3200 Tags: constructive algorithms, interactive Solve time: 5m 3s Verified: no Solution Problem Understanding We are dealing with a hidden multiset of tiles where each tile carries a value from 1 to n. The hidden configuration can be thought of as an array of frequencies a₁, a₂, …, aₙ, where aᵢ is the number of tiles with value i. The sum of...

CF 1305D - Kuroni and the Celebration

CF 1305D - Kuroni and the Celebration Rating: 1900 Tags: constructive algorithms, dfs and similar, interactive, trees Solve time: 3m 8s Verified: no Solution Problem Understanding We are given a fixed tree with up to 1000 vertices. Somewhere in this tree there is a hidden root vertex $r$, which represents Kuroni’s hotel. The structure of the tree is known, but the root is not. The only way to extract information...

CF 1299E - So Mean

CF 1299E - So Mean Rating: 3400 Tags: interactive, math Solve time: 9m 8s Verified: no Solution Problem Understanding We are given a hidden permutation of numbers from $1$ to $n$, where $n$ is even. We cannot directly see it, but we can query any subset of indices. For a chosen subset, the judge tells us only whether the average value of the selected positions is an integer. That condition...

CF 1292E - Rin and The Unknown Flower

CF 1292E - Rin and The Unknown Flower Rating: 3500 Tags: constructive algorithms, greedy, interactive, math Solve time: 4m 51s Verified: no Solution Problem Understanding We are trying to reconstruct a hidden string of length up to 50. The string is guaranteed to use only three symbols: C, H, and O. The only way to obtain information is through a substring query mechanism: we send a pattern string, and we...

Codeforces Round 616 (Div. 2)

Codeforces Round 616 (Div. 2) Div. 2 | 3 problems | 0/3 verified | Difficulty 900-2800 | 15m 2s # Problem Rating Tags Accepted Time ✓ A Even But Not Even 900 greedy, math, strings 20,680 4m 55s B Array Sharpening 1300 greedy, implementation 15,358 5m 13s F Coffee Varieties (easy version) 2800 graphs, interactive 726 4m 54s

CF 1291F - Coffee Varieties (easy version)

CF 1291F - Coffee Varieties (easy version) Rating: 2800 Tags: graphs, interactive Solve time: 4m 54s Verified: no Solution Problem Understanding We are given a hidden sequence of café types, where each café produces exactly one integer “coffee variety”. We do not know the sequence itself, but we can probe cafés one by one. The interaction tool behaves like a sliding-window memory system. Every time we query a café, the...

CF 1290D - Coffee Varieties (hard version)

CF 1290D - Coffee Varieties (hard version) Rating: 3000 Tags: constructive algorithms, graphs, interactive Solve time: 3m 41s Verified: no Solution Problem Understanding We are given a hidden array of length $n$, where each position represents a café and each café produces exactly one type of coffee. The value at position $i$ is the coffee variety label $a_i$, but we never see it directly. Instead, we can query a café...

CF 1286C2 - Madhouse (Hard version)

CF 1286C2 - Madhouse (Hard version) Rating: 2800 Tags: brute force, constructive algorithms, hashing, interactive, math Solve time: 6m 2s Verified: no Solution Problem Understanding A hidden string of length $n$ is fixed before the game starts. The player’s goal is to recover this exact string. Instead of being given it directly, the only way to gain information is by querying substrings of ranges. When a range $[l, r]$ is...

CF 1286C1 - Madhouse (Easy version)

CF 1286C1 - Madhouse (Easy version) Rating: 2400 Tags: brute force, constructive algorithms, interactive, math Solve time: 4m 5s Verified: no Solution Problem Understanding We are dealing with a hidden string of length $n$, made of lowercase English letters. We cannot see the string directly. Instead, we can query any segment $s[l..r]$, and the judge returns all substrings of that segment, but with two distortions: the order of substrings is...

CF 1282D - Enchanted Artifact

CF 1282D - Enchanted Artifact Rating: 2300 Tags: constructive algorithms, interactive, strings Solve time: 10m 8s Verified: no Solution Problem Understanding We are interacting with a hidden binary string $s$ consisting only of characters a and b . We do not know its length, but it is at most 300. Our task is to discover $s$ using queries. Each query is another string $t$, and the system responds with the...

VK Cup 2019 - Квалификация (Engine)

VK Cup 2019 - Квалификация (Engine) Special | 5 problems | 1/5 verified | Difficulty - | 15m 17s # Problem Rating Tags Accepted Time ✓ A \u0421\u043a\u0440\u044b\u0442\u044b\u0439 \u0434\u0440\u0443\u0433 *special 891 4m 45s B Code Review *special 844 2m 41s C #define \u0417\u0430\u0434\u0430\u0447\u0430 B ... *special 698 2m 4s ✓ E2 \u041a\u043e\u043d\u0442\u0440\u043e\u043b\u044c\u043d\u0430\u044f \u0441\u0443\u043c\u043c\u0430 *special 138 3m 19s F \u0428\u0430\u0440\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0441\u0442\u043e\u0432 *special, binary-search, interactive 92 2m 28s

CF 1270D - Strange Device

CF 1270D - Strange Device Rating: 1900 Tags: constructive algorithms, interactive, math, sortings Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given an unknown array of distinct integers. We cannot read it directly. Instead, we can query any subset of exactly k positions, and the device returns the position and value of the element that would rank as the m -th smallest among those k values. The...

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 1201E2 - Knightmare (hard)

CF 1201E2 - Knightmare (hard) Rating: 3000 Tags: graphs, interactive, shortest paths Solve time: 5m 52s Verified: no Solution Problem Understanding We are placed on an even-by-even grid, and two knights start on different squares. One is white, one is black. Each player controls exactly one knight and alternates moves, starting with the white side if we choose it. A move is standard knight movement. The game ends immediately when...

CF 1100D - Dasha and Chess

CF 1100D - Dasha and Chess Rating: 2500 Tags: constructive algorithms, games, interactive Solve time: 9m 7s Verified: no Solution Problem Understanding We are simulating an interaction on a 999 by 999 grid with a single white king and many black rooks. The king moves first and can step to any of the eight neighboring cells. After each king move, an adversary moves exactly one rook to any empty square,...

Mail.Ru Cup 2018 Round 3

Mail.Ru Cup 2018 Round 3 Special | 8 problems | 7/8 verified | Difficulty 800-3200 | 29m 37s # Problem Rating Tags Accepted Time ✓ A Determine Line 800 implementation 7,307 3m 25s ✓ B Divide Candies 1600 math, number-theory 4,546 6m 37s ✓ C Pick Heroes 1700 greedy, implementation, interactive 2,579 5m D Decorate Apple Tree 1600 constructive-algorithms, dfs-and-similar, dp 6,719 2m 24s ✓ E Check Transcription 2100 brute-force,...

CF 1056C - Pick Heroes

CF 1056C - Pick Heroes Rating: 1700 Tags: greedy, implementation, interactive, sortings Solve time: 5m Verified: no Solution Problem Understanding Two players are building two equally sized teams by alternately taking heroes from a common pool of $2n$ candidates. Each hero has a fixed strength, and once taken it disappears from the game. On top of this, some heroes come in special pairs: if one hero of such a pair...

CF 1061F - Lost Root

CF 1061F - Lost Root Rating: 2400 Tags: interactive, probabilities Solve time: 8m 41s Verified: no Solution Problem Understanding We are given a tree that is known to be a perfect $k$-ary tree, meaning it has a root, every internal node has exactly $k$ children, and all leaves are at the same depth. The structure of the tree is fixed, but the vertex labels from $1$ to $n$ are arbitrarily...

CF 1063C - Dwarves, Hats and Extrasensory Abilities

CF 1063C - Dwarves, Hats and Extrasensory Abilities Rating: 1900 Tags: binary search, constructive algorithms, geometry, interactive Solve time: 3m 24s Verified: no Solution Problem Understanding We are interacting with an unknown assignment of colors to points, where the opponent can choose each point’s color after seeing where we place it. We must output a sequence of distinct integer-coordinate points. After each point is placed, we immediately learn whether it...

Codeforces Round 524 (Div. 2)

Codeforces Round 524 (Div. 2) Div. 2 | 6 problems | 3/6 verified | Difficulty 800-2400 | 26m 36s # Problem Rating Tags Accepted Time ✓ A Petya and Origami 800 math 19,175 5m 14s ✓ B Margarite and the best present 900 math 12,636 2m 38s ✓ C Masha and two friends 1500 implementation 4,218 3m 5s ✓ D Olya and magical square 2000 constructive-algorithms, implementation, math 1,666 7m...

CF 1080F - Katya and Segments Sets

CF 1080F - Katya and Segments Sets Rating: 2400 Tags: data structures, interactive, sortings Solve time: 3m Verified: no Solution Problem Understanding We are given several collections of segments, where each collection corresponds to a set index from 1 to n. Inside a single set, there may be many segments, and each segment is a closed interval on the number line. The task revolves around answering queries about a range...

CF 1081F - Tricky Interactor

CF 1081F - Tricky Interactor Rating: 2600 Tags: constructive algorithms, implementation, interactive Solve time: 6m 44s Verified: no Solution Problem Understanding We are given a hidden binary array of length $n$, containing only zeros and ones. We are also told how many ones it originally contains, but not their positions. The array is placed in the hands of an interactive judge that mutates it after every query in a very...

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

CF 1773I - Interactive Factorial Guessing

CF 1773I - Interactive Factorial Guessing Rating: 2500 Tags: brute force, games, implementation, interactive Solve time: 2m 18s Verified: no Solution Problem Understanding We are interacting with a hidden integer $n$, but we are not allowed to see it directly. Instead, we can ask up to 10 questions of the form: “what is the $k$-th digit from the right of $n!$ in decimal representation?”. If that digit does not exist...

CF 1773H - Hot and Cold

CF 1773H - Hot and Cold Rating: 2600 Tags: binary search, interactive Solve time: 2m 18s Verified: no Solution Problem Understanding We are playing a coordinate guessing game on a large integer grid. There is a hidden target point somewhere in the square from $(0,0)$ to $(10^6,10^6)$. We are allowed to “query” any point by printing its coordinates, and after each query the system tells us how our Euclidean distance...

CF 1729E - Guess the Cycle Size

CF 1729E - Guess the Cycle Size Rating: 1800 Tags: interactive, probabilities Solve time: 6m 14s Verified: no Solution Problem Understanding We are interacting with a hidden structure that is guaranteed to be a simple cycle on $n$ vertices, where $n$ can be as large as $10^{18}$. The vertices are labeled by distinct integers, but the actual cycle order is unknown. The only way to extract information is by querying...

CF 1721F - Matching Reduction

CF 1721F - Matching Reduction Rating: 2800 Tags: brute force, constructive algorithms, dfs and similar, flows, graph matchings, graphs, interactive Solve time: 4m 58s Verified: no Solution Problem Understanding We are working with a bipartite graph where the left side has $n_1$ vertices and the right side has $n_2$ vertices. Edges are fixed and each edge connects one left vertex to one right vertex. At any moment, we consider a...

CF 1583D - Omkar and the Meaning of Life

CF 1583D - Omkar and the Meaning of Life Rating: 1800 Tags: constructive algorithms, greedy, interactive Solve time: 5m 5s Verified: no Solution Problem Understanding We are trying to recover an unknown permutation of the numbers from 1 to n. We never see this permutation directly. Instead, we can probe it using a query mechanism that mixes our chosen array with the hidden permutation in a very specific way. Each...

CF 1578M - The Mind

CF 1578M - The Mind Rating: 2700 Tags: constructive algorithms, interactive, probabilities Solve time: 6m 11s Verified: no Solution Problem Understanding Each test gives us a hand of five distinct numbers between 1 and 100. Two players independently receive such hands, and each player only sees their own five numbers. From those five numbers, only the smallest one matters for the actual game, because the rules force every player to...

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 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 1546B - AquaMoon and Stolen String

CF 1546B - AquaMoon and Stolen String Rating: 1200 Tags: interactive, math Solve time: 7m 28s Verified: yes Solution Problem Understanding We are given a multiset of original strings and a second multiset formed after a disturbance process. The disturbance worked in two stages. First, all strings were paired except one special string that stayed unpaired. Then, for each pair, the two strings were partially “mixed” by swapping characters at...

Codeforces Round 732 (Div. 2)

Codeforces Round 732 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-1200 | 11m 6s # Problem Rating Tags Accepted Time ✓ A AquaMoon and Two Arrays 800 brute-force, greedy 18,588 3m 38s ✓ B AquaMoon and Stolen String 1200 interactive, math 13,952 7m 28s ✓

CF 1520F1 - Guess the K-th Zero (Easy version)

CF 1520F1 - Guess the K-th Zero (Easy version) Rating: 1600 Tags: binary search, interactive Solve time: 8m 38s Verified: no Solution Problem Understanding We are given a hidden binary array of length $n$. We cannot see the array directly. Instead, we can ask queries on any interval $[l, r]$, and the system returns the number of ones in that segment. From this information, we must determine the position of...

CF 1520F2 - Guess the K-th Zero (Hard version)

CF 1520F2 - Guess the K-th Zero (Hard version) Rating: 2200 Tags: binary search, constructive algorithms, data structures, interactive Solve time: 4m 57s Verified: no Solution Problem Understanding We are dealing with a hidden binary array of length $n$, where each position is either zero or one. The array does not change on its own, but it is modified by our own actions: every time we correctly identify the position...

CF 1499G - Graph Coloring

CF 1499G - Graph Coloring Rating: 3100 Tags: data structures, graphs, interactive Solve time: 5m 52s Verified: no Solution Problem Understanding We start with a bipartite graph whose edges arrive online. Each edge must eventually be assigned one of two labels, red or blue. For any vertex, we compare how many incident edges are red versus blue, and we pay the absolute difference of these two counts. The goal is...

CF 1491F - Magnets

CF 1491F - Magnets Rating: 2700 Tags: binary search, constructive algorithms, interactive Solve time: 3m 38s Verified: no Solution Problem Understanding We are given a set of magnets, each secretly belonging to one of three types: North, South, or a special “inactive” type that produces no magnetic behavior. The only way to learn anything about them is through a machine that compares two chosen groups: one placed on the left...

CF 1404D - Game of Pairs

CF 1404D - Game of Pairs Rating: 2800 Tags: constructive algorithms, dfs and similar, interactive, math, number theory Solve time: 4m 8s Verified: no Solution Problem Understanding We are working with a two-player construction game on the numbers from 1 to 2n. One player first partitions these numbers into n disjoint pairs. After that, the second player selects exactly one number from each pair. The score is the sum of...

CF 1370F1 - The Hidden Pair (Easy Version) Rating: 2400 Tags: binary search, dfs and similar, graphs, interactive, shortest paths, trees Model: gpt-5-5 Solve time: 2m 35s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e5372-8200-83ec-8cd2-b905527f64bf Solution Problem Understanding We are working with a tree where two unknown vertices have been chosen as hidden targets. The only way to gain information is through queries on subsets of nodes. When we query a set,...

Educational Codeforces Round 65 (Rated for Div. 2)

Educational Codeforces Round 65 (Rated for Div. 2) Div. 2 | 7 problems | 3/7 verified | Difficulty 800-3100 | 13m 57s # Problem Rating Tags Accepted Time ✓ A Telephone Number 800 brute-force, greedy, strings 20,276 2m 3s ✓ B Lost Numbers 1400 brute-force, divide-and-conquer, interactive 16,459 1m 25s C News Distribution 1400 dfs-and-similar, dsu, graphs 25,981 3m 18s ✓ D Bicolored RBS 1500 constructive-algorithms, greedy 7,369 2m 39s...

Codeforces Round 534 (Div. 1)

Codeforces Round 534 (Div. 1) Div. 1 | 4 problems | 3/4 verified | Difficulty 1400-3100 | 11m 18s # Problem Rating Tags Accepted Time ✓ A Grid game 1400 constructive-algorithms, implementation 10,596 3m 23s ✓ B Game with modulo 2000 binary-search, constructive-algorithms, interactive 3,528 1m 38s C Johnny Solving 2700 constructive-algorithms, dfs-and-similar, graphs 953 4m 21s ✓ D Professional layer 3100 bitmasks, dp 493 1m 56s ✓

CF 1205C - Palindromic Paths

CF 1205C - Palindromic Paths Rating: 2400 Tags: implementation, interactive Solve time: 5m 3s Verified: no Solution Problem Understanding We are given an unknown binary grid of size $n \times n$, where $n$ is odd. Each cell contains either 0 or 1. Two facts are guaranteed: the top-left cell is 1 and the bottom-right cell is 0. We cannot directly read the grid. Instead, we can query any pair of...

CF 1179E - Alesya and Discrete Math

CF 1179E - Alesya and Discrete Math Rating: 3200 Tags: divide and conquer, interactive Solve time: 10m 9s Verified: no Solution Problem Understanding We are dealing with several functions that behave like monotone step counters on a huge integer line. Each function starts at value zero at position zero, ends at a fixed value L at position 10^18, and can only change in a very restricted way: as we move...

CF 1174F - Ehab and the Big Finale

CF 1174F - Ehab and the Big Finale Rating: 2400 Tags: constructive algorithms, divide and conquer, graphs, implementation, interactive, trees Solve time: 11m 51s Verified: no Solution Problem Understanding We are given a tree with nodes numbered from 1 to n, rooted at node 1. Inside this tree, there is a hidden node x. The only way to learn about x is through two types of queries: asking for the...

CF 1091G - New Year and the Factorisation Collaboration

CF 1091G - New Year and the Factorisation Collaboration Rating: 3200 Tags: interactive, math, number theory Solve time: 5m 45s Verified: no Solution Problem Understanding We are interacting with a hidden integer modulus $n$, and our goal is to recover its full factorisation. The twist is that we cannot access $n$ directly through arithmetic or inspection. Instead, we are given a restricted modular calculator that performs operations modulo $n$, including...

2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 8/13 | Rating range: 1000-2900 | Time: 40m 49s Problem Name Rating Tags Solve Time Verified A Company Merging 1300 greedy 2m 19s ✓ B LaTeX Expert 1900 - 1m 7s ✗ C New Year Presents 2400 constructive-algorithms, data-structures 3m 14s ✗ D Similar Arrays 1800 constructive-algorithms 2m 13s...

CF 1090F - How to Learn You Score

CF 1090F - How to Learn You Score Rating: 2600 Tags: constructive algorithms, interactive Solve time: 6m 5s Verified: no Solution I can’t safely produce a correct, detailed editorial for Codeforces 1090F from the information given here, because the actual problem statement (what the interaction allows, what the judge returns, and what needs to be reconstructed) is missing. For a 2600-rated interactive constructive problem, the entire solution hinges on very...

2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 6/13 | Rating range: 900-3400 | Time: 49m 47s Problem Name Rating Tags Solve Time Verified A Alice the Fan 2200 dp 9m 32s ✗ B Bimatching 3200 graphs 55s ✓ C Cactus Search 2500 interactive 1m 34s ✓ D Distance Sum 3100 graphs 1m 45s ✗ E Easy Chess...

CF 1089C - Cactus Search

CF 1089C - Cactus Search Rating: 2500 Tags: interactive Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given a connected structure that is almost a tree but may contain simple cycles, with the restriction that any edge belongs to at most one cycle. Inside this graph there is a hidden vertex chosen by the judge. Our only way to interact is to query a vertex, and the...

CF 916D - Jamie and To-do List

CF 916D - Jamie and To-do List Rating: 2200 Tags: data structures, interactive, trees Solve time: 4m 6s Verified: yes Solution Problem Understanding The system maintains a dynamic collection of named tasks. Each task has a unique string identifier and, if it exists, an integer priority where smaller means more important. Over time, tasks are added, removed, or have their priorities changed. On top of that, time is not strictly...

CF 1114E - Arithmetic Progression

CF 1114E - Arithmetic Progression Rating: 2200 Tags: binary search, interactive, number theory, probabilities Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a hidden array of size $n$, but the array is not directly accessible and is permuted arbitrarily. The only structural guarantee is that if we sort its elements, they form a perfect arithmetic progression with a strictly positive common difference. So the multiset of...

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

CF 1129E - Legendary Tree

CF 1129E - Legendary Tree Rating: 3100 Tags: binary search, interactive, trees Solve time: 1m 24s Verified: no Solution Problem Understanding We are asked to reconstruct an unknown tree of $n$ vertices by asking a limited type of query. The query is interactive: for any two disjoint, non-empty sets of vertices $S$ and $T$, and a chosen vertex $v$, we receive the number of pairs $(s, t) \in S \times...

CF 1137D - Cooperative Game

CF 1137D - Cooperative Game Rating: 2400 Tags: constructive algorithms, interactive, number theory Solve time: 1m 47s Verified: no Solution Problem Understanding We are asked to coordinate ten players on a secret graph consisting of a directed path leading to a cycle. The path has length t , ending at the start of a cycle of length c , which represents a scenic lake road. Every vertex has exactly one...

CF 1142E - Pink Floyd

CF 1142E - Pink Floyd Rating: 3200 Tags: graphs, interactive Solve time: 1m 32s Verified: no Solution Problem Understanding We are given a complete undirected graph on $n$ nodes, but each edge is assigned a direction, making it a tournament. A subset of these edges are colored pink and their directions are known. The remaining edges are green, and their directions are initially unknown. Our goal is to identify a...

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 1145G - AI Takeover

CF 1145G - AI Takeover Rating: - Tags: *special, interactive Solve time: 59s Verified: yes Solution Problem Understanding This is an interactive game against a fixed but unknown opponent program. The opponent chooses one deterministic strategy at the beginning of the test and sticks to it for all 20 rounds. Your task is to play rock-paper-scissors and interactively discover enough about that strategy to guarantee a win streak of at...

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

Forethought Future Cup - Final Round (Onsite Finalists Only)

Forethought Future Cup - Final Round (Onsite Finalists Only) Type: Special | Problems: 6 | Verified: 2/6 | Rating range: 1500-3500 | Time: 9m 37s Problem Name Rating Tags Solve Time Verified A Hide and Seek 1500 graphs 1m 51s ✗ B Chladni Figure 1900 brute-force, strings 1m 2s ✓ C Thanos Nim 2000 games 1m 22s ✓ D Palindrome XOR 2400 dfs-and-similar, graphs 1m 45s ✗ E Rainbow Coins...

CF 1147F - Zigzag Game

CF 1147F - Zigzag Game Rating: 3500 Tags: games, interactive Solve time: 1m 44s Verified: no Solution Problem Understanding The game is played on a complete bipartite graph with two equal groups of vertices. Every vertex on the left side connects to every vertex on the right side, and each such edge has a unique weight. The input gives these weights as an $n \times n$ matrix, where entry $a_{ij}$...

CF 1147E - Rainbow Coins

CF 1147E - Rainbow Coins Rating: 3000 Tags: interactive Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a hidden assignment of colors to numbered coins, where each coin is exactly one of three colors. The goal is to partition the coins into three groups so that each group contains coins of a single color, but we do not know the colors directly. The only operation allowed...

CF 1153E - Serval and Snake

CF 1153E - Serval and Snake Rating: 2200 Tags: binary search, brute force, interactive Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a hidden simple path drawn on an $n \times n$ grid. The path represents a snake: it visits distinct cells, each consecutive pair shares a side, and the two ends of the path are special cells called the head and the tail. We cannot...

CF 1155E - Guess the Root

CF 1155E - Guess the Root Rating: 2200 Tags: brute force, interactive, math Solve time: 1m 39s Verified: no Solution Problem Understanding The problem gives us a hidden polynomial of degree at most 10 with integer coefficients, each strictly less than $10^6 + 3$. The task is to find an integer $x_0$ such that the polynomial evaluates to zero modulo $10^6 + 3$. We do not see the coefficients directly;...

CF 1158E - Strange device

CF 1158E - Strange device Rating: 3400 Tags: binary search, interactive, math, trees Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to reconstruct an unknown tree with $n$ vertices by interacting with a device that allows a single type of query. Each vertex of the tree has a lamp, and the device lets us propose a set of distances $d_1, d_2, \dots, d_n$. When we submit...

CF 1201E1 - Knightmare (easy)

CF 1201E1 - Knightmare (easy) Rating: 2900 Tags: graphs, interactive, shortest paths Solve time: 1m 55s Verified: yes Solution Problem Understanding We are given a small chessboard and two knights placed on it. One knight is white and moves first, the other is black. On each turn, a player moves their own knight using standard knight moves. The interaction continues until one side wins or 350 moves are reached. Winning...

CF 1275F - Шардирование постов

CF 1275F - \u0428\u0430\u0440\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0441\u0442\u043e\u0432 Rating: - Tags: *special, binary search, interactive Solve time: 2m 28s Verified: no Solution There is not enough information to diagnose the bug or provide a corrected solution. The sample 3 3 tab one bat with expected output 6 tabbat appears to belong to a string construction problem, but you have not provided: the problem statement, the original Python solution, or even the name of...

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

Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)

Central-European Olympiad in Informatics, CEOI 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) Type: ICPC/IOI | Problems: 3 | Verified: 1/3 | Rating range: 2300-3200 | Time: 20m 41s Problem Name Rating Tags Solve Time Verified A The Potion of Great Power 2400 *special, 2-sat, binary-search 2m 3s ✗ B Spring cleaning 2300 *special, data-structures, dfs-and-similar 14m 30s ✗ C Chess Rush 3200 *special, combinatorics, dp 4m 8s ✓

CF 1403A - The Potion of Great Power

CF 1403A - The Potion of Great Power Rating: 2400 Tags: *special, 2-sat, binary search, data structures, graphs, interactive, sortings, two pointers Solve time: 2m 3s Verified: no Solution Problem Understanding We have a dynamic friendship network among N shamans, each living at a specific altitude H[i] . Initially, no shaman trusts anyone, and every day a single friendship either forms or dissolves. Each shaman can trust at most D...

CF 1406E - Deleting Numbers

CF 1406E - Deleting Numbers Rating: 2600 Tags: interactive, math, number theory Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to identify a hidden integer x between 1 and n . Initially, we have the full set of integers from 1 to n . We can perform three types of operations: we can query how many numbers in the current set are divisible by some integer...

CF 1407C - Chocolate Bunny

CF 1407C - Chocolate Bunny Rating: 1600 Tags: constructive algorithms, interactive, math, two pointers Solve time: 4m 46s Verified: no Solution Now it’s clear why your solution fails. The traceback: IndexError: list index out of range pairs.append((bi - a[j], i)) This comes from trying to access a[j] for j in range(6) (the original guitar solution assumes 6 strings) while your input is not the 1413C guitar problem . Your new...

Codeforces Round 669 (Div. 2)

Codeforces Round 669 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 1/5 | Rating range: 1100-2500 | Time: 10m 44s Problem Name Rating Tags Solve Time Verified A Ahahahahahahahaha 1100 constructive-algorithms, math 1m 30s ✗ B Big Vova 1300 brute-force, greedy, math 1m 32s ✗ C Chocolate Bunny 1600 constructive-algorithms, interactive, math 4m 46s ✗ D Discrete Centrifugal Jumps 2200 data-structures, dp, graphs 1m 9s ✓ E Egor...

CF 1423M - Milutin's Plums

CF 1423M - Milutin's Plums Rating: 2800 Tags: interactive Solve time: 57s Verified: yes Solution Problem Understanding We are given an unknown matrix with $n$ rows and $m$ columns, and each cell contains an integer weight. Our only way to learn values is by querying individual positions. The goal is to identify the smallest value anywhere in the matrix, but we are not allowed to scan it directly. The structure...

CF 1425F - Flamingoes of Mystery

CF 1425F - Flamingoes of Mystery Rating: 1400 Tags: interactive Solve time: 2m 18s Verified: no Solution Problem Understanding We have an unknown array $A_1, A_2, \dots, A_N$, where $A_i$ is the number of flamingoes in cage $i$. The only operation available is asking for the sum of a contiguous segment. A query of the form $(L,R)$ returns $$A_L + A_{L+1} + \cdots + A_R$$ with the restriction that $L...

CF 1428H - Rotary Laser Lock

CF 1428H - Rotary Laser Lock Rating: 3500 Tags: binary search, interactive Solve time: 59s Verified: yes Solution Problem Understanding We are asked to unlock a circular lock with n wheels. Each wheel has a number from 0 to m-1 . The lock has a hidden target combination, and we can query the lock with a proposed sequence of wheel positions. The lock will tell us the minimal clockwise rotation...

Codeforces Round 618 (Div. 1)

Codeforces Round 618 (Div. 1) Div. 1 | 3 problems | 1/3 verified | Difficulty 1800-3400 | 15m 48s # Problem Rating Tags Accepted Time ✓ B Aerodynamic 1800 geometry 5,609 1m 58s ✓ C Water Balance 2100 data-structures, geometry, greedy 4,333 4m 42s E So Mean 3400 interactive, math 195 9m 8s

CF 1438F - Olha and Igor

CF 1438F - Olha and Igor Rating: 3000 Tags: interactive, probabilities, trees Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a perfect binary tree of height $h$, which contains $n = 2^h - 1$ nodes. Each node has a unique label from 1 to $n$, but the labeling is completely unknown. Our task is to determine the label of the root. We can interact with the...

CF 1442F - Differentiating Games

CF 1442F - Differentiating Games Rating: 3400 Tags: games, interactive Solve time: 1m 21s Verified: no Solution Problem Understanding We are dealing with an interactive combinatorial game on a directed graph. Each vertex may hold a token, and two players alternate moves. On a turn, a player chooses any token and moves it along an outgoing edge. If a player cannot move any token, they lose. The interactor selects a...

CF 1444E - Finding the Vertex

CF 1444E - Finding the Vertex Rating: 3500 Tags: brute force, dfs and similar, dp, interactive, trees Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a tree with up to 100 vertices, and somewhere inside this tree there is a hidden “special” vertex. We do not know which one it is. The only way to gain information is to query an edge, and the response tells...

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

CF 1466I - The Riddle of the Sphinx

CF 1466I - The Riddle of the Sphinx Rating: 3400 Tags: binary search, data structures, interactive Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a hidden array of length n . Each element is an integer in the range [0, 2^b - 1] . We never see the values directly. Instead, we can repeatedly choose an index i and a number y , and ask whether...

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

CF 1470C - Strange Shuffle

CF 1470C - Strange Shuffle Rating: 2500 Tags: binary search, brute force, constructive algorithms, interactive Solve time: 1m 57s Verified: no Solution Problem Understanding We have a circle of $n$ players, each holding $k$ cards. Every turn, each player distributes half their cards to the left and half to the right, rounding as appropriate. There is one impostor who breaks this rule and instead gives all their cards to the...

Codeforces Round 700 (Div. 1)

Codeforces Round 700 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1700-3500 | Time: 14m 35s Problem Name Rating Tags Solve Time Verified A Searching Local Minimum 1700 binary-search, interactive, ternary-search 2m 8s ✓ B1 Painting the Array I 1900 constructive-algorithms, data-structures, dp 1m 44s ✓ B2 Painting the Array II 2100 constructive-algorithms, data-structures, dp 2m 53s ✗ C Continuous City 2500 bitmasks, constructive-algorithms...

CF 1479A - Searching Local Minimum

CF 1479A - Searching Local Minimum Rating: 1700 Tags: binary search, interactive, ternary search Solve time: 2m 8s Verified: yes Solution Problem Understanding We are asked to find a local minimum in a hidden permutation of integers from 1 to $n$. The permutation is a rearrangement of numbers $1$ to $n$ without repetition. A local minimum is an index $k$ such that the value at $a_k$ is strictly smaller than...

CF 1482G - Vabank

CF 1482G - Vabank Rating: 3200 Tags: binary search, interactive Solve time: 2m 59s 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 integers: 202 ,...

CF 1486C2 - Guessing the Greatest (hard version)

CF 1486C2 - Guessing the Greatest (hard version) Rating: 1900 Tags: binary search, interactive Solve time: 2m 52s Verified: no Solution Problem Understanding We are given a hidden array of distinct values, and we can only interact with it through queries. Each query asks for a subsegment and returns the position of the second largest value inside that subsegment (but the index is reported in the original array). Our goal...

CF 1486C1 - Guessing the Greatest (easy version)

CF 1486C1 - Guessing the Greatest (easy version) Rating: 1600 Tags: binary search, interactive Solve time: 3m 1s 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 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 1498E - Two Houses

CF 1498E - Two Houses Rating: 2200 Tags: brute force, graphs, greedy, interactive, sortings Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a city with $n$ houses, where for each pair of houses there is exactly one directed road connecting them, either from the first to the second or vice versa. The input does not specify the directions of these roads. Instead, we are given an...

Codeforces Round 712 (Div. 1)

Codeforces Round 712 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1600-3500 | Time: 26m 57s Problem Name Rating Tags Solve Time Verified A Balance the Bits 1600 constructive-algorithms, greedy 3m 28s ✗ B 3-Coloring 1700 constructive-algorithms, games, interactive 6m 29s ✗ C Travelling Salesman Problem 2200 binary-search, data-structures, dp 11m 59s ✓ D Flip the Cards 2600 2-sat, constructive-algorithms, data-structures 1m 1s ✗...

CF 1503B - 3-Coloring

CF 1503B - 3-Coloring Rating: 1700 Tags: constructive algorithms, games, interactive Solve time: 6m 29s Verified: no Solution Problem Understanding Alice and Bob are filling an $n \times n$ grid. On every turn Alice first announces a color from ${1,2,3}$. Bob must then choose an empty cell and place a token of a different color. Bob loses immediately if two edge-adjacent cells ever end up with the same color. His...

April Fools Day Contest 2021

April Fools Day Contest 2021 Type: April Fools | Problems: 9 | Verified: 6/9 | Rating range: 900-2600 | Time: 32m 41s Problem Name Rating Tags Solve Time Verified A Is it rated - 2 900 *special, implementation, interactive 7m 52s ✓ B DMCA 1600 *special, implementation, number-theory 5m 40s ✗ C Fibonacci Words 1400 *special, implementation 3m 11s ✓ D Xenolith? Hippodrome? 1800 *special, number-theory 2m 17s ✓ E...

CF 1505A - Is it rated - 2

CF 1505A - Is it rated - 2 Rating: 900 Tags: *special, implementation, interactive Solve time: 7m 52s Verified: yes Solution The runtime error here is a simple input parsing mistake . The input has a test case format where each test case consists of a number n followed by a string of length n . The previous code assumes that the first line of each test case contains two...

CF 1510I - Is It Rated?

CF 1510I - Is It Rated? Rating: 2700 Tags: greedy, interactive, math, probabilities Solve time: 3m 29s Verified: no Solution Problem Understanding In this problem, you act as a participant, Izzy, in a series of wagers predicting whether improv contests will be rated or unrated. For each wager, you see the predictions of all other participants, then make your own prediction. After that, the real outcome is revealed. Your goal...

CF 1514E - Baby Ehab's Hyper Apartment

CF 1514E - Baby Ehab's Hyper Apartment Rating: 2700 Tags: binary search, graphs, interactive, sortings, two pointers Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a single apartment floor modeled as a number line, with n rooms located at integer coordinates from 1 to n. Each room has an initial height assigned to it, and we are allowed to modify the heights in a constrained way....

Codeforces Round 720 (Div. 2)

Codeforces Round 720 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 0/5 | Rating range: 1000-2700 | Time: 26m 47s Problem Name Rating Tags Solve Time Verified A Nastia and Nearly Good Numbers 1000 constructive-algorithms, math, number-theory 2m 11s ✗ B Nastia and a Good Array 1300 constructive-algorithms, math, number-theory 4m 34s ✗ C Nastia and a Hidden Permutation 2000 constructive-algorithms, interactive 2m 36s ✗ D Nastia Plays...

CF 1521C - Nastia and a Hidden Permutation

CF 1521C - Nastia and a Hidden Permutation Rating: 2000 Tags: constructive algorithms, interactive Solve time: 2m 36s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden permutation of length n containing all integers from 1 to n using an interactive querying mechanism. For each query, we choose two distinct indices i and j , a type t (either 1 or 2), and a threshold x ....

CF 1526F - Median Queries

CF 1526F - Median Queries Rating: 3000 Tags: constructive algorithms, interactive, probabilities Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a hidden permutation of the numbers from 1 to n. The permutation is fixed, but we never see it directly. Instead, we can only interact with it through a query on three indices. A query picks three distinct positions a, b, c, and returns the median...

CF 1534H - Lost Nodes

CF 1534H - Lost Nodes Rating: 3500 Tags: constructive algorithms, dp, graphs, interactive, sortings, trees Solve time: 1m 32s Verified: no Solution Setup and Assumptions Consider a closed container of fixed volume $V$ containing an ideal gas whose bulk temperature is $T_1$. The container walls are maintained at temperature $T$, and $T$ need not equal $T_1$. The problem asks for the instantaneous pressure exerted by the gas on the walls...

CF 1534D - Lost Tree

CF 1534D - Lost Tree Rating: 1800 Tags: constructive algorithms, interactive, trees Solve time: 6m 14s Verified: no Solution Problem Understanding We are asked to reconstruct an unweighted tree given a limited interactive query mechanism. The tree has $n$ nodes labeled $1$ through $n$, and we are allowed to query the distance from any chosen node to all others. Each query returns an array where the $i$-th entry is the...

CF 1534E - Lost Array

CF 1534E - Lost Array Rating: 2300 Tags: graphs, greedy, interactive, shortest paths Solve time: 2m 40s Verified: no Solution Problem Understanding We are given a hidden array of length n . We cannot see its elements directly, but we are allowed to ask queries. Each query chooses exactly k distinct positions, and the system returns the XOR of the values at those positions. Our goal is not to reconstruct...

CF 1535E - Gold Transfer

CF 1535E - Gold Transfer Rating: 2200 Tags: binary search, data structures, dp, greedy, interactive, trees Solve time: 7m 16s Verified: no Solution I see what is happening. The actual output is empty. That usually happens when the code reads input correctly but never prints anything, which often occurs if we are using input = sys.stdin.readline but forget to strip() the newline when converting to integers, or we are printing...

CF 1545D - AquaMoon and Wrong Coordinate

CF 1545D - AquaMoon and Wrong Coordinate Rating: 3000 Tags: constructive algorithms, interactive, math Solve time: 5m 40s Verified: no Solution

CF 1562F - Tubular Bells

CF 1562F - Tubular Bells Rating: 2900 Tags: interactive, math, number theory, probabilities Solve time: 3m 24s Verified: no Solution Problem Understanding We are given a hidden permutation of integers that forms a contiguous interval, but the endpoints of that interval are unknown. Each position in the permutation stores a distinct integer, and together they cover every value in some range of length $n$. The only way to learn about...

CF 1566H - Xor-quiz

CF 1566H - Xor-quiz Rating: 3200 Tags: constructive algorithms, dp, interactive, math, number theory Solve time: 4m 33s Verified: no Solution Problem Understanding We are given a hidden set $A$ of size $n$, where every element is an integer between $1$ and $c$. We can query any value $x$, and the judge responds with a value computed from the elements of $A$: it takes all $y \in A$ that are...

CF 1578I - Interactive Rays

CF 1578I - Interactive Rays Rating: 3300 Tags: geometry, interactive Solve time: 2m 13s Verified: no Solution Problem Understanding We are working in a plane where a circle is hidden from us. The circle is fully determined by its center coordinates and its radius, but we do not know them. Our only tool is to shoot a ray starting from the origin and passing through an integer point we choose....

Technocup 2022 - Elimination Round 2

Technocup 2022 - Elimination Round 2 Type: Special | Problems: 7 | Verified: 3/7 | Rating range: 800-3200 | Time: 22m 9s Problem Name Rating Tags Solve Time Verified A Mathematical Addition 800 math 5m 41s ✗ B Coloring Rectangles 1000 greedy, math 1m 43s ✓ C Two Arrays 900 greedy, math, sortings 1m 42s ✓ D Guess the Permutation 2000 binary-search, combinatorics, interactive 2m 25s ✗ E Game with...

CF 1584D - Guess the Permutation

CF 1584D - Guess the Permutation Rating: 2000 Tags: binary search, combinatorics, interactive, math Solve time: 2m 25s Verified: no Solution Problem Understanding We are given a sequence of length $n$ that initially contains integers from $1$ to $n$ in increasing order. Then the jury selects three indices $i < j < k$ with $j - i > 1$ and reverses two subsegments: the first from $i$ to $j-1$, and...

CF 1592D - Hemose in ICPC ?

CF 1592D - Hemose in ICPC ? Rating: 2300 Tags: binary search, dfs and similar, implementation, interactive, math, number theory, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a tree where each edge has an unknown positive weight. We cannot see these weights, but we are allowed to interact with a device that reveals a specific structural property of any chosen subset of nodes. For...

CF 1599H - Hidden Fortress

CF 1599H - Hidden Fortress Rating: 2100 Tags: interactive, math Solve time: 1m 46s Verified: no Solution Problem Understanding We are working on a huge integer grid, and somewhere inside it lies a hidden axis-aligned rectangle. We are not allowed to enter this rectangle directly. Instead, we can probe any grid cell and receive the Manhattan distance to the closest point of the rectangle, unless we accidentally probe inside it,...

CF 1617D2 - Too Many Impostors (hard version)

CF 1617D2 - Too Many Impostors (hard version) Rating: 2400 Tags: constructive algorithms, implementation, interactive, math Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a group of n players, each labeled from 1 to n , where n is always a multiple of 3. Some of these players are impostors, and the rest are crewmates. We do not know the number of impostors k in advance,...

CF 1617D1 - Too Many Impostors (easy version)

CF 1617D1 - Too Many Impostors (easy version) Rating: 1800 Tags: constructive algorithms, implementation, interactive Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a set of players, each of whom is either an impostor or a crewmate. The total number of players, $n$, is divisible by three. Among these players, the number of impostors, $k$, is unknown but guaranteed to be strictly between one-third and two-thirds...

Hello 2022

Hello 2022 Type: Special | Problems: 9 | Verified: 2/9 | Rating range: 800-3500 | Time: 19m 10s Problem Name Rating Tags Solve Time Verified A Stable Arrangement of Rooks 800 constructive-algorithms 6m 15s ✗ B Integers Shop 1500 data-structures, greedy, implementation 1m 49s ✓ C Hidden Permutations 1700 dfs-and-similar, interactive, math 1m 40s ✗ D The Winter Hike 2100 constructive-algorithms, greedy, math 1m 40s ✗ E New School 2300...

CF 1621C - Hidden Permutations

CF 1621C - Hidden Permutations Rating: 1700 Tags: dfs and similar, interactive, math Solve time: 1m 40s Verified: no Solution Problem Understanding We are dealing with two permutations of the same set of indices from 1 to n. One permutation, call it p, is hidden and fixed. The second permutation, q, starts as the identity permutation but is not stable: every time we ask for any single value of q,...

CF 1624F - Interacdive Problem

CF 1624F - Interacdive Problem Rating: 2000 Tags: binary search, constructive algorithms, interactive Solve time: 1m 34s Verified: no Solution Problem Understanding We are interacting with a hidden integer $x$, where we are initially told a modulus-like parameter $n$. The only way to influence or observe the hidden state is by issuing commands that add a chosen value $c$ to $x$, after which we are told the value of $\lfloor...

CF 1628C - Grid Xor

CF 1628C - Grid Xor Rating: 2300 Tags: constructive algorithms, greedy, implementation, interactive, math Solve time: 7m 41s Verified: no Solution Problem Understanding We are given an even-sized $n \times n$ grid of integers that was stolen, and instead of the original numbers, we only know the XOR of the neighbors of each cell. Our task is to compute the XOR of all the original numbers in the grid. Neighbors...

CF 1633F - Perfect Matching

CF 1633F - Perfect Matching Rating: 2800 Tags: data structures, divide and conquer, interactive, trees Solve time: 39s Verified: no Solution Working

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 1634D - Finding Zero

CF 1634D - Finding Zero Rating: 2000 Tags: constructive algorithms, interactive, math Solve time: 1m 45s Verified: no Solution Problem Understanding We are given an array of hidden non-negative integers, and exactly one position in it contains a zero. Our only way to learn about the array is through queries that inspect any three distinct indices. A query does not reveal the values themselves, instead it returns the spread of...

Pinely Treasure Hunt Contest

Pinely Treasure Hunt Contest Type: Special | Problems: 11 | Verified: 9/11 | Rating range: - | Time: 14m 19s Problem Name Rating Tags Solve Time Verified A Treasure Hunt - graphs, interactive 1m ✓ B Treasure Hunt - graphs, interactive 1m 14s ✓ C Treasure Hunt - graphs, interactive 55s ✓ D Treasure Hunt - graphs, interactive 2m 31s ✗ E Treasure Hunt - graphs, interactive 1m 7s ✓...

CF 1639K - Treasure Hunt

CF 1639K - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 2m 27s 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 derive...

CF 1639I - Treasure Hunt

CF 1639I - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 1m 17s Verified: yes Solution Problem Understanding We are exploring an unknown connected graph, but we never see global labels of vertices or edges. Instead, we start at a known vertex and repeatedly move along incident edges chosen locally. Whenever we arrive at a vertex for the first time, it is marked as visited and this information becomes...

CF 1639J - Treasure Hunt

CF 1639J - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 56s Verified: yes Solution Problem Understanding The problem presents an interactive treasure hunt on a hidden undirected graph. Each vertex corresponds to a junction with a treasure. You begin at a specified start vertex, and every time you visit a new vertex, you collect the treasure there. The challenge is that when standing at a vertex, you do...

CF 1639D - Treasure Hunt

CF 1639D - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 2m 31s 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 derive...

CF 1639G - Treasure Hunt

CF 1639G - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 1m 6s Verified: yes Solution Problem Understanding We are exploring an unknown connected graph. We know the complete graph beforehand, including every edge, but once the interaction starts we lose the vertex labels. At every step we stand at some vertex and receive only the degrees of its neighbors together with a bit telling whether that neighbor has...

CF 1639H - Treasure Hunt

CF 1639H - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 53s Verified: yes Solution Problem Understanding We are asked to simulate a treasure hunt on an unknown undirected graph. Each vertex has a treasure and a flag. We start at a known vertex, and at each move, we are shown the degrees of the neighbors and whether they already have a flag. We do not know the labels...

CF 1639E - Treasure Hunt

CF 1639E - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 1m 7s Verified: yes Solution Problem Understanding We are placed inside an unknown connected undirected graph. We start at a known vertex, but after that we never see vertex IDs again in a useful way. Every time we arrive at a vertex, the interactor shows us only its degree and a list of its neighbors in random order....

CF 1639F - Treasure Hunt

CF 1639F - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 53s Verified: yes Solution Problem Understanding We are asked to simulate a treasure hunt on a hidden, undirected graph. Each vertex represents a junction with a treasure, and each edge is a road connecting junctions. You start at a known vertex, and your goal is to visit every vertex at least once, collecting treasures as you go. Each...

CF 1639B - Treasure Hunt

CF 1639B - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 1m 14s Verified: yes Solution Problem Understanding This task is an interactive graph exploration problem. We start from a known vertex of a connected undirected graph. Every vertex contains a treasure, and the first time we visit a vertex we automatically mark it with a flag. From the current position we only see, for each neighboring vertex, its...

CF 1639A - Treasure Hunt

CF 1639A - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 1m Verified: yes Solution Problem Understanding The problem presents a treasure hunt on an undirected graph where each vertex represents a junction and each edge represents a road connecting junctions. You start at a given vertex, and every time you visit a vertex for the first time, you dig up a treasure and place a flag. The challenge...

CF 1639C - Treasure Hunt

CF 1639C - Treasure Hunt Rating: - Tags: graphs, interactive Solve time: 55s Verified: yes Solution Problem Understanding We are given a treasure-hunting scenario mapped onto an undirected graph. Each vertex represents a junction containing a treasure, and edges represent roads connecting the junctions. The hunter starts at a specific vertex and can move along edges to adjacent vertices. At each vertex, the hunter observes two pieces of information about...

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 1666I - Interactive Treasure Hunt

CF 1666I - Interactive Treasure Hunt Rating: 2200 Tags: brute force, constructive algorithms, geometry, interactive, math Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a grid of size $n \times m$ where two treasures are hidden in distinct cells. The goal is to locate both treasures using a combination of two operations: DIG r c and SCAN r c . A DIG attempts to find a...

CF 1672E - notepad.exe

CF 1672E - notepad.exe Rating: 2200 Tags: binary search, constructive algorithms, greedy, interactive Solve time: 2m 9s Verified: no Solution Problem Understanding We are dealing with a hidden array of word lengths, and the only way to learn anything about it is by querying a hypothetical text editor. For any chosen line width $w$, the editor packs words greedily in order, inserting at least one space between adjacent words, and...

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

Codeforces Round 796 (Div. 1)

Codeforces Round 796 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 2/6 | Rating range: 1600-3500 | Time: 12m 43s Problem Name Rating Tags Solve Time Verified A The Enchanted Forest 1600 brute-force, greedy 2m 3s ✗ B Railway System 1700 constructive-algorithms, graphs, greedy 1m 50s ✗ C Sanae and Giant Robot 2500 binary-search, brute-force, data-structures 2m 31s ✗ D Cute number 2900 binary-search, brute-force, data-structures 2m 34s...

CF 1687B - Railway System

CF 1687B - Railway System Rating: 1700 Tags: constructive algorithms, graphs, greedy, interactive, sortings Solve time: 1m 50s Verified: no Solution Problem Understanding We are given a railway network consisting of n stations and m bidirectional tracks, each with a positive length. The network may not be fully connected and can have multiple tracks between the same pair of stations. Each track can either be functional or not, and we...

CF 1697D - Guess The String

CF 1697D - Guess The String Rating: 1900 Tags: binary search, constructive algorithms, interactive Solve time: 2m 11s Verified: no Solution Problem Understanding We are trying to reconstruct an unknown string of length $n$, where each position contains a lowercase letter. The only way to interact with this hidden string is through two operations: we can directly reveal the character at a chosen position, or we can query a segment...

CF 1698D - Fixed Point Guessing

CF 1698D - Fixed Point Guessing Rating: 1600 Tags: binary search, constructive algorithms, interactive Solve time: 2m 13s Verified: no Solution Problem Understanding We start with a permutation of numbers from 1 to n, but the permutation is not arbitrary. It is created from the identity arrangement by choosing disjoint pairs of positions and swapping the values inside each pair. Because n is odd, exactly one position is left untouched...

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 1713D - Tournament Countdown

CF 1713D - Tournament Countdown Rating: 1800 Tags: constructive algorithms, greedy, interactive, number theory, probabilities Solve time: 1m 55s Verified: no Solution Problem Understanding We are dealing with a complete single-elimination tournament of size $2^n$. Players are indexed from 1 to $2^n$. Matches happened in a fixed bracket: adjacent pairs played first, then winners of neighboring matches played again, and so on until one champion remains. We do not see...

CF 1715F - Crop Squares

CF 1715F - Crop Squares Rating: 2700 Tags: constructive algorithms, geometry, interactive, math Solve time: 1m 59s Verified: no Solution Problem Understanding We are given a rectangular field aligned with axes, and somewhere inside it there is a hidden axis-aligned unit square whose lower-left corner is unknown. We cannot directly query points or coordinates. Instead, we have a very specific tool: we can submit a polygon, and the system returns...

CF 1738F - Connectivity Addicts

CF 1738F - Connectivity Addicts Rating: 2400 Tags: constructive algorithms, dsu, graphs, greedy, interactive, shortest paths, trees Solve time: 2m 35s Verified: no Solution Problem Understanding We are given an undirected graph where initially we only know the number of vertices and the degree of each vertex. The task is to assign a color to each vertex so that two conditions hold. First, vertices sharing a color must form a...

CF 1746E1 - Joking (Easy Version)

CF 1746E1 - Joking (Easy Version) Rating: 2500 Tags: binary search, constructive algorithms, interactive, ternary search Solve time: 2m 18s Verified: no Solution Problem Understanding In this problem, you are trying to identify a hidden integer x between 1 and n . You can ask whether x belongs to any subset of numbers you choose. Each response is either "YES" or "NO". However, some responses may be false - we...

CF 1746E2 - Joking (Hard Version)

CF 1746E2 - Joking (Hard Version) Rating: 3200 Tags: dp, interactive Solve time: 1m 22s Verified: no Solution I can't reliably diagnose a timeout from the input/output pair alone. A timeout means the program is running too long, not that it produced an incorrect value. To identify the bug, I need to see the actual Python code that timed out. For this problem, the distinction matters because the cause could...

CF 1761G - Centroid Guess

CF 1761G - Centroid Guess Rating: 3500 Tags: interactive, probabilities, trees Solve time: 5m 43s Verified: no Solution Problem Understanding We are given a hidden tree with n nodes, and we do not know its structure. Our goal is to identify its centroid, which is the unique node such that removing it leaves all connected components with at most n/2 nodes each. The interaction allows us to query the distance...

CF 1762D - GCD Queries

CF 1762D - GCD Queries Rating: 2100 Tags: constructive algorithms, interactive, number theory Solve time: 2m 21s Verified: no Solution Problem Understanding We are asked to find an index of the element 0 in a hidden permutation of integers from 0 to n-1 . The permutation is not given directly, but we can ask for the greatest common divisor (GCD) of any two distinct elements in the array. The interaction...

CF 1764G3 - Doremy's Perfect DS Class (Hard Version)

CF 1764G3 - Doremy's Perfect DS Class (Hard Version) Rating: 3300 Tags: binary search, interactive Solve time: 8m 26s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 1 to $n$, and our goal is to identify the position of the number 1 with at most 20 interactive queries. Each query allows us to select a contiguous subarray $[l,r]$ and an integer $k$, then receive...

CF 1764G1 - Doremy's Perfect DS Class (Easy Version)

CF 1764G1 - Doremy's Perfect DS Class (Easy Version) Rating: 2900 Tags: binary search, interactive Solve time: 6m 7s Verified: no Solution Problem Understanding We are asked to locate the position of the number 1 in a hidden permutation of integers from 1 to n . The permutation is fixed, and we can query the permutation by providing a range [l, r] and a divisor k . The query returns...

CF 1764G2 - Doremy's Perfect DS Class (Medium Version)

CF 1764G2 - Doremy's Perfect DS Class (Medium Version) Rating: 3000 Tags: binary search, interactive Solve time: 2m 7s Verified: no Solution Problem Understanding We are given a hidden permutation of numbers from 1 to n. We cannot see it directly, but we can interactively ask queries. Each query selects a segment of indices and a divisor k, and we are told how many distinct values appear after transforming every...

CF 1765G - Guess the String

CF 1765G - Guess the String Rating: 2600 Tags: constructive algorithms, interactive, probabilities Solve time: 2m 3s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden binary string of length $n$, knowing that its first character is always '0'. We cannot read the string directly. Instead, we can query two special functions: the prefix function $p_i$, which measures the length of the longest prefix that matches the...

SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)

SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 14 | Verified: 4/14 | Rating range: 800-3500 | Time: 26m 25s Problem Name Rating Tags Solve Time Verified A Walking Boy 800 greedy 1m 17s ✓ B Vittorio Plays with LEGO Bricks 2200 dp, geometry 1m 38s ✗ C Library game 2500 games, greedy, interactive 1m 21s ✗ D Teamwork 2800 constructive-algorithms, greedy, math 1m...

CF 1776I - Spinach Pizza

CF 1776I - Spinach Pizza Rating: 2500 Tags: games, geometry, greedy, interactive Solve time: 1m 19s Verified: no Solution Problem Understanding We are given a strictly convex polygon with labeled vertices in counterclockwise order. Each move consists of choosing one currently unused vertex. The chosen vertex determines a triangle formed by that vertex and its two adjacent vertices in the current polygon, and that triangle is removed from the remaining...

CF 1776C - Library game

CF 1776C - Library game Rating: 2500 Tags: games, greedy, interactive, sortings Solve time: 1m 21s Verified: no Solution Problem Understanding We are playing a sequential game on a line of labeled sections, each section representing a distinct subject. Each day, one of two players chooses a contiguous interval of sections, constrained by a fixed length coming from a multiset of available “passes”. After the interval is announced, the opponent...

CF 1779E - Anya's Simultaneous Exhibition

CF 1779E - Anya's Simultaneous Exhibition Rating: 2400 Tags: constructive algorithms, graphs, greedy, interactive, sortings Solve time: 3m 24s Verified: no Solution Problem Understanding We are asked to identify candidate masters among a group of chess players where the outcome of any head-to-head match is deterministic but may be non-transitive. That means some cycles can exist, such as player A beating B, B beating C, and C beating A. Anya...

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

Codeforces Round 864 (Div. 2)

Codeforces Round 864 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-3000 | Time: 10m 17s Problem Name Rating Tags Solve Time Verified A Li Hua and Maze 800 constructive-algorithms, flows, graphs 1m 35s ✗ B Li Hua and Pattern 1100 constructive-algorithms, greedy 1m 21s ✓ C Li Hua and Chess 1600 constructive-algorithms, greedy, interactive 1m 47s ✗ D Li Hua and Tree 1900...

CF 1797C - Li Hua and Chess

CF 1797C - Li Hua and Chess Rating: 1600 Tags: constructive algorithms, greedy, interactive Solve time: 1m 47s Verified: no Solution Problem Understanding We are dealing with a hidden position on an extremely large grid, up to one billion in both dimensions. A king is placed on one cell, and our task is to determine its exact coordinates. We cannot directly access the position. Instead, we can query any cell...

Codeforces Round 859 (Div. 4)

Codeforces Round 859 (Div. 4) Type: Div. 4 | Problems: 8 | Verified: 4/8 | Rating range: 800-1700 | Time: 13m 51s Problem Name Rating Tags Solve Time Verified A Plus or Minus 800 implementation 3m 56s ✗ B Grab the Candies 800 greedy 1m 26s ✓ C Find and Replace 800 greedy, implementation, strings 1m 54s ✓ D Odd Queries 900 data-structures, implementation 1m 29s ✓ E Interview 1300...

CF 1807E - Interview

CF 1807E - Interview Rating: 1300 Tags: binary search, implementation, interactive Solve time: 1m 39s Verified: no Solution Problem Understanding We are given several independent test cases. In each one there is a collection of piles of stones. Every pile contains some number of stones, and all stones have weight 1 except for a single hidden special stone located in exactly one pile, which contributes an extra unit of weight....

CF 1812H - Expected Twist

CF 1812H - Expected Twist Rating: - Tags: *special, interactive Solve time: 1m 24s Verified: no Solution Problem Understanding We are given a hidden array of length $n$, and the only way to interact with it is to ask for the maximum value inside any contiguous segment. Each query reveals a single number: the maximum over a chosen interval. The goal is to determine the minimum element of the entire...

CF 1815B - Sum Graph

CF 1815B - Sum Graph Rating: 2000 Tags: brute force, constructive algorithms, graphs, implementation, interactive, shortest paths, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are asked to identify a hidden permutation of numbers from 1 to n by interacting with a graph that we construct using queries. Initially, the graph has n isolated nodes. A type 1 query "+ x" adds edges connecting nodes whose indices...

CF 1819E - Roads in E City

CF 1819E - Roads in E City Rating: 3200 Tags: interactive, math, probabilities, trees Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a city represented as a graph with intersections as nodes and roads as edges. Some roads have been repaired and allow traffic, while others have not. Our task is to determine exactly which roads are repaired. The twist is that we do not know...

CF 1826F - Fading into Fog

CF 1826F - Fading into Fog Rating: 2800 Tags: geometry, interactive, math, probabilities Solve time: 1m 21s Verified: no Solution Problem Understanding We are asked to find a set of hidden points on a 2D plane using queries that return projections of all points onto a line of our choice. Each query gives us the locations of these projections along the line, with slight precision errors. The points themselves are...

CF 1838F - Stuck Conveyor

CF 1838F - Stuck Conveyor Rating: 3000 Tags: binary search, constructive algorithms, interactive Solve time: 3m 6s Verified: no Solution Where the previous logic goes wrong The earlier solution implicitly assumed: We only need to satisfy density constraints in contiguous blocks of size $k$. But the actual condition is stronger and prefix-suffix symmetric at every position $i$ : For every $i$: first $i$ elements contain at least $\lceil i/k \rceil$...

CF 1839E - Decreasing Game

CF 1839E - Decreasing Game Rating: 2400 Tags: constructive algorithms, dfs and similar, dp, greedy, interactive Solve time: 1m 19s Verified: no Solution Problem Understanding We are playing a two-person game on an array of positive integers. In each round, the first player chooses a position with a positive value, then the second player must choose a different position that is also positive. The two chosen values are reduced simultaneously...

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

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

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

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

CF 1846F - Rudolph and Mimic

CF 1846F - Rudolph and Mimic Rating: 1800 Tags: constructive algorithms, implementation, interactive Solve time: 1m 14s Verified: no Solution Problem Understanding We are given a collection of positions, each holding an object with a visible type label. Hidden among them is a single special entity, the mimic. The mimic occupies exactly one position, but it is allowed to change what type it appears to be over time, and it...

CF 1847E - Triangle Platinum?

CF 1847E - Triangle Platinum? Rating: 2900 Tags: brute force, combinatorics, implementation, interactive, math, probabilities Solve time: 1m 20s Verified: no Solution Problem Understanding We are given an array of $n$ hidden integers, each between $1$ and $4$. We cannot see these numbers directly, but we can ask queries about triples of indices. Each query returns a number related to the area of a triangle formed by the three values...

CF 1854D - Michael and Hotel

CF 1854D - Michael and Hotel Rating: 3000 Tags: binary search, interactive, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a directed graph on $n \le 500$ vertices where each vertex has exactly one outgoing edge. From every room $i$, a teleporter sends us deterministically to room $a_i$. Repeating teleportation means repeatedly applying this function, so after $k$ steps we are at $f^k(u)$, where $f(i)=a_i$....

CF 1855F - Michael and Hotel

CF 1855F - Michael and Hotel Rating: 3000 Tags: binary search, interactive Solve time: 1m 24s Verified: no Solution Problem Understanding We are given a hotel with n rooms, numbered 1 through n , each equipped with a teleporter that deterministically sends anyone in that room to a fixed target room. The array a of length n encodes these teleporters, where a[i] is the room you arrive in if you...

CF 1856D - More Wrong

CF 1856D - More Wrong Rating: 2100 Tags: divide and conquer, interactive Solve time: 1m 33s Verified: no Solution Problem Understanding We are asked to find the position of the maximum element in a hidden permutation of length $n$ by using queries that tell us the number of inversions in a subarray. Each query has a cost that grows quadratically with the subarray length, and we have a global budget...

Codeforces Round 1093 (Div. 2)

Codeforces Round 1093 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 0/7 | Rating range: 1400-2700 | Time: 12m 27s Problem Name Rating Tags Solve Time Verified A Blocked - greedy, sortings 2m 44s ✗ B OIE Excursion - greedy 1m 37s ✗ C Grid L 1400 brute-force, math 1m 25s ✗ D1 Unique Values (Easy version) 1900 binary-search, interactive 1m 50s ✗ D2 Unique Values (Hard version)...

CF 2220D2 - Unique Values (Hard version)

CF 2220D2 - Unique Values (Hard version) Rating: 2000 Tags: binary search, interactive Solve time: 1m 48s Verified: no Solution Problem Understanding We are given an array of length $2n+1$. Every number from $1$ to $n$ appears exactly twice, except for one special value that appears three times. This creates a very rigid structure: all values are paired except one value that has an “extra copy”. We do not see...

CF 2220D1 - Unique Values (Easy version)

CF 2220D1 - Unique Values (Easy version) Rating: 1900 Tags: binary search, interactive Solve time: 1m 50s Verified: no Solution Problem Understanding In the original interactive problem, there is a hidden array of length $2n+1$. Every value from $1$ to $n$ appears exactly twice, except for one special value that appears three times. The task is to identify the three positions containing that special value. For the non-interactive version used...

CF 2216E - Oriented Journey

CF 2216E - Oriented Journey Rating: 2200 Tags: communication, constructive algorithms, interactive Solve time: 2m 1s Verified: no Solution The value $V = 7\frac{1}{16}$ corresponds to the chi-square statistic computed from $k = 11$ categories, as in Eq. (5). The number of degrees of freedom is therefore $\nu = k - 1 = 10$. To determine whether $V$ is improbably high, one consults the line of Table 1 corresponding to...

CF 2197E2 - Interactive Graph (Hard Version)

CF 2197E2 - Interactive Graph (Hard Version) Rating: 2000 Tags: combinatorics, dfs and similar, dp, graphs, interactive Solve time: 1m 28s Verified: no Solution Problem Understanding We are tasked with reconstructing a hidden directed acyclic graph with n vertices by asking queries about its paths. Each query gives the k -th path in lexicographical order. Our goal is to identify all the edges in the graph using at most n...

CF 2197E1 - Interactive Graph (Simple Version)

CF 2197E1 - Interactive Graph (Simple Version) Rating: 1800 Tags: binary search, combinatorics, dfs and similar, dp, graphs, interactive Solve time: 1m 27s Verified: no Solution Problem Understanding We are tasked with reconstructing an unknown directed acyclic graph using an interactive interface. The graph has n vertices and an unknown number of edges m , and no loops or multiple edges. The only way to probe the graph is by...

CF 2191E - Comparable Permutations

CF 2191E - Comparable Permutations Rating: 2300 Tags: interactive, two pointers Solve time: 2m 4s Verified: no Solution Something went wrong. If this issue persists please contact us through our help center at help.openai.com.

CF 2160D - MAD Interactive Problem

CF 2160D - MAD Interactive Problem Rating: 1700 Tags: constructive algorithms, greedy, interactive, math Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a hidden array of length $2n$. Every number from $1$ to $n$ appears exactly twice, but their order is unknown. We cannot see the array directly. Instead, we can query any subset of indices, and the system returns a single value: the largest number...

CF 2151G1 - Hidden Single (Version 1)

CF 2151G1 - Hidden Single (Version 1) Rating: 2600 Tags: binary search, divide and conquer, interactive, math Solve time: 1m 30s Verified: no Solution Problem Understanding We are given a hidden array of length 2n-1 where each number from 1 to n appears exactly twice except for one number, which appears exactly once. Our goal is to determine which number appears only once. We do not need to find its...

CF 2151G2 - Hidden Single (Version 2)

CF 2151G2 - Hidden Single (Version 2) Rating: 2800 Tags: binary search, divide and conquer, interactive, math, probabilities Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a hidden sequence of length $2n-1$ that contains every number from $1$ to $n$ exactly twice, except for one special value that appears only once. So the multiset looks like a perfect pairing structure with a single unpaired element. We...

CF 2136F2 - From the Unknown (Hard Version)

CF 2136F2 - From the Unknown (Hard Version) Rating: 2500 Tags: constructive algorithms, interactive, math Solve time: 1m 26s Verified: no Solution Problem Understanding We are interacting with a text editor whose behavior depends on a hidden parameter $W$, the width of a line. An article is a sequence of word lengths, and the editor lays words into lines greedily: it fills the current line until the next word would...

CF 2136F1 - From the Unknown (Easy Version)

CF 2136F1 - From the Unknown (Easy Version) Rating: 2100 Tags: constructive algorithms, interactive Solve time: 1m 28s Verified: no Solution Problem Understanding We are given an interactive editor that wraps words into lines based on a hidden width parameter $W$. Each article is represented as a sequence of word lengths. The editor outputs either the number of lines needed to display the article if every word fits within the...

CF 2136D - For the Champion

CF 2136D - For the Champion Rating: 1700 Tags: constructive algorithms, interactive, math Solve time: 2m 4s Verified: no Solution Solution Let $p = \beta - \alpha$ be the probability that a single $U_j$ lies in the interval $[\alpha, \beta)$, as in equation (4). A gap of length $r$ occurs when $r$ consecutive $U$'s fall outside $[\alpha, \beta)$, followed by a $U$ inside the interval. For a random sequence, the...

CF 2130E3 - Interactive RBS (Hard Version)

CF 2130E3 - Interactive RBS (Hard Version) Rating: 2300 Tags: interactive Solve time: 1m 37s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden sequence of parentheses of length $n$ using an interactive oracle. The sequence contains only '(' and ')' characters and is guaranteed to have at least one opening and one closing bracket. We can query the oracle by selecting up to 1000 indices, possibly...

CF 2130E2 - Interactive RBS (Medium Version)

CF 2130E2 - Interactive RBS (Medium Version) Rating: 2000 Tags: binary search, bitmasks, constructive algorithms, interactive, strings Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a hidden sequence of parentheses of length n , containing at least one '(' and one ')' . The sequence is regular in the sense that some of its contiguous substrings are valid bracket sequences. Our goal is to determine the...

CF 2130E1 - Interactive RBS (Easy Version)

CF 2130E1 - Interactive RBS (Easy Version) Rating: 1900 Tags: binary search, constructive algorithms, interactive, strings Solve time: 2m Verified: no Solution Problem Understanding In the original interactive problem there is a hidden bracket sequence consisting of '(' and ')' . We may ask queries about selected positions, and the judge returns the number of regular bracket substrings in the constructed string. The goal is to reconstruct the entire hidden...

CF 2078E - Finding OR Sum

CF 2078E - Finding OR Sum Rating: 1900 Tags: bitmasks, implementation, interactive, math Solve time: 1m 29s Verified: no Solution Problem Understanding We are given two hidden non-negative integers, x and y , each less than $2^{30}$. Our goal is to determine the sum of bitwise ORs $(m \mid x) + (m \mid y)$ for a given integer m . The catch is that we are allowed only two interactive...

CF 2067D - Object Identification

CF 2067D - Object Identification Rating: 1400 Tags: constructive algorithms, graphs, interactive Solve time: 1m 52s Verified: no Solution Problem Understanding We are given an array x of length n with integers from 1 to n , and a hidden array y of the same length. Each pair (x_i, y_i) is unique and x_i ≠ y_i . The challenge is to identify whether the hidden object is a directed graph...

CF 1994H - Fortnite

CF 1994H - Fortnite Rating: 3500 Tags: combinatorics, constructive algorithms, games, greedy, hashing, interactive, math, number theory, strings Solve time: 2m 4s Verified: no Solution Exploration The first problem asks whether an infinite sequence of perfect squares $(a_n^2)$ can exist such that each term starting from the third satisfies the Fibonacci-type recurrence $a_n^2 = a_{n-1}^2 + a_{n-2}^2.$ Since squares grow faster than linearly and the recurrence is additive, the existence...

CF 1987H - Fumo Temple

CF 1987H - Fumo Temple Rating: 3500 Tags: interactive Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to find a hidden cell in a rectangular matrix of size $n \times m$, where each cell contains either -1, 0, or 1. The cell we are searching for is special: when we query any other cell, the response we receive is the Manhattan distance to the hidden cell...

CF 1937C - Bitwise Operation Wizard

CF 1937C - Bitwise Operation Wizard Rating: 1700 Tags: bitmasks, constructive algorithms, interactive Solve time: 3m 9s Verified: no Solution Problem Understanding We are interacting with a hidden permutation of numbers from 0 to n-1 , but we never see it directly. Instead, we are allowed to compare expressions of the form (p[a] | p[b]) , where | is bitwise OR, by querying the interactor. Each query compares two such...

CF 1930H - Interactive Mex Tree

CF 1930H - Interactive Mex Tree Rating: 3300 Tags: constructive algorithms, dfs and similar, interactive, trees Solve time: 3m 43s Verified: no Solution Problem Understanding We are dealing with a tree, but the real structure we care about is hidden behind an interactive layer. In every test case, we must output two permutations of node labels. After that, in each query round, an adversary chooses two nodes and secretly assigns...

CF 1858E2 - Rollbacks (Hard Version)

CF 1858E2 - Rollbacks (Hard Version) Rating: 2600 Tags: data structures, interactive, trees Solve time: 1m 2s Verified: yes Solution Problem Understanding We are asked to maintain a dynamic array while processing four types of queries: append a number, remove the last $k$ numbers, roll back the last change (append or remove), and report the number of distinct numbers in the array. The array is initially empty. Every rollback undoes...

CF 1867E2 - Salyg1n and Array (hard version)

CF 1867E2 - Salyg1n and Array (hard version) Rating: 2200 Tags: constructive algorithms, interactive Solve time: 1m 39s Verified: no Solution Problem Understanding We are given an array of hidden integers and a fixed segment length $k$. We are not allowed to directly inspect the array, but we can ask queries on any contiguous block of exactly $k$ elements. A query returns the XOR of that block, but it also...

CF 1867E1 - Salyg1n and Array (simple version)

CF 1867E1 - Salyg1n and Array (simple version) Rating: 2000 Tags: constructive algorithms, interactive, math Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a hidden array of length $n$, where each element is an integer. We do not see the array directly. Instead, we are allowed to ask queries on contiguous segments of fixed length $k$. Each query asks for the XOR of a segment of...

CF 1867C - Salyg1n and the MEX Game

CF 1867C - Salyg1n and the MEX Game Rating: 1300 Tags: constructive algorithms, data structures, games, greedy, interactive Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a sorted set of distinct integers. We do not control this set directly; instead, we interact with an opponent through moves that change it. Each move we either insert a new number into the set or allow Bob to remove...

CF 1879E - Interactive Game with Coloring

CF 1879E - Interactive Game with Coloring Rating: 2400 Tags: brute force, constructive algorithms, dfs and similar, graphs, implementation, interactive, trees Solve time: 1m 59s Verified: yes Solution Problem Understanding We are given a rooted tree with $n$ vertices, where vertex 1 is the root. Each vertex $i > 1$ has a parent $p_i$, so the tree is naturally defined by this parent array. The task is to color the...

CF 1887E - Good Colorings

CF 1887E - Good Colorings Rating: 3100 Tags: binary search, constructive algorithms, graphs, interactive Solve time: 2m 16s Verified: no Solution Problem Understanding We are asked to interact with a grid of size $n \times n$. Initially, $2n$ cells are pre-colored with unique colors from $1$ to $2n$, and the rest are uncolored. In each of up to 10 allowed moves, we can request Alice to color a previously uncolored...

CF 1896G - Pepe Racing

CF 1896G - Pepe Racing Rating: 3200 Tags: constructive algorithms, implementation, interactive, sortings Solve time: 2m 6s Verified: no Solution Problem Understanding There are $n^2$ racers with distinct speeds. A race may contain exactly $n$ racers, and the only information returned is the winner of that race. The original interactive task asks us to determine the complete ordering of the fastest $n^2-n+1$ racers while using at most $2n^2-2n+1$ races. The...

CF 1903E - Geo Game

CF 1903E - Geo Game Rating: 2000 Tags: greedy, interactive, math Solve time: 2m 14s Verified: no Solution Problem Understanding We are asked to reason about a two-player game on a 2D plane. The game starts from a fixed point and consists of picking points one by one from a set of given points. Each time a point is picked, the square of the Euclidean distance from the previously chosen...

CF 1906C - Cursed Game

CF 1906C - Cursed Game Rating: 3000 Tags: interactive Solve time: 1m 18s Verified: yes Solution Problem Understanding We are asked to play an interactive game against a demon, who hides a 3×3 secret grid with at least one hole. For each round, we are given an odd integer $N$ and must submit an $N \times N$ grid of black and white cells. The demon produces an $(N-2) \times (N-2)$...

CF 1918E - ace5 and Task Order

CF 1918E - ace5 and Task Order Rating: 2200 Tags: constructive algorithms, divide and conquer, implementation, interactive, probabilities, sortings Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 1 to $n$. The permutation is unknown, and our goal is to determine it. The only tool is a number $x$ initially set by the interactor and a query operation: we ask about...

CF 1919H - Tree Diameter

CF 1919H - Tree Diameter Rating: 2000 Tags: interactive, trees Solve time: 2m 14s Verified: no Solution Problem Understanding We are asked to reconstruct an unknown tree with $n$ vertices and $n-1$ edges by interacting with a grader that allows two types of queries. The first query lets us assign arbitrary positive weights to the edges and returns the resulting diameter of the weighted tree. The second query measures the...

CF 1924F - Anti-Proxy Attendance

CF 1924F - Anti-Proxy Attendance Rating: 3500 Tags: constructive algorithms, dp, interactive, ternary search Solve time: 42s Verified: no Solution I can't write a correct editorial for Codeforces 1924F from the problem statement alone. This problem is a 3500-rated interactive problem with a highly nontrivial strategy. To produce the editorial you've requested, I would need the actual solution idea, editorial, accepted code, or at least a detailed description of the...

Codeforces Round 1058 (Div. 1)

Codeforces Round 1058 (Div. 1) Div. 1 | 7 problems | 1/7 verified | Difficulty 1700-3500 | 14m 14s # Problem Rating Tags Accepted Time ✓ A MAD Interactive Problem 1700 constructive-algorithms, implementation, interactive 8,128 2m 27s B Rectangles 2100 brute-force, data-structures, dp 2,308 1m 48s ✓ C Twin Polynomials 2300 combinatorics, graph-matchings, math 1,687 1m 54s D1 Inverse Minimum Partition (Easy Version) 2500 binary-search, brute-force, dp 1,019 2m 20s...

Codeforces Round 1046 (Div. 1)

Codeforces Round 1046 (Div. 1) Div. 1 | 8 problems | 0/8 verified | Difficulty 1200-3500 | 14m 1s # Problem Rating Tags Accepted Time ✓ A Against the Difference 1200 data-structures, dp 18,322 1m 59s B For the Champion 1700 constructive-algorithms, interactive, math 7,334 1m 49s C By the Assignment 2000 binary-search, bitmasks, combinatorics 3,881 1m 52s D1 From the Unknown (Easy Version) 2100 constructive-algorithms, interactive, math 2,433 1m...

April Fools Day Contest 2025

April Fools Day Contest 2025 April Fools | 10 problems | 4/10 verified | Difficulty - | 12m 6s # Problem Rating Tags Accepted Time ✓ A Piecing It Together *special, string-suffix-structures 13,814 39s B Plinko *special, games, interactive 5,992 1m 27s C Would It Be Unrated? *special, binary-search, brute-force 3,744 1m 3s ✓ D Where Am I? *special, geometry 5,301 32s E Pair Count *special, number-theory 785 1m 32s...

Codeforces Round 1025 (Div. 2)

Codeforces Round 1025 (Div. 2) Div. 2 | 8 problems | 2/8 verified | Difficulty 800-3000 | 13m 18s # Problem Rating Tags Accepted Time ✓ A It's Time To Duel 800 implementation 26,948 1m 33s ✓ B Slice to Survive 1200 bitmasks, greedy, math 17,332 1m 37s ✓ C1 Hacking Numbers (Easy Version) 1500 bitmasks, constructive-algorithms, interactive 11,416 1m 39s C2 Hacking Numbers (Medium Version) 1700 constructive-algorithms, interactive, math...

2025 ICPC Asia Pacific Championship - Online Mirror (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2025 ICPC Asia Pacific Championship - Online Mirror (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 13 problems | 3/13 verified | Difficulty 1300-3500 | 8m 55s # Problem Rating Tags Accepted Time ✓ A Control Towers 1900 1,243 41s B Three-Dimensional Embedding 3500 42 39s C Cactus Connectivity 2700 336 55s ✓ D Tower of Hanoi 2400 563 50s E Minus Operator 3300 interactive 76 34s F Hold...

Kotlin Heroes: Episode 12

Kotlin Heroes: Episode 12 Kotlin | 9 problems | 4/9 verified | Difficulty - | 13m 56s # Problem Rating Tags Accepted Time ✓ A Password Generator *special 1,053 1m 53s B Showmatch *special 570 1m 14s ✓ C Coin Game *special, greedy 488 1m 21s ✓ D Uppercase or Lowercase? *special, interactive 267 1m 40s E Color the Arrows *special, dp 163 1m 14s ✓ F Weapon Upgrade *special,...

CF 1934D2 - XOR Break --- Game Version

CF 1934D2 - XOR Break --- Game Version Rating: 2400 Tags: bitmasks, games, greedy, interactive Solve time: 1m 52s Verified: no Solution Problem Understanding We are given a starting number and two players who alternately “decompose” it. A move is only possible if the current number can be written as the XOR of two strictly smaller positive integers. If such a split exists, the active player chooses a valid split,...

CF 1934C - Find a Mine

CF 1934C - Find a Mine Rating: 1700 Tags: binary search, constructive algorithms, geometry, greedy, interactive, math Solve time: 2m 6s Verified: no Solution Problem Understanding We are given a very large grid with n rows and m columns, where n and m can each be up to 10^8. In this grid, exactly two cells contain mines at distinct coordinates. We do not know where the mines are, but we...

Codeforces Round 930 (Div. 1)

Codeforces Round 930 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1700-3400 | Time: 15m 24s Problem Name Rating Tags Solve Time Verified A Bitwise Operation Wizard 1700 bitmasks, constructive-algorithms, greedy 2m 1s ✗ B Pinball 2000 binary-search, data-structures, implementation 2m 22s ✗ C Pok\u00e9mon Arena 2400 data-structures, graphs, greedy 1m 47s ✓ D Bitwise Paradox 3100 binary-search, bitmasks, data-structures 4m 3s ✗ E...

CF 1936A - Bitwise Operation Wizard

CF 1936A - Bitwise Operation Wizard Rating: 1700 Tags: bitmasks, constructive algorithms, greedy, interactive, math Solve time: 2m 1s Verified: no Solution Problem Understanding We are given a hidden permutation of numbers from 0 to $n-1$. Our task is to identify two indices $i$ and $j$ such that the XOR of the values at these positions, $p_i \oplus p_j$, is as large as possible. Direct access to the permutation is...

XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules)

XVIII Open Olympiad in Informatics - Final Stage, Day 1 (Unrated, Online Mirror, IOI rules) Type: ICPC/IOI | Problems: 4 | Verified: 2/4 | Rating range: - | Time: 3m 39s Problem Name Rating Tags Solve Time Verified A Draw Polygon Lines - *special, constructive-algorithms, dp 1m 1s ✓ B Evidence Board - *special, constructive-algorithms, dfs-and-similar 51s ✗ C More Gifts - *special, dfs-and-similar, two-pointers 1m 14s ✓ D Big...

CF 1939A - Draw Polygon Lines

CF 1939A - Draw Polygon Lines Rating: - Tags: *special, constructive algorithms, dp, geometry, interactive Solve time: 1m 1s Verified: yes Solution Problem Understanding We are given a set of points on a 2D plane, and we are asked to draw polygonal lines by connecting these points in a single sequence. Each point must be used exactly once as a vertex of the drawn polyline, and the resulting segments must...

CF 1970D3 - Arithmancy (Hard)

CF 1970D3 - Arithmancy (Hard) Rating: 3100 Tags: interactive Solve time: 2m 23s Verified: no Solution Problem Understanding We are tasked with designing n distinct strings of characters X and O, called magic words. Each student generates a spell by concatenating two of these words in order, possibly the same word twice, and reports the number of distinct non-empty substrings in the resulting spell. Our goal is to reverse this...

CF 1970D2 - Arithmancy (Medium)

CF 1970D2 - Arithmancy (Medium) Rating: 2600 Tags: constructive algorithms, interactive, probabilities, strings Solve time: 1m 57s Verified: no Solution Problem Understanding We are asked to play the role of Professor Vector. We need to construct a set of distinct magic words made of 'X' and 'O' and then, given a number called the power of a spell, figure out which two words (and in which order) were concatenated to...

CF 1970D1 - Arithmancy (Easy)

CF 1970D1 - Arithmancy (Easy) Rating: 2100 Tags: brute force, constructive algorithms, interactive, strings Solve time: 2m 4s Verified: no Solution Problem Understanding We are asked to play the role of Professor Vector in an interactive problem. Our task is twofold. First, we need to generate n distinct magic words consisting only of X and O . Second, given the "power" of a spell, which is defined as the number...

CF 1977E - Tensor

CF 1977E - Tensor Rating: 2600 Tags: constructive algorithms, graphs, interactive Solve time: 2m 2s Verified: no Solution Problem Understanding We are given an interactive problem where there is a hidden directed graph with $n$ vertices, numbered from $1$ to $n$. Each edge in the graph goes "backwards," meaning it connects a higher-numbered vertex $j$ to a lower-numbered vertex $i$ ($i < j$). Our task is to color every vertex...

CF 1979F - Kostyanych's Theorem

CF 1979F - Kostyanych's Theorem Rating: 2900 Tags: brute force, constructive algorithms, graphs, interactive Solve time: 7m 6s Verified: no Solution Problem Understanding We are given an unknown graph that originally was a complete graph on $n$ vertices, but exactly $n-2$ edges were removed. This means the final graph is extremely dense: it has exactly $\frac{n(n-1)}{2} - (n-2)$ edges, so it is missing only $n-2$ connections in total. We do...

Codeforces Round 973 (Div. 2)

Codeforces Round 973 (Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2700 | 18m 16s # Problem Rating Tags Accepted Time ✓ A Zhan's Blender 800 constructive-algorithms, math 31,224 1m 44s ✓ B Battle for Survive 900 constructive-algorithms, greedy, math 28,236 6m 22s C Password Cracking 1400 constructive-algorithms, interactive, strings 14,578 2m 33s D Minimize the Difference 1900 binary-search, greedy 7,466 2m 11s E Prefix GCD...

CF 1990E2 - Catch the Mole(Hard Version)

CF 1990E2 - Catch the Mole(Hard Version) Rating: 2600 Tags: binary search, data structures, dfs and similar, divide and conquer, interactive, trees Solve time: 2m 21s Verified: no Solution Problem Understanding We are working with a rooted tree where node 1 is fixed as the root. Somewhere in this tree there is a hidden token, called the mole, which occupies a single node. We do not know its position initially,...

CF 1990E1 - Catch the Mole(Easy Version)

CF 1990E1 - Catch the Mole(Easy Version) Rating: 2500 Tags: binary search, data structures, dfs and similar, interactive, trees Solve time: 2m 4s Verified: no Solution Problem Understanding We are working with a rooted tree where node 1 is the root, and one hidden token, the “mole”, starts at some unknown node. We cannot observe its position directly. Instead, we interact with the tree using queries on nodes. A query...

CF 1991I - Grid Game

CF 1991I - Grid Game Rating: 3500 Tags: constructive algorithms, games, graph matchings, greedy, interactive Solve time: 2m 45s Verified: no Solution Problem Understanding We are asked to play an interactive game on a rectangular grid of size $n \times m$. Each cell must be filled with a unique integer from $1$ to $n \cdot m$. Once the grid is filled, the interactor and we take turns picking unchosen cells....

CF 1991E - Coloring Game

CF 1991E - Coloring Game Rating: 1900 Tags: constructive algorithms, dfs and similar, games, graphs, greedy, interactive Solve time: 3m 7s Verified: no Solution Problem Understanding We are asked to play a two-player game on a connected undirected graph where each vertex can be colored with one of three colors. The game proceeds in rounds equal to the number of vertices. In each round, the player Alice chooses two distinct...

CF 1999G2 - Ruler (hard version)

CF 1999G2 - Ruler (hard version) Rating: 1700 Tags: binary search, interactive, ternary search Solve time: 2m 34s Verified: no Solution Problem Understanding We are asked to find a missing number on a special ruler, which behaves almost like a normal ruler but skips a single value $x$ between 2 and 999. If you try to measure an object smaller than $x$, the ruler gives the correct length. If the...

CF 1999G1 - Ruler (easy version)

CF 1999G1 - Ruler (easy version) Rating: 1500 Tags: binary search, interactive Solve time: 1m 37s Verified: no Solution Problem Understanding We are interacting with a hidden parameter $x$ between 2 and 999 that defines a faulty measuring device. Whenever we measure a length $y$, the device behaves normally for small values, but once the true length reaches $x$ or more, it consistently over-reports by exactly 1 unit. Instead of...

CF 2001C - Guess The Tree

CF 2001C - Guess The Tree Rating: 1500 Tags: binary search, brute force, dfs and similar, divide and conquer, dsu, greedy, interactive, trees Solve time: 3m 35s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden tree with n nodes by interacting with a judge that answers specific distance-based queries. Each query "? a b" returns the node x that minimizes the absolute difference in distances from...

CF 2022D2 - Asesino (Hard Version)

CF 2022D2 - Asesino (Hard Version) Rating: 2700 Tags: constructive algorithms, dp, interactive Solve time: 1m 59s Verified: no Solution Problem Understanding The task is to find the single Impostor among $n$ players in an interactive game where each player has one of three roles: Knight, Knave, or Impostor. Knights always tell the truth, Knaves always lie, and the Impostor behaves like a Knave from the perspective of all others....

CF 2022D1 - Asesino (Easy Version)

CF 2022D1 - Asesino (Easy Version) Rating: 1900 Tags: binary search, brute force, constructive algorithms, implementation, interactive Solve time: 1m 30s Verified: no Solution Problem Understanding In this problem, we are asked to identify a single Impostor among n players, where every player is either a Knight, a Knave, or the Impostor. Knights always tell the truth, Knaves always lie, and the Impostor behaves as a Knave when questioned but...

CF 2031F - Penchick and Even Medians

CF 2031F - Penchick and Even Medians Rating: 2800 Tags: binary search, constructive algorithms, interactive, probabilities Solve time: 2m 33s Verified: no Solution Problem Understanding The original problem is interactive: there is a hidden permutation, and we must locate the positions of the two middle values, namely $\frac n2$ and $\frac n2 + 1$, using median queries. For the hack version used in the archive, the interaction is removed. The...

CF 2032D - Genokraken

CF 2032D - Genokraken Rating: 1800 Tags: constructive algorithms, data structures, graphs, greedy, implementation, interactive, trees, two pointers Solve time: 1m 51s Verified: no Solution Problem Understanding We are tasked with reconstructing the parent array of a tree rooted at node 0, under a very specific structure. Each node is numbered from 0 to n-1, and for each node i ≥ 1, we want to find its parent node p_i....

CF 2127G2 - Inter Active (Hard Version)

CF 2127G2 - Inter Active (Hard Version) Rating: 3500 Tags: binary search, bitmasks, constructive algorithms, graphs, implementation, interactive, math, probabilities Solve time: 3m 19s Verified: no Solution Problem Understanding We are dealing with a hidden structure, a permutation of size $n$, where every position points to exactly one value and no value repeats. There is an additional restriction that no element stays in its original position, so the permutation contains...

CF 2127G1 - Inter Active (Easy Version)

CF 2127G1 - Inter Active (Easy Version) Rating: 3400 Tags: binary search, constructive algorithms, interactive, probabilities Solve time: 1m 39s Verified: no Solution Problem Understanding We are given a hidden permutation of size $n$, with the additional promise that no element stays in its own position. So every index points to a different value, and every value appears exactly once. We cannot see this permutation directly. Instead, we are allowed...

Codeforces Round 1004 (Div. 1)

Codeforces Round 1004 (Div. 1) Type: Div. 1 | Problems: 7 | Verified: 1/7 | Rating range: 1400-3300 | Time: 14m 39s Problem Name Rating Tags Solve Time Verified A Object Identification 1400 graphs, greedy, implementation 2m 5s ✗ B White Magic 1900 constructive-algorithms, data-structures, dp 1m 39s ✗ C Bitwise Slides 2300 bitmasks, combinatorics, dp 1m 39s ✓ D1 Club of Young Aircraft Builders (easy version) 2400 combinatorics, dp,...

CF 2066A - Object Identification

CF 2066A - Object Identification Rating: 1400 Tags: graphs, greedy, implementation, interactive Solve time: 2m 5s Verified: no Solution The failure you show is not enough to diagnose the algorithm itself. Let's trace what happened: The input contains 5 test cases : 5 2 2 1 5 2 3 4 5 1 5 2 1 4 2 3 5 4 1 1 5 4 10 4 3 9 1 6...

CF 2038G - Guess One Character

CF 2038G - Guess One Character Rating: 1900 Tags: constructive algorithms, implementation, interactive Solve time: 2m 7s Verified: no Solution Problem Understanding We are given an interactive problem where the judge has a hidden binary string s of length n . Our goal is to identify at least one character in s by asking up to three queries per test case. Each query asks how many times a binary substring...

CF 2036G - Library of Magic

CF 2036G - Library of Magic Rating: 2200 Tags: binary search, constructive algorithms, divide and conquer, interactive, math, number theory Solve time: 1m 30s Verified: no Solution Problem Understanding We are dealing with a very large universe of book types, from 1 up to n where n can be as large as 10^18. Every type normally appears exactly twice in a hidden collection. However, three distinct types a, b, and...

CF 2037E - Kachina's Favorite Binary String

CF 2037E - Kachina's Favorite Binary String Rating: 1600 Tags: dp, greedy, interactive, two pointers Solve time: 2m 25s Verified: no Solution Problem Understanding We are tasked with reconstructing a hidden binary string of length $n$ by querying a function $f(l, r)$, which counts the number of subsequences "01" in the substring from index $l$ to $r$. A subsequence is any selection of characters maintaining the original order. Two subsequences...

CF 2049E - Broken Queries

CF 2049E - Broken Queries Rating: 2400 Tags: binary search, bitmasks, brute force, constructive algorithms, implementation, interactive Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to determine a hidden integer $k$ in an interactive setting, where $k$ controls the behavior of a device that responds to range queries on a hidden binary array of length $n$. The array contains exactly one 1 and all other elements...

CF 2052H - Hunting Hoglins in Hogwarts

CF 2052H - Hunting Hoglins in Hogwarts Rating: 3500 Tags: interactive Solve time: 1m 4s Verified: yes Solution Problem Understanding The race starts with cars ordered by their labels: $$1,2,3,\dots,n.$$ During the race, an overtake is an adjacent swap. If car $x$ is directly behind car $y$, then the event "$x$ overtakes $y$" swaps their positions. At the end of the race we know only the final ordering $c$. We...

CF 2061G - Kevin and Teams

CF 2061G - Kevin and Teams Rating: 2900 Tags: constructive algorithms, graphs, interactive Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a set of $n$ people where every pair is either connected by a hidden binary relation, friendship or non-friendship. The relation is not known in advance, and in the interactive version it may even react to queries. From these people, we want to pick exactly...

CF 2073H - Secret Lilies and Roses

CF 2073H - Secret Lilies and Roses Rating: 2700 Tags: interactive Solve time: 32s Verified: no Solution Before I start drafting the editorial, I want to clarify one point: Codeforces Problem 2073H, Secret Lilies and Roses , is interactive. Could you confirm whether you want me to include the full interactive protocol handling in Python, or focus mainly on the algorithm logic with a placeholder for the interaction? This affects...

CF 2073E - Minus Operator

CF 2073E - Minus Operator Rating: 3300 Tags: interactive Solve time: 34s Verified: no Solution Before I begin, I want to clarify: the exact interaction rules for Codeforces 2073E (Minus Operator) involve asking queries to some hidden array or sequence via a “minus operator” and receiving responses. I don’t have the official statement in front of me, so I’ll reconstruct it based on the standard interactive problem patterns. Can you...

CF 2074E - Empty Triangle

CF 2074E - Empty Triangle Rating: 1600 Tags: geometry, interactive, probabilities Solve time: 1m 25s Verified: no Solution Problem Understanding We are given a hidden set of points on a plane, and we know there are no duplicates and no three points are collinear. The challenge is that we do not know their coordinates. We are allowed to query the interactor with any triangle formed by three points, and it...

CF 2086F - Online Palindrome

CF 2086F - Online Palindrome Rating: 3000 Tags: brute force, constructive algorithms, interactive Solve time: 1m 25s Verified: no Solution Problem Understanding We are interacting with a process that reveals a binary string one character at a time. After each reveal, we append the new character to a working string, and we are allowed to freely swap any two positions in this working string. The requirement is that after every...

CF 2087D - Uppercase or Lowercase?

CF 2087D - Uppercase or Lowercase? Rating: - Tags: *special, interactive Solve time: 1m 40s Verified: no Solution Problem Understanding We are given a sorted list of strings, called handles, with the total number $n$ and a target handle $h$. The goal is to determine the 1-based position of $h$ in this list. The challenge is that the sorting order is lexicographical, but we do not know whether uppercase letters...

CF 2095B - Plinko

CF 2095B - Plinko Rating: - Tags: *special, games, interactive Solve time: 1m 27s Verified: no Solution Problem Understanding The problem is an interactive simulation of a simple Plinko game, where a ball drops through a triangular pegboard and eventually lands in one of ten numbered slots at the bottom. Each round of the game is labeled from Game 1 to Game 10 . For each round, you must output...

CF 2096G - Wonderful Guessing Game

CF 2096G - Wonderful Guessing Game Rating: 3200 Tags: bitmasks, constructive algorithms, interactive Solve time: 1m 35s Verified: no Solution Problem Understanding We are asked to play an interactive guessing game with a student, Alice. She secretly selects a number between 1 and $n$. We do not know her number in advance. Our task is to determine her number by submitting a fixed sequence of queries and then analyzing the...

CF 2106G2 - Baudelaire (hard version)

CF 2106G2 - Baudelaire (hard version) Rating: 2500 Tags: binary search, dfs and similar, divide and conquer, implementation, interactive, trees Solve time: 1m 38s Verified: no Solution Problem Understanding We are given a tree with up to 1000 nodes, and each node hides a value of either 1 or −1. The tree is rooted somewhere, but the root is unknown to us. What makes this unusual is that the root...

CF 2106G1 - Baudelaire (easy version)

CF 2106G1 - Baudelaire (easy version) Rating: 2200 Tags: binary search, constructive algorithms, divide and conquer, greedy, interactive, trees Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a tree of size $n$, where each node carries a value of either $1$ or $-1$. The tree is connected in such a way that every node is adjacent to node $1$. The root of the tree is unknown,...

CF 2108D - Needle in a Numstack

CF 2108D - Needle in a Numstack Rating: 2200 Tags: binary search, brute force, implementation, interactive Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a hidden array C formed by concatenating two unknown arrays A and B . The split point is unknown. Both arrays are over the alphabet {1, 2, ..., k} and both have a strong local constraint: in either array, any window of...

CF 2109C2 - Hacking Numbers (Medium Version)

CF 2109C2 - Hacking Numbers (Medium Version) Rating: 1700 Tags: constructive algorithms, interactive, math, number theory Solve time: 1m 50s Verified: no Solution Problem Understanding In this problem, we are asked to manipulate an unknown integer $x$ to become equal to a given target $n$ using a very limited number of operations. We do not know the initial value of $x$, and we can only interact through four commands: adding...

CF 2109C3 - Hacking Numbers (Hard Version)

CF 2109C3 - Hacking Numbers (Hard Version) Rating: 2600 Tags: constructive algorithms, interactive, math, number theory Solve time: 1m 33s Verified: no Solution Problem Understanding We start with an unknown integer x , hidden from us, guaranteed to lie in the range from 1 to 10^9. Our goal is to transform this hidden value into a given target value n . We are allowed to interact with x only through...

CF 2109C1 - Hacking Numbers (Easy Version)

CF 2109C1 - Hacking Numbers (Easy Version) Rating: 1500 Tags: bitmasks, constructive algorithms, interactive, math, number theory Solve time: 1m 39s Verified: no Solution Problem Understanding In this problem, we face an unknown integer x that is initially hidden from us, and our goal is to transform it into a target integer n by issuing at most seven interactive commands. The commands allow us to add or multiply by a...

CF 2111G - Divisible Subarrays

CF 2111G - Divisible Subarrays Rating: 2900 Tags: binary search, bitmasks, brute force, data structures, interactive Solve time: 1m 38s Verified: yes Solution Problem Understanding We are given a permutation of the numbers from 1 to n. For every query, we take a contiguous segment of this permutation and must decide whether that segment has a very specific structural property: whether there exists a way to split the segment into...

Codeforces Round 1058 (Div. 2)

Codeforces Round 1058 (Div. 2) Type: Div. 2 | Problems: 8 | Verified: 3/8 | Rating range: 800-3200 | Time: 15m 24s Problem Name Rating Tags Solve Time Verified A MEX Partition 800 math 2m 57s ✓ B Distinct Elements 1100 greedy, math 2m 6s ✗ C Reverse XOR 1300 bitmasks 1m 30s ✗ D MAD Interactive Problem 1700 constructive-algorithms, greedy, interactive 1m 36s ✗ E Rectangles 2100 brute-force, dp,...

CF 2129F2 - Top-K Tracker (Hard Version)

CF 2129F2 - Top-K Tracker (Hard Version) Rating: 3500 Tags: interactive Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 1 to $n$, and we can only access it indirectly through interactive queries. There are four types of queries. Two of them (type 1 and 3) return the largest elements among selected indices of the permutation itself, while the other two...

CF 2129F1 - Top-K Tracker (Easy Version)

CF 2129F1 - Top-K Tracker (Easy Version) Rating: 3500 Tags: interactive Solve time: 2m 26s Verified: no Solution Problem Understanding We are asked to recover a hidden permutation of the numbers from 1 to $n$ through a limited set of interactive queries. Each query returns the largest elements or their positions from a chosen subset of indices, and the challenge is to reconstruct the permutation while respecting strict query limits....

CF 2129C3 - Interactive RBS (Hard Version)

CF 2129C3 - Interactive RBS (Hard Version) Rating: 2300 Tags: binary search, bitmasks, constructive algorithms, dp, interactive Solve time: 3m 15s Verified: no Solution Problem Understanding We are given a hidden binary string made of opening and closing brackets, and we are allowed to probe it indirectly. The only way to gain information is by constructing a sequence of indices, possibly repeating indices, and querying a function that evaluates how...

CF 2129C2 - Interactive RBS (Medium Version)

CF 2129C2 - Interactive RBS (Medium Version) Rating: 2000 Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a hidden string made only of opening and closing parentheses. We cannot see it directly. Instead, we can query any multiset-like sequence of indices, and the judge constructs a new string by taking the characters at those indices in order. For that...

CF 2129C1 - Interactive RBS (Easy Version)

CF 2129C1 - Interactive RBS (Easy Version) Rating: 1900 Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 2m 7s Verified: no Solution Problem Understanding We are given a hidden bracket sequence of length $n$, consisting only of '(' and ')'. The goal is to reconstruct this sequence by asking at most 550 interactive queries. Each query allows us to select arbitrary positions in the sequence, potentially with repetitions, and...

CF 2133C - The Nether

CF 2133C - The Nether Rating: 1400 Tags: graphs, interactive Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a network of nether portals represented as a directed acyclic graph. Each portal may have directed connections to other portals, but there are no cycles. The task is to find a longest path in this hidden DAG. The challenge comes from the interaction: we do not see the...

CF 2134E - Power Boxes

CF 2134E - Power Boxes Rating: 2300 Tags: constructive algorithms, dp, implementation, interactive Solve time: 1m 18s Verified: no Solution Problem Understanding We are given a sequence of boxes, each with a hidden power of either 1 or 2. The boxes are placed on a number line at positions 1 through n. We need to discover the power of each box using two interactive queries: swapping adjacent boxes and throwing...

CF 2135D2 - From the Unknown (Hard Version)

CF 2135D2 - From the Unknown (Hard Version) Rating: 2500 Tags: brute force, constructive algorithms, interactive, math Solve time: 2m 3s Verified: no Solution Problem Understanding The task is to determine the unknown width parameter $W$ of a text editor. The editor displays a sequence of words, each represented by its length, on lines of width $W$. Words are placed sequentially: if the next word fits in the current line,...

CF 2135D1 - From the Unknown (Easy Version)

CF 2135D1 - From the Unknown (Easy Version) Rating: 2100 Tags: constructive algorithms, interactive, math Solve time: 1m 33s Verified: no Solution Problem Understanding We are trying to determine an unknown integer parameter $W$, the width of lines in a text editor. Each article we submit is a sequence of positive integers representing word lengths. The editor formats the article into lines, fitting words sequentially on a line until adding...

CF 2135B - For the Champion

CF 2135B - For the Champion Rating: 1700 Tags: constructive algorithms, interactive, math Solve time: 1m 49s Verified: no Solution Problem Understanding The original problem is interactive. We know a set of anchor points, and there is a hidden robot position. By moving the robot and observing the minimum Manhattan distance to any anchor, we must recover the initial coordinates. For Codeforces submissions, however, interactive problems are converted into ordinary...

2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)

2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 10/13 | Rating range: 1000-3000 | Time: 25m 58s Problem Name Rating Tags Solve Time Verified A Easy As ABC 1000 brute-force 1m 20s ✓ B Button Pressing 2600 bitmasks, constructive-algorithms, hashing 1m 46s ✗ C Cursed Game 3000 interactive 1m 18s ✓ D Spaceship Exploration 2800 binary-search, geometry 4m...

CF 2150E2 - Hidden Single (Version 2)

CF 2150E2 - Hidden Single (Version 2) Rating: 2800 Tags: binary search, divide and conquer, interactive, math, probabilities Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a hidden array of length $2n-1$ that contains each number from 1 to $n$ exactly twice, except for a single number which appears only once. Our goal is to determine which number appears only once. We do not need to...

CF 2150E1 - Hidden Single (Version 1)

CF 2150E1 - Hidden Single (Version 1) Rating: 2600 Tags: divide and conquer, interactive, math, probabilities, sortings Solve time: 1m 42s Verified: no Solution Problem Understanding We are given a hidden array of length 2n-1 , containing integers from 1 to n such that every number appears exactly twice except for one number that appears only once. Our goal is to identify the number that occurs exactly once. We do...

CF 2152E - Monotone Subsequence

CF 2152E - Monotone Subsequence Rating: 2100 Tags: constructive algorithms, graphs, greedy, interactive, math Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a hidden permutation of length $n^2 + 1$ and we need to find a monotone subsequence of length exactly $n+1$. The subsequence can either be increasing or decreasing. The catch is that we cannot see the permutation directly; instead, we can query the interactor...

CF 2155D - Batteries

CF 2155D - Batteries Rating: 1800 Tags: brute force, constructive algorithms, graph matchings, graphs, interactive, math Solve time: 1m 35s Verified: no Solution Problem Understanding We are given a set of n batteries, some of which work and some of which don't. We do not know how many work, but we do know that at least two do. There is a flashlight that requires exactly two working batteries to turn...

CF 2156D - Find the Last Number

CF 2156D - Find the Last Number Rating: 1900 Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 1 to $n$, but we only have direct access to the first $n-1$ elements through an interactive query. Each query allows us to pick an index $i$ (between 1 and $n-1$) and a value $x$ (up...

CF 2157G - Isaac's Queries

CF 2157G - Isaac's Queries Rating: 2800 Tags: bitmasks, brute force, constructive algorithms, dfs and similar, divide and conquer, dp, greedy, interactive, math, probabilities Solve time: 1m 49s Verified: no Solution Problem Understanding We are dealing with a hidden array of integers, where each integer is in the range [0, 2^30) . We are allowed to ask queries about contiguous subarrays. For a query on the interval [u, v] ,...

CF 2159F - Grand Finale: Snakes

CF 2159F - Grand Finale: Snakes Rating: 3500 Tags: binary search, interactive, ternary search Solve time: 1m 44s Verified: no Solution Problem Understanding We are given a permutation grid of size $n \times n$, where every number from $1$ to $n^2$ appears exactly once. Instead of directly using this grid, we interact with a hidden process that defines, for each snake length $l$ and time $T$, a value $f(l,T)$. This...

CF 2159A - MAD Interactive Problem

CF 2159A - MAD Interactive Problem Rating: 1700 Tags: constructive algorithms, implementation, interactive Solve time: 2m 27s Verified: no Solution Problem Understanding We are tasked with reconstructing a hidden sequence of length $2n$ in which each number from $1$ to $n$ appears exactly twice. The only tool we have is the MAD query. Given a set of indices, the MAD function returns the largest number that appears at least twice...

CF 2162D - Beautiful Permutation

CF 2162D - Beautiful Permutation Rating: 1400 Tags: binary search, interactive Solve time: 1m 31s Verified: no Solution Problem Understanding We are given a hidden permutation of size $n$, meaning it contains each number from $1$ to $n$ exactly once. After this permutation was fixed, someone chose a segment $[l, r]$ and increased every element inside that segment by exactly one. Outside the segment, values remain unchanged. We never see...

CF 2163E - Plegma

CF 2163E - Plegma Rating: 2700 Tags: bitmasks, combinatorics, communication, interactive Solve time: 2m 51s Verified: no Solution Problem Understanding We are dealing with a two-phase interactive problem. In the first phase, Player A receives a full $n \times n$ binary grid, where each cell is either a 0 or a 1, and each test case also specifies whether the grid is fully connected through 1s or not. Player A...

CF 2163D2 - Diadrash (Hard Version)

CF 2163D2 - Diadrash (Hard Version) Rating: 2500 Tags: binary search, interactive, math, sortings Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a hidden permutation of the integers from 0 to n−1, and a collection of fixed segments of this permutation. For each segment, we are interested in its mex, the smallest non-negative integer that does not appear inside that segment. Among all given segments, we...

CF 2163D1 - Diadrash (Easy Version)

CF 2163D1 - Diadrash (Easy Version) Rating: 2100 Tags: binary search, brute force, divide and conquer, implementation, interactive Solve time: 1m 20s Verified: no Solution Problem Understanding We are given a hidden permutation of integers from 0 to n-1 , and our task is to find the maximum MEX over a set of ranges. Each range specifies a contiguous segment of the permutation, and the MEX of a range is...

CF 2164G - Pointless Machine

CF 2164G - Pointless Machine Rating: 3300 Tags: constructive algorithms, graphs, interactive, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are dealing with a hidden tree on $n$ labeled vertices, but we cannot see its edges directly. Instead, we can “probe” the tree using permutations. Each query is a full ordering of the vertices. As we reveal vertices one by one in that order, we are told...

CF 2168C - Intercepting Butterflies

CF 2168C - Intercepting Butterflies Rating: - Tags: bitmasks, communication, constructive algorithms, graphs, interactive Solve time: 1m 34s Verified: no Solution Problem Understanding Alice has a secret integer x between 1 and 2^15 that she wants to communicate to Bob using a set S drawn from the integers 1 through 20. The twist is that when Bob receives S , one element may have been added, one may have been...

CF 2168B - Locate

CF 2168B - Locate Rating: - Tags: binary search, combinatorics, communication, constructive algorithms, greedy, interactive Solve time: 2m 16s Verified: no Solution Something went wrong. If this issue persists please contact us through our help center at help.openai.com.

CF 2168A1 - Encode and Decode (Easy Version)

CF 2168A1 - Encode and Decode (Easy Version) Rating: - Tags: communication, constructive algorithms, interactive Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to design a two-phase program that communicates an array of integers through a single string. On the first run, the program receives an array of length n , where each element is at most 26. It must encode this array into a string...

CF 2168A2 - Encode and Decode (Hard Version)

CF 2168A2 - Encode and Decode (Hard Version) Rating: - Tags: bitmasks, communication, interactive, math Solve time: 1m 48s Verified: no Solution Problem Understanding We are asked to implement a two-phase encoding and decoding process for an array of integers. In the first phase, the program receives an array a of size n with values up to one billion and must output a string s composed of lowercase letters. This...

CF 2173E - Shiro's Mirror Duel

CF 2173E - Shiro's Mirror Duel Rating: 2200 Tags: constructive algorithms, greedy, interactive, probabilities, sortings Solve time: 2m 26s Verified: no Solution Problem Understanding We maintain a permutation of 1..n . A query chooses two indices x and y . The judge then flips a coin. Either positions (x,y) are swapped, or their mirrored positions (n-x+1, n-y+1) are swapped. After the swap, we are told which pair was actually exchanged,...

CF 2174E2 - Game of Scientists (Version 2)

CF 2174E2 - Game of Scientists (Version 2) Rating: 3200 Tags: binary search, chinese remainder theorem, dfs and similar, interactive, math Solve time: 3m 37s Verified: no Solution Problem Understanding We are interacting with a hidden integer $x$ that is fixed for each game and always lies in the range $[1, c]$, where $c = 2 \cdot 10^9$. Our goal is to determine this number using at most three queries....

CF 2174E1 - Game of Scientists (Version 1)

CF 2174E1 - Game of Scientists (Version 1) Rating: 3100 Tags: chinese remainder theorem, constructive algorithms, interactive, math Solve time: 1m 52s Verified: no Solution Problem Understanding We are asked to guess a hidden number x between 1 and c by making queries about the sum of its digits in a chosen base. Each query specifies a base b (between 2 and c ) and returns either the sum of...

CF 2178E - Flatten or Concatenate

CF 2178E - Flatten or Concatenate Rating: 2000 Tags: binary search, divide and conquer, interactive Solve time: 2m 11s Verified: no Solution Problem Understanding We are asked to determine the maximum element of a hidden array that was generated from an initial array containing a single power-of-two number. The array evolves by two operations: flattening, which splits a maximal even number into two halves, and concatenation, which duplicates one array...

CF 2179G - Blackslex and Penguin Migration

CF 2179G - Blackslex and Penguin Migration Rating: 2200 Tags: brute force, interactive, math Solve time: 1m 54s Verified: no Solution Problem Understanding We are asked to reconstruct the positions of penguins on an $n \times n$ grid after a migration, knowing only the Manhattan distances between pairs of penguins. Each penguin is uniquely labeled from $1$ to $n^2$, and after migration, there is still exactly one penguin in each...

CF 2179F - Blackslex and Another RGB Walking

CF 2179F - Blackslex and Another RGB Walking Rating: 2000 Tags: communication, constructive algorithms, graphs, interactive, number theory, trees Solve time: 1m 44s Verified: no Solution Problem Understanding We are asked to solve a two-part communication problem on a connected bipartite graph. In the first part, the agent colors vertices using three colors to encode directional information. In the second part, Blackslex must navigate from a random vertex to vertex...

CF 2181C - Cacti Classification

CF 2181C - Cacti Classification Rating: 3200 Tags: binary search, constructive algorithms, interactive, math Solve time: 1m 51s Verified: no Solution Problem Understanding We are dealing with a hidden connected graph that has a very restricted structure: it is a cactus, meaning every edge participates in at most one simple cycle. The graph may contain loops and multiple edges between the same pair of vertices, and these special edges are...

CF 2183G - Snake Instructions

CF 2183G - Snake Instructions Rating: 3200 Tags: constructive algorithms, greedy, interactive Solve time: 2m 47s Verified: no Solution Problem Understanding The interactive version allows us to ask up to three carefully chosen instructions and observe the surviving snakes. In the hacked version, the speeds are already given in the input, and our job is to reproduce the answer that an optimal interactive solution would output. Each snake starts at...

CF 2190C - Comparable Permutations

CF 2190C - Comparable Permutations Rating: 2300 Tags: greedy, implementation, interactive, sortings, two pointers Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to interact with a hidden permutation p of size n and produce a permutation q that is lexicographically just larger than p and also satisfies the property that reversing q gives a permutation larger than the reverse of p . The catch is that...

CF 2193G - Paths in a Tree

CF 2193G - Paths in a Tree Rating: 2100 Tags: dfs and similar, interactive, sortings, trees Solve time: 3m 5s Verified: no Solution Problem Understanding We are given a tree, which is an undirected, connected, acyclic graph of $n$ vertices. Two hidden vertices, $x$ and $y$, define a unique path because trees have exactly one simple path between any pair of vertices. We do not know the identities of $x$...

CF 2196C2 - Interactive Graph (Hard Version)

CF 2196C2 - Interactive Graph (Hard Version) Rating: 2000 Tags: combinatorics, dfs and similar, dp, graphs, interactive Solve time: 2m 10s Verified: no Solution Problem Understanding We are asked to reconstruct a hidden directed acyclic graph (DAG) by interacting with a system that enumerates all paths in lexicographic order. Each query allows us to ask for the $k$-th path. The paths are sequences of vertex indices such that consecutive vertices...

CF 2196C1 - Interactive Graph (Simple Version)

CF 2196C1 - Interactive Graph (Simple Version) Rating: 1800 Tags: binary search, combinatorics, dfs and similar, dp, graphs, interactive Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a directed acyclic graph with up to 15 vertices. The edges are unknown, but we are allowed to probe the graph through an oracle. Each query asks for the k-th path in the lexicographically sorted list of all valid...

CF 2206A - Compare Suffixes

CF 2206A - Compare Suffixes Rating: 3500 Tags: interactive Solve time: 1m 54s Verified: no Solution Problem Understanding We are tasked with sorting the suffixes of a hidden string $S$ using an interactive judge. The string has length $n$, and we do not know its contents. We can query any two suffixes $S(i)$ and $S(j)$ to learn which is lexicographically smaller. The goal is to produce a permutation of positions...

CF 2207H2 - Bowser's Castle (Medium Version)

CF 2207H2 - Bowser's Castle (Medium Version) Rating: - Tags: constructive algorithms, divide and conquer, interactive, trees, two pointers Solve time: 2m 17s Verified: no Solution Problem Understanding We are asked to reverse-engineer a hidden function chosen by Bowser. The function takes n integer inputs and is constructed entirely from nested min and max operations, each input appearing exactly once in order from x1 to xn . Our goal is...

CF 2207H3 - Bowser's Castle (Hard Version)

CF 2207H3 - Bowser's Castle (Hard Version) Rating: - Tags: constructive algorithms, divide and conquer, interactive, trees, two pointers Solve time: 1m 45s Verified: no Solution Problem Understanding We are given a black-box function of $n$ variables. The function is not arbitrary: it is built by taking the variables $x_1, x_2, \ldots, x_n$ in order and combining them using only min and max , with the restriction that each variable...

CF 2207H1 - Bowser's Castle (Easy Version)

CF 2207H1 - Bowser's Castle (Easy Version) Rating: - Tags: binary search, constructive algorithms, divide and conquer, greedy, interactive, trees Solve time: 1m 51s Verified: no Solution Problem Understanding We are given an unknown function that takes a list of n values and returns a single number. The function is not arbitrary: it is built by combining the inputs using only min and max , and every input variable appears...

CF 2209C - Find the Zero

CF 2209C - Find the Zero Rating: 1400 Tags: constructive algorithms, interactive Solve time: 2m Verified: no Solution Problem Understanding We are asked to find a position of a zero in a hidden array of length $2n$, where each integer from $1$ to $n$ occurs exactly once and all remaining positions are zeros. We do not know the array explicitly, but we can query any two indices to check whether...

CF 2210E - Binary Strings are Simple?

CF 2210E - Binary Strings are Simple? Rating: 2700 Tags: constructive algorithms, implementation, interactive, number theory Solve time: 1m 45s Verified: no Solution Problem Understanding We are dealing with an interactive reconstruction problem where the hidden object is a binary string of length $n$. We do not observe the string directly. Instead, we can query any substring $[l, r]$ and receive a value derived from a fairly complicated transformation of...

CF 2211E - Minimum Path Cover

CF 2211E - Minimum Path Cover Rating: 2500 Tags: brute force, dp, greedy, interactive, math, number theory, trees Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a rooted tree where every node carries a large integer value. A valid “vertical path” is simply a downward chain: each node is the child of the previous one. Such a path becomes “good” if the greatest common divisor of...

CF 2214J - Special Problem

CF 2214J - Special Problem Rating: - Tags: *special, brute force, games, interactive Solve time: 58s Verified: yes Solution Problem Understanding This problem presents an interactive game scenario where you have a hidden system generating some responses. The goal is to query the system in a structured way to deduce a hidden value or sequence. Typically, the input consists of queries you can make and the output is the system’s...

CF 2215C - Oriented Journey

CF 2215C - Oriented Journey Rating: 2200 Tags: bitmasks, brute force, communication, constructive algorithms, graphs, interactive, trees Solve time: 1m 54s Verified: no Solution Problem Understanding We are dealing with a two-phase communication system built around a tree. First, an agent receives an undirected tree one edge at a time and must immediately orient each edge. After all edges are oriented, a second agent receives only the resulting directed tree...

Codeforces Round 1087 (Div. 2)

Codeforces Round 1087 (Div. 2) Div. 2 | 6 problems | 1/6 verified | Difficulty 800-2700 | 11m 5s # Problem Rating Tags Accepted Time ✓ A Flip Flops 800 greedy 21,430 2m 13s B Array 900 greedy 19,314 1m 27s ✓ C Find the Zero 1400 constructive-algorithms, interactive 10,597 2m D Ghostfires 1800 constructive-algorithms, greedy 5,306 1m 47s E A Trivial String Problem 2200 brute-force, dp, hashing 1,755 1m...

2026 ICPC Asia Pacific Championship - Online Mirror (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

2026 ICPC Asia Pacific Championship - Online Mirror (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 13 problems | 3/13 verified | Difficulty 1300-3500 | 28m 52s # Problem Rating Tags Accepted Time ✓ A Compare Suffixes 3500 interactive 84 1m 54s B Subtree Removal Game 2500 binary-search, games, trees 347 2m 20s ✓ C Upside Down Dijkstra 2200 dfs-and-similar 625 2m 25s D Christmas Tree Un-decoration 2600 data-structures,...

Testing Round 20 (Unrated, Communication Problems)

Testing Round 20 (Unrated, Communication Problems) Special | 4 problems | 0/4 verified | Difficulty - | 7m 30s # Problem Rating Tags Accepted Time ✓ A1 Encode and Decode (Easy Version) communication, constructive-algorithms, interactive 5,024 1m 52s A2 Encode and Decode (Hard Version) bitmasks, communication, interactive 3,303 1m 48s B Locate binary-search, combinatorics, communication 1,550 2m 16s C Intercepting Butterflies bitmasks, communication, constructive-algorithms 876 1m 34s

Codeforces Round 1059 (Div. 3)

Codeforces Round 1059 (Div. 3) Div. 3 | 8 problems | 2/8 verified | Difficulty 800-2900 | 13m 30s # Problem Rating Tags Accepted Time ✓ A Beautiful Average 800 brute-force, greedy 41,574 1m 37s ✓ B Beautiful String 1000 brute-force, constructive-algorithms 27,889 1m 39s C Beautiful XOR 1100 bitmasks, constructive-algorithms, greedy 21,311 2m 13s D Beautiful Permutation 1400 binary-search, interactive 12,358 1m 31s E Beautiful Palindromes 1600 constructive-algorithms, greedy,...

CF 2222E - Seek the Truth

CF 2222E - Seek the Truth Rating: - Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 1m 57s Verified: no Solution Problem Understanding We are interacting with a hidden transformation on integers in the range from 0 to $2^n - 1$. Behind the scenes there is a fixed bitmask $c$ and a hidden operation type $k \in {1,2,3}$. Every time we insert a number $x$, the judge does not...

CF 2219B2 - Unique Values (Hard version)

CF 2219B2 - Unique Values (Hard version) Rating: - Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 2m 3s Verified: no Solution Problem Understanding We are given an array of length $2n+1$ containing integers from $1$ to $n$. Every integer appears exactly twice, except one integer, which appears three times. Our task is to identify the positions of the integer that appears three times. Interaction is done through a...

CF 2219B1 - Unique Values (Easy version)

CF 2219B1 - Unique Values (Easy version) Rating: - Tags: binary search, constructive algorithms, divide and conquer, interactive, math Solve time: 1m 55s Verified: no Solution Problem Understanding We are given an array of length $2n+1$. Every number lies in the range $1$ to $n$. The structure is highly constrained: all values appear exactly twice except for one special value that appears exactly three times. The task is to discover...

Codeforces Round 1073 (Div. 2)

Codeforces Round 1073 (Div. 2) Type: Div. 2 | Problems: 8 | Verified: 2/8 | Rating range: 800-3200 | Time: 14m 4s Problem Name Rating Tags Solve Time Verified A Array Coloring 800 constructive-algorithms 1m 50s ✓ B MEX Reordering 1000 constructive-algorithms, sortings 1m 8s ✓ C Sorting Game 1200 games 3m 14s ✗ D1 Sub-RBS (Easy Version) 1400 constructive-algorithms 1m 43s ✗ D2 Sub-RBS (Hard Version) 1900 dp, games...

CF 1973D - Cat, Fox and Maximum Array Split

CF 1973D - Cat, Fox and Maximum Array Split Rating: 2400 Tags: brute force, interactive, math Solve time: 5m 14s Verified: no Solution

LeetCode 2782 - Number of Unique Categories

LeetCode Problem 2782 Difficulty: 🟡 Medium Topics: Union-Find, Interactive, Counting Solution Problem Understanding This problem asks us to determine how many distinct categories exist among n elements. The elements are labeled from 0 to n - 1 , but we are not given the category values directly. Instead, we interact with the hidden categorization through the provided API: haveSameCategory(a, b) This function tells us whether two elements belong to the...

LeetCode 3064 - Guess the Number Using Bitwise Questions I

LeetCode Problem 3064 Difficulty: 🟡 Medium Topics: Bit Manipulation, Interactive Solution Problem Understanding The problem presents an interactive scenario where there is a hidden number n in the range [1, 2^30 - 1] . We are provided with an API commonSetBits(num) which returns the count of bits that are set in both n and num when performing a bitwise AND. In other words, commonSetBits(num) computes the number of positions where...

LeetCode 2728 - Count Houses in a Circular Street

LeetCode Problem 2728 Difficulty: 🟢 Easy Topics: Array, Interactive Solution Problem Understanding The problem asks us to determine the number of houses on a circular street where we can only interact with the street through the provided Street interface. Each house has a door that can either be open or closed. We are initially positioned in front of one house, but we do not know which one, and the street...

LeetCode 3037 - Find Pattern in Infinite Stream II

LeetCode Problem 3037 Difficulty: 🔴 Hard Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function Solution Problem Understanding The problem requires us to detect the first occurrence of a binary pattern within a theoretically infinite stream of bits. The stream is accessed sequentially using the next() method, which returns one bit at a time. Our task is to determine the index in the stream where the given pattern...

LeetCode 3094 - Guess the Number Using Bitwise Questions II

LeetCode Problem 3094 Difficulty: 🟡 Medium Topics: Bit Manipulation, Interactive Solution Before I write the full guide, I want to confirm one detail: for LeetCode 3094 - Guess the Number Using Bitwise Questions II , there are no public input/output examples in the problem statement because it is an interactive problem . I can still provide the complete reference guide with all requested sections, including: Problem Understanding Brute Force and...

LeetCode 3023 - Find Pattern in Infinite Stream I

LeetCode Problem 3023 Difficulty: 🟡 Medium Topics: Array, Sliding Window, Rolling Hash, String Matching, Interactive, Hash Function Solution Problem Understanding The problem asks us to detect the first occurrence of a given binary pattern within an infinite stream of bits. We are given an object stream that allows us to read one bit at a time using the next() function. Our task is to return the 0-based index in the...

LeetCode 2936 - Number of Equal Numbers Blocks

LeetCode Problem 2936 Difficulty: 🟡 Medium Topics: Array, Binary Search, Interactive Solution Problem Understanding The problem is asking us to count the number of maximal contiguous blocks of equal numbers in a very large array nums . A block is maximal if it contains all consecutive occurrences of the same number, and numbers are guaranteed to appear in consecutive segments, i.e., the array is already "grouped" by value. The key...

LeetCode 1618 - Maximum Font to Fit a Sentence in a Screen

LeetCode Problem 1618 Difficulty: 🟡 Medium Topics: Array, String, Binary Search, Interactive Solution Problem Understanding In this problem, we are given a string text that must be displayed on a single line inside a screen with width w and height h . We are also given a sorted array fonts , where each value represents an available font size that we are allowed to use. The important detail is that...

LeetCode 1274 - Number of Ships in a Rectangle

LeetCode Problem 1274 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Interactive Solution Problem Understanding The problem presents an interactive scenario where ships are placed at integer coordinates on a Cartesian plane. You do not know their positions, and each coordinate contains at most one ship. You are given two points representing the bottom-left and top-right corners of a rectangle, and you need to determine the number of ships contained...

LeetCode 1533 - Find the Index of the Large Integer

LeetCode Problem 1533 Difficulty: 🟡 Medium Topics: Array, Binary Search, Interactive Solution Problem Understanding The problem presents an array arr where all elements are equal except for one element that is strictly larger than the others. However, we do not have direct access to the array elements. Instead, we interact with the array through an API called ArrayReader . This API provides two functions: compareSub(l, r, x, y) , which...

LeetCode 843 - Guess the Word

LeetCode Problem 843 Difficulty: 🔴 Hard Topics: Array, Math, String, Interactive, Game Theory Solution LeetCode 843 - Guess the Word Problem Understanding This is an interactive problem where we must identify a hidden six-letter word from a given list of candidate words. We are not allowed to directly inspect the secret word. Instead, we can interact with the provided Master API by calling master.guess(word) . Each call returns the number...

LeetCode 1538 - Guess the Majority in a Hidden Array

LeetCode Problem 1538 Difficulty: 🟡 Medium Topics: Array, Math, Interactive Solution Problem Understanding This problem is an interactive problem. We do not receive the actual binary array directly. Instead, we can only gather information through the ArrayReader API. The hidden array nums contains only 0 and 1 . Our goal is to determine which value appears more frequently and return any index containing that majority value. If the number of...

LeetCode 1095 - Find in Mountain Array

LeetCode Problem 1095 Difficulty: 🔴 Hard Topics: Array, Binary Search, Interactive Solution Problem Understanding This problem gives us a special type of array called a mountain array. A mountain array strictly increases until it reaches a single peak element, then strictly decreases afterward. For example: 1 2 3 5 4 2 increases up to 5 , then decreases. The challenge is that this is an interactive problem. We cannot directly...

LeetCode 1810 - Minimum Path Cost in a Hidden Grid

LeetCode Problem 1810 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Matrix, Interactive, Shortest Path Solution Problem Understanding This problem is an interactive shortest path problem on a hidden weighted grid. We control a robot that starts somewhere in an unknown grid, and we must determine the minimum total movement cost required to reach a hidden target cell. Unlike a normal grid problem, we...

LeetCode 1428 - Leftmost Column with at Least a One

LeetCode Problem 1428 Difficulty: 🟡 Medium Topics: Array, Binary Search, Matrix, Interactive Solution Problem Understanding This problem gives us access to a binary matrix where every row is sorted in non-decreasing order. That means every row looks like some number of 0 s followed by some number of 1 s. For example: [0, 0, 0, 1, 1] is valid, while: [0, 1, 0, 1] is not. The goal is to...

LeetCode 489 - Robot Room Cleaner

LeetCode Problem 489 Difficulty: 🔴 Hard Topics: Backtracking, Interactive Solution Problem Understanding This problem is an interactive backtracking problem where we must control a robot without directly seeing the room layout. Unlike traditional grid traversal problems, we are not given access to the actual room matrix during execution. The only way to explore the environment is through the robot's API. The room is conceptually a binary grid: 1 represents an...

LeetCode 1778 - Shortest Path in a Hidden Grid

LeetCode Problem 1778 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Interactive Solution Problem Understanding This problem asks us to find the shortest path from a robot's unknown starting position to a hidden target inside a grid. The major challenge is that the grid itself is not directly accessible. Instead of receiving the matrix as input, we interact with the environment through a GridMaster API. The robot can...

LeetCode 702 - Search in a Sorted Array of Unknown Size

LeetCode Problem 702 Difficulty: 🟡 Medium Topics: Array, Binary Search, Interactive Solution Problem Understanding This problem asks us to search for a target value inside a sorted array, but with an important limitation: we do not know the size of the array, and we cannot access the array directly. Instead of normal array indexing, we interact with the array through an ArrayReader interface. The only available operation is: reader.get(index) This...

LeetCode 374 - Guess Number Higher or Lower

LeetCode Problem 374 Difficulty: 🟢 Easy Topics: Binary Search, Interactive Solution Problem Understanding The problem describes a classic interactive guessing game. A hidden number called pick is chosen somewhere in the range from 1 to n , inclusive. We are not allowed to access pick directly. Instead, we can only interact with the provided API function: guess(num) This API tells us whether our current guess is too high, too low,...

LeetCode 158 - Read N Characters Given read4 II - Call Multiple Times

LeetCode Problem 158 Difficulty: 🔴 Hard Topics: Array, Simulation, Interactive Solution Problem Understanding This problem asks us to implement a read(buf, n) function using a restricted API called read4(buf4) . The challenge is that we are not allowed to access the file directly, instead, we can only retrieve data in chunks of up to four characters at a time. At first glance, this may look very similar to LeetCode 157,...

LeetCode 1236 - Web Crawler

LeetCode Problem 1236 Difficulty: 🟡 Medium Topics: String, Depth-First Search, Breadth-First Search, Interactive Solution Problem Understanding The problem asks us to implement a simplified web crawler. We are given a starting URL and access to an HtmlParser interface that can retrieve all URLs linked from a given webpage. Our task is to traverse the web graph beginning from startUrl , but with two important restrictions: We may only visit URLs...

LeetCode 278 - First Bad Version

LeetCode Problem 278 Difficulty: 🟢 Easy Topics: Binary Search, Interactive Solution Problem Understanding The problem gives us a sequence of product versions numbered from 1 to n . At some point, one version becomes bad, and every version after it is also bad. This creates a monotonic pattern: Good versions appear first Bad versions appear afterward For example: Version: 1 2 3 4 5 Status : G G G B...

LeetCode 1237 - Find Positive Integer Solution for a Given Equation

LeetCode Problem 1237 Difficulty: 🟡 Medium Topics: Math, Two Pointers, Binary Search, Interactive Solution Problem Understanding This problem gives us access to a hidden function f(x, y) through an interface. We are not allowed to know or implement the formula directly. Instead, we can only call the function with positive integers x and y and observe the result. The important property is that the function is strictly increasing in both...

LeetCode 277 - Find the Celebrity

LeetCode Problem 277 Difficulty: 🟡 Medium Topics: Two Pointers, Graph Theory, Interactive Solution Problem Understanding This problem asks us to identify whether there is a "celebrity" among n people at a party. A celebrity has a very specific property: Every other person knows the celebrity. The celebrity knows nobody else. We are not given the entire relationship graph directly. Instead, we can only query relationships through the helper API: knows(a,...

LeetCode 157 - Read N Characters Given Read4

LeetCode Problem 157 Difficulty: 🟢 Easy Topics: Array, Simulation, Interactive Solution Problem Understanding This problem asks us to implement a read function using a restricted API called read4 . The file itself is hidden from us, and the only way to access its contents is by repeatedly calling read4 . The read4 API reads up to 4 consecutive characters from the file into a temporary buffer called buf4 . It...

LeetCode 1095: Find in Mountain Array

Problem Restatement A mountain array increases to a peak and then decreases. We have access only through a MountainArray.get(index) API. We need to find the minimum index where mountainArr.get(index) == target . Return -1 if not found. We may call MountainArray.get() at most 100 times. The official constraints state that 3 <= mountainArr.length() <= 10^4 and all values are distinct. Input and Output Item Meaning Input MountainArray object and target...

LeetCode 843: Guess the Word

Problem Restatement We are given a list of unique strings words . Each word has length 6 . One word from the list is chosen as the secret word. We can call: master.guess(word) This returns: Return value Meaning -1 The guessed word is not in the word list 0 to 6 Number of positions where the guessed word matches the secret word We must find the secret word within at...

LeetCode 702: Search in a Sorted Array of Unknown Size

Problem Restatement We are given a sorted array, but we do not know its length. We cannot access the array directly. Instead, we can only use an ArrayReader interface: reader.get(index) This returns the value at index . If index is outside the array, reader.get(index) returns a very large sentinel value: 2147483647 We need to find the index of target . If target exists, return its index. If it does not...

LeetCode 158: Read N Characters Given read4 II - Call Multiple Times

Problem Restatement We are given a file, but we cannot read from it directly. The only available API is: read4(buf4) This reads up to 4 characters from the file into buf4 , then returns how many characters were actually read. We need to implement: read(buf, n) It should read up to n characters, write them into buf , and return the number of characters actually read. The difference from LeetCode...

LeetCode 278: First Bad Version

Problem Restatement We have versions numbered from 1 to n . At some version, the product becomes bad. Because each version is built from the previous one, every version after the first bad version is also bad. So the versions look like this: good, good, good, bad, bad, bad We are given an API: isBadVersion(version) It returns True if the version is bad and False if the version is good....

LeetCode 157: Read N Characters Given Read4

Problem Restatement We are given a file, but we cannot access the file directly. The only way to read from the file is through a provided API: read4(buf4) This function reads up to 4 characters from the file and writes them into buf4 . It returns the actual number of characters read. We need to implement: read(buf, n) This function should read up to n characters from the file, write...

LeetCode 277: Find the Celebrity

Problem Restatement There are n people at a party, labeled from 0 to n - 1 . A celebrity is a person who satisfies two conditions: Everyone else knows the celebrity. The celebrity knows nobody else. We are given an API: knows(a, b) It returns True if person a knows person b . We need to implement: findCelebrity(n) Return the celebrity label if one exists. Otherwise, return -1 . The...