Codeforces Round 576 (Div. 1)

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
1198 Codeforces Round 576 (Div. 1) FINISHED False 7200 172941887 July 30, 2019, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 9114 ) A MP3 PROGRAMMING sortings two pointers 1700

B"One common way of digitalizing sound is to record sound intensity at particular time moments. For each time moment intensity is recorded as a non-negative integer. Thus we can represent a sound file as an array of n non-negative integers. If there are exactly K distinct values in the array, then we need k = lceil log_{2} K rceil bits to store each value. It then takes nk bits to store the whole file. To reduce the memory consumption we need to apply some compression. One common way is to reduce the number of possible intensity values. We choose two integers l <= r , and after that all intensity values are changed in the following way: if the intensity value is within the range [l;r] , we don't change it. If it is less than l , we change it to l ; if it is greater than r , we change it to r . You can see that we lose some low and some high intensities. Your task is to apply this compression in such a way that the file fits onto a disk of size I bytes, and the number of changed elements in the array is minimal possible. We remind you that 1 byte contains 8 bits. k = lceil log_{2} K rceil is the smallest integer such that K <= 2^{k} . In particular, if K = 1 , then k = 0 . The first line contains two integers n and I ( 1 <= n <= 4 cdot 10^{5} , 1 <= I <= 10^{8} ) -- the length of the array and the size of the disk in bytes, respectively. The next line contains n integers a_{i} ( 0 <= a_{i} <= 10^{9} ) -- the array denoting the sound file. Print a single integer -- the minimal possible number of changed elements. In the first example we can choose l=2, r=3 . The array becomes 2 2 2 3 3 3, the number of distinct elements is K=2 , and the sound file fits onto the disk. Only two values are changed. In the second example the disk is larger, so the initial file fits it and no changes are required. In the thi"...

Tutorials

