Codeforces Round 575 (Div. 3)

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
1196 Codeforces Round 575 (Div. 3) FINISHED False 7200 173460287 July 24, 2019, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 9870 ) D2 RGB Substring (hard version) PROGRAMMING data structures dp implementation two pointers 1600

B'The only difference between easy and hard versions is the size of the input. You are given a string s consisting of n characters, each character is 'R ', 'G ' or 'B '. You are also given an integer k . Your task is to change the minimum number of characters in the initial string s so that after the changes there will be a string of length k that is a substring of s , and is also a substring of the infinite string "RGBRGBRGB ...". A string a is a substring of string b if there exists a positive integer i such that a_1 = b_i , a_2 = b_{i + 1} , a_3 = b_{i + 2} , ..., a_{|a|} = b_{i + |a| - 1} . For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not. You have to answer q independent queries. The first line of the input contains one integer q ( 1 <= q <= 2 cdot 10^5 ) -- the number of queries. Then q queries follow. The first line of the query contains two integers n and k ( 1 <= k <= n <= 2 cdot 10^5 ) -- the length of the string s and the length of the substring. The second line of the query contains a string s consisting of n characters 'R ', 'G ' and 'B '. It is guaranteed that the sum of n over all queries does not exceed 2 cdot 10^5 ( sum n <= 2 cdot 10^5 ). For each query print one integer -- the minimum number of characters you need to change in the initial string s so that after changing there will be a substring of length k in s that is also a substring of the infinite string "RGBRGBRGB ...". In the first example, you can change the first character to 'R ' and obtain the substring "RG", or change the second character to 'R ' and obtain "BR", or change the third, fourth or fifth character to 'B ' and obtain "GB". In the second example, the substring is "BRG". '...

