Codeforces Round 1066 (Div. 1 + Div. 2)

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
2157 Codeforces Round 1066 (Div. 1 + Div. 2) FINISHED False 10800 12515123 Nov. 23, 2025, 9:35 a.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 115 ) H Keygen 3 PROGRAMMING brute force combinatorics constructive algorithms

A permutation(^{\text{∗}}) of length (n) is called valid if it has both of the following properties: It is bitonic(^{\dagger}); Exactly (m) of its subsets are cycles(^{\ddagger}). Let (k) denote the number of permutations satisfying the above condition. Your task is to find and print (\min(k, 2000)) examples of such permutations. (^{\dagger}) A permutation (p_1, p_2, \ldots, p_n) is bitonic if there exists an index (i) ((1 \leq i \leq n)) such that (p_{j-1} \leq p_j) for (2 \leq j \leq i); (p_j \geq p_{j+1}) for (i \leq j \leq n-1). (^{\ddagger}) A subset (C \subseteq \{ 1, 2, \ldots, n \}) is a cycle if it satisfies the following conditions: (C) is non-empty; if (x \in C), then (p_x \in C); (C) is minimal, i.e., there does not exist a cycle (C') such that (C' \subset C). (^{\text{∗}})A permutation of length (n) is an array consisting of (n) distinct integers from (1) to (n) in arbitrary order. For example, (2,3,1,5,4) is a permutation, but (1,2,2) is not a permutation ((2) appears twice in the array), and (1,3,4) is also not a permutation ((n=3) but there is (4) in the array). The input consists of a single line containing two integers (n), (m) ((1 \le m \leq n \le 100)) — the length of the permutations and the target number of cycles. In the first line, print a single integer (r): the number of permutations you are going to print. Note that (r) must be (\min(k, 2000)) as defined in the statement. Then, print (r) lines. Each line must contain a bitonic permutation of length (n), with (m) cycles. In the example, there are (9) valid permutations (i.e., bitonic permutations of length (6), with (3) cycles). For example, (3, 5, 6, 4, 2, 1) is bitonic (in the above definition, (i = 3)), and it has (3) cycles: (\{1, 3, 6\}), (\{2, 5\}), (\{4\}). So y

Tutorials

Codeforces Round 1066 (Div. 1 + Div. 2) Editorial

Submissions

No solutions yet.