#shortest paths

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 938D - Buy a Ticket Rating: 2000 Tags: data structures, graphs, shortest paths Model: gpt-5-3-mini Solve time: 2m Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a32790c-167c-83ec-bdc2-cbedf9f20620 Solution Problem Understanding We are given a weighted undirected graph where cities are vertices and train routes are edges with travel costs. Each city also has a fixed price for buying a concert ticket in that city. For any starting city, a person may travel...

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