Codeforces Round 792 (Div. 1 + 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
1684 Codeforces Round 792 (Div. 1 + Div. 2) FINISHED False 7200 78852299 May 19, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 3193 ) E MEX vs DIFF PROGRAMMING brute force constructive algorithms data structures greedy two pointers 2100

B"You are given an array a of n non-negative integers. In one operation you can change any number in the array to any other non-negative integer. Let's define the cost of the array as operatorname{DIFF}(a) - operatorname{MEX}(a) , where operatorname{MEX} of a set of non-negative integers is the smallest non-negative integer not present in the set, and operatorname{DIFF} is the number of different numbers in the array. For example, operatorname{MEX}( {1, 2, 3 }) = 0 , operatorname{MEX}( {0, 1, 2, 4, 5 }) = 3 . You should find the minimal cost of the array a if you are allowed to make at most k operations. The input consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. Description of the test cases follows. The first line of each test case contains two integers n and k ( 1 <= n <= 10^5 , 0 <= k <= 10^5 ) -- the length of the array a and the number of operations that you are allowed to make. The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 0 <= a_i <= 10^9 ) -- the elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 10^5 . For each test case output a single integer -- minimal cost that it is possible to get making at most k operations. In the first test case no operations are needed to minimize the value of operatorname{DIFF} - operatorname{MEX} . In the second test case it is possible to replace 5 by 1 . After that the array a is [0, , 2, , 4, , 1] , operatorname{DIFF} = 4 , operatorname{MEX} = operatorname{MEX}( {0, 1, 2, 4 }) = 3 , so the answer is 1 . In the third test case one possible array a is [4, , 13, , 0, , 0, , 13, , 1, , 2] , operatorname{DIFF} = 5 , operatorname{MEX} = 3 . In the fourth test "...

Tutorials

