#dfs and similar

CF 1042F - Leaf Sets Rating: 2400 Tags: data structures, dfs and similar, dsu, graphs, greedy, sortings, trees Model: gpt-5-5 Solve time: 1m 22s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33bd15-e528-83ec-b5a4-de0286e26609 Solution Problem Understanding We are given a tree where only some vertices matter: those with degree exactly one, which we call leaves. The task is not about grouping all vertices, but only about grouping these leaves. Each group must satisfy...

CF 1000E - We Need More Bosses Rating: 2100 Tags: dfs and similar, graphs, trees Model: gpt-5-3-mini Solve time: 1m 14s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33b176-33dc-83ec-aa43-47f37c1f6b9a Solution Problem Understanding We are given an undirected connected graph that may contain cycles. We are allowed to choose two special vertices, call them $s$ and $t$, after seeing the graph. Once those endpoints are fixed, we consider all simple paths from $s$...

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 990F - Flow Control Rating: 2400 Tags: dfs and similar, dp, greedy, trees Model: gpt-5-3-mini Solve time: 1m 23s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33ab95-73ac-83ec-a6af-8d4d9e5fd6cd Solution Problem Understanding We are given a connected undirected graph with junctions as vertices and pipes as edges. Each edge must be assigned an integer flow value, and that value can be interpreted with a direction: positive means the flow goes from the first...

CF 982F - The Meeting Place Cannot Be Changed Rating: 2700 Tags: dfs and similar, graphs Model: gpt-5-3-mini Solve time: 1m 27s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a33a65c-a680-83ec-b683-c182360d8ebc Solution Problem Understanding We are given a directed graph representing intersections connected by one-way roads. A car starts from some unknown intersection and then keeps moving along outgoing roads forever. We are guaranteed that this movement never gets stuck, meaning from every...

CF 977E - Cyclic Components Rating: 1500 Tags: dfs and similar, dsu, graphs Model: gpt-5-3-mini Solve time: 1m 1s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a501-2120-83ec-ad40-57e2d61c49fa Solution Problem Understanding We are given an undirected graph, and the task is to count how many of its connected components form a simple cycle. A component is considered a cycle when all of its vertices can be arranged in a ring so that every...

CF 939D - Love Rescue Rating: 1600 Tags: dfs and similar, dsu, graphs, greedy, strings Model: gpt-5-3-mini Solve time: 1m 14s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a339873-b5b0-83ec-af64-de42c9d02b4a Solution Problem Understanding We are given two strings of equal length, one written on Valya’s pullover and one on Tolya’s T-shirt. The goal is to make the two strings identical using a set of allowed transformation rules. Each spell corresponds to a pair...

CF 932B - Recursive Queries Rating: 1300 Tags: binary search, data structures, dfs and similar Model: gpt-5-3-mini Solve time: 1m 34s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a32e3b7-e7dc-83ec-a17b-6d7184217e41 Solution Problem Understanding We are given a function defined on positive integers that repeatedly transforms a number by taking its digit product and then collapsing it again in a recursive way until a single digit remains. That final digit is what we call...

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

CF 954D - Fight Against Traffic Rating: 1600 Tags: dfs and similar, graphs, shortest paths Model: gpt-5-3-mini Solve time: 1m 12s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a327cbb-fd5c-83ec-acef-a0a85d314a96 Solution Problem Understanding We are given an undirected connected graph representing junctions and roads, where each road has unit length. The shortest distance between any two junctions is defined as the minimum number of edges in a path. Two special nodes are highlighted,...

CF 936E - Iqea Rating: 3400 Tags: data structures, dfs and similar, divide and conquer, dsu, shortest paths, trees Model: gpt-5-3-mini Solve time: 2m 13s Verified: yes (1/1 samples) Solution Problem Understanding We are given a set of cells on a large grid. Each cell is a city, and roads exist between any two cities that share an edge on the grid. The important geometric constraints are that the chosen...

