#divide and conquer

CF 997D - Cycles in product Rating: 2900 Tags: combinatorics, divide and conquer, trees Model: gpt-5-3-mini Solve time: 1m 48s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33af98-d4a0-83ec-9fa7-52b68b919935 Solution Problem Understanding We are given two trees and we build their Cartesian product graph. Each vertex of the new graph is a pair consisting of one node from the first tree and one node from the second tree. From such a pair, we...

CF 1042D - Petya and Array Rating: 1800 Tags: data structures, divide and conquer, two pointers Model: gpt-5-3-mini Solve time: 1m 19s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a337e74-0c8c-83ec-89c6-71e8972be404 Solution Problem Understanding We are given a sequence of integers laid out in a row, and we are interested in contiguous fragments of this row. For every possible fragment, we compute its sum, and we need to count how many of these...

CF 1041F - Ray in the tube Rating: 2500 Tags: data structures, divide and conquer, dp, math Model: gpt-5-3-mini Solve time: 1m 39s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33bb87-06c0-83ec-b667-3f627d49e575 Solution Problem Understanding We are given two horizontal lines, each containing a set of integer x-coordinates where sensors are placed. The lower line has height $y_1$, the upper line has height $y_2$, and $y_1 < y_2$. We choose one point $A$...

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

CF 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 990G - GCD Counting Rating: 2400 Tags: divide and conquer, dp, dsu, number theory, trees Model: gpt-5-5 Solve time: 1m 41s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32935e-70f4-83ec-a952-c1e336e827ce Solution Problem Understanding We are given a tree where each vertex carries an integer value. For any two vertices, we consider the unique simple path between them and take the greatest common divisor of all values along that path. The task is...

CF 1311F - Moving Points Rating: 1900 Tags: data structures, divide and conquer, implementation, sortings Model: gpt-5-3-mini Solve time: 1m 50s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2dddac-65f8-83ec-bdff-9c933b0e2972 Solution Problem Understanding We are given a set of points on a number line. Each point starts at some integer position and moves forever in time, each with its own constant velocity. If we pick any two points, their distance changes over time...

CF 1268D - Invertation in Tournament Rating: 3200 Tags: brute force, divide and conquer, graphs, math Model: gpt-5-3-mini Solve time: 3m 22s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2d8cdd-8bac-83ec-a73f-1c9a8e0eb4dd Solution Problem Understanding We are given a complete directed graph where every pair of vertices has exactly one directed edge between them. This is a tournament. The structure is fully described by an adjacency matrix, so for each pair we know which...

CF 1373G - Pawns Rating: 2600 Tags: data structures, divide and conquer, greedy Model: gpt-5-3-mini Solve time: 5m 16s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e5b13-8504-83ec-ba02-aa6ed7e2a5da Solution Problem Understanding We are maintaining a dynamic set of pawns on an $n \times n$ grid. Each update toggles a pawn at a specific cell, and after every update we must determine how many extra rows need to be appended on top of the...

CF 1373D - Maximum Sum on Even Positions Rating: 1600 Tags: divide and conquer, dp, greedy, implementation Model: gpt-5-3-mini Solve time: 4m 2s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a2e59d2-33cc-83ec-96b9-54fb19eac428 Solution Problem Understanding We are given several arrays, and for each one we are allowed to perform at most one operation: choose a continuous segment and reverse it. After this optional modification, we look only at elements sitting on even indices,...