Codeforces Round #792 (Div. 1 + Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
157727781 Gassa E May 19, 2022, 4:32 p.m. OK D TESTS 34 62 9420800 2100
157735796 Bobocan E May 19, 2022, 5:59 p.m. OK GNU C11 TESTS 34 46 6144000 2100
157724178 LBRhhhh E May 19, 2022, 4:22 p.m. OK GNU C++14 TESTS 34 46 2252800 2100
157756617 zulk E May 20, 2022, 1:34 a.m. OK GNU C++14 TESTS 37 46 2560000 2100
157727529 cyh_toby E May 19, 2022, 4:31 p.m. OK GNU C++14 TESTS 34 46 3072000 2100
157766553 Shirost E May 20, 2022, 5 a.m. OK GNU C++14 TESTS 37 46 4812800 2100
157758846 Paqis E May 20, 2022, 2:29 a.m. OK GNU C++14 TESTS 37 46 9625600 2100
157752287 antguz E May 19, 2022, 10:58 p.m. OK GNU C++14 TESTS 37 61 921600 2100
157758669 Paqis E May 20, 2022, 2:25 a.m. OK GNU C++14 TESTS 37 61 9625600 2100
157725292 Antimony E May 19, 2022, 4:25 p.m. OK GNU C++14 TESTS 34 62 2662400 2100
157749663 daniyarello E May 19, 2022, 9:29 p.m. OK GNU C++14 TESTS 37 62 4505600 2100
157765150 Cu_OH_2 E May 20, 2022, 4:36 a.m. OK GNU C++14 TESTS 37 62 4915200 2100
157765189 Andycraft E May 20, 2022, 4:37 a.m. OK GNU C++17 TESTS 37 46 2252800 2100
157726930 Lieska E May 19, 2022, 4:29 p.m. OK GNU C++17 TESTS 34 46 2560000 2100
157760457 acwing_meow E May 20, 2022, 3:04 a.m. OK GNU C++17 TESTS 37 46 2867200 2100
157739320 salix_leaf E May 19, 2022, 6:29 p.m. OK GNU C++17 TESTS 34 46 2969600 2100
157742971 Deaga E May 19, 2022, 7:17 p.m. OK GNU C++17 TESTS 37 46 3788800 2100
157740129 Abdel-AzizMostafa E May 19, 2022, 6:39 p.m. OK GNU C++17 TESTS 37 46 3993600 2100
157736685 Zenzenzense E May 19, 2022, 6:05 p.m. OK GNU C++17 TESTS 34 46 5324800 2100
157737633 lddlinan E May 19, 2022, 6:13 p.m. OK GNU C++17 TESTS 34 46 10240000 2100
157726506 xzrrooney E May 19, 2022, 4:28 p.m. OK GNU C++17 TESTS 34 46 13107200 2100
157725880 Dd2dD2 E May 19, 2022, 4:27 p.m. OK GNU C++17 TESTS 34 61 3072000 2100
157756908 isheoran E May 20, 2022, 1:42 a.m. OK GNU C++17 (64) TESTS 37 46 2969600 2100
157733502 _c_k_r_ E May 19, 2022, 5:46 p.m. OK GNU C++17 (64) TESTS 34 46 6041600 2100
157734713 shinigami11 E May 19, 2022, 5:52 p.m. OK GNU C++17 (64) TESTS 34 46 7065600 2100
157746475 FedorKudashev E May 19, 2022, 8:15 p.m. OK GNU C++17 (64) TESTS 37 46 7577600 2100
157738299 antoniomsah E May 19, 2022, 6:19 p.m. OK GNU C++17 (64) TESTS 34 61 2662400 2100
157763192 Hyperlink_Blocked E May 20, 2022, 4 a.m. OK GNU C++17 (64) TESTS 37 61 6758400 2100
157727866 suzuken_w E May 19, 2022, 4:32 p.m. OK GNU C++17 (64) TESTS 34 61 7987200 2100
157759642 YYYLLL2021 E May 20, 2022, 2:48 a.m. OK GNU C++17 (64) TESTS 37 62 6348800 2100
157769376 youtsuha E May 20, 2022, 5:44 a.m. OK GNU C++17 (64) TESTS 37 62 6963200 2100
157726300 retiredd E May 19, 2022, 4:28 p.m. OK GNU C++17 (64) TESTS 34 62 8499200 2100
157757424 Shrimp__ E May 20, 2022, 1:56 a.m. OK GNU C++20 (64) TESTS 37 31 819200 2100
157758583 Shrimp__ E May 20, 2022, 2:23 a.m. OK GNU C++20 (64) TESTS 37 31 819200 2100
157754351 FLself E May 20, 2022, 12:19 a.m. OK GNU C++20 (64) TESTS 37 31 4608000 2100
157741900 DC17 E May 19, 2022, 7:02 p.m. OK GNU C++20 (64) TESTS 37 31 6348800 2100
157763473 zn_com E May 20, 2022, 4:06 a.m. OK GNU C++20 (64) TESTS 37 46 2662400 2100
157765152 Bananana. E May 20, 2022, 4:36 a.m. OK GNU C++20 (64) TESTS 37 46 3481600 2100
157732772 circletime E May 19, 2022, 5:43 p.m. OK GNU C++20 (64) TESTS 34 46 4812800 2100
157764710 I_Love_Aruzhan E May 20, 2022, 4:29 a.m. OK GNU C++20 (64) TESTS 37 46 5222400 2100
157752623 _mak_ E May 19, 2022, 11:13 p.m. OK GNU C++20 (64) TESTS 37 46 6348800 2100
157725171 Bungmint E May 19, 2022, 4:25 p.m. OK GNU C++20 (64) TESTS 34 46 6963200 2100
157724293 Runislove E May 19, 2022, 4:22 p.m. OK Go TESTS 34 296 12492800 2100
157751900 profchi E May 19, 2022, 10:44 p.m. OK Java 11 TESTS 37 295 2560000 2100
157734895 MrOtter E May 19, 2022, 5:53 p.m. OK Java 11 TESTS 34 311 29081600 2100
157727724 DumplingLife E May 19, 2022, 4:32 p.m. OK Java 8 TESTS 34 343 32665600 2100
157726637 tarattata1 E May 19, 2022, 4:29 p.m. OK MS C++ 2017 TESTS 34 108 6144000 2100
157734219 1_2_3_4_5_9 E May 19, 2022, 5:49 p.m. OK PyPy 2 TESTS 34 327 43929600 2100
157728086 14_15_16 E May 19, 2022, 4:32 p.m. OK PyPy 2 TESTS 34 327 43929600 2100
157724243 eepsilon E May 19, 2022, 4:22 p.m. OK PyPy 3 TESTS 34 311 35020800 2100
157732778 KanishkGoel E May 19, 2022, 5:43 p.m. OK PyPy 3 TESTS 34 327 30208000 2100
157738968 Mashin_larner E May 19, 2022, 6:25 p.m. OK PyPy 3 TESTS 34 358 38400000 2100
157740842 Usurper__ E May 19, 2022, 6:48 p.m. OK PyPy 3 TESTS 37 514 32768000 2100
157740366 undertaker271 E May 19, 2022, 6:42 p.m. OK PyPy 3 TESTS 37 1107 34816000 2100
157769077 asdsasd E May 20, 2022, 5:40 a.m. OK PyPy 3-64 TESTS 37 249 23756800 2100
157738645 t0mmyn E May 19, 2022, 6:22 p.m. OK PyPy 3-64 TESTS 34 311 54169600 2100
157749362 oadey89 E May 19, 2022, 9:22 p.m. OK PyPy 3-64 TESTS 37 343 21913600 2100
157725920 tassei903 E May 19, 2022, 4:27 p.m. OK PyPy 3-64 TESTS 34 358 55603200 2100
157749243 oadey89 E May 19, 2022, 9:19 p.m. OK PyPy 3-64 TESTS 37 373 23040000 2100
157749308 oadey89 E May 19, 2022, 9:21 p.m. OK PyPy 3-64 TESTS 37 374 23040000 2100
157749266 oadey89 E May 19, 2022, 9:19 p.m. OK PyPy 3-64 TESTS 37 389 23040000 2100
157749117 oadey89 E May 19, 2022, 9:16 p.m. OK PyPy 3-64 TESTS 37 389 23040000 2100
157756780 siganai E May 20, 2022, 1:38 a.m. OK PyPy 3-64 TESTS 37 389 27545600 2100
157758006 abhijeet.panihar.cse20 E May 20, 2022, 2:10 a.m. OK PyPy 3-64 TESTS 37 421 27136000 2100
157750510 qwerty787788 E May 19, 2022, 9:53 p.m. OK Rust 2021 TESTS 37 46 3891200 2100

remove filters

Back to search problems