Codeforces Round 1051 (Div. 2)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
2143 Codeforces Round 1051 (Div. 2) FINISHED False 7200 18285923 Sept. 17, 2025, 2:35 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 2739 ) D2 Inversion Graph Coloring (Hard Version) PROGRAMMING binary search data structures dp two pointers

This is the hard version of the problem. The difference between the versions is that in this version, (n \le 2000). You can hack only if you solved all versions of this problem. A sequence (b_1, b_2, \ldots, b_k) is called good if there exists a coloring of each index (i) in red or blue such that for every pair of indices (i < j) with (b_i > b_j), the colors assigned to (i) and (j) are different. You are given a sequence (a_1, a_2, \ldots, a_n). Compute the number of good subsequences of the sequence, including the empty subsequence(^{\text{∗}}). Since the answer can be very large, output it modulo (10^9 + 7). (^{\text{∗}})A sequence (b) is a subsequence of a sequence (a) if (b) can be obtained from (a) by the deletion of several (possibly, zero or all) element from arbitrary positions. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 100)). The description of the test cases follows. The first line contains an integer (n) ((1 \leq n \leq 2000)) — the length of the sequence The second line contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le n)) — the contents of the sequence. It is guaranteed that the sum of (n) over all test cases does not exceed (2000). For each test case, output a single line containing the number of good subsequences modulo (10^9 + 7). In the first test case, the subsequences that are not good are (4, 3, 1), (4, 2, 1), and (4, 2, 3, 1). Since there are (16) subsequences in total, this means there are (16 - 3 = 13) good subsequences. In the third test case, every subsequence is good.

Tutorials