E

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
58055235 hatsuyuki15 A July 31, 2019, 4:47 a.m. OK D TESTS 110 233 8499200 1700
58008112 hos.lyric A July 30, 2019, 3:11 p.m. OK D TESTS 108 249 22118400 1700
57999686 Gassa A July 30, 2019, 2:50 p.m. OK D TESTS 108 249 27545600 1700
58386266 AutumnKite A Aug. 6, 2019, 12:04 p.m. OK GNU C++11 TESTS 112 62 1433600 1700
58057919 AutumnKite A July 31, 2019, 6:13 a.m. OK GNU C++11 TESTS 110 62 1433600 1700
58497388 luogu_bot5 A Aug. 9, 2019, 12:46 p.m. OK GNU C++11 TESTS 112 62 1638400 1700
64771533 Dream-chasing_Juvenile A Nov. 13, 2019, 12:17 a.m. OK GNU C++11 TESTS 112 62 1638400 1700
58001833 msuwakow A July 30, 2019, 2:55 p.m. OK GNU C++11 TESTS 108 62 1638400 1700
58246233 bdcaknoip A Aug. 4, 2019, 5:34 a.m. OK GNU C++11 TESTS 112 62 3174400 1700
58197469 luogu_bot5 A Aug. 3, 2019, 1:47 a.m. OK GNU C++11 TESTS 112 62 3174400 1700
58084707 liubin A July 31, 2019, 3:07 p.m. OK GNU C++11 TESTS 111 62 3174400 1700
57996515 stal_xy23z7b8 A July 30, 2019, 2:44 p.m. OK GNU C++11 TESTS 108 62 3174400 1700
58686829 Depth_First_Search A Aug. 13, 2019, 12:21 a.m. OK GNU C++11 TESTS 112 62 3276800 1700
58186254 tokitsukaze A Aug. 2, 2019, 5:16 p.m. OK GNU C++14 TESTS 112 77 3276800 1700
58004155 Linkus A July 30, 2019, 3 p.m. OK GNU C++14 TESTS 108 77 4812800 1700
58615895 rhrnald A Aug. 11, 2019, 2:27 p.m. OK GNU C++14 TESTS 112 109 16076800 1700
58414536 1558996 A Aug. 7, 2019, 3:55 a.m. OK GNU C++14 TESTS 112 124 3174400 1700
59082623 LittleAA A Aug. 19, 2019, 9:47 a.m. OK GNU C++14 TESTS 112 124 16076800 1700
66621528 Toxel A Dec. 11, 2019, 7:10 a.m. OK GNU C++14 TESTS 112 139 1638400 1700
58000629 Toxtricity A July 30, 2019, 2:52 p.m. OK GNU C++14 TESTS 108 139 1638400 1700
58048930 nonameless A July 31, 2019, 1:43 a.m. OK GNU C++14 TESTS 110 139 3174400 1700
58080546 Mr_Mafia A July 31, 2019, 1:46 p.m. OK GNU C++14 TESTS 111 139 16076800 1700
64689277 tzaph_ A Nov. 11, 2019, 12:40 p.m. OK GNU C++14 TESTS 112 140 1638400 1700
58174881 GoogleBot A Aug. 2, 2019, 12:41 p.m. OK GNU C++17 TESTS 112 109 3174400 1700
58065757 xidongdong A July 31, 2019, 8:52 a.m. OK GNU C++17 TESTS 110 109 3174400 1700
58003566 GoogleBot A July 30, 2019, 2:59 p.m. OK GNU C++17 TESTS 108 109 3174400 1700
58000052 kessido A July 30, 2019, 2:51 p.m. OK GNU C++17 TESTS 108 109 3174400 1700
58065831 xidongdong A July 31, 2019, 8:54 a.m. OK GNU C++17 TESTS 110 124 3174400 1700
58185965 lkunalvermal A Aug. 2, 2019, 5:09 p.m. OK GNU C++17 TESTS 112 124 3174400 1700
58065982 xidongdong A July 31, 2019, 8:56 a.m. OK GNU C++17 TESTS 110 124 3174400 1700
58065395 xidongdong A July 31, 2019, 8:46 a.m. OK GNU C++17 TESTS 110 124 3174400 1700
58046469 Unsterblicher_Geist A July 31, 2019, 12:02 a.m. OK GNU C++17 TESTS 110 124 8089600 1700
68696805 kaike A Jan. 13, 2020, 8:11 a.m. OK GNU C++17 TESTS 112 139 4812800 1700
58407594 reanimatorzon A Aug. 6, 2019, 10:01 p.m. OK Go TESTS 112 155 9728000 1700
58227531 WangJialei A Aug. 3, 2019, 3:09 p.m. OK Go TESTS 112 421 9728000 1700
58927108 T_Nady A Aug. 16, 2019, 8:14 p.m. OK Java 8 TESTS 112 186 0 1700
58010737 uwi A July 30, 2019, 3:19 p.m. OK Java 8 TESTS 108 202 12697600 1700
58552268 happybelly A Aug. 10, 2019, 9:02 p.m. OK Java 8 TESTS 112 233 0 1700
58185951 Agnimandur A Aug. 2, 2019, 5:08 p.m. OK Java 8 TESTS 112 234 15462400 1700
57996474 Petr A July 30, 2019, 2:44 p.m. OK Java 8 TESTS 108 248 13721600 1700
58717256 huhansan A Aug. 13, 2019, 2:34 p.m. OK Java 8 TESTS 112 249 13721600 1700
65300018 aminul A Nov. 18, 2019, 12:55 p.m. OK Java 8 TESTS 112 249 16896000 1700
58054162 Darth_Jar_Jar_Binks A July 31, 2019, 4:09 a.m. OK Java 8 TESTS 110 265 18739200 1700
58121447 LAKOUAM_IMAD A Aug. 1, 2019, 10:56 a.m. OK Java 8 TESTS 112 280 15257600 1700
60369722 darren_yao A Sept. 11, 2019, 12:18 a.m. OK Java 8 TESTS 112 295 30924800 1700
58518660 kotter A Aug. 10, 2019, 2:39 a.m. OK Kotlin TESTS 112 514 41574400 1700
59833591 Spheniscine A Sept. 1, 2019, 1:59 a.m. OK Kotlin TESTS 112 670 63180800 1700
58122560 darnley A Aug. 1, 2019, 11:24 a.m. OK Kotlin TESTS 112 701 41267200 1700
58122367 darnley A Aug. 1, 2019, 11:20 a.m. OK Kotlin TESTS 112 701 41267200 1700
58063260 darnley A July 31, 2019, 8:07 a.m. OK Kotlin TESTS 110 701 44032000 1700
58122143 darnley A Aug. 1, 2019, 11:14 a.m. OK Kotlin TESTS 112 716 41267200 1700
58063078 darnley A July 31, 2019, 8:04 a.m. OK Kotlin TESTS 110 717 41267200 1700
59433829 hogloid A Aug. 25, 2019, 7:44 a.m. OK Kotlin TESTS 112 733 41267200 1700
59687651 Spheniscine A Aug. 30, 2019, 3:08 a.m. OK Kotlin TESTS 112 920 44032000 1700
58104005 Spheniscine A Aug. 1, 2019, 3 a.m. OK Kotlin TESTS 111 936 25600000 1700
58005740 riantkb A July 30, 2019, 3:05 p.m. OK Mono C# TESTS 108 202 47616000 1700
58000826 eki A July 30, 2019, 2:53 p.m. OK Mono C# TESTS 108 233 39731200 1700
58007796 claw88 A July 30, 2019, 3:10 p.m. OK Mono C# TESTS 108 717 52531200 1700
60757353 vjudge4 A Sept. 18, 2019, 9:34 a.m. OK MS C++ TESTS 112 124 6451200 1700
58492573 vjudge5 A Aug. 9, 2019, 10:36 a.m. OK MS C++ TESTS 112 171 4812800 1700
58109301 vjudge1 A Aug. 1, 2019, 6:19 a.m. OK MS C++ TESTS 111 265 39321600 1700
60753813 vjudge5 A Sept. 18, 2019, 7:49 a.m. OK MS C++ TESTS 112 296 20889600 1700
58051013 vjudge3 A July 31, 2019, 2:38 a.m. OK MS C++ TESTS 110 312 20889600 1700
65258719 vjudge5 A Nov. 17, 2019, 2:17 p.m. OK MS C++ TESTS 112 436 14438400 1700
61100924 math957963 A Sept. 23, 2019, 6:42 a.m. OK MS C++ TESTS 112 576 35737600 1700
61900323 vjudge4 A Oct. 5, 2019, 8:25 a.m. OK MS C++ TESTS 112 592 14950400 1700
58038684 Milanin A July 30, 2019, 6:45 p.m. OK MS C++ 2017 TESTS 109 171 3276800 1700
60445268 cckk4467 A Sept. 12, 2019, 1:55 p.m. OK MS C++ 2017 TESTS 112 171 6041600 1700
65277139 vjudge1 A Nov. 18, 2019, 2:27 a.m. OK MS C++ 2017 TESTS 112 296 36044800 1700
58573668 116c A Aug. 11, 2019, 11:24 a.m. OK MS C++ 2017 TESTS 112 358 14540800 1700
58042117 Schullz A July 30, 2019, 8:13 p.m. OK MS C++ 2017 TESTS 109 358 17715200 1700
58005609 P___ A July 30, 2019, 3:04 p.m. OK MS C++ 2017 TESTS 108 389 16179200 1700
58057311 yp0413170331 A July 31, 2019, 5:56 a.m. OK MS C++ 2017 TESTS 110 390 12083200 1700
58057261 yp0413170331 A July 31, 2019, 5:54 a.m. OK MS C++ 2017 TESTS 110 405 12083200 1700
68854029 AleksanderBalobanov A Jan. 15, 2020, 10:02 a.m. OK MS C++ 2017 TESTS 112 405 16896000 1700
58336936 Stul19 A Aug. 5, 2019, 11:50 a.m. OK MS C++ 2017 TESTS 112 421 3174400 1700
58096929 mayakin A July 31, 2019, 8:27 p.m. OK PHP TESTS 111 857 123494400 1700
58682590 yumtam A Aug. 12, 2019, 7:51 p.m. OK PyPy 2 TESTS 112 296 42905600 1700
58039457 drd93 A July 30, 2019, 7:02 p.m. OK PyPy 2 TESTS 109 358 32256000 1700
58876950 Helli.code A Aug. 15, 2019, 6:24 p.m. OK PyPy 2 TESTS 112 358 103424000 1700
58150419 Vedkribhu A Aug. 2, 2019, 2:11 a.m. OK PyPy 2 TESTS 112 389 40243200 1700
58788432 jolt.tks A Aug. 14, 2019, 12:57 a.m. OK PyPy 2 TESTS 112 420 51916800 1700
62407417 nikeshthapa255 A Oct. 12, 2019, 9:25 a.m. OK PyPy 2 TESTS 112 420 103424000 1700
57998990 alexwice A July 30, 2019, 2:49 p.m. OK PyPy 2 TESTS 108 420 104448000 1700
57999627 MathisHammel A July 30, 2019, 2:50 p.m. OK PyPy 2 TESTS 108 452 104448000 1700
65693540 GTrigger A Nov. 25, 2019, 6:32 a.m. OK PyPy 2 TESTS 112 467 104448000 1700
58266335 soumyasarkar1998 A Aug. 4, 2019, 2:41 p.m. OK PyPy 2 TESTS 112 468 104448000 1700
58143660 sm1ley A Aug. 1, 2019, 7:30 p.m. OK PyPy 3 TESTS 112 624 31027200 1700
59504588 nealzane A Aug. 26, 2019, 5:19 a.m. OK PyPy 3 TESTS 112 624 103526400 1700
65292594 irza_law A Nov. 18, 2019, 10:20 a.m. OK PyPy 3 TESTS 112 638 103833600 1700
58106283 pyduper A Aug. 1, 2019, 4:30 a.m. OK PyPy 3 TESTS 111 639 103526400 1700
58036731 TangentOfA A July 30, 2019, 6:13 p.m. OK PyPy 3 TESTS 109 639 103526400 1700
61726014 darkus-_- A Oct. 2, 2019, 3:28 p.m. OK PyPy 3 TESTS 112 639 206950400 1700
58180423 wentwrong A Aug. 2, 2019, 2:58 p.m. OK PyPy 3 TESTS 112 654 37068800 1700
69193615 chielo A Jan. 20, 2020, 2:14 p.m. OK PyPy 3 TESTS 112 654 103526400 1700
58063342 king_coder1 A July 31, 2019, 8:09 a.m. OK PyPy 3 TESTS 110 654 103526400 1700
58569234 amruth_kumar A Aug. 11, 2019, 9:19 a.m. OK PyPy 3 TESTS 112 655 103526400 1700
58194008 rishabhs120 A Aug. 2, 2019, 9:53 p.m. OK Python 3 TESTS 112 561 106905600 1700
58117008 eugalt A Aug. 1, 2019, 9:13 a.m. OK Python 3 TESTS 111 577 106905600 1700
58105731 eugalt A Aug. 1, 2019, 4:08 a.m. OK Python 3 TESTS 111 607 106905600 1700
58171849 BugLeave A Aug. 2, 2019, 11:39 a.m. OK Python 3 TESTS 112 608 29184000 1700
58116887 eugalt A Aug. 1, 2019, 9:10 a.m. OK Python 3 TESTS 111 608 106905600 1700
58196909 MadJayhawk A Aug. 3, 2019, 1:19 a.m. OK Python 3 TESTS 112 764 213708800 1700
58181123 wentwrong A Aug. 2, 2019, 3:13 p.m. OK Python 3 TESTS 112 811 29286400 1700
58143720 sm1ley A Aug. 1, 2019, 7:32 p.m. OK Python 3 TESTS 112 858 28876800 1700
69501684 MinecraftFuns A Jan. 25, 2020, 6:49 a.m. OK Python 3 TESTS 112 935 29388800 1700
58228302 user_0001 A Aug. 3, 2019, 3:30 p.m. OK Python 3 TESTS 112 982 28774400 1700
58003646 EbTech A July 30, 2019, 2:59 p.m. OK Rust TESTS 108 77 11878400 1700
58833524 izhuer A Aug. 14, 2019, 7:13 p.m. OK Rust TESTS 112 78 13414400 1700
58836346 izhuer A Aug. 14, 2019, 9:13 p.m. OK Rust TESTS 112 155 13414400 1700
65391044 tuna_salad A Nov. 19, 2019, 5:39 p.m. OK Rust TESTS 112 155 16076800 1700
58049565 YeXiaoRain A July 31, 2019, 2 a.m. OK Rust TESTS 110 170 22016000 1700
58836461 ForeverChelsea A Aug. 14, 2019, 9:20 p.m. OK Rust TESTS 112 171 13414400 1700

remove filters

Back to search problems