Tutorials

Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
57845541 arounderstands D2 July 27, 2019, 10:59 a.m. OK Clang++17 Diagnostics TESTS 27 217 0 1600
66027071 vjudge3 D2 Nov. 30, 2019, 9 a.m. OK Clang++17 Diagnostics TESTS 27 249 102400 1600
57871805 hatsuyuki15 D2 July 28, 2019, 2:23 a.m. OK D TESTS 27 233 5836800 1600
60401818 Denor D2 Sept. 11, 2019, 4:58 p.m. OK Delphi TESTS 27 108 512000 1600
57860364 ruban D2 July 27, 2019, 5:27 p.m. OK Delphi TESTS 27 1575 137728000 1600
58193524 Craspedacusta D2 Aug. 2, 2019, 9:26 p.m. OK FPC TESTS 27 717 3379200 1600
57863219 ruban D2 July 27, 2019, 7:04 p.m. OK FPC TESTS 27 795 138649600 1600
57734059 MRoy D2 July 25, 2019, 9:25 a.m. OK GNU C11 TESTS 27 670 819200 1600
57846514 cs234_shrey D2 July 27, 2019, 11:24 a.m. OK GNU C11 TESTS 27 685 1024000 1600
57757687 Xetnys_Rorre D2 July 25, 2019, 4:50 p.m. OK GNU C11 TESTS 27 685 1024000 1600
58400203 NetravatPendsey D2 Aug. 6, 2019, 5:25 p.m. OK GNU C11 TESTS 27 702 1945600 1600
57851620 TaeHoonYoon D2 July 27, 2019, 1:21 p.m. OK GNU C11 TESTS 27 717 2457600 1600
58399385 NetravatPendsey D2 Aug. 6, 2019, 5:02 p.m. OK GNU C11 TESTS 27 748 1945600 1600
58399308 NetravatPendsey D2 Aug. 6, 2019, 5 p.m. OK GNU C11 TESTS 27 764 1945600 1600
58210744 hz2016 D2 Aug. 3, 2019, 8:43 a.m. OK GNU C++11 TESTS 27 31 1638400 1600
58210657 hz2016 D2 Aug. 3, 2019, 8:41 a.m. OK GNU C++11 TESTS 27 31 1638400 1600
58209646 hz2016 D2 Aug. 3, 2019, 8:23 a.m. OK GNU C++11 TESTS 27 31 1843200 1600
67206790 910306264 D2 Dec. 19, 2019, 12:42 p.m. OK GNU C++11 TESTS 27 31 3891200 1600
57735184 ticmis D2 July 25, 2019, 9:44 a.m. OK GNU C++11 TESTS 27 46 1638400 1600
58221101 Frame233 D2 Aug. 3, 2019, 12:35 p.m. OK GNU C++11 TESTS 27 46 2764800 1600
58642980 Kylin_ D2 Aug. 12, 2019, 4:36 a.m. OK GNU C++11 TESTS 27 46 3072000 1600
58883705 luogu_bot2 D2 Aug. 16, 2019, 12:09 a.m. OK GNU C++11 TESTS 27 46 3276800 1600
60602061 luogu_bot2 D2 Sept. 15, 2019, 8:10 a.m. OK GNU C++11 TESTS 27 61 2662400 1600
60602063 devout D2 Sept. 15, 2019, 8:10 a.m. OK GNU C++11 TESTS 27 61 2662400 1600
58920984 tokitsukaze D2 Aug. 16, 2019, 5:10 p.m. OK GNU C++14 TESTS 27 46 1126400 1600
58129481 hehelego D2 Aug. 1, 2019, 1:44 p.m. OK GNU C++14 TESTS 27 77 3174400 1600
64338102 lclpsoz D2 Nov. 5, 2019, 11:47 p.m. OK GNU C++14 TESTS 27 78 1024000 1600
57756114 notan_07 D2 July 25, 2019, 4:21 p.m. OK GNU C++14 TESTS 27 78 2867200 1600
57744306 Muhammad98 D2 July 25, 2019, 12:29 p.m. OK GNU C++14 TESTS 27 93 204800 1600
58102065 vjudge5 D2 Aug. 1, 2019, 1:44 a.m. OK GNU C++14 TESTS 27 93 204800 1600
59491850 ljk0411jg D2 Aug. 25, 2019, 7:39 p.m. OK GNU C++14 TESTS 27 93 204800 1600
58212845 enjoy_coding D2 Aug. 3, 2019, 9:28 a.m. OK GNU C++14 TESTS 27 93 512000 1600
58385356 too_young_too_top1 D2 Aug. 6, 2019, 11:44 a.m. OK GNU C++14 TESTS 27 93 716800 1600
57826313 xiayuyang D2 July 27, 2019, 3:20 a.m. OK GNU C++14 TESTS 27 93 819200 1600
59270593 lesskreker D2 Aug. 22, 2019, 12:33 p.m. OK GNU C++17 TESTS 27 46 512000 1600
61610203 CQXYM D2 Oct. 1, 2019, 1:53 p.m. OK GNU C++17 TESTS 27 77 1228800 1600
58536520 Alex_3102 D2 Aug. 10, 2019, 12:09 p.m. OK GNU C++17 TESTS 27 77 2662400 1600
57784362 ydh D2 July 26, 2019, 7:11 a.m. OK GNU C++17 TESTS 27 78 3174400 1600
58115828 vjudge3 D2 Aug. 1, 2019, 8:50 a.m. OK GNU C++17 TESTS 27 93 204800 1600
57728577 AlessioZeni D2 July 25, 2019, 7:55 a.m. OK GNU C++17 TESTS 27 93 204800 1600
58329209 NiroBC D2 Aug. 5, 2019, 8:48 a.m. OK GNU C++17 TESTS 27 93 204800 1600
58078599 vjudge5 D2 July 31, 2019, 1:11 p.m. OK GNU C++17 TESTS 27 93 409600 1600
58372285 Againstmoon D2 Aug. 6, 2019, 7:01 a.m. OK GNU C++17 TESTS 27 93 512000 1600
58806567 90n D2 Aug. 14, 2019, 9:09 a.m. OK GNU C++17 TESTS 27 93 819200 1600
59698771 reanimatorzon D2 Aug. 30, 2019, 9:43 a.m. OK Go TESTS 27 62 4505600 1600
62839198 sighduck D2 Oct. 18, 2019, 1:20 a.m. OK Go TESTS 27 296 4608000 1600
58255647 vjudge1 D2 Aug. 4, 2019, 9:53 a.m. OK Go TESTS 27 904 4608000 1600
58255628 WangJialei D2 Aug. 4, 2019, 9:52 a.m. OK Go TESTS 27 920 4608000 1600
57937935 jmazon D2 July 29, 2019, 11:31 a.m. OK Haskell TESTS 27 390 14745600 1600
67276310 CodAR D2 Dec. 20, 2019, 10:20 a.m. OK Java 11 TESTS 27 670 260608000 1600
58173623 Ziklon D2 Aug. 2, 2019, 12:17 p.m. OK Java 8 TESTS 27 139 0 1600
58126886 atharvat77 D2 Aug. 1, 2019, 12:54 p.m. OK Java 8 TESTS 27 140 0 1600
58078836 spar5h D2 July 31, 2019, 1:15 p.m. OK Java 8 TESTS 27 155 0 1600
57841883 revanthreddy85 D2 July 27, 2019, 9:36 a.m. OK Java 8 TESTS 27 155 0 1600
57762066 pikapika00 D2 July 25, 2019, 6:25 p.m. OK Java 8 TESTS 27 155 0 1600
63767301 Apurva021 D2 Oct. 30, 2019, 6:41 a.m. OK Java 8 TESTS 27 156 0 1600
57739738 hagar_yasser D2 July 25, 2019, 11:05 a.m. OK Java 8 TESTS 27 156 0 1600
68384522 sakt_coder D2 Jan. 8, 2020, 4:58 a.m. OK Java 8 TESTS 27 171 0 1600
67168560 kalyanirishabh1198 D2 Dec. 18, 2019, 4:26 p.m. OK Java 8 TESTS 27 171 0 1600
63615209 prituladima D2 Oct. 27, 2019, 7:07 p.m. OK Java 8 TESTS 27 171 0 1600
57743108 bohuss D2 July 25, 2019, 12:06 p.m. OK Kotlin TESTS 27 155 0 1600
58226806 Spheniscine D2 Aug. 3, 2019, 2:49 p.m. OK Kotlin TESTS 27 452 1536000 1600
57948203 thuutin D2 July 29, 2019, 3:13 p.m. OK Kotlin TESTS 27 889 1536000 1600
57728098 kkyuggu D2 July 25, 2019, 7:47 a.m. OK Kotlin TESTS 27 1419 307200 1600
60194511 Benq D2 Sept. 7, 2019, 12:25 a.m. OK Kotlin TESTS 27 1715 921600 1600
58028404 og.kostya D2 July 30, 2019, 4:20 p.m. OK Mono C# TESTS 27 93 3174400 1600
58111926 treasuryonly D2 Aug. 1, 2019, 7:31 a.m. OK Mono C# TESTS 27 155 6246400 1600
57936422 batraz D2 July 29, 2019, 10:57 a.m. OK Mono C# TESTS 27 1310 3072000 1600
57746892 aliaksei.smaliuk D2 July 25, 2019, 1:21 p.m. OK Mono C# TESTS 27 1388 10854400 1600
57790203 NEvOl D2 July 26, 2019, 9:10 a.m. OK Mono C# TESTS 27 1466 6758400 1600
61020417 vjudge1 D2 Sept. 21, 2019, 2:26 p.m. OK MS C++ TESTS 27 78 1024000 1600
58500262 vjudge3 D2 Aug. 9, 2019, 1:57 p.m. OK MS C++ TESTS 27 78 1024000 1600
60749310 vjudge1 D2 Sept. 18, 2019, 5:01 a.m. OK MS C++ TESTS 27 78 13004800 1600
60754836 vjudge5 D2 Sept. 18, 2019, 8:19 a.m. OK MS C++ TESTS 27 93 204800 1600
58660629 vjudge1 D2 Aug. 12, 2019, 10:47 a.m. OK MS C++ TESTS 27 93 204800 1600
58489389 vjudge4 D2 Aug. 9, 2019, 8:59 a.m. OK MS C++ TESTS 27 93 307200 1600
58484413 vjudge4 D2 Aug. 9, 2019, 7:04 a.m. OK MS C++ TESTS 27 93 1024000 1600
58558475 vjudge4 D2 Aug. 11, 2019, 4:03 a.m. OK MS C++ TESTS 27 93 1024000 1600
61020316 vjudge4 D2 Sept. 21, 2019, 2:25 p.m. OK MS C++ TESTS 27 93 1024000 1600
59651662 vjudge5 D2 Aug. 29, 2019, 8:30 a.m. OK MS C++ TESTS 27 93 1228800 1600
60345895 2462478392 D2 Sept. 10, 2019, 12:34 p.m. OK MS C++ 2017 TESTS 27 139 13004800 1600
57744881 liuhb D2 July 25, 2019, 12:41 p.m. OK MS C++ 2017 TESTS 27 140 2457600 1600
57800790 yubhop D2 July 26, 2019, 1:11 p.m. OK MS C++ 2017 TESTS 27 155 1024000 1600
59688334 guoriyue D2 Aug. 30, 2019, 3:47 a.m. OK MS C++ 2017 TESTS 27 155 1024000 1600
58065524 yyoooo D2 July 31, 2019, 8:48 a.m. OK MS C++ 2017 TESTS 27 155 1024000 1600
57744325 printfok D2 July 25, 2019, 12:29 p.m. OK MS C++ 2017 TESTS 27 155 1024000 1600
57729045 hwangganzi D2 July 25, 2019, 8:03 a.m. OK MS C++ 2017 TESTS 27 155 2560000 1600
58065565 vjudge4 D2 July 31, 2019, 8:49 a.m. OK MS C++ 2017 TESTS 27 156 1024000 1600
58063119 Saber_Altria D2 July 31, 2019, 8:05 a.m. OK MS C++ 2017 TESTS 27 156 1843200 1600
58065242 vjudge4 D2 July 31, 2019, 8:43 a.m. OK MS C++ 2017 TESTS 27 156 1843200 1600
57795471 mayakin D2 July 26, 2019, 11:14 a.m. OK PHP TESTS 27 1263 83558400 1600
57898335 yumtam D2 July 28, 2019, 2:34 p.m. OK PyPy 2 TESTS 27 311 11776000 1600
57948312 thuutin D2 July 29, 2019, 3:16 p.m. OK PyPy 2 TESTS 27 919 25702400 1600
57787022 anshuman16423 D2 July 26, 2019, 8:10 a.m. OK PyPy 2 TESTS 27 1793 3379200 1600
57803769 sprkgoyal D2 July 26, 2019, 2:20 p.m. OK PyPy 3 TESTS 27 420 10137600 1600
57735204 MalleAbile D2 July 25, 2019, 9:45 a.m. OK PyPy 3 TESTS 27 436 11059200 1600
65624256 UTMoonlight D2 Nov. 24, 2019, 7:21 a.m. OK PyPy 3 TESTS 27 451 11366400 1600
58870183 tai45236 D2 Aug. 15, 2019, 3:03 p.m. OK PyPy 3 TESTS 27 467 10547200 1600
57804748 sm1ley D2 July 26, 2019, 2:42 p.m. OK PyPy 3 TESTS 27 467 12288000 1600
63515286 fruha D2 Oct. 26, 2019, 11:40 p.m. OK PyPy 3 TESTS 27 468 12492800 1600
57897682 petya47 D2 July 28, 2019, 2:17 p.m. OK PyPy 3 TESTS 27 482 10547200 1600
57800880 Pokeylope D2 July 26, 2019, 1:13 p.m. OK PyPy 3 TESTS 27 482 11161600 1600
57943091 prateekvr1 D2 July 29, 2019, 1:17 p.m. OK PyPy 3 TESTS 27 483 10752000 1600
57798105 yfo D2 July 26, 2019, 12:13 p.m. OK PyPy 3 TESTS 27 499 10342400 1600
57766312 deadguy D2 July 25, 2019, 8:39 p.m. OK Python 2 TESTS 27 951 3481600 1600
59587327 iprakhar22 D2 Aug. 27, 2019, 6:34 p.m. OK Python 2 TESTS 27 1107 3481600 1600
57903732 Helli.code D2 July 28, 2019, 4:45 p.m. OK Python 2 TESTS 27 1387 3481600 1600
58844893 wolffd D2 Aug. 15, 2019, 4:40 a.m. OK Python 2 TESTS 27 1590 4710400 1600
57818708 xbbjames1 D2 July 26, 2019, 9:21 p.m. OK Python 2 TESTS 27 1793 3788800 1600
58136611 soumyasarkar1998 D2 Aug. 1, 2019, 4:22 p.m. OK Python 2 TESTS 27 1824 22630400 1600
58179982 renjied D2 Aug. 2, 2019, 2:46 p.m. OK Python 2 TESTS 27 1996 6348800 1600
58128518 renjied D2 Aug. 1, 2019, 1:26 p.m. OK Python 2 TESTS 27 1996 6348800 1600
58045654 abdaddy D2 July 30, 2019, 11:05 p.m. OK Python 3 TESTS 27 748 7270400 1600
57861769 asvasil D2 July 27, 2019, 6:13 p.m. OK Python 3 TESTS 27 1153 2867200 1600
57794971 KAin0 D2 July 26, 2019, 11:03 a.m. OK Python 3 TESTS 27 1169 10137600 1600
57795128 KAin0 D2 July 26, 2019, 11:07 a.m. OK Python 3 TESTS 27 1247 9216000 1600
67919616 sureshsinghspd D2 Dec. 29, 2019, 4:09 p.m. OK Python 3 TESTS 27 1294 5734400 1600
57727426 echikawa D2 July 25, 2019, 7:35 a.m. OK Python 3 TESTS 27 1310 11878400 1600
57726763 IceFire D2 July 25, 2019, 7:24 a.m. OK Python 3 TESTS 27 1325 2150400 1600
57808957 kp_2141 D2 July 26, 2019, 4:22 p.m. OK Python 3 TESTS 27 1341 11878400 1600
57868046 the_white_devil D2 July 27, 2019, 10:52 p.m. OK Python 3 TESTS 27 1372 3891200 1600
57977666 jr.projekctor D2 July 30, 2019, 8:15 a.m. OK Python 3 TESTS 27 1372 13619200 1600
59141421 Andrey_R D2 Aug. 20, 2019, 2:35 p.m. OK Ruby TESTS 27 1075 3686400 1600
60935373 nemi_zzz D2 Sept. 20, 2019, 3:07 p.m. OK Ruby TESTS 27 1762 32563200 1600
61787809 ikazuya0201 D2 Oct. 3, 2019, 2:57 p.m. OK Rust TESTS 27 109 5939200 1600
59068548 Asura D2 Aug. 19, 2019, 3:15 a.m. OK Rust TESTS 27 1715 716800 1600
57975553 hello-noob D2 July 30, 2019, 7:35 a.m. OK Scala TESTS 27 1794 0 1600

remove filters

Back to search problems