CF 1365D - Solve The Maze Rating: 1700 Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, implementation, shortest paths Model: gpt-5-3-mini Solve time: 2m 7s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e497a-d7ec-83ec-8d81-7aac5910ae19 Solution Problem Understanding The maze is a small grid where each cell is either a wall, empty space, a good person, or a bad person. All movement is four-directional and blocked by walls. The only exit is the...

CF 1369E - DeadLee Rating: 2400 Tags: data structures, dfs and similar, greedy, implementation, sortings Model: gpt-5-3-mini Solve time: 3m 48s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e507d-5c50-83ec-98a0-7e3f660bf5f5 Solution Problem Understanding Each friend is connected to exactly two food types, and each food type has a limited stock of plates. When a friend is called, they attempt to consume one plate from each of their two preferred types. If at least...

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

CF 1331E - Jordan Smiley Rating: ? Tags: *special, dfs and similar, geometry, implementation Model: gpt-5-3-mini Solve time: 4m 30s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e0448-ddd8-83ec-a640-42ed2a7f9fae Solution Problem Understanding The input describes a point on an infinite grid, identified by two non-negative integers, row and col . This grid is not interpreted as a standard Cartesian plane where every cell is equivalent. Instead, it is part of a geometric construction...

CF 1272E - Nearest Opposite Parity Rating: 1900 Tags: dfs and similar, graphs, shortest paths Model: gpt-5-5 Solve time: 2m 33s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d93db-6110-83ec-a15a-c26dceb74345 Solution Problem Understanding We are given a one-dimensional board of length $n$, where each cell $i$ contains a value $a_i$. From position $i$, we can jump deterministically to at most two other positions: $i - a_i$ and $i + a_i$, as long as...

CF 1325F - Ehab's Last Theorem Rating: 2500 Tags: constructive algorithms, dfs and similar, graphs, greedy Model: gpt-5-5 Solve time: 6m 18s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2df425-592c-83ec-8ec3-29541239cb9e Solution Problem Understanding We are given a connected undirected simple graph with up to $10^5$ vertices and up to $2 \cdot 10^5$ edges. The task is not to optimize some cost or count something, but to explicitly construct one of two specific...

CF 1364D - Ehab's Last Corollary Rating: 2100 Tags: constructive algorithms, dfs and similar, graphs, greedy, implementation, trees Model: gpt-5-3-mini Solve time: 2m 58s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e47c0-f80c-83ec-a0be-6bd3409333b8 Solution Problem Understanding We are given a connected undirected graph. Alongside the graph, we are given a parameter $k$, and we are asked to produce one of two possible outputs depending on what structure we can guarantee from the graph....

CF 1311B - WeirdSort Rating: 1200 Tags: dfs and similar, sortings Model: gpt-5-3-mini Solve time: 1m 37s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2ddd1f-d1b0-83ec-a3a6-913f2c755799 Solution Problem Understanding We are given an array of integers and a limited set of “swap permissions”. Each permission corresponds to a position i , meaning we are allowed to swap the pair (a[i], a[i+1]) . Each such swap can be used arbitrarily many times, so effectively...

CF 1388C - Uncle Bogdan and Country Happiness Rating: 1800 Tags: dfs and similar, greedy, math, trees Model: gpt-5-3-mini Solve time: 2m 35s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e786e-940c-83ec-aff8-b894ca81a057 Solution Problem Understanding The country is a tree of cities rooted at city 1, and every citizen starts their day in the capital before returning to their home city along the unique shortest path in the tree. Each city has a...

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

CF 1324F - Maximum White Subtree Rating: 1800 Tags: dfs and similar, dp, graphs, trees Model: gpt-5-3-mini Solve time: 2m 38s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2def77-79d8-83ec-88a3-9beb32439d59 Solution Problem Understanding We are given a tree where every vertex is colored either white or black. For each vertex $v$, we want to look at all connected subgraphs of the tree that include $v$, and among them choose one that maximizes the...

