Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)

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
1774 Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) FINISHED False 9000 65978663 Dec. 17, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 137 ) H Maximum Permutation PROGRAMMING constructive algorithms

B'Ecrade bought a deck of cards numbered from 1 to n . Let the value of a permutation a of length n be min limits_{i = 1}^{n - k + 1} sum limits_{j = i}^{i + k - 1}a_j . Ecrade wants to find the most valuable one among all permutations of the cards. However, it seems a little difficult, so please help him! The first line contains a single integer t ( 1 <= q t <= q 2 cdot 10^4 ) -- the number of test cases. The description of test cases follows. The only line of each test case contains two integers n,k ( 4 <= q k < n <= q 10^5 ). It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^6 . For each test case, output the largest possible value in the first line. Then in the second line, print n integers a_1,a_2, ... ,a_n ( 1 <= a_i <= n , all a_i are distinct) -- the elements of the permutation that has the largest value. If there are multiple such permutations, output any of them. In the first test case, [1,4,5,3,2] has a value of 13 . It can be shown that no permutations of length 5 have a value greater than 13 when k = 4 . In the second test case, [4,2,5,7,8,3,1,6] has a value of 18 . It can be shown that no permutations of length 8 have a value greater than 18 when k = 4 . '...

Tutorials

Polynomial Round 2022 (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
185749585 Ahmad_Hajjouz H Dec. 18, 2022, 5:26 a.m. OK GNU C++17 (64) TESTS 34 545 1638400

remove filters

Back to search problems