Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))

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
1530 Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine)) FINISHED False 10800 110647463 July 17, 2021, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 149 ) G What a Reversal PROGRAMMING constructive algorithms

B"You have two strings a and b of equal length n consisting of characters 0 and 1, and an integer k . You need to make strings a and b equal. In one step, you can choose any substring of a containing exactly k characters 1 (and arbitrary number of characters 0) and reverse it. Formally, if a = a_1 a_2 ldots a_n , you can choose any integers l and r ( 1 <= l <= r <= n ) such that there are exactly k ones among characters a_l, a_{l+1}, ldots, a_r , and set a to a_1 a_2 ldots a_{l-1} a_r a_{r-1} ldots a_l a_{r+1} a_{r+2} ldots a_n . Find a way to make a equal to b using at most 4n reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 2000 ). Description of the test cases follows. Each test case consists of three lines. The first line of each test case contains two integers n and k ( 1 <= n <= 2000 ; 0 <= k <= n ). The second line contains string a of length n . The third line contains string b of the same length. Both strings consist of characters 0 and 1. It is guaranteed that the sum of n over all test cases does not exceed 2000 . For each test case, if it's impossible to make a equal to b in at most 4n reversals, print a single integer -1 . Otherwise, print an integer m ( 0 <= m <= 4n ), denoting the number of reversals in your sequence of steps, followed by m pairs of integers l_i, r_i ( 1 <= l_i <= r_i <= n ), denoting the boundaries of the substrings of a to be reversed, in chronological order. Each substring must contain exactly k ones at the moment of reversal. Note that m doesn't have to be minimized. If there are multiple answers,"...

Tutorials

Codeforces Round #733 Editorial (all problems)

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
122853898 hos.lyric G July 17, 2021, 5:23 p.m. OK D TESTS 98 62 9011200
122864474 rainboy G July 17, 2021, 7:28 p.m. OK GNU C11 TESTS 98 46 3788800
122874899 sunset G July 17, 2021, 11:56 p.m. OK GNU C++14 TESTS 98 31 3993600
122870055 johnchen902 G July 17, 2021, 9:01 p.m. OK GNU C++17 TESTS 98 31 3788800
122852256 ecnerwala G July 17, 2021, 5:18 p.m. OK GNU C++17 TESTS 98 46 3891200
122853646 Marcin_smu G July 17, 2021, 5:22 p.m. OK GNU C++17 TESTS 98 46 4300800
122867765 icecuber G July 17, 2021, 8:12 p.m. OK GNU C++17 TESTS 98 61 3993600
122880351 tlwpdus G July 18, 2021, 2:35 a.m. OK GNU C++17 TESTS 98 62 3993600
122870774 lalit_of_mirzapur G July 17, 2021, 9:21 p.m. OK GNU C++17 TESTS 98 109 4300800
122880874 yhx-12243 G July 18, 2021, 2:46 a.m. OK GNU C++17 (64) TESTS 98 31 4403200
122865125 AndreySergunin G July 17, 2021, 7:35 p.m. OK GNU C++17 (64) TESTS 98 46 4505600
122864369 hitonanode G July 17, 2021, 7:28 p.m. OK GNU C++17 (64) TESTS 98 46 4505600
122847648 heno239 G July 17, 2021, 5:03 p.m. OK GNU C++17 (64) TESTS 98 46 5324800
122870371 AndreySergunin G July 17, 2021, 9:10 p.m. OK GNU C++17 (64) TESTS 98 62 4505600
122875207 cheissmart G July 18, 2021, 12:08 a.m. OK GNU C++17 (64) TESTS 98 62 5017600

remove filters

Back to search problems