CF 1340D - Nastya and Time Machine Rating: 2600 Tags: constructive algorithms, dfs and similar, graphs, trees Model: gpt-5-3-mini Solve time: 4m 8s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e1967-f7b8-83ec-a5ed-2b526864a552 Solution Problem Understanding We are given a tree of $n$ vertices, with vertex $1$ as the starting and ending location. The traveler begins at vertex $1$ at time $0$. Every edge traversal takes exactly one unit of time, so moving along...

CF 1320E - Treeland and Viruses Rating: 3000 Tags: data structures, dfs and similar, dp, shortest paths, trees Model: gpt-5-5 Solve time: 7m 20s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2de8a4-e50c-83ec-a13a-1c80b9179d39 Solution Problem Understanding The process happens on a tree of cities. In each scenario, several infection sources are placed on different nodes, each source belonging to a distinct virus type and having a propagation strength. Viruses spread in rounds, and...

CF 1381D - The Majestic Brown Tree Snake Rating: 3000 Tags: dfs and similar, dp, greedy, trees, two pointers Model: gpt-5-3-mini Solve time: 3m 8s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e6d43-3be8-83ec-91e7-75c0a4fc2a1d Solution Problem Understanding We are given a tree and a “snake” that occupies a simple path between two vertices. The head is at one endpoint of this path and the tail is at the other endpoint. The snake is...

CF 1348F - Phoenix and Memory Rating: 2600 Tags: data structures, dfs and similar, graphs, greedy Model: gpt-5-3-mini Solve time: 3m 38s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e260b-7944-83ec-b0a5-2cf38808ad6a Solution Problem Understanding Each position in the final lineup comes with a constraint: at position i , the person sitting there must have a label from a contiguous range [a_i, b_i] . The labels themselves form a permutation of 1 to n...

CF 1327D - Infinite Path Rating: 2200 Tags: brute force, dfs and similar, graphs, math, number theory Model: gpt-5-3-mini Solve time: 3m 33s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2df9a5-21fc-83ec-95b0-5cb969319ab1 Solution Problem Understanding We are given a permutation that defines a directed graph where every node has exactly one outgoing edge. Each index points to its image under the permutation, and each node also carries a color. Starting from a node,...

CF 1336A - Linova and Kingdom Rating: 1600 Tags: dfs and similar, dp, greedy, sortings, trees Model: gpt-5-3-mini Solve time: 2m 38s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e1063-f548-83ec-9101-e12e782ec1b0 Solution Problem Understanding We are given a tree rooted at city 1. Each city is either selected as an industrial city or a tourism city, with exactly $k$ cities chosen as industrial. Every industrial city sends one envoy to the capital. That...

CF 1354E - Graph Coloring Rating: 2100 Tags: dfs and similar, dp, graphs Model: gpt-5-3-mini Solve time: 7m 8s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e30b4-0040-83ec-b7bd-a3c3c9ef7f21 Solution Problem Understanding We are given an undirected graph and asked to assign each vertex one of three labels, 1, 2, or 3. The labels are not arbitrary: every edge forces its endpoints to have labels that differ by exactly one. That means an edge...

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

CF 1316D - Nash Matrix Rating: 2000 Tags: constructive algorithms, dfs and similar, graphs, implementation Model: gpt-5-3-mini Solve time: 2m 17s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2de522-2b84-83ec-9041-a685022914d8 Solution Problem Understanding We are given a complete description of what happens on every cell of an $n \times n$ grid, but only in a compressed form. For each starting cell, we are told the final outcome of repeatedly following movement instructions written...

CF 1263D - Secret Passwords Rating: 1500 Tags: dfs and similar, dsu, graphs Model: gpt-5-3-mini Solve time: 1m 57s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d8071-ffa0-83ec-857d-abcaf5fc2df4 Solution Problem Understanding We are given a collection of strings, where each string represents a password. The system does not treat these passwords as completely independent. Instead, it defines a notion of “equivalence” between passwords: two passwords are equivalent if they share at least one...