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. |
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 "... |
Codeforces Round #792 (Div. 1 + Div. 2) Editorial |
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 |
Back to search problems