Codeforces Round 1051 (Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
339175662 -firefly- D2 Sept. 17, 2025, 7:37 p.m. OK C# 13 TESTS 13 968 32256000
339143499 Novachrono_ D2 Sept. 17, 2025, 4:01 p.m. OK C++17 (GCC 7-32) TESTS 13 265 18534400
339150885 bufferingblady D2 Sept. 17, 2025, 4:21 p.m. OK C++17 (GCC 7-32) TESTS 13 296 35635200
339199776 torn4dom4n D2 Sept. 18, 2025, 3:36 a.m. OK C++17 (GCC 7-32) TESTS 13 296 72499200
339154799 anik2000s D2 Sept. 17, 2025, 4:31 p.m. OK C++17 (GCC 7-32) TESTS 13 312 30617600
339173176 pradeepsingh271220 D2 Sept. 17, 2025, 7:05 p.m. OK C++17 (GCC 7-32) TESTS 13 327 30310400
339146192 Mamun217bd D2 Sept. 17, 2025, 4:08 p.m. OK C++17 (GCC 7-32) TESTS 13 358 11059200
339145400 NguyenQuyetDinh2.cpp D2 Sept. 17, 2025, 4:06 p.m. OK C++17 (GCC 7-32) TESTS 13 358 48435200
339153877 quant77 D2 Sept. 17, 2025, 4:29 p.m. OK C++17 (GCC 7-32) TESTS 13 390 30617600
339152596 venom_32 D2 Sept. 17, 2025, 4:26 p.m. OK C++17 (GCC 7-32) TESTS 13 390 30617600
339151524 ciphermalware D2 Sept. 17, 2025, 4:23 p.m. OK C++17 (GCC 7-32) TESTS 13 390 30617600
339145930 stdb_laster D2 Sept. 17, 2025, 4:07 p.m. OK C++20 (GCC 13-64) TESTS 13 265 11366400
339160589 Ice_man2.0 D2 Sept. 17, 2025, 5:24 p.m. OK C++20 (GCC 13-64) TESTS 13 296 24678400
339155172 kausthubsurya04 D2 Sept. 17, 2025, 4:32 p.m. OK C++20 (GCC 13-64) TESTS 13 312 30924800
339154967 tiger2005 D2 Sept. 17, 2025, 4:32 p.m. OK C++20 (GCC 13-64) TESTS 13 342 48640000
339145519 Grafana D2 Sept. 17, 2025, 4:06 p.m. OK C++20 (GCC 13-64) TESTS 13 343 30924800
339148805 ImSarthak D2 Sept. 17, 2025, 4:15 p.m. OK C++20 (GCC 13-64) TESTS 13 358 11366400
339161438 BaarishBoy D2 Sept. 17, 2025, 5:29 p.m. OK C++20 (GCC 13-64) TESTS 13 358 99328000
339151907 mgisabsolute D2 Sept. 17, 2025, 4:24 p.m. OK C++20 (GCC 13-64) TESTS 13 374 47104000
339145351 ivanovmark D2 Sept. 17, 2025, 4:06 p.m. OK C++20 (GCC 13-64) TESTS 13 390 24780800
339167718 MayankSavaliya D2 Sept. 17, 2025, 6:13 p.m. OK C++20 (GCC 13-64) TESTS 13 390 27136000
339206076 A_G D2 Sept. 18, 2025, 5:22 a.m. OK C++23 (GCC 14-64, msys2) TESTS 13 265 30924800
339147272 albrecht D2 Sept. 17, 2025, 4:11 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 281 27136000
339170016 wh01sShakin D2 Sept. 17, 2025, 6:32 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 296 18841600
339169525 who1sShakin D2 Sept. 17, 2025, 6:28 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 296 18841600
339145542 samarth4720 D2 Sept. 17, 2025, 4:06 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 296 18841600
339150917 GoogleBot D2 Sept. 17, 2025, 4:21 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 296 31027200
339190891 Alail_996 D2 Sept. 18, 2025, 1:19 a.m. OK C++23 (GCC 14-64, msys2) TESTS 13 311 18534400
339146372 uk369 D2 Sept. 17, 2025, 4:09 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 311 18534400
339155601 binghan D2 Sept. 17, 2025, 4:33 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 311 32358400
339142443 rishirathore214 D2 Sept. 17, 2025, 3:58 p.m. OK C++23 (GCC 14-64, msys2) TESTS 13 311 34918400
339167671 ICPCCode D2 Sept. 17, 2025, 6:12 p.m. OK GNU C11 TESTS 13 1156 72601600
339167735 BoomTiwari D2 Sept. 17, 2025, 6:13 p.m. OK GNU C11 TESTS 13 1264 96460800
339145445 d.o. D2 Sept. 17, 2025, 4:06 p.m. OK Go TESTS 13 531 64819200
339145374 Supergene D2 Sept. 17, 2025, 4:06 p.m. OK Go TESTS 13 577 64716800
339152082 24505a4203 D2 Sept. 17, 2025, 4:24 p.m. OK Java 21 TESTS 13 702 19148800
339150889 bharadwaj_manu D2 Sept. 17, 2025, 4:21 p.m. OK Java 21 TESTS 13 953 78336000
339151273 deepanshu_zen08 D2 Sept. 17, 2025, 4:22 p.m. OK Java 21 TESTS 13 1062 79872000
339152228 animesh_288 D2 Sept. 17, 2025, 4:25 p.m. OK Java 21 TESTS 13 1078 78950400
339151523 TargetEXPERT23 D2 Sept. 17, 2025, 4:23 p.m. OK Java 21 TESTS 13 1140 78438400
339176353 MaxBuzz D2 Sept. 17, 2025, 7:46 p.m. OK Java 21 TESTS 13 1561 146432000
339152399 Samyajit125 D2 Sept. 17, 2025, 4:25 p.m. OK Java 21 TESTS 13 2343 77619200
339156331 bhawnapannu27 D2 Sept. 17, 2025, 4:34 p.m. OK Java 8 TESTS 13 828 77824000
339149982 enan_mahmud D2 Sept. 17, 2025, 4:19 p.m. OK Java 8 TESTS 13 921 78028800
339152755 amber_100 D2 Sept. 17, 2025, 4:26 p.m. OK Java 8 TESTS 13 1031 78131200
339154242 robiulawal1aa D2 Sept. 17, 2025, 4:30 p.m. OK Kotlin 2.2 TESTS 13 1296 77516800
339186033 mathsplanck D2 Sept. 17, 2025, 11:16 p.m. OK PyPy 3-64 TESTS 13 1280 77004800
339148536 happybear21 D2 Sept. 17, 2025, 4:15 p.m. OK PyPy 3-64 TESTS 13 1342 51916800
339144840 wnrud D2 Sept. 17, 2025, 4:04 p.m. OK PyPy 3-64 TESTS 13 1374 74342400
339143128 holycow_dup D2 Sept. 17, 2025, 4 p.m. OK PyPy 3-64 TESTS 13 1577 75468800
339174397 white_two D2 Sept. 17, 2025, 7:21 p.m. OK PyPy 3-64 TESTS 13 1702 45977600
339203659 helltractor D2 Sept. 18, 2025, 4:46 a.m. OK PyPy 3-64 TESTS 13 1703 80076800
339147131 yupooh D2 Sept. 17, 2025, 4:11 p.m. OK PyPy 3-64 TESTS 13 2015 119500800
339183905 denilb D2 Sept. 17, 2025, 10:11 p.m. OK PyPy 3-64 TESTS 13 2077 78540800
339177962 DT4V D2 Sept. 17, 2025, 8:09 p.m. OK PyPy 3-64 TESTS 13 2077 79564800
339191830 czjnbb D2 Sept. 18, 2025, 1:40 a.m. OK PyPy 3-64 TESTS 13 2234 59699200
339147424 Egor D2 Sept. 17, 2025, 4:11 p.m. OK Rust 2024 TESTS 13 2156 64921600

remove filters

Back to search problems