Codeforces Round 745 (Div. 1)

Solutions for Codeforces Round 745 (Div. 1) (contest 1580). 0/6 problems verified against sample I/O. Difficulty range: 1700-3400.

6 items

Codeforces Round 745 (Div. 1)

Type: Div. 1 | Problems: 6 | Verified: 0/6 | Rating range: 1700-3400 | Time: 18m 51s

Problem Name Rating Tags Solve Time Verified
A Portal 1700 brute-force, data-structures, dp 3m 44s ✗
B Mathematics Curriculum 2600 brute-force, combinatorics, dp 2m 4s ✗
C Train Maintenance 2200 brute-force, data-structures, implementation 5m 43s ✗
D Subsequence 2900 brute-force, divide-and-conquer, dp 2m 30s ✗
E Railway Construction 3400 brute-force, constructive-algorithms, data-structures 4m 10s ✗
F Problems for Codeforces 3300 combinatorics, fft, math 40s ✗
Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580E - Railway Construction

We are given a network of railway stations in Gensokyo, connected by two-way railways with positive lengths. The stations are numbered from 1 to $n$, with station 1 being the main hub. The network is fully connected, so every station is reachable from any other station.
codeforces competitive-programming brute-force constructive-algorithms data-structures graphs shortest-paths Jun 10, 2026
Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580C - Train Maintenance

We have a system that tracks trains of different models over a sequence of days. At the start, there are no trains. On each day, we either add a train of a specific model or remove one.
codeforces competitive-programming brute-force data-structures implementation Jun 10, 2026
Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580F - Problems for Codeforces

I can write a full editorial in that format, but I need the actual solution first. Codeforces 1580F is a 3300-rated problem whose accepted solution is highly nontrivial and relies on fairly deep generating-function techniques with FFT.
codeforces competitive-programming combinatorics fft math Jun 10, 2026
Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580D - Subsequence

We are given a sequence of distinct integers of length $n$, and we are asked to select a subsequence of length $m$ to maximize a specific value.
codeforces competitive-programming brute-force divide-and-conquer dp greedy trees Jun 10, 2026
Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580A - Portal

We are given a binary grid. A cell containing 1 is an obsidian block and a cell containing 0 is empty. We may flip any cell, changing 0 to 1 or 1 to 0, with cost one per flip.
codeforces competitive-programming brute-force data-structures dp greedy implementation Jun 10, 2026
Practice › Codeforces Solutions › Codeforces Round 745 (Div. 1) ›

CF 1580B - Mathematics Curriculum

We are asked to count permutations of the numbers from 1 to $n$ that have exactly $k$ "good" numbers. A number $x$ in a permutation is called good if, when we look at all contiguous subarrays containing $x$, there are exactly $m$ distinct maxima.
codeforces competitive-programming brute-force combinatorics dp trees Jun 10, 2026